力扣刷题记录10.27-

Last updated on November 1, 2024 pm

最近背八股，刷题刷的少了🫠

2024/10/27

一、数组

（1）缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

方法：原地哈希（时间复杂度O（n），空间复杂度：只用到原数组）

方法一：标记
  • 第一次遍历：使得所有不在【1，N】区间的数都变得大于N。
    • 如果一个数字已经大于N，就不需要管，于是只需要把负数和0变成N+1
  • 第二次遍历，将所有绝对值在【1，N】区间的数字，其绝对值|x|-1位置的数字变成负数
  • 第三次遍历，返回第一个不是负数的数的下标。如果都为整数，返回N+1

注意位置0对应数字1，依次类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
       int n=nums.size();
       for(int i=0;i<n;i++){
          if(nums[i]<=0)
             nums[i]=n+1;
       }
       for(int i=0;i<n;i++){
          int num=abs(nums[i]);
          if(num>=1&&num<=n)
             nums[num-1]=-abs(nums[num-1]);
       }
       for(int i=0;i<n;i++){
          if(nums[i]>0)
             return i+1;
       }
       return n+1;
    }
};
方法二：置换

想要把数组恢复成，数字x在x-1的位置上这样的形式。

  • 第一次遍历，如果数字x在【1，N】区间，就将它与x-1位置的元素交换

    • 如果交换后的元素还在【1，N】区间，就继续交换
    • 如果发现x和x-1的位置相同，说明已经交换过，无需交换

  • 第二次遍历，如果发现x位置的元素不是x+1，就可以返回x+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<n;i++){
            while(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){
                swap(nums[nums[i]-1],nums[i]);
            } 
        }
        for(int i=0;i<n;i++){
                if(nums[i]!=i+1){
                    return i+1;
                }
            }
        return n+1;
    }
};

二、DFS

（1） 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<vector<int>> path={{0,1},{1,0},{0,-1},{-1,0}};

    bool exist(vector<vector<char>>& board, string word) {
        int m=board.size(),n=board[0].size();
        int l=word.size();
        auto dfs=[&](auto &&dfs,int i,int j,int k)->bool{
            if(board[i][j]!=word[k]){
                return false;
            }
            if(k==l-1) return true;
            board[i][j]=0;
            for(int q=0;q<4;q++){
                int ni=i+path[q][0],nj=j+path[q][1];
                if(ni>=0&&ni<m&&nj>=0&&nj<n&&board[ni][nj]){
                    if(dfs(dfs,ni,nj,k+1))
                        return true;
                }
            }
            board[i][j]=word[k];
            return false;
        };

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(dfs(dfs,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
};

三、树

（1）计算所有路径和

自己定义树节点类。计算根节点到每个叶子结点的路径和，返回一个数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class TreeNode {
public:
   int val;
   std::vector<TreeNode*> children;
}

void calculatePathSums(TreeNode* node,int currentSum,std::vector<int>& pathSums)
{
   if(!node) return;
   
   currentSum+=node->val;
   
   if(node->children.empty()){
      pathSums.push_back(currentSum);
   }else{
      for(TreeNode* child : node->children){
         calculatePathSums(child,currentSum,pathSums);
      }
   }
}

vector<int> getRootToLeafSums(TreeNode* root){
   vector<int> pathSums;
   calculatePathSums(root,0,pathSums);
   return pathSums;
}

2024/10/30

一、哈希表

（1）连续的子数组和

给你一个整数数组 nums 和一个整数 k ，如果 nums 有一个 好的子数组 返回 true ，否则返回 false：

一个 好的子数组 是：

  • 长度 至少为 2 ，且子数组元素总和为 k 的倍数。

注意：

  • 子数组 是数组中 连续 的部分。
  • 如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终 视为 k 的一个倍数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool checkSubarraySum(vector<int>&nums,int k){
   int n=nums.size();
   vector<int> sum(n+1,0);
   for(int i=1;i<=n;i++){
      sum[i]=sum[i-1]+nums[i];
   }
   unordered_set<int> set;
   for(int i=2;i<=n;i++) {
      set.insert(sum[i-2]%k);
      if(set.count(sum[i]%k)){
         return true;
      }
   }
   return false;
}

（2）快乐数

「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

1、哈希表法
  • 最终会得到 1。
  • 最终会进入循环。
  • 值会越来越大，最后接近无穷大。（不用处理）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution { 
public:
   int getNext(int n){
      int totalSum=0;
      while(n>0){
         int d=n%10;
         n=n/10;
         totalSum+=d*d;
      }
      return totalSum;
   }
   
    bool isHappy(int n) {
        unordered_set<int> seen;
        while(n!=1&&!seenContains(n)){
           seen.Add(n);
           n=getNext(n);
        }
       return n==1;
    }
};
2、快慢指针法

（想到了判断循环链表）

1
2
3
4
5
6
7
8
9
bool isHappy(int n) {
   int slowRunner=n;
   int fastRunner=getNext(n);
   while(fastRunner!=1&&fastRunner!=slowRunner){
      slowRunner=getNext(slowRunner);
      fastRunner=getNext(getNext(fastRunner));
   }
   return f
}

二、回溯

（1）非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
   vector<int> temp;
   vector<vector<int> > ans;
   
   void dfs(int cur,int last,vector<int>&nums){
      if(cur==nums.size()){
         if(temp.size()>=2){
            ans.push_back(temp);
         }
         return;
      }
      if(nums[cur]>=last) {
         temp.push_back(nums[cur]);
         dfs(cur+1,nums[cur],nums);
         temp.pop_back();
      }
      if(nums[cur]!=last){
         dfs(cur+1,last,nums);
      }
   }

    vector<vector<int>> findSubsequences(vector<int>& nums) {
       dfs(0,INT_MIN,nums);
       return ans;
    }
};

三、面试题

（1）最长的快乐字符串

要求编写一个算法来生成“最长的快乐字符串”，即一个不包含 "aaa", "bbb" 或 "ccc" 子串的字符串。给定三个整数 a、b 和 c，表示字母 'a'、'b' 和 'c' 的最大数量，你需要构造最长满足条件的字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
string LongHappy(int a,int b,int c){
   vector<pair<char,int>> count={{'a',a},{'b',b},{'c',c}};
   string result;
   while(true){
      count.sort(count.begin(),count.end(),[](const pair<char,int> a,const pair <char,int> b){return a.second<b.second});
      bool added=false;
      for(auto &p:count){
         int c=p.second;
         char ch=p.first;
         if(c==0){
            continue;
         }
         int n=result.size();
         if(n>=2&&result[n-1]==ch&&result[n-2]==ch){
            continue;
         }
         result+=ch;
         p.second--;
         added=true;
         break;
      }
      if(!added) break;    
   }
   return result;
}

2024/10/31

一、区间

（1） 汇总区间

给定一个 无重复元素 的 有序 整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

列表中的每个区间范围 [a,b] 应该按如下格式输出：

  • "a->b" ，如果 a != b
  • "a" ，如果 a == b

主要是学一下官解的优雅。思路肯定都有，但是如何能做到代码既正确又简洁呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
       int n=nums.size();
       int i=0;
       vector<string> res;
       while(i<n){
          int left=i;
          i++;
          while(i<n&&nums[i]==nums[i-1]+1){
             i++;
          }
          int right=i-1;
          string tmp=to_string(nums[left]);
          if(left<right){
             tmp.append("->");
             tmp.append(to_string(nums[right]));
          }
          res.push_back(move(tmp));
       }
       return res;
    } 
};

第一、官解的写法不需要把最后一个区间在循环结束后放入向量中。

第二、std::move 将 temp 转换为右值引用，告诉编译器：不再需要 temp 的数据，可以直接“搬走”它的资源（如字符串内容的指针）。

通过“移动”而不是“拷贝”，避免了额外的内存分配，减少了不必要的数据复制，从而提升性能。在移动完成后，temp 处于“空”状态，里面的内容可能被清空或无效。因此，移动后的 temp 不应再被使用。

（2） 合并区间

跟上一题思路一模一样，就就懒得说了

（3）插入区间

给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。

在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。返回插入之后的 intervals。注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。

（试图原地修改结果出bug了，还是老老实实地一个一个插入新数组吧）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int> > ans;
        int n=intervals.size();
        int l=newInterval[0],r=newInterval[1];
        bool isDone=0;
        for(auto interval:intervals){
            if(interval[0]>r){
                if(!isDone){
                    ans.push_back({l,r});
                    isDone=1;
                }
                ans.push_back(interval);
            }
            else if(interval[1]<l){
                ans.push_back(interval);
            }
            else{
                l=min(l,interval[0]);
                r=max(r,interval[1]);
            }
        }
        if(!isDone) ans.push_back({l,r});
        return ans;
    }
};

2024/11/1

一、区间

（1）用最少数量的箭引爆气球

跟合并区间很像。就是很多区间，合并完得到多少个的感觉。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end());
        int l=points[0][0],r=points[0][1];
        int cnt=1;
        for(auto point:points){
            if(point[0]<=r){
                l=max(l,point[0]);
                r=min(r,point[1]);
            }
            else{
                cnt++;
                l=point[0];
                r=point[1];
            }
        }
        return cnt;
    }
};

二、栈

（1）逆波兰表达式求值

逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时，使用一个栈存储操作数，从左到右遍历逆波兰表达式，进行如下操作：

  • 如果遇到操作数，则将操作数入栈；

  • 如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。

整个逆波兰表达式遍历完毕之后，栈内只有一个元素，该元素即为逆波兰表达式的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
       int n=tokens.size();
       for(int i=0;i<n;i++){
          string& token=tokens[i];
          if(isNumber(token)){
             stk.push(stoi(token));
          }else{
             int num2=stk.top();stk.pop();
             int num1=stk.top();stk.pop();
             switch(token[0]){
                case '+': stk.push(nums1+nums2);break;
                case '-': stk.push(nums1-nums2);break;
                case '*': stk.push(nums1*nums2);break;
                case '/': stk.push(nums1/nums2);break;
             }
          }
       }
       return stk.top();
    }
};

（2）基本计算器 II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

  • 这里仅给出将运算式转换为逆波兰表达式的部分。
  • 遇到数字就放入输出中，遇到运算符先压入栈中，如果栈不为空且栈顶元素优先级大于等于当前运算符就把栈顶元素放入输出（保证计算的正确性）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int getPriority(char op) {
   if(op=='-'||op=='+') return 1;
   if(op=='*'||op=='/') return 2;
   return 0;
}

bool isOperator(char c) {
   return c=='+'||c=='-'||c=='*'||c=='/';
}

vector<int> toPostfix(string& s) {
   stack<char> ops;
   vector<int> ans;
   for(char c:s){
      if(isdigit(c)){
         ans.push_back(c);
      }else if(isOperator(c)){
         while(!ops.empty()&&getPriority(ops.top())>=getPriority(c)){
            ans.push_back(ops.top());
            ops.pop();
         }
         ops.push(c);
      }
   }
   while(!ops.empty){
      ans.push_back(ops.top());
      ops.pop();
   }
   return ans;
}

三、滑动窗口

（1）串联所有单词的子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        if(s.empty()||words.empty()) return {};
       int wn=words[0].size();
       int n=words.size();
       int m=s.size();
       unordered_map<string,int> count;
       for(const string& word: words)
          count[word]++;
       vector<int> ans;
       for(int i=0;i<nw;i++){
          int l=i,r=i;
          unordered_map<string,int> curCount;
          int cnt=0;
          
          while(r+nw<=m) {
             string w=s.substr(r,nw);
             r+=n;
             curCount[w]++;
             cnt++;
             
             while(curCount[w]>count[w]) {
                string lw=s.substr(l,nw);
                l+=n;
                curCount[lw]--;
                cnt--;
             }
          }
          
          if(cnt==nw){
             res.push_back(l);
          }
       }
       
    }
};
c++
#c++
力扣刷题记录10.27-
http://example.com/2024/10/27/力扣刷题记录10.27-/
Author
Yaodeer
Posted on
October 27, 2024
Licensed under