首页

想了想方便复习，把hot100先不按模块，零碎的把做过的还有简单题先搞定了再说。题都挪到这篇。
话不多说开刷😤！！！

在线OJ

输入输出和头文件使用的不熟练导致面的时候浪费了不少时间😅备忘一下：

常用C++头文件

功能 头文件 常用内容
输入输出 #include <iostream> cin,cout
容器 #include <vector> vector
映射 #include <unordered_map>,#include <map> 哈希表，字典树结构
集合 #include <unordered_set>, #include <set> 查找唯一值集合
字符串处理 #include <string> string 类
算法 #include <algorithm> sort,reverse,swap, max, min
数学函数 #include <cmath> abs, pow, sqrt, ceil, floor
输入输出格式 #include <iomanip> setprecision

优化输入输出性能

ios:sync_with_stdio(false);
cin.tie(0);

哈希

1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。

解题思路

论第一道题的含金量👍我一开始提交的版本是纯暴力类型，然后这会想用哈希优化一下，然后莫名思维混乱了。
梳理梳理：

  1. 遍历nums
  2. 如果target-nums[i]在哈希表中，返回两个索引{hash[target-nums[i]],i}
  3. 否则当前数字及其索引存入哈希表

AC代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hash;
        for(int i=0;i<nums.size();i++){
            if(hash.find(target-nums[i])!=hash.end()){
                return {hash[target-nums[i]],i};
            }
            hash[nums[i]]=i;
        }
        return {};
    }
};

49.字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

提示：

  • 1 <= strs.length <= 104
  • 0 <= strs[i].length <= 100
  • strs[i] 仅包含小写字母

解题思路

没想到怎么用哈希，但是题解方法神了

  1. 遍历每个字符串

  2. 排序字符串
    将字符串中的字母排序，字母异位词会有相同的排序结果。

  3. 使用哈希表分组

  • 排序后的字符串作为哈希表的key
  • 将对应原始字符串列表作为value
  1. 输出结果
    哈希表中相同key的所有value就是一组字母异位词，将它们收集到最终的结果中返回即可

完整代码

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> hash;
        for(string str:strs){
            string s=str;
            sort(s.begin(),s.end());
            hash[s].push_back(str);
        }
        vector<vector<string>> ans;
        for(const auto& ha:hash){
            ans.push_back(ha.second);
        }
        return ans;
    }
};

1.最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

解题思路

题解戳此
注意为了时间复杂度为O(n)不能sort

  1. 遍历unordered_set而不是nums
  2. 不断找num+1、num+2…是否在集合中，并记录长度
  3. 当num-1不存在集合中时，num才能作为最长连续序列的起点
  4. 更新最大长度

AC代码

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> hash;
        for(int num:nums){
            if(!hash.count(num)){
                hash.insert(num);
            }
        }
        int maxlen=0;
        for(const auto& num:hash){
            int curnum=num,curlen=1;
            if(!hash.count(num-1)){
                while(hash.count(curnum+1)){
                    curnum++;
                    curlen++;
                }
            }
            maxlen=max(maxlen,curlen);
        }
        return maxlen;
    }
};

双指针

283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意，必须在不复制数组的情况下原地对数组进行操作。

解题思路

一开始看到这道题就觉得不就是交换嘛。但是发现题目中的：“保持非零元素的相对顺序”我就懵了。于是开始暴力穷举循环一层套一层…后来被拉回正道。
核心思想不变，仍是“交换”。
但是交换的条件是将非零元素全部移到数组头部，虽然直观看来与题目所引导的“0全部移到末尾”完全反着来，但是我发现这样做比把0移到末尾再对非零元素进行某种交换排序要来的简单得多。题目作者居心叵测啊（不是

AC代码

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i=0; 
        for(int j=0;j<nums.size();j++){
            if(nums[j]!=0){
                swap(nums[i],nums[j]);
                i++;
            }
        }
    }
};

滑动窗口

子串

普通数组

矩阵

链表

206.反转链表

又是一道经典中的经典题🙀

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

解题思路

  1. 链表反转的本质
  • 让当前节点cur指向它的前一个节点pre。而不是后一个节点next
  • 更新pre和cur，直到cur为空。此时pre为新的head节点
  1. 链表反转过程模拟

    假设存在链表：1->2->3->4->nullptr

  • 初始状态：pre = nullptr && cur = head
  • 逐步变化：
    cur tmp(cur->next) cur->next=pre pre=cur cur=tmpS
    1 2 1->nullptr pre=1 cur=2
    2 3 2->1 pre=2 cur=3
    3 4 3->2 pre=3 cur=4
    4 nullptr 4->3 pre=4 cur=nullptr（结束）
  • 最终pre变成4，即新的链表头头。

此时链表结构为：5 -> 4 -> 3 -> 2 -> 1 -> nullptr

  1. 本题关键步骤
  • 记录下一个节点
  • 反转指向
  • 更新pre（当前节点变成新的头）
  • 继续遍历

完整代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur!=nullptr){
            ListNode* tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
};

21.合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1和l2均按非递减顺序排列

解题思路

  1. 终止条件：有链表为空
  • list1为空，合并结果直接为list2
  • list2为空，合并结果直接为list1
  1. 递归调用：小的打头，每一步递归后返回的值链接到链表末尾
  • 如果list1节点的值 < list2：寻找list1后面节点还有没有也比list2小的节点
让list1->next接上递归后合并的结果；
返回当前较小的节点list1;
  • else：寻找list2后面节点还有没有也比list1小的节点
让list2->next接上递归后合并的结果；
返回当前较小的节点list2;

完整代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==NULL || list2==NULL){
            return list1==NULL ? list2:list1;
        }
        if(list1->val < list2->val){
            list1->next = mergeTwoLists(list1->next,list2);
            return list1;
        }
        else{
            list2->next = mergeTwoLists(list1,list2->next);
            return list2;
        }
    }
};

2.两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

解题思路

这道题着实难倒我🥹乖乖去看题解

  1. 链表逆序存储数字

  2. 两个链表的节点值 + 进位值如果记为a：

  • a % 10为当前节点保存的数位
  • a / 10为新的进位值
  1. 递归思路
  • 如果l1、l2都为空且carry=0，递归结束
  • 定义sum=carry
  • 如果l1不为空，sum+=l1->val，l1=l1->next
  • 同理，如果l2不为空，sum+=l2->val，l2=l2->next
  • new一个当前节点node：ListNode* node=new ListNode(sum%10)
  • 递归调用处理node->next
  • 返回当前节点node

完整代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2,int carry=0) {
        if(l1==nullptr && l2==nullptr && carry==0){
            return nullptr;
        }
        int sum=carry;
        if(l1!=nullptr){
            sum+=l1->val;
            l1=l1->next;
        }
        if(l2!=nullptr){
            sum+=l2->val;
            l2=l2->next;
        }
        ListNode* node=new ListNode(sum%10);
        carry=sum/10;
        node->next=addTwoNumbers(l1,l2,carry);
        return node;
    }
};

二叉树

图论

回溯

二分查找

35.搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为O(logn)的算法。

解题思路

我一开始用的暴力穷举，如下。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        while(nums.size()!=1){
            if(target<nums[0]){
                return 0;
            }
            for(int i=0;i<nums.size()-1;i++){
                if(nums[i]==target){
                    return i;
                }
                else if(nums[i]<target && nums[i+1]>=target){
                    return i+1;
                }
            }
            return nums.size();
        }
        return (target<=nums[0])? 0:1;
    }
};

然后提交之后意识到不符合题意，于是再来换个思路：二分查找
我前几天刚记的二分查找笔记 今天竟然没意识到这道题有多直白地明示我要用!!!∑(ﾟДﾟノ)ノ

二分查找：在有序集合中搜索特定值。

使用术语：

  • 目标 target
  • 索引 index
  • 左、右指示符 left、right
  • 中间指示符 mid

计算 mid 位置：
如果 nums[mid] == target，直接返回索引。
如果 nums[mid] < target，说明 target 应该在右半部分，所以left向右移动（left = mid + 1）。
如果 nums[mid] > target，说明 target 应该在左半部分，所以right向左移动（ right = mid - 1）。

循环结束后，left 就是 target 应该插入的位置。

AC代码

二分查找最基础的方法。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left,right;
        left=0;
        right=nums.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]==target){
                return mid;
            }
            else if(nums[mid]<target){
                left=mid+1;
            }
            else{
                right=mid-1;
            }
        }
        return left;
    }
};

栈

20.有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

解题思路

定义栈的括号匹配规则；() [] {}

初始化一个栈;
当遇到左括号时：
    左括号压栈；
当遇到右括号时:
    如果（栈空）:
        ×；
    否则：
        char 栈顶元素；
        弹出栈顶元素；
        如果栈顶元素与当前右括号不匹配：
            ×；
字符串遍历完后：
    如果（栈空）：
        √；
  • 这里的for循环可以直接用for(char ch:s)，表示对于字符串s中的每一个字符ch,执行循环内容。

AC代码

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char,char>pairs={{')','('},{']','['},{'}','{'}};
        stack<char>stk;
        for(char ch:s){
            if(ch=='(' || ch=='[' || ch=='{'){
                stk.push(ch);
            }
            else{
                if(stk.empty()){
                    return false;
                }
                char top=stk.top();
                stk.pop();
                if(pairs[ch]!=top){
                    return false;
                }
            }
        }
        if(stk.empty()){
            return true;
        }
        return false;
    }
};

堆

贪心算法

动态规划

70.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

解题思路

试图暴力然后失败。然后查看题解：竟然是动态规划~

重点理解部分：

  • 逆向思维：如果要到第n个台阶，就必须从第n-1阶走1步，或者从第n-2阶走2步。
  • dp[n]=dp[n-1]+dp[n-2]

为什么这样递推？
动态规划的核心是拆分子问题,然后找到递推关系。本质根据题目限制条件，建立递推关系，然后用代码实现。
👉 因为你每次只能走 1 级或 2 级，所以你到 n 级的方式只能来自 n-1 和 n-2，而不能来自 n-3、n-4 等。

//先处理边界情况
如果n<=2：返回n；
//动规
定义a=1,b=2；（对应能上的楼梯阶数）和当前阶梯的方案数量temp;
遍历n（从3开始）：
    temp=a+b； //dp[i]=dp[i-2]+dp[i-1]
    a=b;      //a=dp[i-1]
    b=temp;   //b=dp[i];
返回 b;

完整代码

class Solution {
public:
    int climbStairs(int n) {
        if(n<=2){
            return n;
        }
        int a=1,b=2,temp;
        for(int i=3;i<=n;i++){
            temp=a+b;
            a=b;
            b=temp;
        }
        return b;
    }
};

198.打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

提示：
1 <= nums.length <= 100
0 <= nums[i] <= 400

解题思路

题解写的特别详细！这里复述一下：

动态规划的四个解题步骤：

  • 定义子问题
  • 写出子问题的递推关系
  • 确定dp数组的计算顺序
  • （可选）空间优化

    这里根据自己现有的水平仅梳理前三点。

  1. 定义子问题
    原问题：“从全部房间偷到的最大金额”→子问题：“从前k个房间偷到的最大金额”

  2. 写出子问题的递推关系
    👉已知子问题f(k)，那么只关注当前（即第k个）房间，只有两种偷法：
    偷k && 偷k-2or不偷k && 偷k-1间

👉可得递推关系：f(k)=max{f(k-1),k-1房间的钱+f(k-2)}。这里的f(k)也叫做状态，式子也叫做状态转移方程。

同时别忘了边界情况：无房子（k=0）和只有一个房子(k=1)。

  1. 确定dp数组的计算顺序
    👉dp数组（子问题数组，）：dp[k]=偷前k间房子的最大金额。

👉大多动规问题使用自底向上的dp数组循环方法。

✅️由子问题的计算顺序可得：dp[k]依赖于dp[k-1]和dp[k-2]。那么就可以开写力

完整代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        if(n==0){
            return 0;
        }
        vector<int> dp(n+1,0);
        dp[1]=nums[0];
        for(int i=2;i<=n;i++){
            dp[i]=max(dp[i-1],nums[i-1]+dp[i-2]);
        }
        return dp[n];
    }
};

416.分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

解题思路

这里涉及「恰好装满」的0-1背包问题，教程戳此

完整代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(sum%2!=0){
            return false;
        }
        int target=sum/2;
        vector<bool> dp(target+1,false);
        dp[0]=true;//存在和为i=0的子集
        for(int num:nums){
            for(int i=target;i>=num;i--){
                dp[i]=dp[i] || dp[i-num];
            }
        }
        return dp[target];
    }
};

多维动态规划

技巧

169.多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

提示：

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -109 <= nums[i] <= 109

解题思路

天哪我竟然一次性写对了而且用时击败百分百😭好久没有这样了…哈希哈希我们喜欢你🥰

完整代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> cnts;
        int n=nums.size();
        for(int num:nums){
            cnts[num]++;
        }
        int ans=0;
        for(const auto& cnt:cnts){
            if(cnt.second>n/2){
                return cnt.first;
            }
        }
        return 0;
    }
};