输入：
[
  "abcd",
  "bnrt",
  "crmy",
  "dtye"
]

输出：
true

解释：
第 1 行和第 1 列都是 "abcd"。
第 2 行和第 2 列都是 "bnrt"。
第 3 行和第 3 列都是 "crmy"。
第 4 行和第 4 列都是 "dtye"。

因此，这是一个有效的单词方块。

示例 2：

输入：
[
  "abcd",
  "bnrt",
  "crm",
  "dt"
]

输出：
true

解释：
第 1 行和第 1 列都是 "abcd"。
第 2 行和第 2 列都是 "bnrt"。
第 3 行和第 3 列都是 "crm"。
第 4 行和第 4 列都是 "dt"。

因此，这是一个有效的单词方块。

示例 3：

输入：
[
  "ball",
  "area",
  "read",
  "lady"
]

输出：
false

解释：
第 3 行是 "read" ，然而第 3 列是 "lead"。

因此，这 不是 一个有效的单词方块。


class Solution {
public:
    bool validWordSquare(vector<string>& words) {
        for(int i=0;i<words.size();i++)for(int j=0;j<words[i].size();j++){
            if(j>=words.size() || i>=words[j].size())return false;
            if(words[i][j]!=words[j][i])return false;
        }
        return true;
    }
};

426. 将二叉搜索树转化为排序的双向链表

双向循环链表

429. N叉树的层序遍历

多叉树

430. 扁平化多级双向链表

双向链表

431. 将 N 叉树编码为二叉树

树树、森林_nameofcsdn的博客-CSDN博客

437. 路径总和 III

DFS

438. 找到字符串中所有字母异位词

剑指 Offer II 015. 字符串中的所有变位词

https://blog.csdn.net/nameofcsdn/article/details/119833252

444. 序列重建

LCR 115. 序列重建

445. 两数相加 II

剑指 Offer II 025. 链表中的两数相加

447. 回旋镖的数量

给定平面上 n 对 互不相同 的点 points ，其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组，其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等（需要考虑元组的顺序）。

返回平面上所有回旋镖的数量。

示例 1：

输入：points = [[0,0],[1,0],[2,0]]
输出：2
解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

示例 2：

输入：points = [[1,1],[2,2],[3,3]]
输出：2

示例 3：

输入：points = [[1,1]]
输出：0

提示：

n == points.length
1 <= n <= 500
points[i].length == 2
-104 <= xi, yi <= 104
所有点都 互不相同


class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        vector<map<int,int>>vm(points.size());
        for(int i=0;i<points.size();i++){
            for(int j=i+1;j<points.size();j++){
                int len1 = points[i][0]-points[j][0];
                int len2 = points[i][1]-points[j][1];
                int len = len1*len1+len2*len2;
                vm[i][len]++,vm[j][len]++;
            }
        }
        int ans=0;
        for(auto &m:vm){
            for(auto mi:m){
                ans+=mi.second*(mi.second-1);
            }
        }
        return ans;
    }
};

451. 根据字符出现频率排序

题目：

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

示例 1:

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例 2:

输入:
"cccaaa"

输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3:

输入:
"Aabb"

输出:
"bbAa"

解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

代码：


struct dist
{
	char c;
	int fre;
};
struct cmp
{
	bool operator()(dist a, dist b)
	{
		return a.fre < b.fre;
	}
};
 
class Solution {
public:
	string frequencySort(string s) {
		map<char, int> m;
		priority_queue<dist, vector<dist>, cmp>que;
		dist d;
		for (int i = 0; i < s.length();i++)
		{
			m[s[i]]++;
		}
		for (auto it = m.begin(); it != m.end(); it++)
		{
			d.c = (*it).first, d.fre = (*it).second, que.push(d);
		}
		string ans = "";
		while (!que.empty())
		{
			d = que.top();
			que.pop();
			while(d.fre--)ans += d.c;
		}
		return ans;
	}
};

454. 四数相加 II

数组和集合的搜索数组和集合的搜索_nameofcsdn的博客-CSDN博客

459. 重复的子字符串

KMP

461. 汉明距离

题目：

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：
0 ≤ x, y < 231.

示例:

输入: x = 1, y = 4

输出: 2

解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑

上面的箭头指出了对应二进制位不同的位置。

代码：


class Solution {
public:
	int hammingWeight(uint32_t n) {
		int ans = 0;
		while (n)
		{
			n ^= (n&(-n));
			ans++;
		}
		return ans;
	}
	int hammingDistance(int x, int y) {
		return hammingWeight(x^y);
	}
};

469. 凸多边形

计算几何

470. 用 Rand7() 实现 Rand10()

拒绝采样（Rejection Sampling）

474. 一和零

背包

476. 数字的补数

位运算

478. 在圆内随机生成点

拒绝采样（Rejection Sampling）

483. 最小好进制

不定方程

484. 寻找排列

由范围 [1,n] 内所有整数组成的 n 个整数的排列 perm 可以表示为长度为 n - 1 的字符串 s ，其中:

如果 perm[i] < perm[i + 1] ，那么 s[i] == 'I'
如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D' 。

给定一个字符串 s ，重构字典序上最小的排列 perm 并返回它。

示例 1：

输入： s = "I"
输出： [1,2]
解释： [1,2] 是唯一合法的可以生成秘密签名 "I" 的特定串，数字 1 和 2 构成递增关系。

示例 2：

输入： s = "DI"
输出： [2,1,3]
解释： [2,1,3] 和 [3,1,2] 可以生成秘密签名 "DI"，
但是由于我们要找字典序最小的排列，因此你需要输出 [2,1,3]。

提示：

1 <= s.length <= 105
s[i] 只会包含字符 'D' 和 'I'。

484. 寻找排列

贪心

485. 最大连续 1 的个数

给定一个二进制数组 nums ，计算其中最大连续 1 的个数。

示例 1：

输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.
示例 2:

输入：nums = [1,0,1,1,0,1]
输出：2

提示：

1 <= nums.length <= 105
nums[i] 不是 0 就是 1.


class Solution {
public:
	int findMaxConsecutiveOnes(vector<int>& nums) {
		int n = 0, ans = 0;
		for (int i = 0; i < nums.size(); i++) {
			if (nums[i])n++;
			else ans = max(ans, n), n = 0;
		}
		return max(ans, n);
	}
};

486. 预测赢家

博弈DP

487. 最大连续1的个数 II

给定一个二进制数组 nums ，如果最多可以翻转一个 0 ，则返回数组中连续 1 的最大个数。

示例 1：

输入：nums = [1,0,1,1,0]
输出：4
解释：翻转第一个 0 可以得到最长的连续 1。
当翻转以后，最大连续 1 的个数为 4。
示例 2:

输入：nums = [1,0,1,1,0,1]
输出：4

提示:

1 <= nums.length <= 105
nums[i] 不是 0 就是 1.

进阶：如果输入的数字是作为无限流逐个输入如何处理？换句话说，内存不能存储下所有从流中输入的数字。您可以有效地解决吗？


class Solution {
public:
	int findMaxConsecutiveOnes(vector<int>& nums) {
		int a = -1, b = -1, c = -1, d = -1, ans = 0;
		for (int i = 0; i <= nums.size(); i++) {
			if (i == nums.size() || nums[i] == 0) {
				d = i;
				ans = max(ans, d - b - 1);
				a = b, b = c, c = d;
			}
		}
		return ans;
	}
};

490. 迷宫

puzzle（017.1）Orac

494. 目标和

01背包

496. 下一个更大元素 I

给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

示例 1:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
示例 2:

输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。

提示：

nums1和nums2中所有元素是唯一的。
nums1和nums2 的数组大小都不超过1000。

这个题目很简单，我主要用来锻造我的模板：


class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int>ans=GetNumFromId(nums2,Fmaxrig(nums2));
        map<int,int>m=VectorToMap(nums2,ans);
        ans=VmToVector(nums1,m);
        return ans;
    }
};

497. 非重叠矩形中的随机点

给定一个由非重叠的轴对齐矩形的数组 rects ，其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点，(xi, yi) 是第 i 个矩形的右上角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。

在给定的矩形覆盖的空间内的任何整数点都有可能被返回。

请注意 ，整数点是具有整数坐标的点。

实现 Solution 类:

Solution(int[][] rects) 用给定的矩形数组 rects 初始化对象。
int[] pick() 返回一个随机的整数点 [u, v] 在给定的矩形所覆盖的空间内。

示例 1：

输入: 
["Solution", "pick", "pick", "pick", "pick", "pick"]
[[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
输出: 
[null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]

解释：
Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
solution.pick(); // 返回 [1, -2]
solution.pick(); // 返回 [1, -1]
solution.pick(); // 返回 [-1, -2]
solution.pick(); // 返回 [-2, -2]
solution.pick(); // 返回 [0, 0]

提示：

1 <= rects.length <= 100
rects[i].length == 4
-109 <= ai < xi <= 109
-109 <= bi < yi <= 109
xi - ai <= 2000
yi - bi <= 2000
所有的矩形不重叠。
pick 最多被调用 104 次。


class Solution {
public:
    Solution(vector<vector<int>>& rects) {
        v=rects;
        long long s=0,s2=0;
        for(auto vi:v){
            s+=(long long)(vi[2]+1-vi[0])*(vi[3]+1-vi[1]);
        }
        for(auto vi:v){
            s2+=(long long)(vi[2]+1-vi[0])*(vi[3]+1-vi[1]);
            p.push_back(s2*1.0/s);
        }
    }
    int randIn(int x,int y){
        return rand()%(y+1-x)+x;
    }
    vector<int> pick() {
        double x = rand()%10000/10000.0;
        for(int i=0;i<p.size();i++){
            if(p[i]>=x){
                return vector<int>{randIn(v[i][0],v[i][2]),randIn(v[i][1],v[i][3])};
            }
        }
        return vector<int>{0,0};
    }
    vector<vector<int>> v;
    vector<double>p;
};

499. 迷宫 III

单源最短路径

503. 下一个更大元素 II

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。


class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int>t=nums;
        t.resize(nums.size()*2);
        copy(nums.begin(),nums.end(),t.begin()+nums.size());
        vector<int>tmp=GetNumFromId(t,Fmaxrig(t));
        vector<int>ans=nums;
        copy(tmp.begin(),tmp.begin()+tmp.size()/2,ans.begin());
        return ans;
    }
};

505. 迷宫 II

单源最短路径

509. 斐波那契数

斐波那契数列

510. 二叉搜索树中的中序后继 II

二叉搜索树二叉搜索树（BST）_nameofcsdn的博客-CSDN博客

511. 游戏玩法分析 I

活动表 Activity：

+--------------+---------+
| Column Name  | Type    |
+--------------+---------+
| player_id    | int     |
| device_id    | int     |
| event_date   | date    |
| games_played | int     |
+--------------+---------+
在 SQL 中，表的主键是 (player_id, event_date)。
这张表展示了一些游戏玩家在游戏平台上的行为活动。
每行数据记录了一名玩家在退出平台之前，当天使用同一台设备登录平台后打开的游戏的数目（可能是 0 个）。

查询每位玩家 第一次登陆平台的日期。

查询结果的格式如下所示：

Activity 表：
+-----------+-----------+------------+--------------+
| player_id | device_id | event_date | games_played |
+-----------+-----------+------------+--------------+
| 1         | 2         | 2016-03-01 | 5            |
| 1         | 2         | 2016-05-02 | 6            |
| 2         | 3         | 2017-06-25 | 1            |
| 3         | 1         | 2016-03-02 | 0            |
| 3         | 4         | 2018-07-03 | 5            |
+-----------+-----------+------------+--------------+

Result 表：
+-----------+-------------+
| player_id | first_login |
+-----------+-------------+
| 1         | 2016-03-01  |
| 2         | 2017-06-25  |
| 3         | 2016-03-02  |
+-----------+-------------+

SELECT player_id, MIN(event_date) as first_login  FROM activity GROUP BY player_id;

513. 找树左下角的值

二叉树BFS

515. 在每个树行中找最大值

剑指 Offer II 044. 二叉树每层的最大值 https://blog.csdn.net/nameofcsdn/article/details/119833252

518. 零钱兑换 II

完全背包

519. 随机翻转矩阵

给你一个 m x n 的二元矩阵 matrix ，且所有值被初始化为 0 。请你设计一个算法，随机选取一个满足 matrix[i][j] == 0 的下标 (i, j) ，并将它的值变为 1 。所有满足 matrix[i][j] == 0 的下标 (i, j) 被选取的概率应当均等。

尽量最少调用内置的随机函数，并且优化时间和空间复杂度。

实现 Solution 类：

Solution(int m, int n) 使用二元矩阵的大小 m 和 n 初始化该对象
int[] flip() 返回一个满足 matrix[i][j] == 0 的随机下标 [i, j] ，并将其对应格子中的值变为 1
void reset() 将矩阵中所有的值重置为 0

示例：

输入
["Solution", "flip", "flip", "flip", "reset", "flip"]
[[3, 1], [], [], [], [], []]
输出
[null, [1, 0], [2, 0], [0, 0], null, [2, 0]]

解释
Solution solution = new Solution(3, 1);
solution.flip();  // 返回 [1, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同
solution.flip();  // 返回 [2, 0]，因为 [1,0] 已经返回过了，此时返回 [2,0] 和 [0,0] 的概率应当相同
solution.flip();  // 返回 [0, 0]，根据前面已经返回过的下标，此时只能返回 [0,0]
solution.reset(); // 所有值都重置为 0 ，并可以再次选择下标返回
solution.flip();  // 返回 [2, 0]，此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同

提示：

1 <= m, n <= 104
每次调用flip 时，矩阵中至少存在一个值为 0 的格子。
最多调用 1000 次 flip 和 reset 方法。


class Solution {
public:
    Solution(int m, int n) {
        this->m=m,this->n=n;
        reset();
    }
    
    vector<int> flip() {
        return v[id++];
    }
    
    void reset() {
        v.clear();
        id=0;
        static int a=0;
        srand(a++);
        int x=rand(),y=rand();
        int num=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                v.push_back(vector<int>{(i+x)%m,(j+y)%n});
                if(num++>1000)break;
            }
        }
    }
    int m,n,id;
    vector<vector<int>>v;
};

523. 连续的子数组和

给定一个包含非负数的数组和一个目标整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。

示例 1:

输入: [23,2,4,6,7], k = 6
输出: True
解释: [2,4] 是一个大小为 2 的子数组，并且和为 6。
示例 2:

输入: [23,2,6,4,7], k = 6
输出: True
解释: [23,2,6,4,7]是大小为 5 的子数组，并且和为 42。
说明:

数组的长度不会超过10,000。
你可以认为所有数字总和在 32 位有符号整数范围内。


class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        if(k==0)
        {
            for(int i=1;i<nums.size();i++)
            {
                if(nums[i]==0&&nums[i-1]==0)return true;
            }
            return false;
        }
        map<int,int>m;
        int s=0;
        if(k<0)k=-k;    
        for(int i=0;i<nums.size();i++)
        {
            s+=nums[i];
            s%=k;
            if(m[s]>0||s==0)
            {
                if(m[s]<i)return true;
            }
            else m[s]=i+1;
        }
        return false;
    }
};

525. 连续数组

剑指 Offer II 010. 和为 k 的子数组 https://blog.csdn.net/nameofcsdn/article/details/119833252

528. 按权重随机选择

剑指 Offer II 071. 按权重生成随机数 https://blog.csdn.net/nameofcsdn/article/details/119833252

529. 扫雷游戏

BFS

531. 孤独像素 I

给你一个大小为 m x n 的图像 picture ，图像由黑白像素组成，'B' 表示黑色像素，'W' 表示白色像素，请你统计并返回图像中黑色孤独像素的数量。

黑色孤独像素 的定义为：如果黑色像素 'B' 所在的同一行和同一列不存在其他黑色像素，那么这个黑色像素就是黑色孤独像素。

示例 1：

输入：picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
输出：3
解释：全部三个 'B' 都是黑色的孤独像素

示例 2：

输入：picture = [["B","B","B"],["B","B","W"],["B","B","B"]]
输出：0

提示：

m == picture.length
n == picture[i].length
1 <= m, n <= 500
picture[i][j] 为 'W' 或 'B'


class Solution {
public:
    int findLonelyPixel(vector<vector<char>>& v) {
        vector<int>r(v.size(), 0);
        vector<int>c(v[0].size(), 0);
        for (int i = 0; i < v.size(); i++) {
            for (int j = 0; j < v[0].size(); j++) {
                if (v[i][j] == 'B')r[i]++, c[j]++;
            }
        }
        int ans = 0;
        for (int i = 0; i < v.size(); i++) {
            for (int j = 0; j < v[0].size(); j++) {
                if (v[i][j] == 'B' && r[i]==1&&c[j]==1)ans++;
            }
        }
        return ans;
    }
};

532. 数组中的 k-diff 数对

rust

533. 孤独像素 II

给你一个大小为 m x n 的二维字符数组 picture ，表示一张黑白图像，数组中的 'B' 表示黑色像素，'W' 表示白色像素。另给你一个整数 target ，请你找出并返回符合规则的黑色孤独像素的数量。

黑色孤独像素是指位于某一特定位置 (r, c) 的字符 'B' ，其中：

行 r 和列 c 中的黑色像素恰好有 target 个。
列 c 中所有黑色像素所在的行必须和行 r 完全相同。

示例 1：

输入：picture = [["W","B","W","B","B","W"],["W","B","W","B","B","W"],["W","B","W","B","B","W"],["W","W","B","W","B","W"]], target = 3
输出：6
解释：所有绿色的 'B' 都是我们所求的像素(第 1 列和第 3 列的所有 'B' )
以行 r = 0 和列 c = 1 的 'B' 为例：
- 规则 1 ，行 r = 0 和列 c = 1 都恰好有 target = 3 个黑色像素 
- 规则 2 ，列 c = 1 的黑色像素分别位于行 0，行 1 和行 2。和行 r = 0 完全相同。

示例 2：

输入：picture = [["W","W","B"],["W","W","B"],["W","W","B"]], target = 1
输出：0

提示：

m == picture.length
n == picture[i].length
1 <= m, n <= 200
picture[i][j] 为 'W' 或 'B'
1 <= target <= min(m, n)


class Solution {
public:
    int findBlackPixel(vector<vector<char>>& picture, int target) {
        map<vector<char>,int>m;
        for(int i=0;i<picture.size();i++)m[picture[i]]=i;
        vector<int>r(picture.size(),0);
        vector<int>c(picture[0].size(),0);
        for(int i=0;i<picture.size();i++){
            for(int j=0;j<picture[0].size();j++){
                if(picture[i][j]=='B')r[i]++,c[j]++;
            }
        }
        int ans=0;
        for(int i=0;i<picture.size();i++){
            if(r[i]!=target)continue;
            if(m[picture[i]]!=i)continue;
            int sames=1;
            for(int k=0;k<i;k++){
                if(m[picture[k]]==i)sames++;
            }
            if(sames!=target)continue;
            for(int j=0;j<picture[0].size();j++){
                if(picture[i][j]=='B' && c[j]==target)ans+=target;
            }
        }
        return ans;
    }
};

535. TinyURL 的加密与解密

加解密加解密_nameofcsdn的博客-CSDN博客

538. 把二叉搜索树转换为累加树

剑指 Offer II 054. 所有大于等于节点的值之和

539. 最小时间差

https://blog.csdn.net/nameofcsdn/article/details/119833252

540. 有序数组中的单一元素

二分、三分二分、三分_nameofcsdn的博客-CSDN博客

542. 01 矩阵

BFS

547. 省份数量

并查集

552. 学生出勤记录 II

矩阵快速幂

556. 下一个更大元素 III

给定一个32位正整数 n，你需要找到最小的32位整数，其与 n 中存在的位数完全相同，并且其值大于n。如果不存在这样的32位整数，则返回-1。

示例 1:

输入: 12
输出: 21
示例 2:

输入: 21
输出: -1


class Solution {
public:
    int nextGreaterElement(int n) {
        char*sn;
        int len=IntToStr(n,10,sn);
        if(!next_permutation(sn,sn+len))return -1;
        long long res = StrToInt(sn,10);
        if(res==int(res))return res;
        return -1;
    }
};

559. N 叉树的最大深度

多叉树

560. 和为K的子数组

剑指 Offer II 010. 和为 k 的子数组 https://blog.csdn.net/nameofcsdn/article/details/119833252

562. 矩阵中最长的连续1线段

给定一个 m x n 的二进制矩阵 mat ，返回矩阵中最长的连续1线段。

这条线段可以是水平的、垂直的、对角线的或者反对角线的。

示例 1:

输入: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
输出: 3

示例 2:

输入: mat = [[1,1,1,1],[0,1,1,0],[0,0,0,1]]
输出: 4

提示:

m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j] 不是 0 就是 1.


class Solution {
public:
    int longestLine(vector<vector<int>>& mat) {
        maxr = mat.size(),maxc = mat[0].size();
        vector<int>rs,cs;
        for(int i=0;i<mat[0].size();i++)rs.push_back(0),cs.push_back(i);
        int ans=longestLine(mat,rs,cs,1,0);
        rs.clear(),cs.clear();
        for(int i=0;i<mat.size();i++)rs.push_back(i),cs.push_back(0);
        ans=max(ans,longestLine(mat,rs,cs,0,1));
        for(int i=0;i<mat[0].size();i++)rs.push_back(0),cs.push_back(i);
        ans=max(ans,longestLine(mat,rs,cs,1,1));
        rs.clear(),cs.clear();
        for(int i=0;i<mat.size();i++)rs.push_back(i),cs.push_back(0);
        for(int i=0;i<mat[0].size();i++)rs.push_back(mat.size()-1),cs.push_back(i);
        ans=max(ans,longestLine(mat,rs,cs,-1,1));
        return ans;
    }
    int longestLine(vector<vector<int>>& mat, vector<int>rs,vector<int>cs,int dr,int dc) {
        int maxAns=0;
        for(int i=0;i<rs.size();i++){
            int r=rs[i],c=cs[i];
            vector<int>v;
            while(r>=0 && r<maxr && c>=0 && c<maxc){
                v.push_back(mat[r][c]);
                r+=dr,c+=dc;
            }
            maxAns=max(maxAns,longestLine(v));
        }
        return maxAns;
    }
    int longestLine(vector<int>v) {
        int s=0,ans=0;
        for(auto x:v){
            if(x==1)s++,ans=max(ans,s);
            else s=0;
        }
        return ans;
    }
    int maxr,maxc;
};

565. 数组嵌套

并查集

567. 字符串的排列

剑指 Offer II 014. 字符串中的变位词 https://blog.csdn.net/nameofcsdn/article/details/119833252

581. 最短无序连续子数组

rust

589. N 叉树的前序遍历

多叉树

590. N 叉树的后序遍历

多叉树

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/信息技术墨韵书生/article/detail/62800