LeetCode-3
每天刷的题目比较多，所以一下子集满了一篇，不过大部分都是简单和中等的简单题。
344 反转字符串
刷题时间：2021-10-29
用algorithm的reverse函数
class Solution {
public:
void reverseString(vector<char>& s) { reverse(s.begin(), s.end()); }
};
双指针交换
class Solution {
public:
void reverseString(vector<char>& s) {
int l = 0, r = s.size() - 1;
while (l < r) {
swap(s[l++], s[r--]);
}
}
};
js版本
var reverseString = function(s) {
s.reverse();
};
双指针交换
var reverseString = function (s) {
let l = 0,
r = s.length - 1;
while (l < r) {
let tmp = s[l];
s[l] = s[r];
s[r] = tmp;
l++;
r--;
}
};
557 反转字符串中的单词 III
双指针，自己的思路，就是要注意最后没有空格的情况
class Solution {
public:
string reverseWords(string s) {
int l = 0, r = 0;
while (r < s.length()) {
if (s[++r] == ' ' || r == s.length()) {
int x = r - 1;
while (x > l) {
swap(s[l++], s[x--]);
}
l = r + 1;
}
}
return s;
}
};
js版本，我直接调用api，疯狂调用
var reverseWords = function (s) {
return (res = s
.trim()
.split(' ')
.map((item, index) => {
return item.split('').reverse().join('');
})
.join(' '));
};
541 反转字符串 II
既然做了一和三，那干脆做一下二
一开始想太多了，就挺简单的，唉
class Solution {
public:
string reverseStr(string s, int k) {
int n = s.length();
for (int i = 0; i < n; i += 2 * k) {
int l = i;
int r = min(i + k - 1, n - 1);
while (l < r) {
swap(s[l++], s[r--]);
}
}
return s;
}
};
350 两个数组的交集 II
排序
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
vector<int> v;
int n1 = nums1.size();
int n2 = nums2.size();
int i = 0, j = 0;
while (i < n1 && j < n2) {
if (nums1[i] == nums2[j]) {
v.push_back(nums1[i]);
i++;
j++;
} else if (nums1[i] > nums2[j]) {
j++;
} else {
i++;
}
}
return v;
}
};
哈希表
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) {
return intersect(nums2, nums1);
}
unordered_map<int, int> m;
for (int num : nums1) {
++m[num];
}
vector<int> intersection;
for (int num : nums2) {
if (m.count(num)) {
intersection.push_back(num);
--m[num];
if (m[num] == 0) {
m.erase(num);
}
}
}
return intersection;
}
};
349 两个数组的交集
反向修改一下350的哈希表，改成set集合就行了
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) {
return intersection(nums2, nums1);
}
unordered_set<int> m;
for (int num : nums1) {
m.insert(num);
}
vector<int> v;
for (int num : nums2) {
auto it = m.find(num);
if (it != m.end()) {
v.push_back(num);
m.erase(num);
}
}
return v;
}
};
以前抄袭的更简单，双set，不过和我的差别不大
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> s(nums1.begin(), nums1.end()), res;
for (auto a : nums2) {
if (s.count(a)) res.insert(a);
}
return vector<int>(res.begin(), res.end());
}
};
136 只出现一次的数字
刷题时间：2021-10-30
哈希什么的都不讲了，直接位运算
- 任何数和 00 做异或运算，结果仍然是原来的数，即 a ⊕ 0 = a。
- 任何数和其自身做异或运算，结果是 00，即 a ⊕ a = 0。
- 异或运算满足交换律和结合律，即 a ⊕ b ⊕ a = b ⊕ a ⊕ a = b ⊕ ( a ⊕ a ) = b ⊕ 0 = b。
所以全部异或，最后剩下的就是只出现一次的数字。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int n = nums[0];
for (int i = 1; i < nums.size(); i++) {
n ^= nums[i];
}
return n;
}
};
260 只出现一次的数字 III
刷题时间：2021-10-30
垃圾排序
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<int> v;
int cnt = 0;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] != nums[i - 1]) {
if (cnt == 0) {
v.push_back(nums[i - 1]);
if (v.size() == 2) {
return v;
}
}
cnt = 0;
} else {
cnt++;
}
}
if (cnt == 0) {
v.push_back(nums[nums.size() - 1]);
}
return v;
}
};
哈希表
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
vector<int> v;
map<int, int> m;
for (int& i : nums) {
m[i]++;
}
for (auto& i : m) {
if (i.second == 1) {
v.push_back(i.first);
}
}
return v;
}
};
还有个位异或运算，比只出现一次还抽象一点，当然这个想不到也没事
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int xorsum = 0;
for (int num: nums) {
xorsum ^= num;
}
// 防止溢出
int lsb = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum));
int type1 = 0, type2 = 0;
for (int num: nums) {
if (num & lsb) {
type1 ^= num;
}
else {
type2 ^= num;
}
}
return {type1, type2};
}
};
566 重塑矩阵
刷题时间：2021-10-30
朴素的想法：
class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
int n = mat.size();
int m = mat[0].size();
if (n * m != r * c) {
return mat;
}
vector<vector<int>> v;
for (int i = 0; i < r; i++) {
v.push_back({});
for (int j = 0; j < c; j++) {
int x = i * c + j;
v[i].push_back(mat[x / m][x % m]);
}
}
return v;
}
};
上个简约代码
class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
int m = nums.size();
int n = nums[0].size();
if (m * n != r * c) {
return nums;
}
vector<vector<int>> ans(r, vector<int>(c));
for (int x = 0; x < m * n; ++x) {
ans[x / c][x % c] = nums[x / n][x % n];
}
return ans;
}
};
118 杨辉三角
就按照数学的方法来
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res(numRows, vector<int>());
for (int i = 0; i < numRows; i++) {
// 重塑res[i]的大小
res[i].resize(i + 1, 1);
for (int j = 1; j < i; j++) {
res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
}
}
return res;
}
};
js版本
var generate = function (numRows) {
const res = [];
for (let i = 0; i < numRows; i++) {
let temp = new Array(i + 1).fill(1);
for (let j = 1; j < i; j++) {
temp[j] = res[i - 1][j - 1] + res[i - 1][j];
}
res.push(temp);
}
return res;
};
876 链表的中间结点
刷题时间：2021-10-30
遍历链表，获得总数，再重新遍历一遍。
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* ptr = head;
int cnt = 0;
while (ptr != nullptr) {
cnt++;
ptr = ptr->next;
}
cnt = cnt % 2 == 1 ? cnt / 2 : (cnt + 1) / 2;
ptr = head;
while (cnt > 0) {
ptr = ptr->next;
cnt--;
}
return ptr;
}
};
还有一种数组，毕竟费空间
class Solution {
public:
ListNode* middleNode(ListNode* head) {
vector<ListNode*> A = {head};
while (A.back()->next != NULL)
A.push_back(A.back()->next);
return A[A.size() / 2];
}
};
快慢指针法，两个指针，一个走一步，一个走两步，牛逼啊，这个方法
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};
19 删除链表的倒数第 N 个结点
正常思路
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* ptr = head;
int cnt = 0;
while (ptr != nullptr) {
cnt++;
ptr = ptr->next;
}
ListNode* bh = new ListNode(0, head);
ListNode* cur = bh;
for (int i = cnt; i > 0; i--) {
if (n == i) {
cur->next = cur->next->next;
return bh->next;
}
cur = cur->next;
}
return bh->next;
}
};
快慢指针，非常漂亮的做法，快指针先往前前进n个，然后慢指针从哑节点开始一块前进。
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
ListNode* fast = head;
ListNode* slow = dummy;
for (int i = 0; i < n; ++i) {
fast = fast->next;
}
while (fast) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};
还有一种是栈的做法，先全部压进去，然后pop n个，再取栈顶的进行操作。
500 键盘行
刷题时间：2021-10-31
这题简单题可不简单，虽然思路很简单，但写起来挺复杂的，写起来这么一长串，绝了
class Solution {
public:
vector<string> findWords(vector<string>& words) {
vector<string> v;
unordered_set<char> s[3];
s[0] = {'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'};
s[1] = {'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'};
s[2] = {'z', 'x', 'c', 'v', 'b', 'n', 'm'};
for (string word : words) {
bool flag = true;
string l_word = toLowerCase(word);
int i = 0;
for (; i < 3; i++) {
auto it = s[i].find(l_word[0]);
if (it != s[i].end()) {
break;
}
}
for (int j = 1; j < l_word.length(); j++) {
auto it = s[i].find(l_word[j]);
if (it == s[i].end()) {
flag = false;
break;
}
}
if (flag) {
v.push_back(word);
}
}
return v;
}
string toLowerCase(string str) {
for (int i = 0; i < str.size(); i++) {
if (str[i] >= 'A' && str[i] <= 'Z') {
str[i] = str[i] - 'A' + 'a';
}
}
return str;
}
};
官解的预处理有点妙，每一个英文字母标记其对应键盘上的行号，可惜谁能够想到呢
class Solution {
public:
vector<string> findWords(vector<string>& words) {
vector<string> ans;
string rowIdx = "12210111011122000010020202";
for (auto & word : words) {
bool isValid = true;
char idx = rowIdx[tolower(word[0]) - 'a'];
for (int i = 1; i < word.size(); ++i) {
if(rowIdx[tolower(word[i]) - 'a'] != idx) {
isValid = false;
break;
}
}
if (isValid) {
ans.emplace_back(word);
}
}
return ans;
}
};
36 有效的数独
没写，直接抄官解
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int rows[9][9];
int columns[9][9];
int subboxes[3][3][9];
memset(rows,0,sizeof(rows));
memset(columns,0,sizeof(columns));
memset(subboxes,0,sizeof(subboxes));
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c != '.') {
int index = c - '0' - 1;
rows[i][index]++;
columns[j][index]++;
subboxes[i / 3][j / 3][index]++;
if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
return false;
}
}
}
}
return true;
}
};
73 矩阵置零
诶，我偏要用O(mn)的空间来写。
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
vector<vector<int>> v = matrix;
for (int i = 0; i < matrix.size(); i++) {
for (int j = 0; j < matrix[0].size(); j++) {
if (matrix[i][j] == 0) {
for (int m = 0; m < matrix.size(); m++) {
v[m][j] = 0;
}
for (int n = 0; n < matrix[0].size(); n++) {
v[i][n] = 0;
}
}
}
}
matrix = v;
}
};
O（m+n)空间，使用两个队列解决
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
vector<int> row(n, 1);
vector<int> col(m, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 0) {
row[i] = 0;
col[j] = 0;
}
}
}
for (int i = 0; i < n; i++) {
if (row[i] == 0) {
for (int j = 0; j < m; j++) {
matrix[i][j] = 0;
}
}
}
for (int i = 0; i < m; i++) {
if (col[i] == 0) {
for (int j = 0; j < n; j++) {
matrix[j][i] = 0;
}
}
}
}
};
O（1），使用第一行第一列来保存0，但是第一行第一列的自身需要两个变量来保存
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
int flag_col0 = false, flag_row0 = false;
for (int i = 0; i < m; i++) {
if (!matrix[i][0]) {
flag_col0 = true;
}
}
for (int j = 0; j < n; j++) {
if (!matrix[0][j]) {
flag_row0 = true;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (!matrix[i][j]) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (!matrix[i][0] || !matrix[0][j]) {
matrix[i][j] = 0;
}
}
}
if (flag_col0) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
if (flag_row0) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
}
};
还有个更加进阶的，算了，不会。
只使用一个标记变量记录第一列是否原本存在 00。这样，第一列的第一个元素即可以标记第一行是否出现 00。但为了防止每一列的第一个元素被提前更新，我们需要从最后一行开始，倒序地处理矩阵元素。
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
int flag_col0 = false;
for (int i = 0; i < m; i++) {
if (!matrix[i][0]) {
flag_col0 = true;
}
for (int j = 1; j < n; j++) {
if (!matrix[i][j]) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (int i = m - 1; i >= 0; i--) {
for (int j = 1; j < n; j++) {
if (!matrix[i][0] || !matrix[0][j]) {
matrix[i][j] = 0;
}
}
if (flag_col0) {
matrix[i][0] = 0;
}
}
}
};
3 无重复字符的最长子串
这题难啊，中等中的通过率比较低了，不过我也两次就成功了
不过自己写的不太好，对string操作比较多，容易导致空间利用率下降
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.length();
if (n == 0) {
return 0;
}
int max = 1;
int sum = 1;
string str(1, s[0]);
for (int i = 1; i < n; i++) {
auto p = str.find(s[i]);
if (p == str.npos) {
str += s[i];
sum++;
} else {
str = str.substr(p + 1, str.size() - p + 1) + s[i];
if (sum > max) {
max = sum;
}
sum = str.length();
}
}
return sum > max ? sum : max;
}
};
看一下官方的解答，和我之前想的一样，用哈希值，然后erase，我还以为有多高级呢。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// 哈希集合，记录每个字符是否出现过
unordered_set<char> occ;
int n = s.size();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
// 枚举左指针的位置，初始值隐性地表示为 -1
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.erase(s[i - 1]);
}
while (rk + 1 < n && !occ.count(s[rk + 1])) {
// 不断地移动右指针
occ.insert(s[rk + 1]);
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1);
}
return ans;
}
};
567 字符串的排列
一开始只有个数组来保存，然后每次都要遍历数组来查看是否为0，这样子不好。后续提升就是加了个diff这样子，往中间靠就是减去，往两边走就是相减。
class Solution {
public:
bool checkInclusion(string s1, string s2) {
if (s1.size() > s2.size()) {
return false;
}
int n = s1.size();
vector<int> cnt(26);
for (char ch : s1) {
cnt[ch - 'a']++;
}
int diff = n;
for (int i = 0; i < n; i++) {
diff += cnt[s2[i] - 'a'] > 0 ? -1 : 1;
cnt[s2[i] - 'a']--;
}
if (!diff && isZero(cnt)) {
return true;
}
for (int i = n; i < s2.length(); i++) {
diff += cnt[s2[i] - 'a'] > 0 ? -1 : 1;
cnt[s2[i] - 'a']--;
diff += cnt[s2[i - n] - 'a'] < 0 ? -1 : 1;
++cnt[s2[i - n] - 'a'];
if (diff == 0 && isZero(cnt)) {
return true;
}
}
return false;
}
bool isZero(vector<int> v) {
for (int i : v) {
if (i != 0) {
return false;
}
}
return true;
}
};
还有种方法，滑动窗口。当right往右走。初始化数组为负值，左边如果>0，就一直往前走，否则就不懂。
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n = s1.length(), m = s2.length();
if (n > m) {
return false;
}
vector<int> cnt(26);
for (int i = 0; i < n; ++i) {
--cnt[s1[i] - 'a'];
}
int left = 0;
for (int right = 0; right < m; ++right) {
int x = s2[right] - 'a';
++cnt[x];
while (cnt[x] > 0) {
--cnt[s2[left] - 'a'];
++left;
}
if (right - left + 1 == n) {
return true;
}
}
return false;
}
};
575 分糖果
刷题时间：2021-11-1
简单题简单写，小剪枝了一下
class Solution {
public:
int distributeCandies(vector<int>& candyType) {
int n = candyType.size();
unordered_set<int> set;
for (int i : candyType) {
set.insert(i);
if (set.size() == n / 2) {
return n / 2;
}
}
return set.size();
}
};
比官方的一行写快一点，因为官方没有剪枝
return min(unordered_set<int>(candyType.begin(), candyType.end()).size(), candyType.size() / 2);
387 字符串中的第一个唯一字符
就抄袭，无脑unordered_map也不可取，这种还是可以用数组来更快一点
class Solution {
public:
int firstUniqChar(string s) {
int arr[26]{0};
int n = s.length();
for (int i = 0; i < n; i++) {
arr[s[i] - 'a']++;
}
for (int i = 0; i < n; i++) {
if (arr[s[i] - 'a'] == 1) {
return i;
}
}
return -1;
}
};
383 赎金信
也是哈希的思想，两次循环，时间确实快，但是空间利用率低了点
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int n = ransomNote.length();
int m = magazine.length();
if (n > m) {
return false;
}
int arr[26]{0};
for (int i = 0; i < n; i++) {
arr[ransomNote[i] - 'a']--;
arr[magazine[i] - 'a']++;
}
for (int i = n; i < m; i++) {
arr[magazine[i] - 'a']++;
}
for (int i : arr) {
if (i < 0) {
return false;
}
}
return true;
}
};
上面这个快一点，下面稍微改了一下，剪枝一下，空间利用率提上去，但是时间下来了。就多了0.2M空间就超过好多人，但我还是推崇上面那个，毕竟第二次26个循环快啊。
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int n = ransomNote.length();
int m = magazine.length();
if (n > m) {
return false;
}
int arr[26]{0};
for (int i = 0; i < m; i++) {
arr[magazine[i] - 'a']++;
}
for (int i = 0; i < n; i++) {
arr[ransomNote[i] - 'a']--;
if (arr[ransomNote[i] - 'a'] < 0) {
return false;
}
}
return true;
}
};
242有效的字母异位词
啊这，也很简单
class Solution {
public:
bool isAnagram(string s, string t) {
int n = s.length();
if (n != t.length()) {
return false;
}
int a[26]{0};
for (int i = 0; i < n; i++) {
a[s[i] - 'a']++;
a[t[i] - 'a']--;
}
for (int i : a) {
if (i != 0) {
return false;
}
}
return true;
}
};
733 图像渲染
广度搜索
class Solution {
public:
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, 1, -1, 0};
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc,
int newColor) {
const int curColor = image[sr][sc];
if (newColor == curColor) {
return image;
}
int n = image.size(), m = image[0].size();
queue<pair<int, int>> que;
que.emplace(sr, sc);
image[sr][sc] = newColor;
while (!que.empty()) {
int x = que.front().first, y = que.front().second;
que.pop();
for (int i = 0; i < 4; i++) {
int mx = x + dx[i], my = y + dy[i];
if (mx >= 0 && mx < n && my >= 0 && my < m &&
image[mx][my] == curColor) {
que.emplace(mx, my);
image[mx][my] = newColor;
}
}
}
return image;
}
};
深度优先搜索，感觉这个深度有点绕，没有广度海丽姐、
class Solution {
public:
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, 1, -1, 0};
void dfs(vector<vector<int>>& image, int x, int y, int color, int newColor) {
if (image[x][y] == color) {
image[x][y] = newColor;
for (int i = 0; i < 4; i++) {
int mx = x + dx[i], my = y + dy[i];
if (mx >= 0 && mx < image.size() && my >= 0 && my < image[0].size()) {
dfs(image, mx, my, color, newColor);
}
}
}
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
int currColor = image[sr][sc];
if (currColor != newColor) {
dfs(image, sr, sc, currColor, newColor);
}
return image;
}
};
695 岛屿的最大面积
广度优先搜索，这代码多层套娃，娃中娃。
class Solution {
public:
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, 1, -1, 0};
int maxAreaOfIsland(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
queue<pair<int, int>> que;
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] != 0) {
que.emplace(i, j);
grid[i][j] = 0;
int cnt = 0;
while (!que.empty()) {
int x = que.front().first, y = que.front().second;
que.pop();
cnt++;
for (int a = 0; a < 4; a++) {
int mx = x + dx[a], my = y + dy[a];
if (mx >= 0 && mx < n && my >= 0 && my < m &&
grid[mx][my] == 1) {
que.emplace(mx, my);
grid[mx][my] = 0;
}
}
}
if (cnt > max) {
max = cnt;
}
}
}
}
return max;
}
};
深度优先算法
class Solution {
public:
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, 1, -1, 0};
int dfs(vector<vector<int>>& grid, int cur_i, int cur_j) {
if (grid[cur_i][cur_j] == 1) {
grid[cur_i][cur_j]=0;
for (int a = 0; a < 4; a++) {
int mx = cur_i + dx[a], my = cur_j + dy[a];
if (mx >= 0 && mx < grid.size() && my >= 0 &&
my < grid[0].size() && grid[mx][my] == 1) {
return 1 + dfs(grid, cur_i, cur_j);
}
}
}
return 0;
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int max = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] != 0) {
int cnt = dfs(grid, i, j);
if (cnt > max) {
max = cnt;
}
}
}
}
return max;
}
};
