421、数组中两个数的最大异或值——哈希表、位运算、前缀
暴力方法
最简单的一集
毫无疑问的超时😓
时间复杂度O(n²)
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
int ret = 0;
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
ret = max(ret, nums[i]^nums[j]);
}
}
return ret;
}
};哈希表、位运算、前缀
从最高位开始遍历，mask掩码用于获取每个数字31-i位的前缀。
开始遍历nums，获取每个数字的前缀并存入哈希集合。
要获取最大的异或值，我们假设异或值在第i位为1，即int potentialMaxXOR = maxXOR | (1 << i)
然后开始遍历哈希集合，如果能找到两个前缀的异或值为potentialMaxXOR，那么说明遍历到第i位的最大异或值可以为potentialMaxXOR
遍历完所有位，返回最大异或值
时间复杂度O(n)
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
// 最大异或结果
int maxXOR = 0;
// 掩码
int mask = 0;
for (int i = 31; i >= 0; i--) {
mask |= (1 << i);
unordered_set<int> prefixSet;
// 获取所有数字的前缀
for (int num : nums) {
prefixSet.insert(num & mask);
}
// 假设最大异或结果的第i位为1
int potentialMaxXOR = maxXOR | (1 << i);
// 遍历所有数字的前缀
for (int prefix : prefixSet) {
// 如果存在另一个前缀pref1^pref2==potentialMaxXOR
if (prefixSet.count(potentialMaxXOR ^ prefix)) {
// 则说明该位可以设为1
maxXOR = potentialMaxXOR;
break;
}
}
}
return maxXOR;
}
};318、最大单词长度积
用一个26位二进制数存储一个单词出现的的字符，然后嵌套遍历找到两个掩码的与运算为0的两个单词也就是没有重复字符的单词，更新最大长度积。
class Solution {
public:
int maxProduct(vector<string>& words) {
int len = words.size();
int ret = 0;
vector<int> bitmasks(len, 0); // 存储单词的位掩码
// 计算每个单词的位掩码
for (int i = 0; i < len; i++) {
for (char c : words[i]) {
bitmasks[i] |= (1 << (c - 'a'));
}
}
for(int i=len-1;i>=0;i--){
for(int j=i-1;j>=0;j--){
if ((bitmasks[i] & bitmasks[j]) == 0){
ret = ret > words[i].size() * words[j].size()?ret:words[i].size() * words[j].size();
}
}
}
return ret;
}
};2586、统计范围内的元音字符串——哈希表
创建一个哈希表包含五个元音字符。遍历范围内的字符串，如果字符串的首尾字符都在哈希表中，则为元音字符串，ret++。
class Solution {
public:
int vowelStrings(vector<string>& words, int left, int right) {
unordered_set<char> chs;
chs.insert('a');
chs.insert('e');
chs.insert('i');
chs.insert('o');
chs.insert('u');
int ret = 0;
for(;left<=right;left++){
int len = words[left].size();
if(chs.find(words[left][0])!=chs.end() && chs.find(words[left][len-1])!=chs.end()){
ret++;
}
}
return ret;
}
};2609、最长平衡子字符串——栈
如果栈为空先判断assert是否为1，为1则将其设为0表示可可以开始新的连续状态判断并将元素压入栈；非空则判断是否能凑一对01，能的话就+2同时将assert设为1（用于连续的状态保存）；不能则先判断assert是否为1，为1则将assert设为0并清空栈，因为子串前的所有元素都不能再和后面的元素配对。
class Solution {
public:
int findTheLongestBalancedSubstring(string s) {
int ret = 0;
stack<int> stk;
int cur = 0;
int assert = 0;
for(auto& ch:s){
if(stk.empty()){
cur = 0;
if(assert){
assert = 0;
}
stk.push(ch);
}else{
char tmp = stk.top();
if(ch-tmp == 1){
stk.pop();
cur += 2;
ret = max(cur, ret);
assert = 1;
}else{
cur = 0;
if(assert){
assert = 0;
while(!stk.empty()){
stk.pop();
}
}
stk.push(ch);
}
}
}
return ret;
}
};307、区域和检索 – 数组可修改——线段树
暴力方法
这个方法肯定超时了
class NumArray {
public:
NumArray(vector<int>& nums) {
this->nums = nums;
}
void update(int index, int val) {
nums[index] = val;
}
int sumRange(int left, int right) {
int ret = 0;
for(int i=left;i<=right;i++){
ret += nums[i];
}
return ret;
}
private:
vector<int> nums;
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* obj->update(index,val);
* int param_2 = obj->sumRange(left,right);
*/线段树
线段树（Segment Tree）是一种用于处理区间查询的数据结构。它可以在O(logn)的时间内执行区间查询、区间更新和单点更新等操作。
线段树的基本思想是将待处理的区间划分成一些小区间，每个小区间对应线段树的一个节点。树的叶子节点表示原始数组中的单个元素，而内部节点表示一些区间的统计信息（如和、最大值、最小值等）。
class NumArray {
public:
NumArray(vector<int>& nums) {
int n = nums.size();
tree.resize(4 * n);
build(nums, 0, n - 1, 0);
}
void update(int index, int val) {
updateUtil(0, 0, tree.size() / 4 - 1, index, val);
}
int sumRange(int left, int right) {
return queryUtil(0, 0, tree.size() / 4 - 1, left, right);
}
private:
vector<int> tree;
void build(vector<int>& nums, int start, int end, int treeIndex) {
if (start == end) {
tree[treeIndex] = nums[start];
return;
}
int mid = start + (end - start) / 2;
int leftIndex = 2 * treeIndex + 1;
int rightIndex = 2 * treeIndex + 2;
build(nums, start, mid, leftIndex);
build(nums, mid + 1, end, rightIndex);
tree[treeIndex] = tree[leftIndex] + tree[rightIndex]; // 统计信息，如求和
}
void updateUtil(int treeIndex, int start, int end, int index, int val) {
if (start == end) {
tree[treeIndex] = val;
return;
}
int mid = start + (end - start) / 2;
int leftIndex = 2 * treeIndex + 1;
int rightIndex = 2 * treeIndex + 2;
if (index <= mid) {
updateUtil(leftIndex, start, mid, index, val);
} else {
updateUtil(rightIndex, mid + 1, end, index, val);
}
tree[treeIndex] = tree[leftIndex] + tree[rightIndex]; // 更新统计信息，如求和
}
int queryUtil(int treeIndex, int start, int end, int left, int right) {
if (start > right || end < left) {
return 0; // 区间不重叠，返回默认值
}
if (start >= left && end <= right) {
return tree[treeIndex]; // 当前节点完全被查询区间覆盖，直接返回统计信息
}
int mid = start + (end - start) / 2;
int leftIndex = 2 * treeIndex + 1;
int rightIndex = 2 * treeIndex + 2;
int leftSum = queryUtil(leftIndex, start, mid, left, right);
int rightSum = queryUtil(rightIndex, mid + 1, end, left, right);
return leftSum + rightSum; // 统计信息，如求和
}
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* obj->update(index,val);
* int param_2 = obj->sumRange(left,right);
*/2760、最长奇偶子数组——滑动窗口
遍历数组中的元素，如果flag为0（表示还没有找到起始索引）并且当前元素小于等于threshold并且是偶数，将flag设为1，将left设为当前索引，将ret设为1（考虑到当前元素本身可以构成一个交替子数组），并且继续下一次循环。如果当前元素与前一个元素的奇偶性不同，并且当前元素小于等于threshold，更新ret。如果上述条件不满足，表示当前元素不符合交替子数组的要求，将ret更新为当前索引与left之间的距离，并且将索引i减1，以便下一次循环重新判断该元素。
class Solution {
public:
int longestAlternatingSubarray(vector<int>& nums, int threshold) {
if(nums.size() == 1){
if(nums[0] > threshold || nums[0]%2 != 0){
return 0;
}else{
return 1;
}
}else if(nums.size() == 0){
return 0;
}
int left=0;
int flag=0;
int ret=0;
for(int i=0;i<nums.size();i++){
if(flag==0 && nums[i]<=threshold && nums[i]%2==0){
flag=1;
left=i;
ret = 1>ret?1:ret;
continue;
}
if(flag == 0){
continue;
}
if(nums[i]%2 != nums[i-1]%2 && nums[i] <= threshold){
ret = ret>i-left? ret:i-left+1;
}else{
ret = ret>i-left? ret:i-left;
i--;
flag=0;
}
}
return ret;
}
};2304、网格中的最小路径代价——动态规划
- 使用nums数组存储每个点到终点的最小代价
- 首先初始化第一行直接取值
- 对于后续每行:
- 调用getMin函数,从上一行各点到当前点j的最小代价
- 再加上当前点值,更新nums[grid[i][j]]
- getMin函数遍历上一行点,计算到目标点col的最小代价
- 最后一行中取最小值返回最终答案
class Solution
{
public:
int getMin(int col, vector<int> &vec, vector<int> &nums, vector<vector<int>> &moveCost)
{
int min = INT_MAX;
for (int i = 0; i < vec.size(); i++)
{
if (nums[vec[i]] + moveCost[vec[i]][col] < min)
{
min = nums[vec[i]] + moveCost[vec[i]][col];
}
}
return min;
}
int minPathCost(vector<vector<int>> &grid, vector<vector<int>> &moveCost)
{
int h = grid.size();
int w = grid[0].size();
int ret = INT_MAX;
// 存储最小代价
vector<int> nums(h * w, 0);
// 初始化第一行
for (int i = 0; i < w; i++)
{
nums[grid[0][i]] = grid[0][i];
}
for (int i = 1; i < h; i++)
{
for (int j = 0; j < w; j++)
{
nums[grid[i][j]] = getMin(j, grid[i - 1], nums, moveCost) + grid[i][j];
}
}
// 找到最后一行的最小代价
for (int i = 0; i < w; i++)
{
if (nums[grid[h - 1][i]] < ret)
{
ret = nums[grid[h - 1][i]];
}
}
return ret;
}
};1410、HTML实体解析器——哈希表、子串
首先将实体编码和对应的字符通过哈希表映射。然后遍历哈希表，size_t pos = html_text.find(entry.first)寻找文本中是否存在该子串，存在则替换字串。
class Solution {
public:
string entityParser(string text) {
unordered_map<std::string, char> html_parser;
html_parser["""] = '"';
html_parser["'"] = '\'';
html_parser["&"] = '&';
html_parser[">"] = '>';
html_parser["<"] = '<';
html_parser["⁄"] = '/';
// 使用映射进行HTML实体转换
string html_text = text;
for (auto& entry : html_parser) {
// 寻找子串
size_t pos = html_text.find(entry.first);
while (pos != string::npos) {
html_text.replace(pos, entry.first.length(), 1, entry.second);
pos = html_text.find(entry.first, pos + 1);
}
}
return html_text;
}
};2824、统计和小于目标的下标对数目——双指针
略
class Solution {
public:
int countPairs(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int ret = 0;
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
if(nums[i]+nums[j] < target){
ret++;
}else{
if(i+1 == j){
return ret;
}
}
}
}
return ret;
}
};1457、二叉树中的伪回文路径——位运算
利用整数的二进制表示来表示每个节点值的出现次数。假设每个节点的值范围为 1 到 9，我们可以使用一个整数的二进制末尾的 9 个位来表示每个值的出现次数。
使用一个变量 cnt 来表示当前路径中每个节点值的出现次数。当遍历到一个节点时，我们可以根据该节点的值将相应的位进行异或（从 0 到 1 或从 1 到 0）。例如，假设当前路径中已经有一个节点值为 3，对应的位为 000000100，当遍历到另一个节点值为 3 的节点时，我们可以将该位异或为 000000000，表示该节点值不再出现在当前路径中。
当遍历达到叶节点时，就检测 cnt 的每个位，如果等于 1 的位小于等于 1 则表示该路径为伪回文路径，ret++。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isPalindromicPaths(int cnt){
bitset<9> bits(cnt);
int flag = 0;
for (int i = 0; i < 9; i++) {
if (bits[i] == 1) {
flag += 1;
}
}
return flag <= 1;
}
void postTravel(TreeNode* node, int cnt, int& ret){
if(node == nullptr){
return;
}
cnt ^= (1 << (node->val-1));
if(node->left == nullptr && node->right == nullptr){
if(isPalindromicPaths(cnt)){
ret++;
}
}
postTravel(node->left, cnt, ret);
postTravel(node->right, cnt, ret);
}
int pseudoPalindromicPaths (TreeNode* root) {
int ret = 0;
postTravel(root, 0, ret);
return ret;
}
private:
};828、统计子串中的唯一字符——哈希表、排列组合
通过遍历字符串 s，将每个字符及其索引添加到 index 中。遍历 index 中的每对键值对。对于每个字符，它获取其对应的索引向量 arr，并迭代处理该向量中的每个索引。
在内部循环中，代码计算了两个值 left 和 right，分别表示当前索引前面和后面的间隔长度。如果当前索引是 arr 的第一个元素，则 left 的值为 arr[i] + 1，表示索引前面的间隔长度（加 1 是为了包括当前字符）。如果当前索引是 arr 的最后一个元素，则 right 的值为 s.length() - arr[i]，表示索引后面的间隔长度。否则，left 和 right 分别表示当前索引与前一个索引和后一个索引之间的间隔长度。最后，代码将 left * right 的值累加到 ret 变量中表示有该字符作为唯一字符的子串数量。
class Solution {
public:
int uniqueLetterString(string s) {
unordered_map<char, vector<int>> index;
int ret = 0;
for (int i = 0; i < s.size(); i++) {
index[s[i]].emplace_back(i);
}
for (const auto& pair : index) {
const vector<int>& arr = pair.second;
int len = arr.size();
for (int i = 0; i < len; i++) {
int left = (i == 0) ? arr[i] + 1 : arr[i] - arr[i - 1];
int right = (i == len - 1) ? s.length() - arr[i] : arr[i + 1] - arr[i];
ret += left * right;
}
}
return ret;
}
};907、子数组的最小值之和——单调栈、动态规划
暴力方法
然后进行两层循环遍历数组arr。外层循环变量i表示子数组的起始位置，内层循环变量j表示子数组的结束位置。
对于每个子数组，创建一个栈stk用于存储当前已遍历元素中的最小值。开始时，将arr[i]压入栈中。在内层循环中，获取栈顶元素top的值。如果top小于等于arr[j]，则说明arr[j]不会成为新的最小值，将top累加到ret中，并对ret进行取模运算 ret = ret % 1000000007。如果arr[j]大于top，则说明arr[j]成为了新的最小值，将arr[j]累加到ret中，并将arr[j]压入栈stk中。最后，返回ret作为结果，即子数组最小值的和。
时间复杂度为O(n^2)，毫无疑问会超时。
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int len = arr.size();
int ret = 0;
for(int i=0;i<len;i++){
stack<int> stk;
stk.push(arr[i]);
for(int j=i;j<len;j++){
int top = stk.top();
// cout<<top<<" ";
if(top <= arr[j]){
// cout<<top<<" ";
ret += top;
ret = ret % 1000000007;
}else{
// cout<<arr[j]<<" ";
ret += arr[j];
ret = ret % 1000000007;
stk.push(arr[j]);
}
}
}
return ret;
}
};动态规划
和上一题的动态规划思路类似，针对数组中的每一个元素，计算它在多少个子数组中作为最小值。
利用单调栈计算某一个元素的左边和右边的连续大于该元素的数字数量L和R，那么以该元素为最小值的子数组就有L*R个。
class Solution
{
public:
int sumSubarrayMins(vector<int> &arr)
{
int len = arr.size();
int ret = 0;
vector<int> left(len), right(len);
stack<pair<int, int>> stk;
for (int i = 0; i < len; i++)
{
int cnt = 1;
while (!stk.empty() && stk.top().first > arr[i])
{
cnt += stk.top().second;
stk.pop();
}
stk.push({arr[i], cnt});
left[i] = cnt;
}
while (!stk.empty())
{
stk.pop();
}
for (int i = len - 1; i >= 0; i--)
{
int cnt = 1;
while (!stk.empty() && stk.top().first >= arr[i])
{
cnt += stk.top().second;
stk.pop();
}
stk.push({arr[i], cnt});
right[i] = cnt;
}
for (int i = 0; i < len; i++)
{
long tmp = arr[i] * left[i];
tmp = tmp * right[i];
ret = (ret + tmp) % 1000000007;
}
return ret;
}
};1670、设计前中后队列——链表
该类使用 std::list 作为底层数据结构来实现一个队列。
class FrontMiddleBackQueue {
public:
list<int> LinkList;
FrontMiddleBackQueue() {
}
void pushFront(int val) {
LinkList.push_front(val);
}
void pushMiddle(int val) {
auto mid = next(LinkList.begin(), LinkList.size() / 2);
LinkList.insert(mid, val);
}
void pushBack(int val) {
LinkList.push_back(val);
}
int popFront() {
if(LinkList.size()==0){
return -1;
}
int ret = LinkList.front();
LinkList.erase(LinkList.begin());
return ret;
}
int popMiddle() {
if(LinkList.size()==0){
return -1;
}
auto mid = next(LinkList.begin(), (LinkList.size()-1) / 2);
int ret = *mid;
LinkList.erase(mid);
return ret;
}
int popBack() {
if(LinkList.size()==0){
return -1;
}
int ret = LinkList.back();
LinkList.erase(prev(LinkList.end()));
return ret;
}
};
/**
* Your FrontMiddleBackQueue object will be instantiated and called as such:
* FrontMiddleBackQueue* obj = new FrontMiddleBackQueue();
* obj->pushFront(val);
* obj->pushMiddle(val);
* obj->pushBack(val);
* int param_4 = obj->popFront();
* int param_5 = obj->popMiddle();
* int param_6 = obj->popBack();
*/2336、无限集中的最小数字——哈希表、堆
然后使用make_heap函数将nums转换为最小堆，以确保nums[0]是当前集合中的最小元素。
popSmallest方法首先将当前集合中最小的元素smallest保存下来，然后将其添加到not_exist哈希集合中，表示该元素不再存在于当前集合中。使用pop_heap函数将nums[0]（最小元素）移至向量的末尾，然后使用nums.pop_back()删除该元素。
addBack方法用于将之前被弹出的元素重新添加回集合中。首先，它检查not_exist哈希集合中是否存在要添加的元素num。如果存在，表示该元素之前被弹出过，则从not_exist中删除该元素，并将其添加回nums向量中。再使用push_heap函数将nums转换回最小堆，以维持堆的性质。
class SmallestInfiniteSet {
public:
vector<int> nums;
unordered_set<int> not_exist;
SmallestInfiniteSet() {
for(int i=1;i<=1000;i++){
nums.push_back(i);
}
make_heap(nums.begin(), nums.end(), greater<int>());
}
int popSmallest() {
int smallest = nums[0];
not_exist.insert(smallest);
pop_heap(nums.begin(), nums.end(), greater<int>());
nums.pop_back();
return smallest;
}
void addBack(int num) {
if(not_exist.find(num) != not_exist.end()){
not_exist.erase(num);
nums.push_back(num);
push_heap(nums.begin(), nums.end(), greater<int>());
}else{
return;
}
}
};
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* SmallestInfiniteSet* obj = new SmallestInfiniteSet();
* int param_1 = obj->popSmallest();
* obj->addBack(num);
*/1657、确定两个字符串是否接近——哈希表、排序
首先，通过比较 word1 和 word2 的长度，如果它们的长度不同，就直接返回 false，表示它们不相似。使用两个 unordered_map<char, int> 分别记录 word1 和 word2 中每个字符出现的次数。遍历 word1 和 word2 的每个字符，通过 unordered_map 存储字符出现的次数。检查两个 unordered_map 的大小（即字符种类的数量），如果它们不相等，就返回 false，表示它们不相似。创建两个向量 w1_cnt 和 w2_cnt，用于存储 word1 和 word2 中字符的出现次数。遍历 w1 和 w2 中的每个键值对，将字符出现次数存入对应的向量中。对 w1_cnt 和 w2_cnt 进行排序。检查排序后的两个向量是否完全相同，如果有不同的元素，则返回 false，表示它们不相似。如果以上条件都满足，就返回 true，表示 word1 和 word2 相似。
class Solution {
public:
bool closeStrings(string word1, string word2) {
int w1_len = word1.length();
int w2_len = word2.length();
// 长度不同，必定非相似
if(w1_len != w2_len){
return false;
}
// 存储字符出现次数
unordered_map<char, int> w1;
unordered_map<char, int> w2;
for(int i=0;i<w1_len;i++){
if(w1.find(word1[i]) == w1.end()){
w1[word1[i]] = 1;
}else{
w1[word1[i]]++;
}
if(w2.find(word2[i]) == w2.end()){
w2[word2[i]] = 1;
}else{
w2[word2[i]]++;
}
}
// 出现的字符数量不同，必不相似
if(w1.size() != w2.size()){
return false;
}
vector<int> w1_cnt;
vector<int> w2_cnt;
auto it1 = w1.begin();
auto it2 = w2.begin();
for (; it1 != w1.end(); ){
// 双方字符种类不同，必不相似
if(w1.find(it2->first) == w1.end() || w2.find(it1->first) == w2.end()){
return false;
}
w1_cnt.push_back(it1->second);
w2_cnt.push_back(it2->second);
it1++;
it2++;
}
// 进行排序
sort(w1_cnt.begin(), w1_cnt.end());
sort(w2_cnt.begin(), w2_cnt.end());
return w1_cnt == w2_cnt;
}
};优化
创建两个大小为 26 的整数向量 count1 和 count2，用于记录字符出现的次数。向量的索引对应字母的 ASCII 值减去字符 ‘a’ 的 ASCII 值，即 [0] 对应 ‘a’，[1] 对应 ‘b’，以此类推。遍历 word1 和 word2 中的每个字符，通过字符的 ASCII 值减去 ‘a’ 的 ASCII 值得到索引，然后在对应的向量中增加字符出现的次数。检查两个向量中的元素，如果在同一个位置上，一个向量的元素为 0 而另一个不为 0，或者一个向量的元素不为 0 而另一个为 0，则返回 false，表示它们不相似否则说明两个字符串的出现的字符相同。
对 count1 和 count2 进行排序，使得出现频率相同的字符在同一位置上，如果两个向量相同，则说明两个字符串相似。
class Solution {
public:
bool closeStrings(string word1, string word2) {
vector<int> count1(26), count2(26);
for (char c : word1) {
count1[c - 'a']++;
}
for (char c : word2) {
count2[c - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (count1[i] > 0 && count2[i] == 0 || count1[i] == 0 && count2[i] > 0) {
return false;
}
}
sort(count1.begin(), count1.end());
sort(count2.begin(), count2.end());
return count1 == count2;
}
};。200、岛屿数量——深度优先搜索
首先创建一个与给定网格相同大小的visited数组，用于标记已访问过的格子。
初始化岛屿数量count为0。然后遍历整个网格：
- 如果当前格子是陆地（值为’1’）且未被访问过，则进行DFS搜索。
- DFS搜索中，递归地访问当前格子的上、下、左、右四个相邻格子，并将其标记为已访问。
- 如果相邻格子是陆地，则继续进行递归搜索。
- 当DFS搜索结束后，增加岛屿数量
count。
class Solution {
public:
void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited,
int row, int col){
int m = grid.size();
int n = grid[0].size();
if(row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == '0' || visited[row][col]){
return;
}
visited[row][col] = true;
dfs(grid, visited, row - 1, col); // 上
dfs(grid, visited, row + 1, col); // 下
dfs(grid, visited, row, col - 1); // 左
dfs(grid, visited, row, col + 1); // 右
}
int numIslands(vector<vector<char>>& grid) {
if (grid.empty()) {
return 0;
}
int cnt = 0;
int m = grid.size();
int n = grid[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j] == '1' && !visited[i][j]){
dfs(grid, visited, i, j);
cnt++;
}
}
}
return cnt;
}
};© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
