求职-LeetCode热题100刷题记录

哈希

1.两数之和

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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 []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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整数编码) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class listDict(dict):
    def __init__(self, value_type):
        super().__init__()        # 注意：super 写法要这样调用
        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())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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则更新长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 放在循环体内判断是否执行而不是头部;)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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即可。注意,暴力双循环会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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，则加入结果。过程中,要跳过相同元素来去重。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class 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)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int 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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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表示符合要求
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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){
            //窗口少了字母s[i],引起变化,更新count和differ
            --count[s[i]-'a'];
            if (count[s[i]-'a']==0){
                --differ;
            }
            else if (count[s[i]-'a']==-1){
                ++differ;
            }

             //窗口多了字母s[i+p],引起变化,更新count和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)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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  # 统计和为k的子数组数量
        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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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=2*i+1，右子节点right=2*i+2。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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向右移动到恰好不满足条件为止，更新最小字串，接着再重复上述过程返回最终的最小字串。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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){
                while(l<=r){
                    c=s[l]-65;
                    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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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; } 表示。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 指向新的列表对象、不影响旧的引用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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  # 防止 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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则是通过[行,列]的方式进行修改,支持对行列进行切片修改,效率更高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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       # 设置第 i 行全为 0
            for row in matrix:
                row[j] = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)，推荐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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度等效于上下翻转一次+沿着主对角线翻转一次，可推广至所有元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 = matrix[i][j];
                // swap(temp,matrix[j][n-i-1]);
                // swap(temp,matrix[n-i-1][n-j-1]);
                // swap(temp,matrix[n-j-1][i]);
                // matrix[i][j]=temp;
                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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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。技巧：双指针走完一个链表移到另一个链表的头部。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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++中`.`用于对象访问成员；`->`用于对象指针访问成员

1
2
3
4
5
6
7
8
9
10
11
12
13

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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.哈希表，遍历链表，将每个节点存入哈希表，如果存在重复值，则存在环。

1
2
3
4
5
6
7
8
9
10
11
12
13
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.哈希表，遍历链表，将每个节点存入哈希表，如果存在重复值，则存在环,返回重复值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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.双指针遍历,不断取出两个链表的最小值，将最小值放入新链表末尾节点的后面，返回头节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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在堆上分配内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution(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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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个结点的上一个节点，删除下一个节点即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: Optional[ListNode]
        :type n: int
        :rtype: Optional[ListNode]
        """
        fast = head
        target = head

        # 提前走 n + 1 步
        for _ in range(n + 1):
            if fast:
                fast = fast.next
            else:
                # 如果 fast 提前走不了 n+1 步，说明要删的是第一个节点
                return head.next

        # fast 与 target 同时前进，直到 fast 到尾部
        while fast:
            target = target.next
            fast = fast.next

        # 删除 target 后继节点
        to_delete = target.next
        target.next = target.next.next
        del to_delete  # 可写可不写，Python 会自动 GC

        return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    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的位置方便下一轮两个节点的交换，直到遇到空指针。

1
2
3
4
5
6
7
8
9
10
11
12
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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个节点组成一个子链表，翻转子链表，并将翻转后的子链表连接到原链表的后面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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节点通过递归来求得

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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.优先队列，每次取最小的节点，然后将该节点的下一个节点加入优先队列，直到优先队列为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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->了，当然更推荐在初始化列表中初始化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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) 

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */