LC Hot 100: Solutions and Notes

1. 两数之和

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

vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;
        for(int i=0;i<nums.size();i++){
            auto it=mp.find(target-nums[i]);
            if(it!=mp.end()) return {it->second,i};
            mp.insert(pair(nums[i],i));
        }
        return {};
    }

2. 两数相加

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

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry=0;
        ListNode dummy(0);
        ListNode* tail=&dummy;
        while(l1||l2||carry){
            int sum=(l1?l1->val:0)+(l2?l2->val:0)+carry;
            tail->next=new ListNode(sum%10);
            tail=tail->next;
            carry=sum/10;
            if(l1) l1=l1->next;
            if(l2) l2=l2->next;
        }
        return dummy.next;
    }

3. 无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> cnt;
        int n=s.size(),ans=0,left=0;
        for(int i=0;i<n;i++){
            char c=s[i];
            cnt[c]++;
            while(cnt[c]>1){
                cnt[s[left]]--;
                left++;
            }
            ans=max(ans,i-left+1);
        }
        return ans;
    }

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

string longestPalindrome(string s) {
        string ans="";
        for(int i=0;i<s.size();i++){
            int l=i-1,r=i+1;
            while(l>=0&&r<s.size()&&s[l]==s[r]) l--,r++;
            if(ans.size()<r-l-1) ans=s.substr(l+1,r-l-1);
            l=i,r=i+1;
            while(l>=0&&r<s.size()&&s[l]==s[r]) l--,r++;
            if(ans.size()<r-l-1) ans=s.substr(l+1,r-l-1);
        }
        return ans;
    }

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
**说明：**你不能倾斜容器。

int maxArea(vector<int>& height) {
        int n=height.size();
        int right=n-1,left=0,ans=0;
        while(left<right){
            int l=right-left;
            ans=max(ans,l*min(height[right],height[left]));
            if(height[right]>=height[left]) left++;
            else right--;
        }
        return ans;
    }

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
**注意：**答案中不可以包含重复的三元组。

vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        int n=nums.size();
        for(int i=0;i<n;i++){
            int l=i+1,r=n-1;
            if(nums[i]>0) break;
            if(i>0&&nums[i]==nums[i-1]) continue;
            while(l<r){
                int sum=nums[i]+nums[r]+nums[l];
                if(sum==0){
                    res.push_back({nums[i],nums[l],nums[r]});
                    int left=nums[l],right=nums[r];
                    while(l<r&&nums[l]==left) l++;
                    while(l<r&&nums[l]==right) r--;
                }else if(sum<0) l++;
                else r--;
            }
        }
        return res;
    }

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

class Solution {
public:
    string strs[10]={
        "","","abc","def",
        "ghi","jkl","mno",
        "pqrs","tuv","wxyz",
    };
    vector<string> ans;
    string s="";
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return ans;
        backtrack(digits,0);
        return ans;
    }
    void backtrack(string digits,int index){
        if(digits.size()==index){
            ans.push_back(s);
            return;
        }
        int digit=digits[index]-'0';
        string letter=strs[digit];
        for(int i=0;i<letter.size();i++){
            s.push_back(letter[i]);
            backtrack(digits,index+1);
            s.pop_back();
        }
    }
};

思路

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy=new ListNode(0);
        dummy->next=head;
        ListNode* fast=dummy;
        ListNode* slow=dummy;
        while(n){
            fast=fast->next;
            n--;
        }
        while(fast->next){
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        return dummy->next;
    }

思路

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

bool isValid(string s) {
        if(s.size()%2!=0) return false;
        stack<char> st;
        for(char ch:s){
            if(ch=='(') st.push(')');
            else if(ch=='{') st.push('}');
            else if(ch=='[') st.push(']');
            else{
                if(st.empty()||st.top()!=ch) return false;
                st.pop();
            }
        }
        return st.empty();
    }

思路

21. 合并两个有序链表

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

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy=new ListNode(0);
        ListNode* cur=dummy;
        while(list1&&list2){
            if(list1->val<list2->val) {
                cur->next=list1;
                list1=list1->next;
            }else{
                cur->next=list2;
                list2=list2->next;
            }
            cur=cur->next;
        }
        cur->next=list1?list1:list2;
        return dummy->next;
    }

思路

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

class Solution {
public:
    string path="";
    vector<string> res;
    vector<string> generateParenthesis(int n) {
        backtrack(n,n);
        return res;
    }
    void backtrack(int left,int right){
        if(right<left||left<0||right<0) return;
        if(left==0&&right==0){
            res.push_back(path);
            return;
        }
        path.push_back('(');
        backtrack(left-1,right);
        path.pop_back();
        path.push_back(')');
        backtrack(left,right-1);
        path.pop_back();
    }
};

思路

31. 下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须** 原地 **修改，只允许使用额外常数空间。

void nextPermutation(vector<int>& nums) {
        int i=nums.size()-1;
        while(i>0&&nums[i]<=nums[i-1]) i--;
        if(i==0) reverse(nums.begin(),nums.end());
        else{
            int j=nums.size()-1;
            while(nums[j]<=nums[i-1]) j--;
            swap(nums[i-1],nums[j]);
            reverse(nums.begin()+i,nums.end());
        }
    }

思路

32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

int longestValidParentheses(string s) {
        stack<int> st;
        st.push(-1);
        int ans=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='(') st.push(i);
            else{
                st.pop();
                if(st.empty()) st.push(i);
                else ans=max(ans,i-st.top());
            }
        }
        return ans;
    }

思路

33. 搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

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

思路

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

思路

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtrack(vector<int>& candidates, int target, int sum, int start){
        if(sum==target) {
            res.push_back(path);
            return;
        }
        for(int i=start;i<candidates.size()&&sum+candidates[i]<=target;i++){
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backtrack(candidates,target,sum,i);
            sum-=candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        backtrack(candidates,target,0,0);
        return res;
    }
};

思路

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

int trap(vector<int>& height) {
        int l=0,r=height.size()-1;
        int lmax=0, rmax=0, ans=0;
        while(l<r){
            lmax=max(lmax,height[l]);
            rmax=max(rmax,height[r]);
            if(lmax<rmax){
                ans+=lmax-height[l];
                l++;
            }else{
                ans+=rmax-height[r];
                r--;
            }
        }
        return ans;
    }

思路

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtrack(vector<int>& nums,vector<bool>& used){
        if(path.size()==used.size()){
            res.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(used[i]) continue;
            used[i]=true;
            path.push_back(nums[i]);
            backtrack(nums,used);
            used[i]=false;
            path.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(),false);
        backtrack(nums,used);
        return res;
    }
};

思路

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        for(int i=0;i<n;i++){
            for(int j=0;j<i;j++){
                swap(matrix[i][j],matrix[j][i]);
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n/2;j++){
                swap(matrix[i][j],matrix[i][n-j-1]);
            }
        }
    }

思路

49. 字母异位词分组

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> record;
        for(int i=0;i<strs.size();i++){
            string key=strs[i];
            sort(key.begin(),key.end());
            record[key].push_back(strs[i]);
        }
        vector<vector<string>> ans;
        for(auto it=record.begin();it!=record.end();it++){
            ans.push_back(it->second);
        }
        return ans;
    }

思路

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

int maxSubArray(vector<int>& nums) {
        int ans=nums[0],pre=0;
        for(int x:nums){
            pre=max(x+pre,x);
            ans=max(ans,pre);
        }
        return ans;
    }

思路

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

bool canJump(vector<int>& nums) {
        int rightmost=0,n=nums.size();
        for(int i=0;i<n;i++){
            if(i<=rightmost){
                rightmost=max(rightmost,i+nums[i]);
                if(rightmost>=n-1) return true;
            }
        }
        return false;
    }

思路

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start(i), end(i)] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        sort(intervals.begin(),intervals.end());
        int start=intervals[0][0],end=intervals[0][1];
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0]>end){
                ans.push_back({start,end});
                start=intervals[i][0];
                end=intervals[i][1];
            }else{
                end=max(end,intervals[i][1]);
            }
        }
        ans.push_back({start,end});
        return ans;
    }

思路

62. 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

思路

64. 最小路径和

给定一个包含非负整数的 mxn 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
**说明：**每次只能向下或者向右移动一步。

int minPathSum(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        dp[0][0]=grid[0][0];
        for(int i=1;i<m;i++) dp[i][0]=grid[i][0]+dp[i-1][0];
        for(int j=1;j<n;j++) dp[0][j]=grid[0][j]+dp[0][j-1];
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }

思路

70. 爬楼梯

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

思路

72. 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符

int minDistance(string word1, string word2) {
        int m=word1.size(),n=word2.size();
        vector dp(m+1,vector<int>(n+1));
        for(int i=0;i<=m;i++) dp[i][0]=i;
        for(int j=0;j<=n;j++) dp[0][j]=j;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];
                else dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;
            }
        }
        return dp[m][n];
    }

思路

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。

void sortColors(vector<int>& nums) {
        int p0=0,cur=0,p2=nums.size()-1;
        while(cur<=p2){
            if(nums[cur]==2) swap(nums[cur],nums[p2--]);
            else if(nums[cur]==0) swap(nums[cur++],nums[p0++]);
            else cur++;
        }
    }

思路

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按 任意顺序 返回解集。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtrack(vector<int>& nums, int start){
        res.push_back(path);
        if(start>nums.size()) return;
        for(int i=start;i<nums.size();i++){
            path.push_back(nums[i]);
            backtrack(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        backtrack(nums,0);
        return res;
    }
};

思路

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m=board.size(),n=board[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(dfs(board,word,i,j,0)) return true;
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& board, string word, int i, int j, int p){
        if(p==word.size()) return true;
        int m=board.size(),n=board[0].size();
        if(i<0||j<0||i>=m||j>=n) return false;
        if(board[i][j]!=word[p]) return false;
        char ch=board[i][j];
        board[i][j]='.';
        bool ans=dfs(board,word,i+1,j,p+1)||
                dfs(board,word,i-1,j,p+1)||
                dfs(board,word,i,j+1,p+1)||
                dfs(board,word,i,j-1,p+1);
        board[i][j]=ch;
        return ans;
    }
};

思路

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

思路

85. 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy=new ListNode(0);
        dummy->next=head;
        ListNode* fast=dummy;
        ListNode* slow=dummy;
        while(n){
            fast=fast->next;
            n--;
        }
        while(fast->next){
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        return dummy->next;
    }

思路

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的中序遍历。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
        traversal(root,res);
        return res;
    }
 
    void traversal(TreeNode* root, vector<int> &res){
        if(!root) return;
        traversal(root->left,res);
        res.push_back(root->val);
        traversal(root->right,res);
    }
};

思路

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

int numTrees(int n) {
        vector<int> dp(n+1);
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }

思路

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
节点的左子树只包含 严格小于 当前节点的数。
节点的右子树只包含 严格大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

class Solution {
public:
    TreeNode* pre=NULL;
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        bool left=isValidBST(root->left);
        if(pre&&root->val<=pre->val) return false;
        pre=root;
        bool right=isValidBST(root->right);
        return left&&right;
    }
};

思路

101. 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return compare(root->left,root->right);
    }
 
    bool compare(TreeNode* p, TreeNode* q){
        if(!p&&!q) return true;
        if(!p||!q) return false;
        return p->val==q->val&&compare(p->left,q->right)&&compare(p->right,q->left);
    }
};

思路

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        if(root) que.push(root);
        while(!que.empty()){
            int size=que.size();
            vector<int> ans;
            while(size--){
                TreeNode* node=que.front();
                que.pop();
                ans.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            res.push_back(ans);
        }
        return res;
    }

思路

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

int maxDepth(TreeNode* root) {
        if(!root){return 0;}
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }

思路

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

思路

114. 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

void flatten(TreeNode* root) {
        TreeNode* cur=root;
        while(cur){
            if(cur->left){
                TreeNode* p=cur->left;
                while(p->right) p=p->right;
                p->right=cur->right;
                cur->right=cur->left;
                cur->left=nullptr;
            }
            cur=cur->right;
        }
    }

思路

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> dp(n,vector<int>(2));
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        for(int i=1;i<n;i++){
            dp[i][0]=max(-prices[i],dp[i-1][0]);
            dp[i][1]=max(dp[i-1][1],dp[i][0]+prices[i]);
        }
        return dp[n-1][1];
    }

思路

124. 二叉树中的最大路径和

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

class Solution {
public:
    int ans=INT_MIN;
    int maxPathSum(TreeNode* root) {
        findSum(root);
        return ans;
    }
    int findSum(TreeNode* cur){
        if(!cur) return 0;
        int left=max(findSum(cur->left),0);
        int right=max(findSum(cur->right),0);
        int val=cur->val+left+right;
        ans=max(val,ans);
        return cur->val+max(left,right);
    }
};

思路

128. 最长连续序列

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

int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(),nums.end());
        int res=0;
        for(int n:st){
            if(st.find(n-1)!=st.end()) continue;
            int curNum=n;
            int curLen=1;
            while(st.find(curNum+1)!=st.end()){
                curLen++;
                curNum++;
            }
            res=max(res,curLen);
        }
        return res;
    }

思路

136. 只出现一次的数字

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

思路

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> st(wordDict.begin(),wordDict.end());
        vector<bool> dp(s.size()+1,false);
        dp[0]=true;
        for(int i=1;i<=s.size();i++){
            for(int j=0;j<i;j++){
                if(dp[j]){
                    string word=s.substr(j,i-j);
                    if(st.count(word)){
                        dp[i]=true;
                        break;
                    }
                }
            }
        }
        return dp[s.size()];
    }

思路

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：**pos** 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。否则，返回 false 。

思路

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null**。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：**pos** 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。

思路

146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

class LRUCache {
    int cap;
    list<int> l;
    unordered_map<int,pair<int,list<int>::iterator>> mp;
public:
    LRUCache(int capacity):cap(capacity) {}
 
    int get(int key) {
        if(!mp.count(key)) return -1;
        touch(key);
        return mp[key].first;
    }
 
    void put(int key, int value) {
        if(mp.count(key)){
            l.erase(mp[key].second);
        }else if(cap==l.size()){
            mp.erase(l.front());
            l.pop_front();
        }
        l.push_back(key);
        mp[key]={value,prev(l.end())};
    }
 
    void touch(int key){
        l.erase(mp[key].second);
        l.push_back(key);
        mp[key].second=prev(l.end());
    }
};

思路

148. 排序链表

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head||!head->next) return head;
        ListNode* fast=head->next;
        ListNode* slow=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
        }
        ListNode* mid=slow->next;
        slow->next=nullptr;
        ListNode* left=sortList(head);
        ListNode* right=sortList(mid);
        return merge(left,right);
    }
 
    ListNode* merge(ListNode* l1,ListNode* l2){
        ListNode* dummy=new ListNode(0);
        ListNode* cur=dummy;
        while(l1&&l2){
            if(l1->val<l2->val){
                cur->next=l1;
                l1=l1->next;
            }else{
                cur->next=l2;
                l2=l2->next;
            }
            cur=cur->next;
        }
        cur->next=l1?l1:l2;
        return dummy->next;
    }
};

思路

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
请注意，一个只包含一个元素的数组的乘积是这个元素的值。

int maxProduct(vector<int>& nums) {
        int maxv=1,minv=1,ans=nums[0];
        for(int n:nums){
            if(n<0) swap(maxv,minv);
            maxv=max(n*maxv,n);
            minv=min(n*minv,n);
            ans=max(maxv,ans);
        }
        return ans;
    }

思路

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

class MinStack {
public:
    stack<pair<int,int>> stk;
    MinStack() {}
 
    void push(int val) {
        stk.push({val,min(val,getMin())});
    }
 
    void pop() {
        stk.pop();
    }
 
    int top() {
        return stk.top().first;
    }
 
    int getMin() {
        return stk.empty()?INT_MAX:stk.top().second;
    }
};

思路

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* cur1=headA;
        ListNode* cur2=headB;
        if(!cur1||!cur2) return nullptr;
        while(cur1!=cur2){
            cur1=cur1==nullptr?headB:cur1->next;
            cur2=cur2==nullptr?headA:cur2->next;
        }
        return cur1;
    }

思路

169. 多数元素

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

思路

198. 打家劫舍

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

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

思路

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

思路

206. 反转链表

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

ListNode* reverseList(ListNode* head) {
        ListNode* pre=nullptr;
        ListNode* nxt=nullptr;
        ListNode* cur=head;
        while(cur){
            nxt=cur->next;
            cur->next=pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }

思路

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a(i), b(i)] ，表示如果要学习课程 a(i) 则必须先学习课程 b(i)( )。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

思路

208. 实现 Trie (前缀树)

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

思路

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

思路

221. 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

int maximalSquare(vector<vector<char>>& matrix) {
        int m=matrix.size(),n=matrix[0].size();
        vector dp(m+1,vector<int> (n+1));
        int ans=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(matrix[i][j]=='1'){
                    dp[i+1][j+1]=min({dp[i][j+1],dp[i+1][j],dp[i][j]})+1;
                    ans=max(ans,dp[i+1][j+1]);
                }
            }
        }
        return ans*ans;
    }

思路

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

TreeNode* invertTree(TreeNode* root) {
        if(!root) return{};
        swap(root->left,root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }

思路

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

class Solution {
public:
    ListNode* findMiddle(ListNode* head){
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
    }
    ListNode* reverse(ListNode* head){
        ListNode* pre=nullptr;
        ListNode* nxt=nullptr;
        ListNode* cur=head;
        while(cur){
            nxt=cur->next;
            cur->next=pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }
 
    bool isPalindrome(ListNode* head) {
        ListNode* dummy1=new ListNode(0);
        ListNode* dummy2=new ListNode(0);
        ListNode* list1=findMiddle(head);
        ListNode* list2=reverse(list1);
        dummy2->next=list2;
        dummy1->next=head;
        while(dummy1->next&&dummy2->next){
            if(dummy1->next->val==dummy2->next->val){
                dummy1=dummy1->next;
                dummy2=dummy2->next;
            }else return false;
        }
        return true;
    }
};

思路

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return nullptr;
        if(root==q||root==p) return root;
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        if(left&&right) return root;
        else if(!left&&right) return right;
        else if(left&&!right) return left;
        else return nullptr;
    }

思路

238. 除了自身以外数组的乘积

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积。
题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题。

vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> prefix(n);
        vector<int> suffix(n);
        vector<int> res(n);
        prefix[0]=nums[0];
        suffix[n-1]=nums[n-1];
        for(int i=1;i<n;i++){
            prefix[i]=prefix[i-1]*nums[i];
        }
        for(int i=n-2;i>=0;i--){
            suffix[i]=suffix[i+1]*nums[i];
        }
        res[0]=suffix[1];
        res[n-1]=prefix[n-2];
        for(int i=1;i<n-1;i++){
            res[i]=prefix[i-1]*suffix[i+1];
        }
        return res;
    }

思路

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

思路

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 mxn 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m=matrix.size(),n=matrix[0].size();
        int i=0,j=n-1;
        while(i<m&&j>=0){
            int val=matrix[i][j];
            if(val==target) return true;
            else if(val>target) j--;
            else i++;
        }
        return false;
    }

思路

279. 完全平方数

给你一个整数 n ，返回和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

int numSquares(int n) {
        vector<int> dp(n+1,INT_MAX);
        dp[0]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j*j<=i;j++){
                dp[i]=min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }

思路

283. 移动零

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

void moveZeroes(vector<int>& nums) {
        int left=0,right=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]){
                swap(nums[right],nums[left]);
                left++;
            }
            right++;
        }
    }

思路

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

思路

297. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

思路

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

int lengthOfLIS(vector<int>& nums) {
        int n=nums.size(),ans=1;
        if(n==1) return 1;
        vector<int> dp(n,1);
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]) dp[i]=max(dp[j]+1,dp[i]);
                ans=max(ans,dp[i]);
            }
        }
        return ans;
    }

思路

301. 删除无效的括号

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。

思路

309. 买卖股票的最佳时机含冷冻期

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

int maxProfit(vector<int>& prices) {
        //0持有1保持卖出2今天卖出3冷冻
        int n=prices.size();
        vector<vector<int>> dp(n,vector<int>(4));
        dp[0][0]=0-prices[0];
        dp[0][1]=0;
        dp[0][2]=0;
        dp[0][3]=0;
        for(int i=1;i<n;i++){
            dp[i][0]=max(max(dp[i-1][1],dp[i-1][3])-prices[i],dp[i-1][0]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][3]);
            dp[i][2]=dp[i-1][0]+prices[i];
            dp[i][3]=dp[i-1][2];
        }
        return max(dp[n-1][1],max(dp[n-1][2],dp[n-1][3]));
    }

思路

312. 戳气球

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。

思路

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的最少的**硬币**个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,INT_MAX);
        dp[0]=0;
        for(int i=0;i<coins.size();i++){
            for(int j=coins[i];j<=amount;j++){
                if(dp[j-coins[i]]!=INT_MAX) dp[j]=min(dp[j],dp[j-coins[i]]+1);
            }
        }
        return dp[amount]==INT_MAX?-1:dp[amount];
    }

思路

337. 打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result;
        result=robtree(root);
        return max(result[0],result[1]);
    }
 
    vector<int> robtree(TreeNode* cur){
        if(!cur) return {0,0};
        vector<int> left=robtree(cur->left);
        vector<int> right=robtree(cur->right);
        int val1=cur->val+left[0]+right[0];
        int val2=max(left[0],left[1])+max(right[0],right[1]);
        return {val2,val1};
    }
};

思路

338. 比特位计数

给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

vector<int> countBits(int n) {
        vector<int> ans(n+1);
        for(int i=1;i<=n;i++){
            ans[i]=ans[i&(i-1)]+1;
        }
        return ans;
    }

思路

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> cnt;
        int max_cnt=0;
        for(int n:nums){
            cnt[n]++;
            max_cnt=max(max_cnt,cnt[n]);
        }
        vector<vector<int>> buckets(max_cnt+1);
        for(auto& [x,c]:cnt){
            buckets[c].push_back(x);
        }
        vector<int> ans;
        for(int i=max_cnt;i>=0&&ans.size()<k;i--){
            ans.insert(ans.end(),buckets[i].begin(),buckets[i].end());
        }
        return ans;
    }

思路

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
测试用例保证输出的长度不会超过 10(5)。

思路

399. 除法求值

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [A(i), B(i)] 和 values[i] 共同表示等式 A(i) / B(i) = values[i] 。每个 A(i) 或 B(i) 是一个表示单个变量的字符串。
另有一些以数组 queries 表示的问题，其中 queries[j] = [C(j), D(j)] 表示第 j 个问题，请你根据已知条件找出 C(j) / D(j) = ? 的结果作为答案。
返回 所有问题的答案 。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。
**注意：**输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。
**注意：**未在等式列表中出现的变量是未定义的，因此无法确定它们的答案。

思路

406. 根据身高重建队列

假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [h(i), k(i)] 表示第 i 个人的身高为 h(i) ，前面正好有 k(i)( )个身高大于或等于 h(i) 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [h(j), k(j)] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。

class Solution {
public:
    static bool cmp(vector<int>& a,vector<int>& b){
        if(a[0]==b[0]) return a[1]<b[1];
        return a[0]>b[0];
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(),people.end(),cmp);
        vector<vector<int>> ans;
        for(int i=0;i<people.size();i++){
            int pos=people[i][1];
            ans.insert(ans.begin()+pos,people[i]);
        }
        return ans;
    }
};

思路

416. 分割等和子集

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

bool canPartition(vector<int>& nums) {
        int sum=0;
        for(int n:nums) sum+=n;
        if(sum%2!=0) return false;
        vector<bool> dp(sum+1,false);
        sum=sum/2;
        dp[0]=true;
        for(int i=0;i<nums.size();i++){
            for(int j=sum;j>=0;j--){
                if(j>=nums[i]) dp[j]=dp[j]||dp[j-nums[i]];
            }
        }
        return dp[sum];
    }

思路

437. 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

思路

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

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> need;
        unordered_map<char, int> window;
        for (char c : p) {
            need[c]++;
        }
        int left = 0, right = 0;
        int valid = 0;
        vector<int> res;
        while (right < s.size()) {
            char c = s[right];
            right++;
            if (need.count(c)) {
                window[c]++;
                if (window[c] == need[c]) {
                    valid++;
                }
            }
            while (right - left >= p.size()) {
                // 当窗口符合条件时，把起始索引加入 res
                if (valid == need.size()) {
                    res.push_back(left);
                }
                char d = s[left];
                left++;
                // 进行窗口内数据的一系列更新
                if (need.count(d)) {
                    if (window[d] == need[d]) {
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        return res;
    }

思路

448. 找到所有数组中消失的数字

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n=nums.size();
        vector<int> res;
        for(int num:nums){
            int x=(num-1)%n;
            if(nums[x]<=n) nums[x]+=n;
        }
        for(int i=0;i<n;i++){
            if(nums[i]<=n) res.emplace_back(i+1);
        }
        return res;
    }

思路

461. 汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

int hammingDistance(int x, int y) {
        int res=0,s=x^y;
        while(s){
            res+=s&1;
            s>>=1;
        }
        return res;
    }

思路

494. 目标和

给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

int findTargetSumWays(vector<int>& nums, int target) {
        int sum=0;
        for(int n:nums) sum+=n;
        if((sum+target)%2==1||abs(target)>sum) return 0;
        int bagSize=(sum+target)/2;
        vector<int> dp(bagSize+1,0);
        dp[0]=1;
        for(int i=0;i<nums.size();i++){
            for(int j=bagSize;j>=nums[i];j--){
                dp[j]=dp[j]+dp[j-nums[i]];
            }
        }
        return dp[bagSize];
    }

思路

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

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

class Solution {
public:
    int sum=0;
    TreeNode* convertBST(TreeNode* root) {
        if(!root) return nullptr;
        convertBST(root->right);
        sum+=root->val;
        root->val=sum;
        convertBST(root->left);
        return root;
    }
};

思路

543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的直径。
二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的长度由它们之间边数表示。

class Solution {
public:
    int maxVal=0;
    int diameterOfBinaryTree(TreeNode* root) {
        depthOfNode(root);
        return maxVal;
    }
    int depthOfNode(TreeNode* cur){
        if(!cur) return 0;
        int left=depthOfNode(cur->left);
        int right=depthOfNode(cur->right);
        maxVal=max(left+right,maxVal);
        return max(left,right)+1;
    }
};

思路

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。

int subarraySum(vector<int>& nums, int k) {
        int pre=0,cnt=0;
        unordered_map<int,int> mp;
        mp[0]=1;
        for(auto s:nums){
            pre+=s;
            if(mp.count(pre-k)) cnt+=mp[pre-k];
            mp[pre]++;
        }
        return cnt;
    }

思路

581. 最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的最短子数组，并输出它的长度。

int findUnsortedSubarray(vector<int>& nums) {
        int n=nums.size(),left=-1,right=-1;
        int maxv=INT_MIN,minv=INT_MAX;
        for(int i=0;i<n;i++){
            if(maxv<nums[i]) maxv=nums[i];
            else if (maxv>nums[i]) right=i;
            if(minv>nums[n-i-1]) minv=nums[n-i-1];
            else if(minv<nums[n-i-1]) left=n-i-1;
        }
        return right==-1?0:right-left+1;
    }

思路

617. 合并二叉树

给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1) return root2;
        if(!root2) return root1;
        root1->val+=root2->val;
        root1->left=mergeTrees(root1->left,root2->left);
        root1->right=mergeTrees(root1->right,root2->right);
        return root1;
    }

思路

621. 任务调度器

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表，用字母 A 到 Z 表示，以及一个冷却时间 n。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成，但有一个限制：两个 相同种类 的任务之间必须有长度为 n 的冷却时间。
返回完成所有任务所需要的 最短时间间隔 。

思路

647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。

class Solution {
public:
    int countSubstrings(string s) {
        int ans=0;
        for(int i=0;i<s.size();i++){
            ans+=extend(s,i,i);
            ans+=extend(s,i,i+1);
        }
        return ans;
    }
    int extend(const string& s, int l, int r){
        int res=0;
        while(l>=0&&r<s.size()&&s[l]==s[r]){
            l--;
            r++;
            res++;
        }
        return res;
    }
};

思路

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> st;
        vector<int> ans(temperatures.size(),0);
        for(int i=0;i<temperatures.size();i++){
            while(!st.empty()&&temperatures[i]>temperatures[st.top()]){
                ans[st.top()]=i-st.top();
                st.pop();
            }
            st.push(i);
        }
        return ans;
    }

思路