求职-LeetCode热题100刷题记录

2025-04-192025-05-04

题目来源于leetcode.cn，这里仅记录自己的刷题过程和总结解法，代码部分参考题解部分独创,相关权利归leetcode和原作者所有,转载请注明来源。

哈希

1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
解法：使用哈希表存储访问过的元素，相比双重循环，时间复杂度从O(n^2)降低到O(n)，空间复杂度从O(1)升高到O(n)。

(这里学习到1个c++语法,++i是返回自增后的对象，i++是返回当前对象的临时副本再自增，循环迭代中使用++i优于i++)

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashtable = dict()
        for i,num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target-num],i]
            hashtable[num]=i
        return []

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

};

49.字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
解法：
1.使用排序后的字符串作为哈希表的键，字母异位词会被放入同一个组中。
2.统计每个字符串每个字符出现的次数，将字符出现次数作为哈希表的键，字母异位词会被放入同一个组中。

(python使用ord()函数可以获取字符的ASCII整数编码)

class listDict(dict):
    def __init__(self, value_type):
        super().__init__()        
        self.value_type = value_type

    def __getitem__(self, key):
        if key not in self:
            self[key] = self.value_type()  
        return super().__getitem__(key)
        
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        mp = listDict(list)
        for st in strs:
            key = "".join(sorted(st))
            mp[key].append(st)
        return list(mp.values())

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> mp;
        for (string& str:strs){
            string key = str;
            sort(key.begin(),key.end());
            mp[key].emplace_back(str);
        }
        vector<vector<string>> ans;
        for (auto it=mp.begin();it!=mp.end();++it){
            ans.emplace_back(it.second);
        }
        return ans;
    }
};

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
解法：只求长度，先排序，只需判断相邻元素插值是否为1,为0跳过,不为1则中断,为1则更新长度。

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        lenth = 0
        nums_set = set(nums)
        for num in nums_set:
            if num-1 not in nums_set:
                current_num = num+1
                current_lenth=1
                while current_num in nums_set:
                    current_lenth +=1
                    current_num +=1
                lenth = max(lenth,current_lenth)
        return lenth

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(!nums.size()) return 0;
        sort(nums.begin(), nums.end());
        int length_max = 1;
        int length_temp = 1;
        for(int i=1; i<nums.size(); ++i){
            if(nums[i] == nums[i-1]) continue;
            if(nums[i] == nums[i-1] + 1){
                length_temp++;
            }
            else{
                if(length_temp > length_max)
                    length_max = length_temp;
                length_temp = 1;
            }
        }
        
        if(length_temp > length_max)
            length_max = length_temp;
        return length_max;
    }
};

双指针

283. 移动零

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

1.双指针，一个指针l指向0的位置，一个指针r指向非零元素位置。l在r遇到0时停下来，r指针继续向前移动,当r非零时交换r、l指向的元素。
2.初始j=0,遍历数组，如果元素不为0，则将元素赋值给nums[j]，并将j+1。遍历结束后，将nums[j:]部分全部赋值为0。

(这里学习到1个python语法,对于列表+=和extend等效是原地址修改,l1=l1+l2则会创建新的对象再绑定;c++ vector中erase会删除元素并使迭代器指向被删除元素之后的元素,在遍历中删除元素要将++it 放在循环体内判断是否执行而不是头部;)

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        auto l = nums.begin();
        auto r = nums.begin();
        while (r != nums.end()){
            if (*r != 0){
                int temp = *l;
                *l = *r;
                *r = temp;
                ++l;
            }
            ++r;

        }
    }
};

11. 盛最多水的容器

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

解法：双指针，左右指针向中间靠拢，由于木桶容量只由最短方i决定且是求最大值，故针对最短i的所有j都不需要再遍历，每次移动最短方i即可。注意,暴力双循环会超时。

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        bv = 0
        l,r =0,len(height)-1
        while l!= r:
            if height[l]<height[r]:
                v = (r-l) * height[l]
                l+=1
            else:
                v = (r-l) * height[r]
                r-=1
            bv = max(v,bv)
        return bv

class Solution {
public:
    int maxArea(vector<int>& height) {
        int l=0,r=height.size()-1;
        int bv = 0;
        while (l<r){
            int v =0;
            if (height[l] < height[r]){
                v = (r-l) * height[l];
                ++l;
            }
            else {
                v = (r-l) * height[r];
                --r;
            }
            bv = max(v,bv);
        }
        return bv;
    }
};

15. 三数之和

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

1.转字典排序后不妨设i<j<k和nums[i] <= nums[j] <= nums[k].对于nums[i] + nums[j] + nums[k] == 0,nums[i]<=0、nums[k]>=0必然成立。因此，只需利用双指针枚举i、k判断是否存在j满足条件即可,程序中i,j,k对应left,medium,right，时间复杂度O(n^2)。
2.先排序，然后固定i，双指针枚举j、k.如果*j+*k<-i,增大j;如果j+*k>=-i,减小k;如果j+*k==-*i，则加入结果。过程中,要跳过相同元素来去重。

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums_dict = defaultdict(int)
        for num in nums:
            nums_dict[num] += 1
        nums_list = list(nums_dict.keys())
        nums_list.sort()

        if nums_dict.get(0, 0) > 2:
            res.append([0, 0, 0])
        
        for left in nums_list:
            if left >= 0: break
            for right in reversed(nums_list):
                if right <= 0: break
                medium = -left-right
                if medium in nums_dict:
                    if medium == left or medium == right:
                        if nums_dict[medium] > 1:
                            res.append([left, medium, right])
                    elif medium > left and medium < right:
                        res.append([left, medium, right])
        return res

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res = {};
        sort(nums.begin(),nums.end());
        auto bg = nums.begin();
        auto ed = nums.end();
        for (auto p = bg; p<ed-2;){
            auto l = p+1, r = ed - 1;
            int k = *p;
            while(l < r){
                while(*l+*r<-k&&l<r) l++;
                while(*l+*r>-k&&l<r) r--;
                if(l>=r) break;
                if (*l+*r==-k){
                    res.push_back({*p,*l,*r});
                    int x=*l,y=*r;
                    while(*l==x&&l<r)l++;
                    while(*r==y&&l<r)r--;
                }
            }
            while(*p==k&&p<ed-2)p++;
        }
        return res;
    }
};

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
解法：每个柱子上存储的雨量由leftmax和rightmax较低者决定,双指针向中间走，不断更新leftmax和rightmax。对于left,leftmax一定准确；对于right,rightmax一定准确。故只需判断当前leftmax和rightmax的大小，即可判断是更新left还是right准确。更新后调整索引位置变化1即可,时间复杂度O(n),空间复杂度O(1)。

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l,r=0,len(height)-1
        lmax,rmax=height[0],height[-1]
        ans = 0
        while l<r:
            if lmax<rmax:
                ans+=lmax-height[l]
                l+=1
                lmax=max(lmax,height[l])
            else:
                ans+=rmax-height[r]
                r-=1
                rmax = max(rmax,height[r])
        return ans

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

            }
        }
        return ans;
    }
};

滑动窗口

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

给定一个字符串s,请你找出其中不含有重复字符的最长子串的长度。
解法：双指针，当右指针遇到重复字符时，左指针移动到不含重复字符的位置，过程中维护散列表判断字符是否重复并更新最大长度。

散列表就是哈希表,如Python 的 set / dict，C++ 的 unordered_set / unordered_map，Java 的 HashSet / HashMap。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        occ =set()
        l,r=0,0
        k=0
        while r < len(s):
            if s[r] in occ:
                while s[r] in occ:
                    occ.remove(s[l])
                    l+=1
            occ.add(s[r])
            r+=1
            k=max(k,r-l)
        return k

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> occ;
        int l=0,r=0,ans=0;
        for(r=0;r<s.size();++r){
            while (occ.count(s[r])){
                occ.erase(s[l++]);
            }
            occ.insert(s[r]);
            ans=max(ans,r-l+1);
        }
        return ans;
    }
};

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

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
解法：
注意暴力枚举会超时，因此需要用滑动窗口来优化。

1.比较当前窗口和p中每种字母的数量是否完全相同来判断是否符合要求，滑动时维护当前窗口每种字母的数量
2.统计滑动窗口和字符串 p 中每种字母的数量差count，统计当前窗口与字符串 p 中数量不同的字母的个数differ,滑动时根据count维护differ,differ==0表示符合要求

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        s_len,p_len = len(s), len(p)
        if s_len < p_len: return []
        res = []
        s_count = [0] * 26
        p_count = [0] * 26

        for i in range(p_len):
            s_count[ord(s[i]) - 97] += 1
            p_count[ord(p[i]) - 97] += 1
        if s_count == p_count:
            res.append(0)
        for i in range(s_len - p_len):
            
            s_count[ord(s[i]) - 97] -= 1
            
            s_count[ord(s[i + p_len]) - 97] += 1
            
            if s_count == p_count:
                res.append(i+1)
        return res

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int slen=s.size(),plen=p.size();
        if (slen<plen){
            return vector<int>();
        }
        vector<int> ans;
        vector<int> count(26);
        for (int i=0;i<plen;++i){
            ++count[s[i]-'a'];
            --count[p[i]-'a'];
        }
        int differ = 0;
        for (int i=0;i<26;++i){
            if (count[i]!=0){
                ++differ;
            }
        }
        if (differ==0){
            ans.emplace_back(0);
        }
        for (int i=0;i<slen-plen;++i){
            
            --count[s[i]-'a'];
            if (count[s[i]-'a']==0){
                --differ;
            }
            else if (count[s[i]-'a']==-1){
                ++differ;
            }

             
            ++count[s[i+plen]-'a'];
            if (count[s[i+plen]-'a']==1){
                ++differ;
            }
            else if (count[s[i+plen]-'a']==0){
                --differ;
            }
            if (differ == 0){
                ans.emplace_back(i+1);
            }
        }
        return ans;

    }
};

子串

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返该数组中和为k的子数组的个数。子数组是数组中元素的连续非空序列。
解法：暴力枚举会超时,因此可以在遍历时统计nums[:j]的和sum,使用sum[j]-k=sum[i]来判断是否存在nums[j:i]的和为k的子数组,数量为sum[j]-k出现的次数。时间复杂度由O(n^2)变为O(n),空间复杂度由O(1)变为O(n)。

class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        prefix_count = {0: 1}  
        current_sum = 0  
        count = 0  
        for num in nums:
            current_sum += num
            if current_sum - k in prefix_count:  
                count += prefix_count[current_sum - k]
            prefix_count[current_sum] = prefix_count.get(current_sum, 0) + 1
        return count

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        mp[0]=1;
        int ans=0,pre=0;
        for (auto &num:nums){
            pre += num;
            if (mp.find(pre-k) != mp.end()){
                ans +=mp[pre-k];
            }
            mp[pre]++;

        }
        return ans;
    }
};

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
解法: 滑动过程中只需用一个deque在队首维护最大值即可，队列里不需要完整的排序。只需保证：新元素加入时，删除所有比它小的“无用元素”；确保窗口滑动时，队首如果过期就弹出。

1.python collections.deque实际是一个双向链表，操作首尾元素的效率远高于list,但访问中间元素的效率不如动态数组list。
2.优先队列、最大、最小堆基于完全二叉树实现，元素插入和删除时需要有上浮或下沉操作，可用一个数组维护，根据当前索引i其父节点和子节点有以下关系：父节点parent=(i-1)//2，左子节点left=2i+1，右子节点right=2i+2。

from collections import deque
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res=[]
        n = len(nums)
        q = deque()
        for i in range(k):
            while q and nums[q[-1]]<=nums[i]:
                q.pop()
            q.append(i)
        res.append(nums[q[0]])
        for i in range(k,n):
            while q and nums[q[-1]]<=nums[i]:
                q.pop()
            q.append(i)
            while q[0] <= i-k:
                q.popleft()
            res.append(nums[q[0]])
        return res

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n=nums.size();
        deque<int> q;
        for (int i=0;i<k;++i){
            while (!q.empty() && nums[i] >= nums[q.back()]){
                q.pop_back();
            }
            q.push_back(i);
        }
        vector<int> res = {nums[q.front()]};
        for (int i=k;i<n;++i){
            while (!q.empty() && nums[i]>=nums[q.back()]){
                q.pop_back();
            }
            q.push_back(i);
            while (q.front() < i-k+1){
                q.pop_front();
            }
            res.push_back(nums[q.front()]);
        }
        return res;
    }
};

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

解法：维护一个滑动窗口,r先向右移动到恰好满足条件为止，l向右移动到恰好不满足条件为止，更新最小字串，接着再重复上述过程返回最终的最小字串。

注意，滑动窗口直接从两边向中间缩小，不能完整覆盖所有字串，不能保证一定是最小值。

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        count=[0]*(ord('z')-64)
        differ = 0
        for ch in t:
            c= ord(ch)-65
            count[c]-=1
            if count[c] == -1:
                differ+=1 
        l,r,ans=0,0,""
        mlen=len(s)+1 
        for r in range(len(s)):
            c=ord(s[r])-65
            count[c]+=1
            if count[c]==0:
                differ-=1
            if differ==0:
                while l<=r:
                    c=ord(s[l])-65
                    if count[c]-1<0:
                        if r-l+1<mlen:
                            mlen=r-l+1
                            ans=s[l:r+1]
                        break
                    count[c]-=1
                    l+=1
        return ans

class Solution {
public:
    string minWindow(string s, string t) {
        int count['z'-65+1]={0};
        int m=0,mlen=s.size()+1;
        string ans="";
        for (auto &c : t){
            --count[c-65];
            if (count[c-65]==-1){
                ++m;
            }
        }
        for(int r=0,l=0,c=0;r<s.size();++r){
            c = s[r]-65;
            ++count[c];
            if(count[c]==0){
                --m;
            }
            if (m==0){





if (count[c]-1<0){
                        if (r+1-l<mlen){
                            mlen = r+1-l;
                            ans=s.substr(l,mlen);
                        }
                        break;
                    }
                    count[c]-=1;
                    ++l;
                }
            }
        }
        return ans;
    }
};

普通数组

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分
解法：如果前面元素的和大于0,加上自己就可以变得更大，否则就扔掉，从自身再开始计算。

python中数值极限可以用float(“-inf”)和float(“inf”)表示,c++中用std::numeric_limits::min()和std::numeric_limits::max()获取，当然也可以手动计算:例如有符号整数int,位数一共为n=sieze0f(int)*CHAR_BIT(4字节32位),最大值就是2^(n-1)-1,最小值就是-2^(n-1),由于补码定义,负数比正数多一个-2^(n-1)

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        t=0
        ma=float("-inf")
        for i in nums:
            t=t+i
            if t>ma:
                ma=t
            if t<0:
                t=0
        return ma

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int t=0,ma=std::numeric_limits<int>::min(); 
        for(auto & num: nums){
            t+=num;
            if (t>ma){
                ma=t;
            }
            if (t<0){
                t=0;
            }
        }
        return ma;    
    }
};

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
解法：先根据区间左端点对intervals排序，然后根据区间右端点对intervals进行合并{return a<b }

C++中可以用 std::sort(v.begin(), v.end(), cmp) 排序，默认按 < 运算符排序，也可自定义 cmp 函数。
C++ 匿名函数可用 [](const int& a, const int& b) { return a < b; } 表示。

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        intervals.sort(key=lambda x:x[0])
        ans = []
        for i,j in intervals:
            if not ans or ans[-1][1] < i:
                ans.append([i,j])
            else:
                ans[-1][1]=max(ans[-1][1],j)
        return ans

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),[](vector<int> & a,vector<int> & b){return a[0]<b[0];});
        vector<vector<int>> ans;
        for (auto &interval : intervals){
            if (!ans.size() || ans.back()[1]<interval[0]){
                ans.push_back({interval});
            } 
            else {
                ans.back()[1]=max(ans.back()[1],interval[1]);
            }
        }
        return ans;
    }
};

189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
解法：
1.第i个元素轮转后位置为(i+k)/len(nums),额外存放一个数组赋值，再赋值回去
2.先将整个数组翻转，然后再将前 k 个元素翻转，再将后 n-k 个元素翻转，最后再将整个数组翻转。

对于python list,切片操作list[:]是原地对元素赋值会修改nums本身的内容、影响所有引用，而直接赋值列表会让 nums 指向新的列表对象、不影响旧的引用

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        n= len(nums)
        k = k % n  
        self.reverse(nums,0,n-1)
        self.reverse(nums,0,k-1)
        self.reverse(nums,k,n-1)
    def reverse(self,nums,start,end):
        while start<end:
            nums[start],nums[end]=nums[end],nums[start]
            start+=1
            end-=1

class Solution {
public:
   void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
   void reverse(vector<int>& nums, int start, int end){
         while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }
};

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

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

解法：
1.将左侧乘积和右侧乘积用两个数组进行统计，相乘输出数组即可，空间复杂度O(n)
2.进一步，直接使用输出数组先存储左侧乘积，再乘以右侧乘积得到答案，空间复杂度 O(1)

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        a = [0]*len(nums)
        b= [0]*len(nums)
        a[0]=nums[0]
        b[-1]=nums[-1]
        for i in range(1,len(nums)):
            a[i]=a[i-1]*nums[i]
        for i in range(len(nums)-2,-1,-1):
            b[i]=b[i+1]*nums[i]
        return [b[1]]+[a[i-1]*b[i+1] for i in range(1,len(nums)-1)]+[a[-2]]

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        ans[0]=nums[0];
        for (int i=1;i<n;++i){
            ans[i]=ans[i-1]*nums[i];
        }
        int r=1;
        for (int i=n-1;i>0;--i){
            ans[i]=ans[i-1]*r;
            r*=nums[i];
        }
        ans[0]=r;
        return ans;
    }
};

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
解法：由于空间复杂度只能为常数级别，因此不能使用额外空间，只能使用额外变量。对于一个长度为n的数组，缺失的最小正整数只能在[1,n+1]区间。
方法1：可以借助数组元素的正负记录对应索引代表的正整数是否出现过，出现的第一个正数对应的索引就是需要的结果，如果全部为负，则需要的结果为n+1。为了避免错配，将数组中不影响判断的负数和0置为n+1，用数组元素的绝对值记录原本的值，正负号记录某个正数是否出现过，如此空间复杂度就是常数级别。
方法2：将数组中在区间[1,n+1]的元素移动到索引值相等的位置.遍历数组，对于每一个位置i，交换num[i]和num[num[i]-1]直到num[i]==i+1.最后，第一个不满足条件num[i]=i+1的位置就是缺失的最小正整数，全部满足则是n+1。

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n=len(nums)
        for i in range(len(nums)):
            if nums[i] <1:
                nums[i]=n+1
        for i in range(len(nums)):
            a = abs(nums[i])
            if a<n+1:
                nums[a-1]=-abs(nums[a-1])
        for i in range(len(nums)):
            if nums[i]>0:
                return i+1
        return n+1

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

矩阵

73. 矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。
解法：遍历矩阵，记录元素为0的行和列，然后再遍历一次置为0.如果使用矩阵第一行和第一列进行记录，使用额外变量记录第一行或者第一列是否含0，则空间复杂度降为O(1).

python 二维列表只能对行切片而无法对列切片修改，切片赋值时是原地修改（等号左侧l[:]=…），引用切片（等号右侧…=l[:]）时返回副本。python对象在遍历时，可变对象可以直接修改，不可变对象只能通过索引修改;numpy则是通过[行,列]的方式进行修改,支持对行列进行切片修改,效率更高

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        m,n=len(matrix),len(matrix[0])
        temp = []
        for i in range(m):
            for j in range(n):
                if matrix[i][j]==0:
                    temp.append((i,j))
        for i, j in temp:
            matrix[i][:] = [0] * n       
            for row in matrix:
                row[j] = 0

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m=matrix.size(),n=matrix[0].size();
        vector<vector<int>> temp;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!matrix[i][j]) {
                    temp.push_back({i,j});
                }
            }
        }
        for (auto& v:temp) {
            for (int i = 0; i < m; ++i){
                matrix[i][v[1]]=0;
            }

            for (int i = 0; i < n; ++i){
                matrix[v[0]][i]=0;
            }
            
        }
    }
};

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。
解法：
1.模拟贪吃蛇，遇到边界就顺时针转向，同时将已经探索的节点标记为边界，空间复杂度O(mn)
2.从外层内缩、逐层遍历，每一层从左上角顺时针绕圈遍历，空间复杂度O(1)，推荐

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        ans = []
        left,right,top,bottom=0,len(matrix[0])-1,0,len(matrix)-1
        while left<=right and top <= bottom:
            for column in range(left,right+1):
                ans.append(matrix[top][column])
            for row in range(top+1,bottom+1):
                ans.append(matrix[row][right])
            if left < right and top < bottom: 
                for column in range(right-1,left,-1):
                    ans.append(matrix[bottom][column])
                for row in range(bottom,top,-1):
                    ans.append(matrix[row][left])
            top+=1
            bottom-=1
            left+=1
            right-=1
        return ans

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return {};
        }

        int rows = matrix.size(), columns = matrix[0].size();
        vector<int> order;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                order.push_back(matrix[top][column]);
            }
            for (int row = top + 1; row <= bottom; row++) {
                order.push_back(matrix[row][right]);
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    order.push_back(matrix[bottom][column]);
                }
                for (int row = bottom; row > top; row--) {
                    order.push_back(matrix[row][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }
};

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
解法：
1.每个元素直接相对中心旋转90度，临时变量存储覆盖掉的值,从左上角开始旋转，经过四次旋转，最终替换掉的值将回到左上角。只需遍历四分之一的区域，即可覆盖所有元素的旋转。技巧第i行j列的元素将旋转到倒数第i列(正数n-i-1列)第j行的位置即(i,j)->(j,n-i-1)，取左上角区域n/2 x (n+1)/2 .
2.每个元素直接相对中心旋转90度等效于上下翻转一次+沿着主对角线翻转一次，可推广至所有元素。

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        
        for i in range(n//2):
            for j in range(n):
                matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]
        
        for i in range(n):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n= matrix.size();
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {                                                                       
                
                
                
                
                
                int temp = 0,x=j,y=i;
                for (int k=0;k<5;++k){
                    swap(temp,matrix[y][x]);
                    swap(x,y);
                    x=n-x-1;
                }
            }
        }                                                                      
    }
};

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。
解法：从右上角开始，如果当前值大于taget,排除当前列向左移动；如果当前值小于target,排除当前行向下移动；如果当前值等于target,返回true。如果矩阵遍历完仍未找到，返回false。

class Solution(object):
    def searchMatrix(self,matrix, target):
        if not matrix or not matrix[0]:
                return False

        m, n = len(matrix), len(matrix[0])
        
        
        i, j = 0, n - 1
        
        while i < m and j >= 0:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                j -= 1  
            else:
                i += 1  
        return False

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int i = 0, j = n - 1;

        
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                --j;  
            } else {
                ++i;  
            }
        }

        return false;
    }
};

链表

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
解法：
1.先用哈希表存储A的所有结点，遍历B，如果B的某个结点在哈希表中，则说明存在相交节点，返回该结点。
2.双指针，假设链表长度为m和n.当A,B存在相交节点时，m=a+c,n=b+c，双指针同步走到a+c+b(b+c+a)时遇到相交节点；当A,B不存在相交节点时，双指针同步走到m+n(n+m)时遇到null。技巧：双指针走完一个链表移到另一个链表的头部。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        nodeSet = set()
        curA = headA
        while curA:
            nodeSet.add(curA)
            curA = curA.next
        curB = headB
        while curB:
            if curB in nodeSet:
                return curB
            curB = curB.next
        
        return None

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *pA = headA, *pB = headB;
        while (pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }
};

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
解法：
1.递归，head.next.next = head,head.next=None,即 head为头节点的链表翻转=head.next为头节点的链表翻转+head.next节点指向head
2.遍历，使用临时指针记录当前节点的前后两个节点,依次翻转

c++中.用于对象访问成员；->用于对象指针访问成员


class Solution(object):
    def reverseList(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next=None
        return new_head

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* current=head;
        ListNode* last=nullptr;
        ListNode* next=nullptr;
        while (current){
            next=current->next;
            current->next=last;
            last = current;
            current=next;
        }
        return last;
    }
};

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
回文链表是指正序（从左到右）和倒序（从右到左）读都是一样的链表。
解法：
1.递归，由于使用堆栈,递归函数会一直访问到最后一个节点然后开始逆序返回值。使用指针记录第一个节点，与递归的逆序节点比较，每一层递归指针指向下一个节点，最终可以比较完所有的节点。空间复杂度O(n)
2.双指针，将链表的后半部分反转,比较完成后修复链表。空间复杂度O(1)

在并发环境下，如果函数修改了传入的链表，函数运行时需要锁定其他线程或进程对链表的访问，并在修改后恢复链表

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: bool
        """
        
        n = 0
        current = head
        while current:
            n+=1
            current = current.next
        
        current = head
        last,next = None,None
        for i in range(0,n//2):
            next = current.next
            current.next=last
            last = current
            current=next
        
        if n%2:
            l,r=last,current.next
        else:
            l,r=last,current
        ans = True
        while l and r:
            if l.val != r.val:
                ans = False
                break
            l,r=l.next,r.next
        
        last,next = current,None
        current = last
        while current:
            next = current.next
            current.next = last
            last = current
            current = next
        return ans

class Solution {
    ListNode* lptr;
public:
    bool check(ListNode* node){
        if (node){
            if (!check(node->next)){
                return false;
            }
            if (lptr->val != node->val){
                return false;
            }
            lptr = lptr->next;
        }
        return true;
    }
    bool isPalindrome(ListNode* head) {
        lptr=head;
        return check(head);
    }
};

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。否则，返回 false 。
解法：
1.快慢指针，快指针每次移动两步，慢指针每次移动一步，如果存在环，则快指针会追上慢指针，否则不存在环。
2.哈希表，遍历链表，将每个节点存入哈希表，如果存在重复值，则存在环。

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        p = q = head
        while q and q.next:
            p = p.next
            q = q.next.next
            if p == q:
                return True
        return False

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next){
            slow=slow->next;
            fast=fast->next->next;
            if (fast == slow){
                return true;
            }
        }
        return false;
    }
};

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
解法：
1.快慢指针，快指针每次移动两步，慢指针每次移动一步，如果存在环，则快指针会追上慢指针，否则不存在环。假设头节点、入环点、相遇点之间的距离满足a+b+n(b+c)=2(a+b)=>a=c+(n-1)(b+c)即相遇点到入环点的距离等于链表头节点到入环点的距离。
2.哈希表，遍历链表，将每个节点存入哈希表，如果存在重复值，则存在环,返回重复值。

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        p = q = head
        while q and q.next:
            p = p.next
            q = q.next.next
            if p == q:
                q=head
                while q != p:
                    q=q.next
                    p = p.next
                return q
        return None

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast && fast->next){
            slow=slow->next;
            fast=fast->next->next;
            if (fast == slow){
                ListNode* ans = head;
                while (ans != slow){
                    ans=ans->next;
                    slow=slow->next;
                }
                return ans;
            }
        }
        return nullptr;
    }
};

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解法：
1.递归，merge(l1[i:],l2[j:])=min(l1[i],l2[j]) + merge(l1[i+1:],l2[j:])(假设l1[i] < l2[j])
2.双指针遍历,不断取出两个链表的最小值，将最小值放入新链表末尾节点的后面，返回头节点。

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        node1,node2=list1,list2
        current = ListNode()
        head = current
        while node1 and node2:
            if node1.val <= node2.val:
                temp = node1
                node1=node1.next
            else:
                temp = node2
                node2 = node2.next
            current.next=temp
            current=current.next
        if node1:
            current.next = node1
        if node2:
            current.next = node2
        return head.next

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1){
            return list2;
        }else if(!list2){
            return list1;
        }else if(list1->val < list2->val){
            list1->next=mergeTwoLists(list1->next,list2);
            return list1;
        }else {
            list2->next=mergeTwoLists(list2->next,list1);
            return list2;
        }
    }
};

2. 两数相加

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

注意：局部对象在函数结束时会销毁导致指针悬空，故返回的链表node需要new在堆上分配内存

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: Optional[ListNode]
        :type l2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        head,tail = None,None
        c=0
        while l1 or l2:
            n1 = l1.val if l1 else 0
            n2 = l2.val if l2 else 0
            sum = c+n1+n2
            c = sum//10
            if head:
                tail.next = ListNode(sum % 10)
                tail=tail.next
            else:
                head = ListNode(sum % 10)
                tail = head
            if l1:
                l1=l1.next
            if l2:
                l2=l2.next
        if c:
            tail.next = ListNode(c)
        return head

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = nullptr, *tail = nullptr;
        int carry = 0;
        while (l1 || l2) {
            int n1 = l1 ? l1->val: 0;
            int n2 = l2 ? l2->val: 0;
            int sum = n1 + n2 + carry;
            if (!head) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            carry = sum / 10;
            if (l1) {
                l1 = l1->next;
            }
            if (l2) {
                l2 = l2->next;
            }
        }
        if (carry > 0) {
            tail->next = new ListNode(carry);
        }
        return head;
    }
};

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
解法：快慢指针，快指针先走n+1步，然后快慢指针一起走，当快指针到达链表尾部时，慢指针指向倒数第n个结点的上一个节点，删除下一个节点即可

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: Optional[ListNode]
        :type n: int
        :rtype: Optional[ListNode]
        """
        fast = head
        target = head

        
        for _ in range(n + 1):
            if fast:
                fast = fast.next
            else:
                
                return head.next

        
        while fast:
            target = target.next
            fast = fast.next

        
        to_delete = target.next
        target.next = target.next.next
        del to_delete  

        return head

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast=head;
        ListNode* target=head;
        for (int i=0;i<n+1;++i){
            if(fast){
                fast=fast->next;
            }else{
                return head->next;
            }
        }
        while (fast){
            target=target->next;
            fast=fast->next;
        }
        fast = target->next;
        target->next=target->next->next;
        delete fast;
        return head;

    }
};

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
解法：
1.递归，交换链表头节点和链表的第二个节点，后面的节点交换递归实现即swap[i:]=[i+1,i]+swap[i+2:]
2.迭代，每两个节点i1,i2交换，并记录上一个节点i1.last和下一个节点i2.next的位置方便下一轮两个节点的交换，直到遇到空指针。

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if not head or not head.next:
            return head
        new_head = head.next
        head.next=self.swapPairs(head.next.next)
        new_head.next=head
        return new_head

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next){
            return head;
        }
        ListNode* dump = new ListNode(0,head);
        ListNode* last = dump;
        ListNode* second=head->next;
        ListNode* first=head;
        ListNode* next;
        while (second){
            next = second->next;
            last->next=second;
            second->next = first;
            first->next = next;
            last = first;

            first=next;
            if(next){
                second=next->next;  
            }else{
                second=nullptr;
            }
        }
        return dump->next;
    }
};

25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
解法：
1.递归，reverseKGroup List[:] = reverseKGroup List[:k] + reverseKGroup List[k:],每次递归先检查节点数量是否小于k,然后翻转前k个节点，调用递归翻转后面的节点，注意将链表的头尾对齐。
2.迭代,每k个节点组成一个子链表，翻转子链表，并将翻转后的子链表连接到原链表的后面。

class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: Optional[ListNode]
        :type k: int
        :rtype: Optional[ListNode]
        """
        n=0
        temp=head
        while temp:
            n+=1
            temp=temp.next
            if n==k:
                break
        if n<k:
            return head
        current =head
        last,next=None,None
        for i in range(k):
            next=current.next
            current.next =last
            last = current
            current = next
        head.next=self.reverseKGroup(current,k)
        return last

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* current=head;
        ListNode* last=nullptr;
        ListNode* next=nullptr;
        ListNode* ans=nullptr;
        ListNode* start;
        ListNode* end;
        while (current){
            for(int i=0;i<k;++i){
                if (!current){
                    return ans;
                }
                if (i==0){
                    start=current;
                }
                if (i==k-1){
                    end=current;
                }
                current=current->next;
            }
            if(!ans){
                ans=end;
            }else{
                last->next = end;
            }
            ListNode* temp=start;
            while (temp!=current){
                next = temp->next;
                temp->next = last;
                last=temp;
                temp=next;
            }
            start->next = current;
            last = start;
        }
        return ans;
    }
};

138. 随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码只接受原链表的头节点 head 作为传入参数。
解法：
1.哈希表存储新节点，所有节点创建后，遍历head,修改对应的next和random
2.哈希表存储新节点，每个节点的next和random节点通过递归来求得

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
        mp ={}
        p = head
        while p:
            mp[p]=Node(p.val)
            p = p.next
        p = head
        while p:
            if p.next:
                mp[p].next=mp[p.next]
            if p.random:
                mp[p].random=mp[p.random]
            p = p.next
        return mp[head]

class Solution {
public:
    unordered_map<Node*,Node*> cachedNode;
    Node* copyRandomList(Node* head) {
       if (head == nullptr){
        return nullptr;
       }
       if (!cachedNode.count(head)){
        Node* new_node =new Node(head->val);
        cachedNode[head] = new_node;
        new_node->next = copyRandomList(head->next);
        new_node->random = copyRandomList(head->random);
       }
       return cachedNode[head];
    }
};

148. 排序链表

给你链表的头结点 head ，请将其按升序排列并返回排序后的链表
解法：
1.归并排序，快慢指针找中间节点,子链表递归求排序，然后合并排序后的两部分链表。
2.归并排序，但不使用递归而是迭代替换，依次按照k=1,2,4,8,…(k<链表长度)进行子链表的划分、排序、合并，而不是二分法递归的求法，可以将空间复杂度降至O(1)

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        k =1
        n = 0
        h=head
        while h:
            n+=1
            h = h.next
        res = ListNode(0)
        res.next = head
        while k < n:
            pre,current=res,res.next
            while current:
                h1,i= current,k
                while i and current:
                    current = current.next
                    i -=1
                if i:
                    break
                h2,i= current,k
                while current and i:
                    i-=1
                    current = current.next
                k1,k2=k,k-i
                while k1 or k2:
                    if k1==0:
                        pre.next = h2
                        k2-=1
                        h2 = h2.next
                    elif k2==0:
                        pre.next = h1
                        k1-=1
                        h1=h1.next
                    elif h1.val<h2.val:
                        pre.next = h1
                        k1-=1
                        h1=h1.next
                    else:
                        pre.next = h2
                        k2-=1
                        h2 = h2.next
                    pre = pre.next
                pre.next = current
            k*=2
        return res.next

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next){
            return head;
        }
        ListNode* slow= new ListNode(0,head);
        ListNode* fast = head;
        while(fast){
            fast = fast->next;
            if (fast){
                fast = fast->next;
            }
            slow = slow->next;
        }
        fast = slow->next;
        slow->next = nullptr;
        return merge(sortList(head),sortList(fast));         
    }
    ListNode* merge(ListNode* h1,ListNode* h2){
        ListNode* ans = new ListNode();
        ListNode* res = ans;
        while(h1 && h2){
            if (h1->val < h2->val){
                res->next = h1;
                h1 = h1->next;
            } else{
                res->next = h2;
                h2 = h2->next;
            }
            res= res->next;
        }
        res->next = h1?h1:h2;
        return ans->next;
    }
};

23. 合并 K 个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

解法：
1.迭代,两两合并链表，但需要注意和148. 排序链表的区别，148合并的是二分后的链表，数量最多相差一，这里则不一定，需要单独处理。
2.优先队列，每次取最小的节点，然后将该节点的下一个节点加入优先队列，直到优先队列为空

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[Optional[ListNode]]
        :rtype: Optional[ListNode]
        """
        heap = []
        for i in lists:
            if i:
                heapq.heappush(heap,(i.val,i))
        dummy = ListNode()
        ans = dummy
        while heap:
            f = heapq.heappop(heap)
            ans.next = f[1]
            ans = ans.next
            if f[1].next:
                heapq.heappush(heap,(f[1].next.val,f[1].next))
        return dummy.next

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* ans = nullptr;
        for (auto head : lists){
            ans = merge(head,ans);
        }
        return ans;   
    }
    ListNode* merge(ListNode* h1,ListNode* h2){
        ListNode* ans = new ListNode();
        ListNode* res = ans;
        while(h1 && h2){
            if (h1->val < h2->val){
                res->next = h1;
                h1 = h1->next;
            } else{
                res->next = h2;
                h2 = h2->next;
            }
            res= res->next;
        }
        while (h1){
            res->next = h1;
            h1 = h1->next;
            res= res->next;
        }
        while (h2){
            res->next = h2;
            h2 = h2->next;
            res= res->next;
        }
        return ans->next;
    }
};

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) 的平均时间复杂度运行。
解法：使用双向链表和哈希表构建有序字典，哈希表用于快速查找节点，双向链表用于快速删除节点。

注意c++语法，当成员变量和局部变量choose同名时，需要加上this->，否则会导致局部变量隐藏成员变量，赋值无效,引发编译器无法发现的逻辑错误。成员变量更推荐在初始化列表中初始化(否则多了一次无用构造，要明确初始化和赋值的区别)，避免出现未定义行为。总之：
1.遇到 const、引用、无默认构造 ➔ 必须初始化列表。
2.普通变量 ➔ 也推荐初始化列表，既简洁又高效。
例如c++代码的capacity变量，我在这里找了半天why结果不对，原来是因为我忘记加this->了，当然更推荐在初始化列表中初始化。

class LRUCache:

    def __init__(self, capacity: int):
        self.data = OrderedDict()
        self.capacity = capacity
    def get(self, key: int) -> int:
        if key in self.data:
            self.data.move_to_end(key)
            return self.data[key]
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        if  len(self.data) == self.capacity:
            self.data.popitem(last=False)

struct Node{
    int key,value;
    Node* prev;
    Node* next;
    Node():key(0),value(0),prev(nullptr),next(nullptr){}
    Node(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int,Node*> cache;
    Node* head;
    Node* tail;
    int size;
    int capacity;
public:
    LRUCache(int capacity) {
       size =0;
       this->capacity= capacity;
       head = new Node();
       tail = new Node();
       head->next=tail;
       tail->prev=head;
    }
    
    int get(int key) {
        if (!cache.count(key)){
            return -1;
        }
        Node* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (cache.count(key)){
            Node* node = cache[key];
            node->value = value;
            moveToHead(node);
        }else{
            Node* node = new Node(key,value);
            cache[key] = node;
            append(node);
            ++size;
            if (size >capacity){
                Node* removed = removeTail();
                cache.erase(removed->key);
                delete removed;
                --size;
            }

        }
    }

    void moveToHead(Node* node){
        removeNode(node);
        append(node);
    }
    void append(Node* node){
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    Node* removeTail(){
        Node* node = tail->prev;
        removeNode(node);  
        return node;
    }
};

二叉树

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的中序遍历。
解法：(根据根节点的位置可以分为根左右、左根右、左右根三种情况，分别对应前序、中序、后序遍历，返回相应节点value列表)
1.递归
2.栈迭代,记录节点是否访问，遇到未访问的节点按照相反的顺序将右节点、自身、左节点(根据前序、中序、后序的要求调整相应顺序)压入栈，遇到已访问的节点弹出栈，加入结果。
3.还有一个空间复杂度为O(1)的Morris遍历算法暂时没学会。

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        return self.inorderTraversal(root.left)+[root.val]+self.inorderTraversal(root.right)

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
    bool visited= false;
    vector<int> res;
    vector<pair<int, TreeNode*>> stack={};
    stack.push_back({false,root});
    while (! stack.empty()){
        visited= stack.back().first;
        TreeNode* node = stack.back().second;
        stack.pop_back();
        if (!node){continue;}
        if (!visited){
            stack.push_back({false,node->right});
            stack.push_back({true,node});
            stack.push_back({false,node->left});
        }else{
            res.push_back(node->val);
        }
    } 
    return  res;   
    }
};

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
解法：
1.双端队列，广度优先遍历，一层一层遍历，记录深度，空间复杂度取决队列的元素数量
2.递归，深度优先遍历，记录最大深度，空间复杂度为树的高度

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        queue = deque()
        queue.append(root)
        ans = 0
        while queue:
            sz = len(queue)
            while sz:
                node = queue.popleft()
                if node.left : queue.append(node.left)
                if node.right : queue.append(node.right)
                sz-=1
            ans+=1
        return ans

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

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
解法：
1.递归，深度优先搜索，翻转翻转后的左右子树，字数的翻转用递归
2.队列，广度优先搜索，从根节点开始，交换子节点，将子节点加入队列，一层层交换

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        temp = root.left
        root.left = self.invertTree(root.right)
        root.right = self.invertTree(temp)
        return root

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root){return nullptr;}
        queue<TreeNode*> Q;
        Q.push(root);
        while (Q.size()){
            TreeNode* tm = Q.front();Q.pop();
            TreeNode* temp = tm->left;
            tm->left = tm->right;
            tm->right = temp;
            if (tm->left){
                Q.push(tm->left);
            }
            if (tm->right){
                Q.push(tm->right);
            }
        }
        return root;
    }
};

101. 对称二叉树

给你一个二叉树的根节点 root ，检查它是否轴对称。
解法：
1.使用双端队列，广度优先搜索，将节点加入队列，同时将其左右子节点加入队列，一层一层遍历，如果队列的头节点的左右子节点不一致，则不是对称树。
2.使用递归，判断左右子节点的值是否对称。再递归判断左右节点代表的子树是否对称。对称条件：左子树的左节点与右子树的右节点对称，且左子树的右节点与右子树的左节点对称。

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        temp = deque()
        temp.append(root.left)
        temp.append(root.right)
        while temp:
            next_temp = deque()
            sz = len(temp)
            while sz:
                l = temp.popleft()
                r = temp.pop()
                n1 = l.val if l else None
                n2 = r.val if r else None 
                if n1 != n2:
                    return False
                sz-=2
                if l:
                    next_temp.appendleft(l.right)
                    next_temp.appendleft(l.left)
                if r:
                    next_temp.append(r.left)
                    next_temp.append(r.right)
            temp = next_temp
        return True

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

543. 二叉树的直径

给你一棵二叉树的根节点，返回该树的直径。
二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的长度由它们之间边数表示。
解法：递归，对于任意一个节点，经过该节点的最大长度等于左右子节点的最大深度的和，所以可以在递归求根节点深度的时候更新最大直径。

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.ans = 1
        def depth(node):
            
            if not node:
                return 0
            
            L = depth(node.left)
            
            R = depth(node.right)
            
            self.ans = max(self.ans, L + R + 1)
            
            return max(L, R) + 1

        depth(root)
        return self.ans - 1

class Solution {
public:
    int ans;
    int diameterOfBinaryTree(TreeNode* root) {
        ans  =0;
        depth(root);
        return ans;
    }
    int depth(TreeNode* node){
        if (!node){
            return 0;
        }
        int l = depth(node->left);
        int r = depth(node->right);
        ans = max(ans,l+r);
        return max(l,r)+1;
    }
};

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。
解法：队列，广度优先搜索，将根节点加入队列，同时将其左右子节点加入队列，一层一层遍历，加入结果。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if (!root){
            return {};
        }
        deque<TreeNode*> q;
        q.push_back(root);
        vector<vector<int>> ans;
        while (!q.empty()){
            vector<int> temp;
            int sz = q.size();
            while (sz){
                TreeNode* node = q.front();
                q.pop_front();
                temp.push_back(node->val);
                if (node->left){
                    q.push_back(node->left);
                }
                if (node->right){
                    q.push_back(node->right);
                }
                sz-=1;
            }
            ans.push_back(temp);
        }
        return ans;
    }
};

108. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。
解法：平衡二叉树指每个节点的左右子树的高度差的绝对值不超过 1 ,可以选取中间节点为root，递归构建左右子树

c++切片vector的方法为vector new_vector(nums.begin()+start,nums.begin()+start+length) 左闭右开，拷贝区间 [begin, end) ，但更推荐传递索引下标，避免额外的复制

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        mid = (len(nums)-1)//2
        head = TreeNode(nums[mid])
        head.left = self.sortedArrayToBST(nums[:mid])
        head.right = self.sortedArrayToBST(nums[mid+1:])
        return head

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedArrayToBST(nums,0,nums.size()-1);
    }
    TreeNode* sortedArrayToBST(vector<int>& nums,int left,int right) {
        if (left>right){
            return nullptr;
        }
        int mid=(left+right)/2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = sortedArrayToBST(nums,left,mid-1);
        root->right = sortedArrayToBST(nums,mid+1,right);
        return root;
    }
};

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
解法：
1.递归，过程中需额外传入当前的最大值和最小值，判断当前节点的值是否在范围内，左右子树是否为二叉搜索树
2.迭代，中序遍历，判断后一个节点值是否大于前一个。

1.有关无穷小和无穷大，c++中可以用numeric_limits::min()和numeric_limits::max()来获取最小值和最大值,python中可以用float(‘-inf’)和float(‘inf’)来获取最小值和最大值，此外当输入是int类型时，无穷大、小最好用LONG_MIN/LONG_Max、INFINITY表示。上述宏和方法需要包含头文件limits、climits或cmath
2.主要栈和队列的区别，前者后进先出，后者先进先出，前者方法有push(x)\pop()\top() ,后者方法有push(x)\pop()\front(),双端队列则有push_front(x)\pop_front()\push_back(x)\pop_back(),vector则有push_back(x)\pop_back().双端队列和vector可以用来实现栈。

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root){
            return true;
        }
        deque<pair<bool,TreeNode*>> stack;
        stack.push_front({false,root});
        bool visited = false;
        long int last_val = numeric_limits<long int>::min();
        while (!stack.empty()){
            pair<bool,TreeNode*> temp = stack.front();stack.pop_front();
            visited=temp.first;
            TreeNode* node =temp.second;
            if (visited){
                if(node->val<=last_val)return false;
                last_val=node->val;
            }else{
                if(node->right)stack.push_front({false,node->right});
                stack.push_front({true,node});
                if(node->left)stack.push_front({false,node->left});
            }
        }
        return true;
    }
};

230. 二叉搜索树中第 K 小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
解法：中序遍历，遇到第k个节点，返回其值。

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<TreeNode*> stack;
        while (!stack.empty() or root){
            while (root){
                stack.push_back(root);
                root=root->left;
            }
            root = stack.back();stack.pop_back();
            --k;
            if (k==0)return root->val;
            root = root->right;
        }
        return 0;
    }
};

199. 二叉树的右视图

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
解法：
1.广度优先遍历，保存每一层最右边的元素即可
2.深度优先，利用栈优先遍历最右边的节点，利用栈更新和记录当前节点的深度,同一深度第一个出现的点就是最右边的点。

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        layer = [root]
        ans = []
        while layer:
            ans.append(layer[-1].val)
            temp = []
            for node in layer:
                if node.left:
                    temp.append(node.left)
                if node.right:
                    temp.append(node.right)
            layer=temp
        return ans

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        unordered_map<int,TreeNode*> mp;
        vector<TreeNode* > stack;
        int max_depth =-1;
        int depth=-1;
        vector<int> depth_stack;
        while (!stack.empty() || root){
            while(root){
                ++ depth;
                depth_stack.push_back(depth);
                if (!mp.count(depth))mp[depth]=root;
                stack.push_back(root);
                root = root->right;
            }
            max_depth= max(max_depth,depth);
            root = stack.back();stack.pop_back();
            depth=depth_stack.back();depth_stack.pop_back();
            root=root->left;
        }
        vector<int> ans;
        for (int i=0;i<=max_depth;++i){
            ans.push_back(mp[i]->val);
        }
        return ans;
    }
};

114. 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同。
解法：先序遍历，拼接即可,注意节点加入堆栈的顺序和先序遍历的顺序相反。

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root)return;
        TreeNode dummy=TreeNode(),*res = &dummy;
        vector<pair<bool,TreeNode*>> stack;
        stack.push_back({false,root});
        while (!stack.empty()){
            auto p = stack.back();stack.pop_back();
            TreeNode* node=p.second;
            bool visited = p.first;
            if (visited){
                res->right=node;
                res = res->right;
                res->left=nullptr;
            }else{
                if(node->right)stack.push_back({false,node->right});
                if(node->left)stack.push_back({false,node->left});
                stack.push_back({true,node});
            }
        }
        root=res->right;
    }
};

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

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
解法：preorder的第一个节点为根节点，利用哈希表在inorder中找到根节点的位置划分左右子树，然后根据左右子树的长度把preorder的左右子树也划分出来，再递归求解。终止条件：当传入的数组，左节点索引大于右节点时，返回nullptr。

class Solution {
public:
    unordered_map<int,int> hashtable; 
    TreeNode* build(const vector<int>&preorder,const vector<int>& inorder,int pre_left,int pre_right,int in_left,int in_right){
        if(in_left>in_right){return nullptr;}
        int root_value=preorder[pre_left];
        int root_index_in_inorder=hashtable[root_value]; 
        int left_tree_counts=root_index_in_inorder-in_left;
        TreeNode* root=new TreeNode(root_value);
        root->left=build(preorder,inorder,pre_left+1,pre_left+left_tree_counts,in_left,root_index_in_inorder-1);
        root->right=build(preorder,inorder,pre_left+left_tree_counts+1,pre_right,root_index_in_inorder+1,in_right);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int num=preorder.size();
        for(int i=0;i<num;i++){
            hashtable[inorder[i]]=i;
        }
        return build(preorder,inorder,0,num-1,0,num-1);
    }
};

437. 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
解法：深度优先搜索，递归求解，对于每个节点，递归求解其左右子树的路径总和，并累加到当前节点的路径总和，如果等于targetSum，则路径数目加1。注意退出递归时，要将当前的current_sum还原即全局变量统计的current_sum次数-=1。其次,统计符合目标的次数时要在current_sum统计进字典之前进行，避免target=0时将空路径也算作符合条件的路径。

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        pre_sum={0:1}
        
        def helper(root,current_sum):
            if not root:
                return 0
            ans=0
            current_sum+=root.val
            ans+=pre_sum.get(current_sum-targetSum,0)
            if current_sum in pre_sum:
                pre_sum[current_sum]+=1
            else:
                pre_sum[current_sum]=1
            ans+=helper(root.left,current_sum)
            ans+=helper(root.right,current_sum)
            pre_sum[current_sum]-=1
            return ans
        return helper(root,0)

class Solution {
public:
    unordered_map<long long, int> prefix;

    int dfs(TreeNode *root, long long curr, int targetSum) {
        if (!root) {
            return 0;
        }

        int ret = 0;
        curr += root->val;
        if (prefix.count(curr - targetSum)) {
            ret = prefix[curr - targetSum];
        }

        prefix[curr]++;
        ret += dfs(root->left, curr, targetSum);
        ret += dfs(root->right, curr, targetSum);
        prefix[curr]--;

        return ret;
    }

    int pathSum(TreeNode* root, int targetSum) {
        prefix[0] = 1;
        return dfs(root, 0, targetSum);
    }
};

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

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
解法：
1.遍历每一个节点下的子树是否包含p,q,返回最深的节点,但这样会造成大量重复搜索
2.递归：p,q在当前root的两侧或者一侧。当两侧子树分别包含p和q时，当前节点为最近公共祖先。当一侧确定不包含p和q时即没有公共祖先,另一侧必定包含p和q,递归遍历找这一侧的最近公共祖先。

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if not root or root==p or root==q:
            return root
        left = self.lowestCommonAncestor(root.left,p,q)
        right=self.lowestCommonAncestor(root.right,p,q)
        if left and right :return root
        if left:return left
        if right:return right

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(contain(root->left,p,q)) return lowestCommonAncestor(root->left,p,q);
        if(contain(root->right,p,q)) return lowestCommonAncestor(root->right,p,q);
        return root;
    }
    bool contain(TreeNode* root, TreeNode* p, TreeNode* q){
        vector<TreeNode*> stack;
        bool pflag=false,qflag=false;
        while (root || !stack.empty()){
            while(root){
                if(root == p)pflag=true;
                if(root==q)qflag=true;
                if(pflag && qflag) return true;
                stack.push_back(root);
                root=root->left;
            }
            root=stack.back();stack.pop_back();
            root=root->right;
        }
        return false;
    }
};

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

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。
路径和是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其最大路径和。
解法：深度优先遍历DFS，对于每个节点，包含该节点在内的最大路径序列必然由包含左子节点在内的最大路径单分支、当前节点、包含右子节点在内的最大路径单分支三部分组成。求最大路径单分支的过程可以用递归来求，递归过程中更新最大值。

class Solution:
    maxSum=float('-inf')
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        Solution.maxSum=float('-inf')
        Solution.dfs_max(root)
        return Solution.maxSum
    def dfs_max(node):
        """
        求包含当前节点在内的最大路径和,不向上联络
        """
        if not node:
            return 0
        left_max = max(0,Solution.dfs_max(node.left))
        right_max = max(0,Solution.dfs_max(node.right))
        Solution.maxSum=max(Solution.maxSum,left_max+node.val+right_max)
        ans = node.val+max(left_max,right_max)
        return ans

class Solution {
public:
    int max_sum = INT_MIN;
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return max_sum;
    }
    int dfs(TreeNode* node){
        if (!node) return 0;
        int left_max = max(0,dfs(node->left));
        int right_max = max(0,dfs(node->right));
        max_sum = max(max_sum,left_max+node->val+right_max);
        return node->val+max(left_max,right_max);
    }
};

图论

200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
解法：双循环行列遍历，如果遇到’1’则岛屿数量+1，然后使用BFS或者DFS将相连的’1’标记为’-'表示为已访问。

注意：在标记地图时，要注意使用的变量类型，在c++中，标记格子的’1’是单字符，如果标记为’-1’，在比较时’1’=='-1’会引发意外的错误或行为。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        ans=0
        m,n=len(grid),len(grid[0])
        for y in range(m):
            for x in range(n):
                if grid[y][x]=='1':
                    ans+=1
                    self.bfs(grid,m,n,x,y)
        return ans
    def bfs(self,grid,m,n,x,y):
        q=deque()
        q.append((x,y))
        while q:
            x,y=q.popleft()
            if grid[y][x]!='1':continue
            grid[y][x]='-'
            if x>0:
                q.append((x-1,y))
            if x<n-1:
                q.append((x+1,y))
            if y>0:
                q.append((x,y-1))
            if y<m-1:
                q.append((x,y+1))

class Solution {
    int m;
    int n;
public:
    int numIslands(vector<vector<char>>& grid) {
        m=grid.size();
        n=grid[0].size();
        int ans=0;
        for(int y=0;y<m;++y){
            for (int x=0;x<n;++x){
                if (grid[y][x]=='1'){
                    ++ans;
                    dfs(grid,y,x);
                }
            }
        }
        return ans; 
    }
    void dfs(vector<vector<char>>& grid,int y,int x){
        if (grid[y][x] != '1'){return;}
        grid[y][x]='-';
        if(y+1<m)dfs(grid,y+1,x);
        if(y>0)dfs(grid,y-1,x);
        if(x+1<n)dfs(grid,y,x+1);
        if(x>0)dfs(grid,y,x-1);
    }
};

994. 腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

解法：统计所有的新鲜橘子，每过一分钟，当周围有否烂橘子时,标记自己为烂橘子，并更新新鲜橘子列表。直到没有新鲜橘子为止，返回分钟数。如果没有要移除的烂橘子，说明无法在腐烂下去，返回-1。

class Solution {
    int m;
    int n;
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int t=0;
        set<pair<int,int>> oranges;
        m=grid.size();
        n=grid[0].size();
        for(int y=0;y<m;++y){
            for (int x=0;x<n;++x){
                if (grid[y][x]==1){
                    oranges.insert({y,x});
                }
            }
        }
        vector<set<pair<int,int>>::iterator> To_remove_oranges;
        while (!oranges.empty()){
            To_remove_oranges.clear();
            for(auto it=oranges.begin();it!=oranges.end();++it){
                int y=it->first;
                int x=it->second;
                if (helper(grid,y,x)){
                    To_remove_oranges.push_back(it);
                }
            }
            if(To_remove_oranges.empty()){
                break;
            }
            else{
                for(auto p :To_remove_oranges){
                    int y=p->first;
                    int x=p->second;
                    oranges.erase(p);
                    grid[y][x]=2;
                }
            }
            t+=1;
        }
        return oranges.empty()?t:-1;
    }
    bool helper(vector<vector<int>>& grid,int y,int x){
        if(y>0 && grid[y-1][x]==2) return true;
        if(x>0 && grid[y][x-1]==2) return true;
        if(x<n-1 && grid[y][x+1]==2) return true;
        if(y<m-1 && grid[y+1][x]==2) return true;
        return false;
    }
};

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则必须先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
解法：先修课程指向后修课程,结合图论节点入度的概念可知，只能先修入度为0的课程，然后才能修后续课程，修完一门课程，将后续课程的入度减1，直到所有课程都修完。此时如果仍然存在入度不为0的课程，说明有环路，返回false。

class Solution {
    vector<int> degree;
    vector<vector<int>> edges;
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        degree.resize(numCourses);
        for(auto& v:prerequisites){
            edges[v[1]].push_back(v[0]);
            degree[v[0]]+=1;
        }
        queue<int> q;
        for (int i=0;i<numCourses;++i){
            if(degree[i]==0){
                q.push(i);
            }
        }
        int count=0;
        while(!q.empty()){
            ++count;
            int u=q.front();q.pop();
            for (int v :edges[u]){
                --degree[v];
                if (degree[v]==0){
                    q.push(v);
                }
            }
        }
        return count==numCourses;
    }
};

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 。
解法：将字符串拆分，依次从根节点指向后续的节点来代表这个字符串，末尾使用一个特殊的字符表示字符串的结束。检索时,遍历对比，发现不存在的则返回faslse,根据是否包含特殊字符来判断是否是word本身还是word的前缀

注意：在c++中，定义嵌套自身类型的结构体需要使用指针,如struct NestedMap,而python则不需要

class Trie:

    def __init__(self):
       self.words={}
    def insert(self, word: str) -> None:
        words = self.words
        for c in word:
            if c not in words:
                words[c]={}
            words = words[c]
        words['']=None

    def search(self, word: str) -> bool:
        words =self.words
        for c in word:
            if c not in words:
                return False
            words=words[c]
        return True if '' in words else False
        

    def startsWith(self, prefix: str) -> bool:
        words =self.words
        for c in prefix:
            if c not in words:
                return False
            words=words[c]
        return True


struct NestedMap {
    unordered_map<char, NestedMap*> children;  
};
class Trie {
    NestedMap words;
public:
    Trie() {
        
    }
    
    void insert(string word) {
        NestedMap* current = &words;
        for (auto& c :word){
            if (!current->children.count(c)){
                current->children[c]=new NestedMap();
            }
            current=current->children[c];
        }
        current->children['\0']=nullptr;
        
    }
    
    bool search(string word) {
        NestedMap* current = &words;
        for (auto& c :word){
            if (current->children.count(c)){
                current=current->children[c];
            }else{
                return false;
            }
        }
        if (current->children.count('\0')) return true;
        return false;
        
    }
    
    bool startsWith(string prefix) {
        NestedMap* current = &words;
        for (auto& c :prefix){
            if (current->children.count(c)){
                current=current->children[c];
            }else{
                return false;
            }
        }
        return true;
    }
};

回溯

46. 全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案
解法：回溯法，对于第n个位置,在for循环中填入不同的数，对第n+1个位置的数采用递归填入，然后撤销填入的数跳到下一种情况。如果n=nums.size(),说明填满了，记录该种排列

回溯法的模板就是递归中循环遍历不同的情况，在遍历中递归后续的部分，然后撤销当前的选择，回到下一个情况继续遍历。每一次在循环前判断是否终止和记录需要的结果

class Solution {
    vector<int>* nums;
    int nums_size=0;
    vector<vector<int>> res;
public:
    vector<vector<int>> permute(vector<int>& nums) {
        this->nums=&nums;
        nums_size=nums.size();
        backtrack(0);
        return res;
        
    }
    void backtrack(int index){
        if (index==nums_size){
            res.push_back(*nums);
            return;
        }
        for (int i=index;i<nums_size;++i){
            swap((*nums)[i],(*nums)[index]);
            backtrack(index+1);
            swap((*nums)[index],(*nums)[i]); 
        }

    }
};

78. 子集

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按任意顺序返回解集。
解法：回溯法，但和全排列不同，使用一个数组记录当前的子集，为了避免重复，循环中递归输入的参数由index改为i,即下一次递归填入数组的数一定是i后面的数而不是index后面的数。

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

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
解法：
1.首选算出组合的数量n,假设数字i1对应的字母数量为k1,则对于i1中每一个字母后续都有n//k1种选择,依此可以知道每种组合第一个位置该填哪个字母。依次类推,对于i2中每一个字母后续都有n//k1//k2种选择,依此可以知道每种组合第二个位置该填哪个字母。。。直到填完所有组合。
2.递归回溯,使用临时字符串记录当前的组合，并判断是否完整。如果完整则加入结果集。循环中遍历数字index对应的字母的，在临时字符串加入当前字母，然后递归index+1的情况,递归结束时要撤销临时字符串加入的字母
3.队列,将第一个数字对应的所有字母入队，然后弹出队列中所有字串，就将其与后续数字对应的每一个字母组合后再次

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == '':
            return []
        phoneMap = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
        }

        n = len(digits)
        k = 1
        for i in digits:
            k *= len(phoneMap[i])

        out = ['' for _ in range(k)]

        temp = k
        for i in range(n):
            idx = 0
            temp = temp // len(phoneMap[digits[i]])
            while idx < k:
                for s in phoneMap[digits[i]]:
                    for _ in range(temp):
                        out[idx] += s
                        idx += 1
        return out

class Solution {
    vector<string> combinations;
    unordered_map<char, string> phoneMap{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };

public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()){
            return combinations;
        }
        string comb_temp;
        backtrack(digits,comb_temp,0);
        return combinations;
    }
    void backtrack(string& digits,string& comb_temp,int index){
        if (index==digits.length()){
            combinations.push_back(comb_temp);
            return;
        }
        const string& letters = phoneMap[digits[index]];
        for (const char& letter:letters){
            comb_temp.push_back(letter);
            backtrack(digits,comb_temp,index+1);
            comb_temp.pop_back();
        }
    }
};

class Solution {
    vector<string> combinations;
    unordered_map<char, string> phoneMap{
            {'2', "abc"},
            {'3', "def"},
            {'4', "ghi"},
            {'5', "jkl"},
            {'6', "mno"},
            {'7', "pqrs"},
            {'8', "tuv"},
            {'9', "wxyz"}
        };

public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()){
            return combinations;
        }
        queue<string> q;
        q.push("");
        for(auto& ch:digits){
            int size = q.size();
            for(int i=0;i<size;++i){
                string temp=q.front();q.pop();
                for (auto& c:phoneMap[ch]){
                    q.push(temp+c);
                }
            }
        }
        while (!q.empty()){
            combinations.push_back(q.front());
            q.pop();
        }
        return combinations;
    }
};

39. 组合总和

给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。
解法：回溯法，每填入一个元素i,由于可以重复选取且组合无视顺序，所以递归依然填入i,同时做减法更新target,同时维护好选取元素的临时数组.终止条件：由于题目保证都是正整数，故target<=0时，返回.

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

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
解法：回溯法，递归填入第index个括号，循环中填入左括号或右括号。终止条件：右括号数量大于左括号数量或者index==n,当右括号数量等于n时，将当前结果加入结果集。

class Solution {
    char c[2]={'(',')'};
    vector<string> ans;
public:
    vector<string> generateParenthesis(int n) {
        string temp;
        backtrack(0,n,0,0,temp);
        return ans;
    }
    void backtrack(int index,int n,int left_count,int right_count,string &temp){
        if(right_count>left_count)return;
        if(index==2*n){
            if(right_count==n){ans.push_back(temp);}
            return;
        }
        for (int i=0;i<2;++i){
            temp.push_back(c[i]);
            if (i==0){
                backtrack(index+1,n,left_count+1,right_count,temp);
            }else{
                backtrack(index+1,n,left_count,right_count+1,temp);
            }
            temp.pop_back();
        }
    }
};

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
解法：回溯法，递归填入第index个字符，向四周搜索是否有满足条件的字符,并标记已经访问过的位置。终止条件：board[i][j]!=word[index]或者index+1==word.size()

注意：这里使用unordered_set来记录已经访问过的位置并没有标记board[i][j]再还原的效率高,大量的插入和删除操作会导致效率低下，容易超时










class Solution {
private:
    vector<vector<int>> di = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1}
    };
    bool isExist = false;
    int m, n;
    
public:
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word[0]) {
                    backtrack(board, 0, word, i, j);
                    if (isExist) return true;
                }
            }
        }
        return false;
    }

    void backtrack(vector<vector<char>>& board, int index, string& word, int i, int j) {
        
        if (board[i][j] != word[index])return;
        if (index + 1 == word.length()) {
            isExist = true;
        } else {
            auto board_val = board[i][j];
            board[i][j] = '0';
            
            for (int d = 0; d < 4; d++) {
                int newi = i + di[d][0];
                int newj = j + di[d][1];
                if (newi >= 0 && newi < m && newj >= 0 && newj < n) {
                    backtrack(board, index + 1, word, newi, newj);
                }
            }
            board[i][j] = board_val;
            
        }
    }
};

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
解法：使用动态规划求解dp[i][j]表示s[i:j+1]是否为回文串，再使用回溯法求解所有可能的分割方案。

class Solution {
public:
    int n;
    vector<vector<string>> ans;
    vector<string> temp;
    vector<vector<bool>> dp;
    vector<vector<string>> partition(string s) {
        n=s.size();
        dp=vector<vector<bool>>(n,vector<bool>(n));
        for (int j=0;j<n;++j){
            for(int i=0;i<=j;++i){
                if(i==j){
                    dp[i][j]=true;
                }else {
                    dp[i][j]=(s[i]==s[j])&&(j-i<2 || dp[i+1][j-1]);
                }
            }
        }
        backtrack(0,s);
        return ans;
    }
    void backtrack(int index,string& s){
        if (index==n){
            ans.push_back(temp);
            return;
        }
        for(int i=index;i<n;++i){
            if(dp[index][i]){
                temp.push_back(s.substr(index,i-index+1));
            }else{
                continue;
            }
            backtrack(i+1,s);
            temp.pop_back();
        }
    }
};

51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

解法：首先明白一些基本概念，对于一个n*n的棋盘，主对角线为从左上到右下的斜线，共有2n-1条，特征是主对角线上的元素行列索引差值为常数,即从1-n到n-1每个常数都对应一条主对角线。副对角线为从左下到右上的斜线，也有2n-1条，特征是副对角线上的元素行列索引和为常数,即从0到2n-1每个常数都对应一条副对角线。解决此题，只需按行放置皇后，并将占用(冲突)的列和对角线进行标记，回溯法遍历所有的情况。

class Solution {
    vector<vector<string>> ans; 
    vector<string> qipan; 
    vector<bool> cols; 
    vector<bool> diag1; 
    vector<bool> diag2; 
public:
    vector<vector<string>> solveNQueens(int n) {
        qipan = vector<string>(n, string(n, '.')); 
        cols = vector<bool>(n, false); 
        diag1 = vector<bool>(2 * n - 1, false); 
        diag2 = vector<bool>(2 * n - 1, false); 
        backtrack(0, n); 
        return ans; 
    }

    
    void backtrack(int row, int n) {
        if (row == n) { 
            ans.push_back(qipan);
            return;
        }

        for (int col = 0; col < n; ++col) {
            
            if (cols[col] || diag1[row - col + n - 1] || diag2[row + col]) {
                continue; 
            }

            
            qipan[row][col] = 'Q';
            lock(row, col, n); 
            backtrack(row + 1, n); 
            free(row, col, n); 
            qipan[row][col] = '.'; 
        }
    }

    
    void lock(int row, int col, int n) {
        cols[col] = true; 
        diag1[row - col + n - 1] = true; 
        diag2[row + col] = true; 
    }

    
    void free(int row, int col, int n) {
        cols[col] = false; 
        diag1[row - col + n - 1] = false; 
        diag2[row + col] = false; 
    }
};

二分查找

35. 搜索插入位置

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

解法：二分查找，目标在数组中，双索引会逼近该目标索引，不在则会在逼近时即left>righ时停止，此时left即为插入位置。

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l,r=0,len(nums)-1
        while l<=r:
            mid=(l+r)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]<target:
                l=mid+1
            else:
                r= mid-1
        return l

74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：
每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
解法：二分查找，先找到行，再在该行中二分查找。

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        l=0
        r=len(matrix)-1
        while l<=r:
            mid=(l+r)//2
            if matrix[mid][0]==target:
                return True
            elif matrix[mid][0]<target:
                l=mid+1
            else:
                r=mid-1
        i=0
        j=len(matrix[0])-1
        while i<=j:
            mid=(i+j)//2
            if matrix[r][mid]==target:
                return True
            elif matrix[r][mid]<target:
                i=i+1
            else:
                j=j-1
        return False

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
解法：二分查找，找第一个目标值时二分尽量往左边靠近，找最后一个目标值时二分尽量往右边靠近，两次二分法即可找到。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        l,r=0,len(nums)-1
        first,last=-1,-1
        while l<=r:
            mid=(l+r)//2
            if nums[mid]==target:
                first=mid
                r=mid-1
            elif nums[mid] >target:
                r=mid-1
            else:
                l=mid+1
        l,r=0,len(nums)-1
        while l<=r:
            mid=(l+r)//2
            if nums[mid]==target:
                last=mid
                l=mid+1
            elif nums[mid] >target:
                r=mid-1
            else:
                l=mid+1
        return [first,last]

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) 的算法解决此问题。
解法：二分查找，通过nums[0]、nums[mid]、target的大小关系可以判断二分的方向。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l,r=0,len(nums)-1
        if nums[0]==target:
            return 0
        while l<=r:
            mid=(l+r)//2
            if nums[mid]==target:
                return mid
            if nums[0]<=nums[mid]<target:
                l=mid+1
            elif nums[0]<target<nums[mid]:
                r=mid-1
            elif nums[mid]<=nums[0]<target:
                r=mid-1
            elif nums[mid]<target<nums[0]:
                l=mid+1
            elif target<nums[0]<=nums[mid]:
                l=mid+1
            elif target<nums[mid]<=nums[0]:
                r=mid-1
        return -1

153. 寻找旋转排序数组中的最小值

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次旋转后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

解法：当nums[0]<nums[n-1]或者len(nums)==1时，最小元素为nums[0]。然后二分查找,当nums[mid]刚好小于nums[mid-1]时，最小元素为nums[mid]；否则，根据nums[mid]与nums[0]的关系继续缩小范围。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if nums[0]<nums[-1] or len(nums)==1:
            return nums[0]
        l,r=0,len(nums)-1
        while l<=r:
            mid=(l+r)//2
            if nums[mid]<nums[mid-1]:
                return nums[mid]
            if nums[mid]<nums[0]:
                r=mid-1
            else:
                l=mid+1

4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

算法的时间复杂度应该为 O(log (m+n)) 。
解法：中位数左右两边的元素数量应该相同，只需找到一个合适的位置划分两个数组，使得左边的元素数量等于右边元素数量并且左边最大值小于或等于右边最小值即可。程序中m1,m2指的是右半部分的第一个元素。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n1 = len(nums1)
        n2 = len(nums2)
        if n1 > n2:
            return self.findMedianSortedArrays(nums2,nums1)
        k = (n1 + n2 + 1)//2
        left = 0
        right = n1
        while left < right :
            m1 = left +(right - left)//2
            m2 = k - m1
            if nums1[m1] < nums2[m2-1]:
                left = m1 + 1
            else:
                right = m1
        m1 = left
        m2 = k - m1 
        c1 = max(nums1[m1-1] if m1 > 0 else float("-inf"), nums2[m2-1] if m2 > 0 else float("-inf") )
        if (n1 + n2) % 2 == 1:
            return c1
        c2 = min(nums1[m1] if m1 < n1 else float("inf"), nums2[m2] if m2 <n2 else float("inf"))
        return (c1 + c2) / 2

栈

20. 有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
解法：遇到左括号入栈，遇到右括号判断是否和栈顶匹配，匹配则出栈，否则返回False。

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

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
解法：
1.使用两个栈分别维护最小值和正常值
2.如果要求最小值不能使用额外空间，则可以通过入栈保存当前值和最小值差值的方法来做到，出栈时根据差值判断返回值，过程中更新最小值。

class MinStack {
    vector<int> data;
    vector<int> Mins;

public:
    MinStack() {  
    }
    
    void push(int val) {
        data.push_back(val);
        if (Mins.empty()||val<=Mins.back())Mins.push_back(val);
    }
    
    void pop() {
        if(data.back()==Mins.back())Mins.pop_back();
        data.pop_back(); 
    }
    
    int top() {
        return data.back();
    }
    
    int getMin() {
        return Mins.back();
    }
};

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入
解法：递归或者显式维护一个栈，递归返回[]内的结果，并乘以记录的次数。

class Solution:
    def decodeString(self, s: str) -> str:
        stack, res, multi = [], "", 0
        for c in s:
            if c == '[':
                stack.append([res,multi])
                res,multi="",0
            elif c == ']':
                last_res,cur_multi=stack.pop()
                res=last_res+cur_multi*res
            elif '0' <= c <= '9':
                multi = multi * 10 + int(c)            
            else:
                res += c
        return res

class Solution {
public:
    string decodeString(string s) {
        int i = 0;
        return dfs(s, i);
    }

private:
    string dfs(const string& s, int& i) {
        string res;
        int multi = 0;
        
        while (i < s.size()) {
            char ch = s[i];
            
            if (ch - '0' >= 0 && ch - '0' <= 9)  {  
                multi = multi * 10 + (ch - '0');
            } 
            else if (ch == '[') {  
                i++;  
                string tmp = dfs(s, i);
                while (multi) {
                    res += tmp;  
                    --multi;
                }

            } 
            else if (ch == ']') {  
                return res;
            } 
            else {  
                res += ch;
            }
            ++i;
        }
        return res;
    }
};

739. 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
解法：
1.从左往右遍历是O(n2),重复计算了很多次，从右向左计算则可以利用过去的结果。在计算当前日的升温日时，可以根据后续日期的升温日直接跳转，不存在升温日则为0
2.使用栈，从左往右遍历，当前日温度小于栈顶元素温度直接入栈，大于栈顶元素温度则更新栈顶日期的升温日结果并弹出栈顶元素，继续判断直到栈顶元素温度大于当前日温度并将当前日温度入栈，只需遍历一次。

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        answer=[0]*len(temperatures)
        for i in range(len(temperatures)-2,-1,-1):
            j=i+1
            while j<len(temperatures):
                if temperatures[j]>temperatures[i]:
                    answer[i]=j-i
                    break
                elif answer[j]==0:
                    answer[i]=0
                    break
                else:
                    j+=answer[j]
        return answer

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

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
解法：
1.对于每一个柱子i，包含该柱子在内的最大矩形的左右边界为第一个高度小于height[i]的柱子。可以正反序遍历两次，求得每根柱子左极限和右极限，然后求最大值
2.使用单调递增栈，从左向右遍历，遇到高度小于栈顶柱子的柱子，即可求出包含栈顶柱子的最大矩形面积。弹出栈顶元素，可继续比较求解。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        left,right=[0]*len(heights),[0]*len(heights)
        left[0]=-1
        right[-1]=len(heights)
        for i in range(len(heights)):
            temp=i-1
            while temp>=0 and heights[temp]>=heights[i]:
                temp=left[temp]
            left[i]=temp
        for i in range(len(heights)-2,-1,-1):
            temp=i+1
            while temp<len(heights) and heights[temp]>=heights[i]:
                temp=right[temp]
            right[i]=temp
        ans=0
        for i in range(len(heights)):
            ans=max(ans,(right[i]-left[i]-1)*heights[i])
        return ans

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans=0;
        stack<int> stack;
        heights.push_back(0);
        heights.insert(heights.begin(),0);
        for(int i=0;i<heights.size();++i){
            while (!stack.empty() && heights[i]<heights[stack.top()]){
                int temp = stack.top();stack.pop();
                ans=max(ans,(i-stack.top()-1)*heights[temp]);
            }
            stack.push(i);
        }
        return ans;
    }
};

堆

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

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
解法：
1.使用最小堆，大小为k,加入元素时进行上浮，移除堆首进行下沉，最后堆顶元素即为第k大的元素。
2.使用快速选择算法，随机选取一个元素，将比它小的元素放到左边，将比它大的元素放到右边，比较索引值与k的大小,直到选取第k个元素。

注意：快速选择算法的期望时间复杂度为O(n)，但当选择的元素有重复时需要特别注意双指针分区的移动技巧不然容易超时，暂时没弄明白，建议复习时死记硬背一下。这里推挤下三路分区，更不容易失误。i,j代表左右分区，curr代表当前元素，移动式维护好i,j,最终数组排列为左、中(一个或多个选中的哨兵/partition元素)、右三部分

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []

        for num in nums:
            if len(heap) < k:
                heap.append(num)
                
                i=len(heap)-1
                parent =(i-1)//2
                while i>0 and heap[parent]>heap[i]:
                    heap[parent],heap[i]=heap[i],heap[parent]
                    i=parent
                    parent=(i-1)//2
            else:
                if num > heap[0]:
                    
                    heap[0] = num
                    i=0
                    left=2*i+1
                    right=2*i+2
                    while True:
                        small=i
                        if left<len(heap) and heap[left]<heap[small]:
                            small=left
                        if right<len(heap) and heap[right]<heap[small]:
                            small=right
                        if small==i:
                            break
                        heap[i],heap[small]=heap[small],heap[i]
                        i=small
                        left=2*i+1
                        right=2*i+2
                        

        return heap[0]

class Solution {
public:
    int quickselect(vector<int> &nums, int l, int r, int k) {
        if (l == r)
            return nums[k];
        int partition = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (nums[i] < partition);
            do j--; while (nums[j] > partition);
            if (i < j)
                swap(nums[i], nums[j]);
        }
        if (k <= j)return quickselect(nums, l, j, k);
        else return quickselect(nums, j + 1, r, k);
    }

    int findKthLargest(vector<int> &nums, int k) {
        int n = nums.size();
        return quickselect(nums, 0, n - 1, n - k);
    }
};

class Solution {
public:
    int quickselect(vector<int> &nums, int l, int r, int k) {
        int partition = nums[l], i = l, j = r;
        int current=l;
        while (current <= j) {
            if(nums[current]<partition){
                swap(nums[i],nums[current]);
                i++;
                current++;
            }else if (nums[current]==partition){
                current++;
            }else{
                swap(nums[current],nums[j]);
                j--;
            }
        }
        if (i<=k && k<=j){return nums[k];}
        else if (k < i)return quickselect(nums, l, i-1, k);
        else return quickselect(nums, j + 1, r, k);
    }

    int findKthLargest(vector<int> &nums, int k) {
        int n = nums.size();
        return quickselect(nums, 0, n - 1, n - k);
    }
};

347. 前 K 个高频元素

中等
相关标签
相关企业
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按任意顺序返回答案。
解法：使用最小堆，统计元素出现的频率，然后利用最小堆求第k高的元素。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> fs;
        for (auto&v:nums){
             fs[v]++;
        }
        vector<int> heap;
        for(auto& p:fs){
             int num=p.first;
             int count=p.second;
             if (heap.size()<k){
                heap.push_back(num);
                
                int i=heap.size()-1;
                int parent=(i-1)/2;
                while (i>0 && fs[heap[parent]]>fs[heap[i]]){
                    swap(heap[parent],heap[i]);
                    i=parent;
                    parent=(i-1)/2;
                }
             }else{
                
                if (count>fs[heap[0]]){
                    heap[0]=num;
                    int i=0;
                    int left=2*i+1,right=2*i+2;
                    int small=i;
                    while(true){
                        if(left<heap.size() && fs[heap[left]]<fs[heap[small]]){
                            small=left;
                        }
                        if(right < heap.size() && fs[heap[right]]<fs[heap[small]]){
                            small=right;
                        } 
                        if (small==i)break;
                        swap(heap[i],heap[small]);
                        i=small;
                        left=2*i+1;
                        right=2*i+2;
                    }
                }

             }
        }
        return heap;
    }
};

295. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。

void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
解法：使用两个堆，一个堆存放较小的一半堆顶最大，另一个堆存放较大的一半堆顶最小。放入元素时让当前元素和栈顶元素在两个堆上浮一遍完成一个从左到右或从右到左的流程，保持数量平衡

python的堆heaps.heappush()和heaps.heappop()可以实现堆的操作，默认最小堆，可以用-num实现最大堆。c++的priority_queue可以实现最大堆和最小堆，默认是最大堆，可以设置greater或者less实现最小堆和最大堆。

from heapq import *

class MedianFinder:
    def __init__(self):
        self.A = [] 
        self.B = [] 

    def addNum(self, num: int) -> None:
        if len(self.A)==len(self.B):
            heapq.heappush(self.A,-num)
            heapq.heappush(self.B,-heapq.heappop(self.A))
        else:
            heapq.heappush(self.B,num)
            heapq.heappush(self.A,-heapq.heappop(self.B))

    def findMedian(self) -> float:
        return self.B[0] if len(self.A)!=len(self.B) else (-self.A[0]+self.B[0])/2

class MedianFinder {
public:
    priority_queue<int, vector<int>, greater<int>> A; 
    priority_queue<int, vector<int>, less<int>> B; 
    MedianFinder() { }
    void addNum(int num) {
        if (A.size() != B.size()) {
            A.push(num);
            B.push(A.top());
            A.pop();
        } else {
            B.push(num);
            A.push(B.top());
            B.pop();
        }
    }
    double findMedian() {
        return A.size() != B.size() ? A.top() : (A.top() + B.top()) / 2.0;
    }
};

贪心算法

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
解法：假设我总是在过去的最低点买入股票，每天只需考虑当天卖出能赚多少,并更新维护最低点即可。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minprice =INT_MAX;
        int maxProfit=0;
        for(auto& p:prices){
            if(p<minprice)minprice=p;
            else maxProfit=max(maxProfit,p-minprice);
        }
        return maxProfit;
    }
};

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
解法：维护一个最大可达距离，遍历数组，如果当前位置小于等于最大可达距离，则根据当前可跳跃步数更新最大可达距离，如果当前位置大于最大可达距离，则说明无法到达最后一个下标，返回false。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int max_distance=0;
        for (int i=0;i<nums.size();++i){
            if (i<=max_distance){
                max_distance=max(max_distance,i+nums[i]);
                if (max_distance>=nums.size()-1){
                    return true;
                }
            }else{
                return false;
            }
        }
        return false;
    }
};

45. 跳跃游戏 II

给定一个长
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
解法：每跳一次就是一次极限更新，最小的步数就是最小次数的极限更新。遍历统计当前点可以到达的最远距离，但不一定起跳,只有当前位置已经是极限距离了，必须选取过去的一个点起跳才能到达下一个极限距离。

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size()==1)return 0;
        int step=0;
        int max_distance=0;
        int next_max_distance=0;
        for (int i=0;i<nums.size();++i){
            next_max_distance = max(next_max_distance,i+nums[i]);
            if(i==max_distance){
                step++;
                max_distance=next_max_distance;
                if (max_distance>=nums.size()-1)break;
            }
        }
        return step;
    }
};

763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 “ababcc” 能够被分为 [“abab”, “cc”]，但类似 [“aba”, “bcc”] 或 [“ab”, “ab”, “cc”] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
解法：遍历字符串，统计每个字母出现的最后位置。同一字母需要分在同一片段，故该片段的start和end必然在该字母第一次出现和最后一次出现的位置外侧。维护一个当前片段start和end,根据字母i的最后出现的位置扩展end直到i==end，得到一个符合要求的片段，长度为end-start+1.再求下一个片段的长度，直到遍历完字符串。

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last={}
        for  i,ch in enumerate(s):
            last[ch]=i
        res = list()
        start=end=0
        for i,ch in enumerate(s):
            end=max(end,last[ch])
            if i==end:
                res.append(end-start+1)
                start=end+1
                end=start
        return res

动态规划

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
解法：dp[i] 表示爬到第 i 阶的方法数，则 dp[i] = dp[i-1] + dp[i-2]。

注意这里用递归会超时，递归没有记忆化，会大量重复结算，所以用数组存储中间结果。

class Solution:
    def climbStairs(self, n: int) -> int:
        dp=[0]*(n+1)
        dp[0]=1
        dp[1]=1
        for i in range(2,n+1):
            dp[i]=dp[i-1]+dp[i-2]
        return dp[n]

118. 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
解法:从n=0开始，第n行有n+1个元素，两边元素为1，中间元素为左上和右上元素之和即第i个元素为n-1行第i-1、i个元素之和。

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res=[[1]]
        for row in range(1,numRows):
            temp=[1]*(row+1)
            for i in range(1,row):
                temp[i]=res[-1][i-1]+res[-1][i]
            res.append(temp)
        return res

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
解法：划分子问题，从偷前k=0、1、2…间房子开始计算,偷第k间房子时，可以选择偷或不偷第k间房子，用dp[k]代表偷前k间房子最大收获则可以得到递归关系：dp[k] = max(dp[k-1],dp[k-2]+nums[k-1])。

class Solution:
    def rob(self, nums: List[int]) -> int:
        n=len(nums)
        if n==0:
            return 0
        f=[0]*(n+1)
        f[1]=nums[0]
        for i in range(2,n+1):
            f[i]=max(f[i-1],f[i-2]+nums[i-1])
        return f[n]

279. 完全平方数

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。
完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
解法：f(n)=1+min(f(n-1),f(n-22),f(n-32),…,f(n-k**2))，其中k=1,2,3,…,sqrt(n)。边界f(0)=0

class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n+1);
        f[0]=0;
        for (int i=1;i<=n;++i){
            int mint=INT_MAX;
            for (int j=1;j*j<=i;++j){
                mint=min(mint,f[i-j*j]);
            }
            f[i]=1+mint;
        }
        return f[n];
    }
};

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
解法：动态规划，dp[i]表示凑成i元钱所需的最少硬币数，则dp[i] = 1+min(dp[i-coin])，其中coin为coins中的硬币面值。如果dp[i-coin]不存在，则返回-1

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        f=[0]*(amount+1)
        for i in range(1,amount+1):
            mint=float("inf")
            for c in coins:
               if i-c>=0 and f[i-c]!=-1:
                mint=min(mint,f[i-c])
            if mint==float("inf"):
                f[i]=-1
            else:
                f[i]=1+mint
        return f[amount]

139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
解法：遍历字符串s,判断s[:j]是否可以被字典中的单词拼接出，利用历史s[:i]的结果加上s[i:j]是否在字典中即可判断。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n=len(s)
        f=[False]*(n+1)
        f[0]=True
        for i in range(n):
            for j in range(i+1,n+1):
                if (f[i] and s[i:j] in wordDict):
                    f[j]=True
        return f[n]

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
解法：
1.使用f[i]表示以nums[i]结尾的最长递增子序列的长度，则f[i] = max(f[j]+1)，其中j在i之前且nums[j]小于nums[i]。返回f的最大值。
2.维护一个数组表示最大递增子序列，遍历数组，如果nums[i]大于等于最大递增子序列的最后一个元素，则将其加入最大递增子序列。否则，使用erfenf找到最大递增子序列中第一个大于nums[i]的元素，将其替换为nums[i]。尽管此元素后面的元素是错误的，但数组的长度依然等于最大递增子序列的长度。后续如果能发现更长的递增子序列，则可以很自然的将错误的值全部替换掉。

当二分查找的nums[mid]==target时,为了让l、r能逼近target,需要l=mid或者r=mid而不能同时变化1

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        f=[1]*(len(nums)+1)
        f[0]=0
        for i in range(1,len(nums)+1):
            maxv=0
            for j in range(i-1):
                if nums[j]<nums[i-1]:
                    maxv=max(maxv,f[j+1])
            f[i]=1+maxv
        return max(f)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> res;
        res.push_back(nums[0]);
        for(int i=1;i<nums.size();++i){
            if(nums[i]>res.back())res.push_back(nums[i]);
            else{
                int l=0,r=res.size()-1;
                while(l<r){
                    int mid=(l+r)/2;
                    if (res[mid]<nums[i])l=mid+1;
                    else r=mid;
                }
                res[l]=nums[i];  
            }
        }
        return res.size();
    }
};

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位整数。
解法：动态规划，dp_max[i]表示以i结尾的最大子数组乘积,dp_min[i]表示以i结尾的最小子数组乘积,则dp_max[i] = max(dp_max[i-1]*nums[i],dp_min[i-1]*nums[i],nums[i]),dp_min[i] = min(dp_max[i-1]*nums[i],dp_min[i-1]*nums[i],nums[i]).

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int ans=nums[0];
        int current_max=nums[0];
        int current_min=nums[0];
        for (int i=1;i<nums.size();++i){
            if(nums[i]>0){
                current_max*=nums[i];
                current_min*=nums[i];
            }else{
                int temp = current_max;
                current_max=current_min*nums[i];
                current_min=temp*nums[i];
            }
            current_max=max(nums[i],current_max);
            current_min=min(nums[i],current_min);
            ans=max(ans,current_max);
        }
        return ans;
    }
};

416. 分割等和子集

给你一个只包含正整数的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
解法：使用dp[i][j]表示使用数组的前i个元素能否构成和为j的子集，则需要求dp[len(nums)][sum(nums)/2].递推关系：如果使用元素nums[i]，则dp[i][j] = dp[i-1][j-nums[i]]；如果不使用元素nums[i]，则dp[i][j] = dp[i-1][j].

这里为了优化效率，采取滚动数组,dp[i]倒序覆盖dp[i-1]求解,程序中的一维dp实际是指解法的dp[i]数组。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s % 2 != 0:
            return False
        t = s // 2
        dp = [False] * (t + 1)
        dp[0] = True  
        for num in nums:
            for j in range(t, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]
        return dp[t]

32. 最长有效括号

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
解法：动态规划，dp[i]表示以i结尾的最长有效括号子串的长度，分情况讨论：1、如果s[i]==‘(’，则dp[i] = 0,无法构成有效括号；2、如果s[i]==‘)’,也分两种情况：a.如果s[i-1]==‘(’，刚好匹配dp[i]则dp[i] = dp[i-2]+2；b.如果s[i-1]==‘)‘并且dp[i-1]有效,需要判断i-dp[i-1]-1位置是否为’(’，构成则dp[i] = dp[i-1]+2+dp[i-dp[i-1]-2]。

这里需要注意判断索引的合法性，防止数组越界。python索引为负数不报错，但会导致逻辑错误。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s:
            return 0
        dp=[0]*(len(s))
        for i in range(1,len(s)):
            if s[i]=='(':
                dp[i]=0
            else:
                if s[i-1]=="(":
                    dp[i]=dp[i-2]+2
                elif dp[i-1] and i-dp[i-1]-1>=0 and s[i-dp[i-1]-1]=="(":
                        dp[i]=dp[i-dp[i-1]-2]+dp[i-1]+2 if i-dp[i-1]-2>=0 else dp[i-1]+2
                else:
                    dp[i]=0
        return max(dp)

多维动态规划

62. 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
解法：
1.数学组合,一共m+n-2步，选取m-1步向下走,有C(m+n-2,m-1)种选择。C(m+n-2,m-1) = (m+n-2)!/((m-1)!*(n-1)!)
2.动态规划,dp[i][j]表示从(0,0)走到(i,j)的路径数,则dp[i][j] = dp[i-1][j] + dp[i][j-1],因为只能向下或者向右走一步到达(i,j)。在边界即i=0或j=0时，dp[i][j] = 1.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        ans=1
        i=m+n-2
        j=m-1
        while j:
            ans*=i
            i-=1
            j-=1
        t=1
        j=m-1
        while j:
            t*=j
            j-=1 
        return ans//t

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n));
        for(int i=0;i<m;++i){
            for (int j=0;j<n;++j){
                if (i==0 || j==0 )dp[i][j]=1;
                else dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
解法：动态规划，dp[i][j]表示从(0,0)走到(i,j)的最小路径和，则dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j].

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

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。
解法：
1.Manacher 算法，将字符串变为“#ab#bc#”的形式，这样可以将奇偶字符串统一处理。使用中心扩散法记录回文中心i的半径p[i],并维护一个最大回文边界right_max和对应的中心center.遍历计算p[i]时，根据回文对称性,如果i>=right_max时只能中心扩散计算，当i小于right_max时，可以利用上历史数据：设p关于center的对称位置mirror=2*center-i,当right_max-i>p[mirror]时，p[i]等于p[mirror]+2;当right_max-i==p[mirror]时，p[i]可以从right_max-i开始扩散；当right_max-i小于p[mirror]时，p[i]等于right_max-i.整个过程中维护最大串的长度和中心位置。
2.动态规划，dp[i][j]表示s[i:j+1]是否为回文串，则dp[i][j] = (s[i]==s[j]) and (i+1>=j-1 or dp[i+1][j-1]),注意边界条件。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        t = "#".join("^" + s + "$")
        halfLen = [0] * len(t)
        max_i = box_r=box_center= 0
        for i in range(2, len(t) - 2):
            hl = 1
            if i < box_r:
                hl = min(halfLen[2*box_center-i], box_r - i + 1)
            while t[i - hl] == t[i + hl]:
                hl += 1
                box_r += 1
                box_center=i
            halfLen[i] = hl
            if hl > halfLen[max_i]:
                max_i = i
        max_hl = halfLen[max_i]
        return s[(max_i - max_hl) // 2 : (max_i + max_hl) // 2 - 1]

class Solution {
public:
    string longestPalindrome(string s) {
        int start=0;
        int lenth=0;
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size()));
        
        for(int j=0;j<s.size();++j){
            for (int i=0;i<=j;++i){
                if(i==j) dp[i][j]=true;
                else dp[i][j]=(s[i]==s[j] && (i+1>=j-1||dp[i+1][j-1]));
                if(dp[i][j] && j-i+1>lenth){
                    start = i;
                    lenth=j-i+1;
                }
            }
        }
        return s.substr(start,lenth);
    }
};

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。
一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的公共子序列是这两个字符串所共同拥有的子序列。
解法：动态规划，dp[i][j]表示text1[0:i+1]和text2[0:j+1]的最长公共子序列的长度。当text1[i]==text2[j]时，dp[i][j] = dp[i-1][j-1]+1;否则，dp[i][j] = max(dp[i-1][j],dp[i][j-1]).边界条件：当i=0或j=0时，dp[i][j] = 0.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m=len(text1)
        n=len(text2)
        dp=[[0]*(n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1]==text2[j-1]:
                    dp[i][j]=dp[i-1][j-1]+1
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        return dp[m][n]

72. 编辑距离

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
解法：动态规划，dp[i][j]表示将word1[0:i+1]转换成word2[0:j+1]所使用的最少操作数。在已经将word1[0:i-1]转换成word2[0:j-1]的基础上，分情况讨论：
如果word1[i]==word2[j],不需要操作，dp[i][j] = dp[i-1][j-1];
如果word1[i]!=word2[j],则需要进行替换、插入、删除操作,三种方法取最小：
1.对于替换,需要先将word1前i-1个元素变为word2前j-1个元素，然后用word2第j个元素替换word1第i个元素,得到：dp[i][j] = dp[i-1][j-1]+1
2.对于插入,需要先将word1前i个元素变为word2前j-1个元素，然后在word1末尾插入word2第j个元素,得到：dp[i][j] = dp[i][j-1]+1
3.对于删除，需要先将word1前i-1个元素变为word2前j个元素，然后删除word1第i个元素,得到：dp[i][j] = dp[i-1][j]+1

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m=len(word1)
        n=len(word2)
        dp=[[0]*(n+1) for _ in range(m+1)]
        for i in range(m+1):
            for j in range(n+1):
                if i==0:
                    dp[0][j]=j
                elif j==0:
                    dp[i][0]=i              
                elif word1[i-1]==word2[j-1]:
                    dp[i][j]=dp[i-1][j-1]
                else:
                    dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
        return dp[m][n]

技巧

136. 只出现一次的数字

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
解法：使用位运算，异或运算，相同的数字异或为0，不同数字异或为1，最后剩下的数字就是只出现一次的数字。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res ^= num
        return res

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。
解法：只有多数元素的数量超过一半，故在被不同阵营数字抵消的情况下，只有多数元素能够存活。即Boyer-Moore 投票算法

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 0
        candidate = None

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        return candidate

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。
解法：双指针，遍历数组，优先将2移动到后边。规则：遇到2则交换元素到右指针位置，右指针移动一步，继续判断当前元素，直到不为2；遇到0则交换元素到左指针位置，左指针移动一步。停止条件：i<=右指针

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l,r=0,len(nums)-1
        i=0
        while i<=r:
            while i<=r and nums[i]==2:
                nums[i],nums[r]=nums[r],nums[i]
                r-=1
            if nums[i]==0:
                nums[i],nums[l]=nums[l],nums[i]
                l+=1
            i+=1

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 的下一个排列。

必须原地修改，只允许使用额外常数空间。
解法：把数组看作一串数字，目的是找到一个仅大一点的数即为下一个排列。从左向右，找到最靠后一对满足 numsi< nums[i+1] 的数，然后找到nums[i]后面比它稍大的元素(记为y)，交换这两个元素,将nums[i]后面的元素升序排列。如果找不满足nums[i] < nums[i+1]的数，则说明已经是最大的排列，则需要将整个数组反转，得到最小的排列。

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        x=-1
        for i in range(len(nums)-1):
            if nums[i]<nums[i+1]:
                x=i
        if x==-1:
            nums.sort()
            return
        y=x+1
        for i in range(y+1,len(nums)):
            if nums[x]<nums[i]<nums[y]:
                y=i
        nums[x],nums[y]=nums[y],nums[x]
        nums[x+1:]=sorted(nums[x+1:])

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有一个重复的整数，返回这个重复的数。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。
解法：
1.利用数值本身作为索引，就可以将整个数组映射成一个链表，转换为一个利用快慢指针求入环点的问题。
2.二分法，mid=(1+n)/2,统计小于mid的元素数量，如果小于mid的元素数量大于mid，说明重复的数在mid左边，否则在mid右边。然后不断二分，直到重复的数被找到。

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow,fast=0,0
        slow=nums[slow]
        fast=nums[nums[fast]]
        while slow!=fast:
            slow=nums[slow]
            fast=nums[nums[fast]]
        slow=0
        while slow!=fast:
            slow=nums[slow]
            fast=nums[fast]
        return slow

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int min = 1; 
        int max = nums.size(); 

        while (min < max) {
            int mid = (min + max) / 2;
            
            int cnt = 0;
            for (int v : nums) {
                if (v >= min && v <= mid) {
                    cnt++;
                }
            }

            if (cnt > mid - min + 1) 
                max = mid;
            else
                min = mid + 1;
        }

        return min;
    }
};