前言

数组

快慢&左右index

快慢index核心就是快慢指针问题，数组能通过[]直接访问，所以一般没用数组指针++\–访问

26.力扣-有序数组去重
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int removeDuplicates(vector<int>& nums) {
    int fast = 0;
    int slow = 0;
    int len = nums.size();
    while (fast < len) {
        if (nums[slow] != nums[fast]) {
            /// 先递增slow再赋值
            slow++;
            nums[slow] = nums[fast];
        }
        fast++;
    }
    if (len == 0)
        return 0;
    return slow + 1;
}
27.移除元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int removeElement(vector<int>& nums, int val) {
        int fast = 0;
        int slow = -1;
        int len = nums.size();
        while (fast < len)
        {
            if (nums[fast] != val)
            {
                slow++;
                nums[slow] = nums[fast];
            }
            fast++;
        }
        return slow + 1;
    }
283.移动 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void moveZeroes(vector<int>& nums) {
    int fast = 0;
    int slow = -1;
    int len = nums.size();
    while (fast < len)
    {
        if (nums[fast] != 0)
        {
            slow++;
            nums[slow] = nums[fast];
        }
        fast++;
    }
    slow++;
    while (slow < len)
        nums[slow++] = 0;
}
5.最长回文子串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
std::string palindrome(std::string s, int l, int r) {
    while (l >= 0 && r < s.length() && s[l] == s[r]) {
        l--;
        r++;
    }
    return s.substr(l + 1, r - l - 1);
}

string longestPalindrome(string s) {
    string res = "";
    for (int i = 0; i < s.length(); i++)
    {
        string s1 = palindrome(s, i, i);
        string s2 = palindrome(s, i, i + 1);

        string cur = s1.length() > s2.length() ? s1 : s2;
        res = res.length() > cur.length() ? res : cur;
    }
    return res;
}
977.有序数组的平方
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> sortedSquares(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    vector<int> vec(nums.size());
    int cur = nums.size() - 1;
    while (left <= right)
    {
        int ln = nums[left];
        int rn = nums[right];

        ln *= ln;
        rn *= rn;
        if (ln > rn) {
            vec[cur] = ln;
            left++;
        }
        else
        {
            vec[cur] = rn;
            right--;
        }
        cur--;
    }
    return vec;
}
11. 盛最多水的容器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxArea(vector<int>& height) {
    int left = 0, right = height.size()-1;
    int maxarea = 0;
    while (left < right)
    {
        int wide = right - left;
        int lh = height[left];
        int rh = height[right];
        int hight = std::min(lh, rh);

        maxarea = maxarea > hight * wide ? maxarea : hight * wide;
        if (lh < rh)
            left++;
        else
            right--;
    }
    return maxarea;
}
42. 接雨水
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
int getFrontMax(vector<int>& nums, int index) {
    int max = 0;
    for (int i = 0; i <= index; i++) {
        max = max > nums[i] ? max : nums[i];
    }
    return max;
}

int getBehinMax(vector<int>& nums, int index) {
    int max = 0;
    for (int i = nums.size() - 1; i >=index; i--) {
        max = max > nums[i] ? max : nums[i];
    }
    return max;
}

vector<int> fmaxV(vector<int>& nums) {
    vector<int> v1;
    for (int i = 0; i < nums.size(); i++)
    {
        v1.push_back(getFrontMax(nums, i));
    }
    return v1;
}

vector<int> BmaxV(vector<int>& nums) {
    vector<int> v1;
    for (int i = 0; i < nums.size(); i++)
    {
        v1.push_back(getBehinMax(nums, i));
    }
    return v1;
}

int trap(vector<int>& height) {
    vector<int> fm = fmaxV(height);
    vector<int> bm = BmaxV(height);
    int cont = 0;

    for (int i = 0; i < height.size(); i++)
    {
        int f = fm[i];
        int b = bm[i];
        int min = std::min(f, b);
        cont += min - height[i];
    }
    return cont;
}


///这里求前后缀最大时，时间复杂度高优化如下
vector<int> fmaxV(vector<int>& nums) {
    vector<int> v1(nums.size());
    int currentMax = nums[0];
    v1[0] = currentMax;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] > currentMax) {
            currentMax = nums[i];
        }
        v1[i] = currentMax;
    }
    return v1;
}

vector<int> bmaxV(vector<int>& nums) {
    int n = nums.size();
    vector<int> v1(n);
    int currentMax = nums[n - 1];
    v1[n - 1] = currentMax;
    for (int i = n - 2; i >= 0; i--) {
        if (nums[i] > currentMax) {
            currentMax = nums[i];
        }
        v1[i] = currentMax;
    }
    return v1;
}

接水问题相关讲解

二分问题

一般二分涉及到直接搜索目标、目标左边界、目标右边界的三类问题，第一类是直接搜很好解决，问题是第二类和第三类，

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
/// 如果 target 不存在，搜索左侧边界的二分搜索返回的索引是大于 target 的最小索引
int searchLeftIndex(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        }
        else if (nums[mid] > target) {
            right = mid - 1;
        }
        else if (nums[mid] == target) {
            right = mid - 1;
        }
        
    }

    if (left < 0 || left >= nums.size())
        return -1;

    return nums[left] == target ? left : -1;
}
//如果 target 不存在，搜索右侧边界的二分搜索返回的索引是小于 target 的最大索引。
int searchRightIndex(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        }
        else if (nums[mid] > target) {
            right = mid - 1;
        }
        else if (nums[mid] == target) {
            left = mid + 1;
        }
        
    }

    if (left-1 < 0 || left-1 >= nums.size())
        return -1;

    return nums[left-1] == target ? (left-1) : -1;
}
704.二分查找
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
int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right)
    {
        int mid = (left + right) >> 1;
        if (nums[mid] > target)
        {
            right = mid ;
        }
        else if(nums[mid] < target)
        {
            left = mid + 1;
        }
        else 
        {
            return mid;
        }
    }
    return -1;
}

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right)
    {
        int mid = (left + right) >> 1;
        if (nums[mid] > target)
        {
            right = mid - 1;
        }
        else if(nums[mid] < target)
        {
            left = mid + 1;
        }
        else 
        {
            return mid;
        }
    }
    return -1;
}
35. 搜索插入位置
1
2
3
4
5
6
7
8
9
10
11
12
13
int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return left;
}
34. 在排序数组中查找元素的第一个和最后一个位置
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
vector<int> searchRange(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    int start = -1, end = -1;
    while (left <= right) {
        int mid = (left + right) >> 1;

        if (nums[mid] < target)
        {
            left += 1;
        }
        else if (nums[mid] > target)
        {
            right -= 1;
        }
        else if (nums[mid] == target)
        {
            start = mid;
            right = mid - 1;
        }
    }
    left = 0;
    right = nums.size() - 1;
    while (left <= right) {
        int mid = (left + right) >> 1;

        if (nums[mid] < target)
        {
            left += 1;
        }
        else if (nums[mid] > target)
        {
            right -= 1;
        }
        else if (nums[mid] == target)
        {
            end = mid;
            left = mid + 1;
        }
    }
    
    return { start, end };
}
33. 搜索旋转排序数组-无重复值
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
int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right)
    {
        int mid = (left + right) >> 1;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[left] > nums[mid])
        {
            if (target <= nums[right] && target > nums[mid])
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        else
        {
            if (target >= nums[left] && target < nums[mid])
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
    }
    return -1;
}
81. 搜索旋转排序数组 II-有重复值
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
bool search(vector<int>& nums, int target) {
	int left = 0, right = nums.size() - 1;

	while (left <= right)
	{
		while (left < right && nums[left] == nums[left + 1]) left++;
		while (left < right && nums[right] == nums[right - 1]) right--;
		int mid = (left + right) >> 1;
		if (nums[mid] == target) {
			return true;
		}
		if (nums[mid] > nums[right])
		{
			if (target >= nums[left] && target < nums[mid])
			{
				// [left, mid)
				right = mid - 1;
			}
			else
			{
				left = mid + 1;
			}
		}
		else
		{
			if (target <= nums[right] && target > nums[mid])
			{
				// (mid, right]
				left = mid + 1;
			}
			else
			{
				right = mid - 1;
			}
		}
	}
	return false;
}

153. 寻找旋转排序数组中的最小值-多次旋转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int findMin(vector<int>& nums) {
	int left = 0, right = nums.size() - 1;
	int minNumber = nums.front();
	while (left <= right)
	{
		int mid = (left + right) >> 1;
		/// 当nums[mid] > nums[right]时，说明最小值还在右边，mid在断崖的左边
        /// 当nums[mid] < nums[right]时，说明最小值还在左边，mid在断崖的右边
        
		if (nums[mid] < nums[right])
		{
			right = mid;	
		}
		else
		{
			left = mid + 1;
		}
	}
	return minNumber < nums[left-1] ? minNumber : nums[left-1];
}

4. 寻找两个正序数组的中位数
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
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
	int n = nums1.size();
	int m = nums2.size();
	if (n > m) {
		return findMedianSortedArrays(nums2, nums1);
	}
	int L1, L2, R1, R2, c1, c2, lo = 0, hi = 2 * n;
	while (lo <= hi) {
		c1 = (lo + hi) / 2;
		c2 = m + n - c1;
		L1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
		R1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2];
		L2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
		R2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2];
		if (L1 > R2) {
			hi = c1 - 1;
		}
		else if (L2 > R1) {
			lo = c1 + 1;
		}
		else {
			break;
		}
	}
	return (max(L1, L2) + min(R1, R2)) / 2.0;
}

c1 和 c2：分别表示在 nums1 和 nums2 中的分割线位置。

L1, R1, L2, R2：分别表示分割线左侧和右侧的元素。其中 L1 和 L2 是分割线左侧的元素，R1 和 R2 是分割线右侧的元素。

lo 和 hi：用于二分搜索的范围。

  1. c1 = (lo + hi) / 2;
    • 这里通过二分法计算 nums1 的分割线位置。lo 和 hi 是搜索的边界索引，c1 是当前的中点。这决定了在 nums1 中左侧将有多少个元素。
  2. c2 = m + n - c1;
    • c2 是 nums2 中的分割线位置。由于我们需要确保左右两部分的元素总数相等（或者在总数为奇数时，左侧比右侧多一个元素），c2 是根据 c1 和两个数组总长度计算得出。
  3. L1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
    • L1 是 nums1 中分割线左侧的元素。如果 c1 是 0，说明 nums1 的分割线在数组的最开始位置，左侧没有元素，因此 L1 赋值为 INT_MIN（一个非常小的数，表示没有元素的情况）。否则，L1 是分割线前的那个元素。
  4. R1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2];
    • R1 是 nums1 中分割线右侧的元素。如果 c1 是 2 * n（即分割线在数组的最末端之后），说明 nums1 的右侧没有元素，因此 R1 赋值为 INT_MAX（一个非常大的数，表示没有元素的情况）。否则，R1 是分割线上的元素。
  5. L2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
    • L2 是 nums2 中分割线左侧的元素。与 L1 的计算类似，如果 c2 是 0，说明 nums2 的分割线在数组的最开始位置，因此 L2 也赋值为 INT_MIN。
  6. R2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2];
    • R2 是 nums2 中分割线右侧的元素。与 R1 的计算类似，如果 c2 是 2 * m，说明 nums2 的右侧没有元素，因此 R2 赋值为 INT_MAX。
滑动窗口

今天完成了大部分滑动窗口的题，经过总结发现，滑动窗口的题型分为2种类型：
1.窗口长度不变 [见下图1]

参考题型:643、2379、3、53、424、438、713、1343、239、480

2.窗口长度变化 [见下图2]
在练习完LC上的一些滑动窗口的题后，绝大部分的题是2，1的还没见过，所以重点应该是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
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
# 1.窗口长度固定不变的代码框架伪代码示例
滑动窗口(arr, 目标条件)
{
    初始化 low = 0, high = 0
    初始化 windowsize = k;
    
    while (high < 窗口长度)
    {
    	// 1. 制造的一个 windowsize 窗口
        if (high - low + 1 < windowsize)
        {
        	可以做一些逐步创建窗口的事情
       		
            high++;
        }
        // 2. 移动窗口并处理
        else
        {
            // 此时窗口大小是等于 windowsize
            // 基于当前窗口计算答案
            // 删除最左边的旧的元素，更新window
            // 添加新的元素
            // 递增low 与 high
        }
    }
    // 需要注意的是由于将递增low & high移动到了后面可在退出循环后既high=wndlenght，此时low也要向右移动，我们没有判断这种情况，所以可能需要在后面添加判断left右移的情况
    do something with left decrease
}

# 2.窗口长度变化的代码框架伪代码示例
variable_window()
{
    int start = 0, end = 0;
    while (end < n)
    {
        /* Case 1: 增加窗口大小
           如果这个有限制窗口的一个大小滑动则有这个判断条件，但是一般无
        */
        if (end - start + 1 < k)
        {
            end++;
        }

        /* Case 2: 达到窗口期望大小k
           如果这个窗口达到了期望的大小k则计算结果，但是一般无
        */
        else if (end - start + 1 == k)
        {
            // Perform the required calculations or operations to obtain the answer
            // Store the answer in a variable (ans)

            end++;
        }

        /* Case 3: Reduce the window size
           If the window size is greater than the desired value (k), adjust the window by moving the start index
        */
        else if (end - start + 1 > k)
        {
            while (end - start + 1 > k)
            {
                // Remove calculations or operations involving the element at the start index

                start++;
            }

            // Check if the window size becomes equal to the desired value (k) after adjustment
            if (end - start + 1 == k)
            {
                // Perform calculations or operations and store the answer if necessary
            }

            end++;
        }
    }

    // Return the final answer (ans)
}

滑动窗口(arr, 目标条件)
{
    初始化 left = 0, right = 0
    初始化结果集 result

    while right < arr 的长度
    {
        扩展右边界
        right 向右移动，增加窗口内的元素
        根据 arr[right] 的添加更新窗口状态

        while 当前窗口满足目标条件?
        {
            更新结果 result（如最小长度、最大长度、最大和等）

            收缩左边界
            根据 arr[left] 的去除更新窗口状态
            left 向右移动，减小窗口内的元素
        }
    }
    返回结果 result
}

推荐阅读的解说文章-需要网络工具

76.最小覆盖子串
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
void operationAdd(unordered_map<char, int>& wnd, unordered_map<char, int>& tgt,char newC,int & vaild) {
    if (tgt.find(newC) != tgt.end())
    {
        wnd[newC]++;
        if (wnd[newC] == tgt[newC])
            vaild++;
    }
}

void operationDel(unordered_map<char, int>& wnd, unordered_map<char, int>& tgt, char delC, int& vaild) {
    if (tgt.find(delC) != tgt.end())
    {
        if (wnd[delC] == tgt[delC])
            vaild--;
        wnd[delC]--;
    }
}

string minWindow(string s, string t) {
    string minSubString("");
    unordered_map<char, int> wndkv, tgtkv;
    int start = 0, subLen = INT_MAX;
    for (auto c : t)
        tgtkv[c]++;
    int vaildChar = 0;

    int left = 0, right = 0;
    while (right<s.length())
    {
        /// 扩展右边界
        char newc = s[right++];
        operationAdd(wndkv, tgtkv, newc, vaildChar);

        while (left < right && vaildChar == tgtkv.size())
        {
            /// 更新状态 子串
            if (subLen > right - left) {
                subLen = right - left;
                start = left;
            }
            
            /// 缩小左边界
            char delC = s[left++];
            operationDel(wndkv, tgtkv, delC, vaildChar);
        }
    }
    return subLen == INT_MAX ? "" : s.substr(start, subLen);
}

567. 字符串的排列
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
void operationAdd(unordered_map<char, int>& wnd, unordered_map<char, int>& tgt, char newC, int& vaild) {
    if (tgt.find(newC) != tgt.end())
    {
        wnd[newC]++;
        if (wnd[newC] == tgt[newC])
            vaild++;
    }
}
void operationDel(unordered_map<char, int>& wnd, unordered_map<char, int>& tgt, char delC, int& vaild) {
    if (tgt.find(delC) != tgt.end())
    {
        if (wnd[delC] == tgt[delC])
            vaild--;
        wnd[delC]--;
    }
}

bool checkInclusion(string t, string s) {
    unordered_map<char, int> wndkv, tgtkv;
    for (auto c : t)
        tgtkv[c]++;
    int vaildC = 0;
    int left = 0, right = 0;

    while (right < s.size()) {
        if (right - left + 1 <= t.size()) {
            operationAdd(wndkv, tgtkv, s[right], vaildC);
            right++;
        }
        else {
            if (vaildC == tgtkv.size()) {
                return true;
            }

            operationDel(wndkv, tgtkv, s[left], vaildC);
            if (right < s.size()) {
                operationAdd(wndkv, tgtkv, s[right], vaildC);
            }
            left++;
            right++;
        }
    }
    return vaildC == tgtkv.size();
}
438. 找到字符串中所有字母异位词
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
   void operationAdd(unordered_map<char, int>& wnd, unordered_map<char, int>& tgt, char newC, int& vaild) {
    if (tgt.find(newC) != tgt.end())
    {
        wnd[newC]++;
        if (wnd[newC] == tgt[newC])
            vaild++;
    }
}
void operationDel(unordered_map<char, int>& wnd, unordered_map<char, int>& tgt, char delC, int& vaild) {
    if (tgt.find(delC) != tgt.end())
    {
        if (wnd[delC] == tgt[delC])
            vaild--;
        wnd[delC]--;
    }
}
vector<int> findAnagrams(string s, string t) {
    unordered_map<char, int> wndkv, tgtkv;
    for (auto c : t)
        tgtkv[c]++;
    int vaildC = 0;
    int left = 0, right = 0;

    vector<int> startIndexes;

    while (right < s.size()) {
        if (right - left + 1 <= t.size()) {
            operationAdd(wndkv, tgtkv, s[right], vaildC);
            right++;
        }
        else {
            if (vaildC == tgtkv.size()) {
                startIndexes.push_back(left);
            }

            operationDel(wndkv, tgtkv, s[left], vaildC);
            if (right < s.size()) {
                operationAdd(wndkv, tgtkv, s[right], vaildC);
            }
            left++;
            right++;
        }
    }
    if (vaildC == tgtkv.size()) {
                startIndexes.push_back(left);
    }
    return startIndexes;
}

209.长度最小的子数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int minSubArrayLen(int target, vector<int>& nums) {
    int left = 0, right = 0;
    int start = 0, len = INT_MAX;

    int sum = 0;

    while (right < nums.size())
    {
        sum += nums[right];
        right++;
        while (sum >= target)
        {
            len = len > right - left ? right - left : len;
            sum -= nums[left];
            left++;
        }
    }
    return  len == INT_MAX ? 0 : len;
}
3. 无重复字符的最长子串
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
/// 动态滑动窗口？？？   
int lengthOfLongestSubstring(string s) {
    unordered_set<char> rec;
    int startIndex = 0;
    int curLength = 0;
    int maxlen = 0;

    int left = 0, right = 0;
    while (right < s.size())
    {
        char toAdd = s[right];
        if (rec.find(toAdd) == rec.end())
        {
            rec.insert(toAdd);
            curLength++;
            right++;

            maxlen = curLength > maxlen ? curLength : maxlen;
        }
        else
        {
            char toDel = s[left++];
            startIndex = left;
            curLength--;
            rec.erase(toDel);
        }
    }
    return maxlen;
}
128. 最长连续序列
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
int longestConsecutive(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int left = 0, right = 0;
    int maxLength = 0;
    int tempLength = 0;
    while (right<nums.size())
    {
        if (right == left)
        {
            tempLength++;
            maxLength = tempLength > maxLength ? tempLength : maxLength;
            right++;
        }
        else
        {
            if (nums[right] == nums[right - 1] + 1)
            {
                /// 若我们的 nums[right] 比前一位大1，则连续
                tempLength++;
                maxLength = tempLength > maxLength ? tempLength : maxLength;
                right++;
            }
            else if (nums[right] == nums[right - 1])
            {
                /// 相等前后位，则不管
                maxLength = tempLength > maxLength ? tempLength : maxLength;
                right++;
            }
            else
            {
                /// 此时right下标位置开始不连续了，则更新left和right
                // 更新left
                left = right;
                tempLength = 1;
                maxLength = tempLength > maxLength ? tempLength : maxLength;
                right++;
            }
        }
    }
    return maxLength;
}
239. 滑动窗口最大值*
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
82
83
84
85
86
87
88
/// 超时
int findMax(vector<int>& vec, int startIndex, int endIndex)
{
    vector<int> v((vec.begin() + startIndex), (vec.begin() + endIndex + 1));
    sort(v.begin(), v.end());
    return v.back();
}

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> resultMax;
    int left = 0;
    int right = 0;
    int maxValue = -10001;
    int currentWndSize = 0;
    
    priority_queue<int> pq;


    while (right < nums.size())
    {
        /// 1.构建第一个窗口
        if (right - left + 1 < k)
        {
            right++;
        }
        else {
            /// 2. 滑动
            int max = findMax(nums, left, right);
            resultMax.push_back(max);
            left++;
            right++;
        }
    }
    return resultMax;
}
// 
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> resultMax;
    if (nums.empty() || k <= 0) return resultMax;

    priority_queue<pair<int, int>> pq; // 优先队列，存储值和对应的索引
    unordered_map<int, int> countMap; // 哈希表，跟踪窗口中元素的计数

    for (int i = 0; i < nums.size(); ++i) {
        // 当窗口滑动超过k个元素，减少最左侧元素的计数
        if (i >= k) {
            countMap[nums[i - k]]--;
        }

        // 添加新元素到优先队列和哈希表
        pq.push({nums[i], i});
        countMap[nums[i]]++;

        // 当窗口大小为k时，从优先队列中找到有效的最大值
        if (i >= k - 1) {
            while (!pq.empty() && countMap[pq.top().first] <= 0) {
                pq.pop(); // 移除无效的最大值
            }
            resultMax.push_back(pq.top().first);
        }
    }
    return resultMax;
}

//
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> resultMax;
    if (nums.empty() || k <= 0) return resultMax;
    deque<int> dq; // 存储数组索引

    for (int i = 0; i < nums.size(); ++i) {
        // 移除超出滑动窗口左边界的元素索引
        if (!dq.empty() && dq.front() == i - k) {
            dq.pop_front();
        }
        // 移除所有小于当前元素的索引，保持队列从大到小
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }
        // 添加当前元素的索引
        dq.push_back(i);
        // 当窗口大小为k时，将对应的元素（队列的前端）添加到结果
        if (i >= k - 1) {
            resultMax.push_back(nums[dq.front()]);
        }
    }
    return resultMax;
}
n数和问题
167.两数和II - 数组有序

特殊情况，本题数组为有序数组，且本题答案需要返回的是+1下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 二分法 - 有序的时候使用
vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0, right = numbers.size() - 1;
    vector<int> vec;
    while (left < right)
    {
        int sum = numbers[left] + numbers[right];
        
        if (sum == target)
            return { left+1,right+1 };
        else if (sum > target) {
            right--;
        }
        else if (sum < target) {
            left++;
        }
    }
    return { -1,-1 };
}
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
// 暴力
vector<int> twoSum(vector<int>& numbers, int target) {
    for (int i = 0; i < numbers.size(); i++)
    {
        int num1 = numbers[i];
        for (int j = i + 1; j < numbers.size(); j++)
        {
            int num2 = numbers[j];
            if (num1 + num2 == target)
            {
                return { i,j };
            }
        }
    }
    return { -1,-1 };
}
// hashmap法 - hash适用
vector<int> twoSum(vector<int>& numbers, int target) {
    unordered_map<int, int> mp;
    for (int i = 0; i < numbers.size(); i++)
    {
        auto it = mp.find(target - numbers[i]);
        if (it != mp.end())
        {
            int j = (*it).second;
            return{ i,j };
        }
        mp[numbers[i]] = i;
    }
    return { -1,-1 };
}

本题无序数组的也可以用1.的解法，只不过需要将数组排序后应用1.题的解法，需要修改返回的是值了，而非下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> twoSum(vector<int>& nums, int target) {
 // 先对数组排序
 sort(nums.begin(), nums.end());
 // 左右指针
 int lo = 0, hi = nums.size() - 1;
 while (lo < hi) {
     int sum = nums[lo] + nums[hi];
     // 根据 sum 和 target 的比较，移动左右指针
     if (sum < target) {
         lo++;
     } else if (sum > target) {
         hi--;
     } else if (sum == target) {
         return {nums[lo], nums[hi]};
     }
 }
 return {};
}

拓展-2数和-数组无序-多对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<int>> twoSumTarget(vector<int>& nums, int target, int start) {
    // 先对数组排序，此处排序可以移到外层实现
    sort(nums.begin(), nums.end());
    //
    vector<vector<int>> res;
    int lo = start, hi = nums.size() - 1;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        // 记录索引 lo 和 hi 最初对应的值
        int left = nums[lo], right = nums[hi];
        if (sum < target)      lo++;
        else if (sum > target) hi--;
        else {
            res.push_back({ left, right });
            // 跳过所有重复的元素
            while (lo < hi && nums[lo] == left) lo++;
            while (lo < hi && nums[hi] == right) hi--;
        }
    }
    return res;
}
15.三数和-无序数组
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
vector<vector<int>> twoSumTarget(vector<int>& nums, int target, int start) {
        vector<vector<int>> res;
        int lo = start, hi = nums.size() - 1;
        while (lo < hi) {
            int sum = nums[lo] + nums[hi];
            // 记录索引 lo 和 hi 最初对应的值
            int left = nums[lo], right = nums[hi];
            if (sum < target)      lo++;
            else if (sum > target) hi--;
            else {
                res.push_back({ left, right });
                // 跳过所有重复的元素
                while (lo < hi && nums[lo] == left) lo++;
                while (lo < hi && nums[hi] == right) hi--;
            }
        }
        return res;
    }

    vector<vector<int>> threeSumTarget(vector<int>& nums, int target,int start) {
        vector<vector<int>> res;
        // 先对数组排序，此处排序可以移到外层实现
        sort(nums.begin(), nums.end());
        for (int i = start; i < nums.size(); i++)
        {
            vector<vector<int>>tuple = twoSumTarget(nums, target - nums[i], i + 1);
            for (auto tp : tuple)
            {
                tp.push_back(nums[i]);
                res.push_back(tp);
            }
            // 跳过重复数字
            while (i < nums.size() - 1 && nums[i] == nums[i + 1]) i++;
        }
        return res;
    }
18.四数和-无序数组
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
vector<vector<int>> twoSumTarget(vector<int>& nums, long target, int start) {
    vector<vector<int>> res;
    int lo = start, hi = nums.size() - 1;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        // 记录索引 lo 和 hi 最初对应的值
        int left = nums[lo], right = nums[hi];
        if (sum < target)      lo++;
        else if (sum > target) hi--;
        else {
            res.push_back({ left, right });
            // 跳过所有重复的元素
            while (lo < hi && nums[lo] == left) lo++;
            while (lo < hi && nums[hi] == right) hi--;
        }
    }
    return res;
}

vector<vector<int>> threeSumTarget(vector<int>& nums, long target,int start) {
    vector<vector<int>> res;
    for (int i = start; i < nums.size(); i++)
    {
        vector<vector<int>>tuple = twoSumTarget(nums, target - nums[i], i + 1);
        for (auto tp : tuple)
        {
            tp.push_back(nums[i]);
            res.push_back(tp);
        }
        // 跳过重复数字
        while (i < nums.size() - 1 && nums[i] == nums[i + 1]) i++;
    }
    return res;
}

vector<vector<int>> fourSumTarget(vector<int>& nums, long target,int start) {
    // 先对数组排序，此处排序可以移到外层实现
    sort(nums.begin(), nums.end());

    vector<vector<int>> res;
    for (int i = start; i < nums.size(); i++)
    {
        vector<vector<int>>triple = threeSumTarget(nums, target - nums[i], i + 1);
        for (auto trp : triple)
        {
            trp.push_back(nums[i]);
            res.push_back(trp);
        }
        // 跳过重复数字
        while (i < nums.size() - 1 && nums[i] == nums[i + 1]) i++;
    }
    return res;
}

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/// 使用前请先调用sort排序
sort(nums.begin(), nums.end());
vector<vector<int>> nSumTarget(vector<int>& nums,int n, long target, int start)
{
 vector<vector<int>> res;
 int len = nums.size();
 if (n == 2) {
     return twoSumTarget(nums, target, start);
 }
 else
 {
     for (int i = start; i < nums.size(); i++) {
         vector<vector<int>>vc = nSumTarget(nums,n-1,target - nums[i], i + 1);
         for (auto v : vc)
         {
             v.push_back(nums[i]);
             res.push_back(v);
         }
         while (i < nums.size() - 1 && nums[i] == nums[i + 1]) i++;
     }
 }
 return res;
}

/// 这个是核心!
vector<vector<int>> twoSumTarget(vector<int>& nums, long target, int start) {
 vector<vector<int>> res;
 int lo = start, hi = nums.size() - 1;
 while (lo < hi) {
     int sum = nums[lo] + nums[hi];
     // 记录索引 lo 和 hi 最初对应的值
     int left = nums[lo], right = nums[hi];
     if (sum < target)      lo++;
     else if (sum > target) hi--;
     else {
         res.push_back({ left, right });
         // 跳过所有重复的元素
         while (lo < hi && nums[lo] == left) lo++;
         while (lo < hi && nums[hi] == right) hi--;
     }
 }
 return res;
}
数组前缀和
303. 区域和检索 - 数组不可变
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class NumArray {
private:
    vector<int> sums;
public:
    NumArray(vector<int>& nums) {
        sums.resize(nums.size()+1,0);
        for (int i = 0; i < nums.size(); i++)
        {
            sums[i+1] = sums[i] + nums[i];
        }
    }

    int sumRange(int left, int right) {
        return sums[right+1] - sums[left];
    }
};
304. 二维区域和检索 - 矩阵不可变
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class NumMatrix {
private:
    vector<vector<int>> sums;

public:
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix.front().size();
        sums.resize(m + 1, vector<int>(n + 1, 0));

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                sums[i + 1][j + 1] = sums[i + 1][j] + sums[i][j + 1] - sums[i][j] + matrix[i][j];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return sums[row2 + 1][col2 + 1] - sums[row2 + 1][col1] - sums[row1][col2 + 1] + sums[row1][col1];
    }
};
前缀和&hash表结合问题

本类型为前缀和和hash结合问题，思路较为常规：

1
2
3
4
5
6
7
prefix_Arr = CreatePrefixArr(nums_arr);
hash_map prefix_index_kv;
hash(prefix_Arr,prefix_index_kv);
for(i=1;i<prefix len;i++):
	need = target - prefix_Arr[i]
	prefix_index_kv.contain(need)
	...
523. 连续的子数组和 - 涉及hash
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
// 1.暴力
bool checkSubarraySum(vector<int>& nums, int k) {
    vector<int> prefix = prefixSum(nums);
    
    for (int i = 0; i < prefix.size(); i++)
    {
        int sum = 0;
        for (int j = i+1; j < prefix.size(); j++)
        {
            sum = prefix[j] - prefix[i];
            if (sum % k == 0 && (j - i)> 1)
            {
                return true;
            }
        }
    }
    return false;
}
// 2.非暴力
bool checkSubarraySum(vector<int>& nums, int k) {
    vector<int> prefix(nums.size() + 1, 0);
    for (int i = 0; i < nums.size(); i++)
    {
        prefix[i + 1] = prefix[i] + nums[i];
    }

    unordered_map<int, int> v2i;
    for (int i = 0; i < prefix.size(); i++)
    {
        int val = prefix[i] % k;
        if (v2i.find(val) == v2i.end())
            v2i[val] = i;
    }
    for (int i = 0; i < prefix.size(); i++)
    {
        int need = prefix[i] % k;
        if (v2i.find(need) != v2i.end() && (i - v2i[need] > 1))
        {
            return true;
        }
    }
    return false;
}
525. 连续数组 - 涉及hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int findMaxLength(vector<int>& nums) {
    vector<int> prefix(nums.size() + 1, 0);
    for (int i = 0; i < nums.size(); i++)
        prefix[i + 1] = (nums[i] == 0 ? -1 : 1) + prefix[i];

    unordered_map<int, int> v2im;
    int len = 0;
    for (int i = 0; i < prefix.size(); i++)
    {
        if (v2im.find(prefix[i]) == v2im.end()) {
            v2im[prefix[i]] = i;
        }
        else
        {
            len = std::max(len, i - v2im[prefix[i]]);
        }
    }
    return len;
}
560. 和为 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
int subarraySum(vector<int>& nums, int k) {
    vector<int> prefix(nums.size() + 1, 0);
    unordered_map<int, int> preSum_count_kv;
    preSum_count_kv[0] = 1;

    int res = 0;
    for (int i = 0; i < nums.size(); i++)
    {
        prefix[i + 1] = prefix[i] + nums[i];

        int target = prefix[i+1] - k;
        if (preSum_count_kv.find(target) != preSum_count_kv.end())
        {
            res += preSum_count_kv[target];
        }
        if (preSum_count_kv.find(prefix[i+1]) != preSum_count_kv.end()) {
            preSum_count_kv[prefix[i+1]]++;
        }
        else
        {
            preSum_count_kv[prefix[i+1]] = 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
class Dif {
private:
    vector<int> dec;
public:
    Dif(vector<int> target) {
        dec.push_back(target.front());

        for (int i = 1; i < target.size(); i++)
        {
            dec.push_back(target[i] - target[i-1]);
        }
    }

    void operation(int i, int j, int val) {
        dec[i] += val;
        if (j + 1 < dec.size())
            dec[j + 1] -= val;

    }

    vector<int> getResult()
    {
        vector<int> vec;
        vec.push_back(dec.front());

        for (int i = 1; i < dec.size(); i++)
        {
            vec.push_back(vec.back() + dec[i]);
        }
       
        return vec;
    }
};
其它
56. 合并区间
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
bool Compare(const vector<int>& lf, const vector<int>& rg)
{
	return lf[0] < rg[0];
}

vector<vector<int>> merge(vector<vector<int>>& intervals) {
	std::sort(intervals.begin(), intervals.end(), Compare);

	vector<vector<int>> result;
	result.push_back(intervals.front());
	for (auto& toAdd : intervals)
	{
		vector<int> last = result.back();
		if (last[1] < toAdd[0])
		{
			/// 区间不∩
			result.push_back(toAdd);
			continue;
		}
		if (last[1] >= toAdd[1])
			/// 区间子集
			continue;
		/// 区间相交
		(*(result.end() - 1))[1] = toAdd[1];
	}
	return result;
}
189. 轮转数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void myreverse(vector<int>& nums, int startIndex, int endIndex)
{
	int left = startIndex;
	int right = endIndex;
	while (left < right)
	{
		int temp = nums[left];
		nums[left] = nums[right];
		nums[right] = temp;
		left++;
		right--;
	}
}

void rotate(vector<int>& nums, int k) {
	if (k == 0 || nums.size() <= 1)
		return;
	k = k % nums.size();
	myreverse(nums, 0, nums.size() - 1);
	myreverse(nums, 0, k - 1);
	myreverse(nums, k, nums.size() - 1);
}
238. 除自身以外数组的乘积
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> productExceptSelf(vector<int>& nums) {
	int pre = 1;
	int suf = 1;
	int n = nums.size();
	vector<int> result(nums);
	for (int i = 0; i < n; i++) {
		result[i] = pre;
		pre *= nums[i];
	}
	for (int j = n - 1; j >= 0; j--) {
		result[j] *= suf;
		suf *= nums[j];
	}
	return result;
}
41. 缺失的第一个正数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int firstMissingPositive(vector<int>& nums) {
	for (int i = 0; i < nums.size(); i++)
	{
		while (nums[i] > 0 && nums[i] <= nums.size() && nums[nums[i] - 1] != nums[i])
		{
			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;
}
// 我们知道如果nums不空缺任何数字的话，那么nums排序号后，数字就应该和索引对应
// 再此遍历nums，如果nums的值和索引不对应的话，那么那个索引就是我们需要的结果

链表

链表相关问题本节按照类型进行分类完成整理，基础问题包括链表的一系列需要练习的较为基础的操作，可作为工具子函数使用；

注意事项：

  1. 前缀后缀–问题

链表常用循环查找第index节点问题，这里需要注意的一点的是前缀–和后缀–的差别：

  • while(index--)：先检查值，再执行减法。循环次数等于初始index值。
  • while(--index)：先执行减法，再检查值。循环次数等于初始index值减一

如果需要从初始值开始处理，使用while(index--)；如果需要从初始值减一开始处理，使用while(--index)

  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
public class ListNode {
	public int val;
	public ListNode? next;
	public ListNode(int val = 0, ListNode? next = null)
	{
		this.val = val;
		this.next = next;
	}
}
	
public static ListNode? RemoveListNode(ListNode? head,int val)
{
	ListNode dummy = new(-1, head);
	ListNode? current = dummy;
	while(current.next != null)
	{
		if(val == current.next.val)
		{
			current.next = current.next.next;
		}
		else
		{
			current = current.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
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* RemoveElements(ListNode* head, int val)
{
    ListNode* tempHead = new ListNode(0);
    tempHead->next = head;
    ListNode* current = tempHead;
    while (current->next != nullptr)
    {
        if (current->next->val == val)
        {
            ListNode* temp = current->next;
		 current->next = current->next->next;
            delete temp;
	 }
        else
        {
		 current = current->next;
	 }
    }
    return tempHead->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
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
struct ListNode {
	int val;
	ListNode *next;

    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class MyLinkedList {
private:
    ListNode* fakeHead;
	int size;

public:
    MyLinkedList() {
        fakeHead = new ListNode(-1);
        size = 0;
    }

    int get(int index) {
        if (index < 0 || index > (size - 1))
        {
			return -1;
		}
        ListNode* cur = fakeHead->next;
        while (index--)
        {
            cur = cur->next;
        }
        return cur->val;
    }

    void addAtHead(int val) {
        ListNode* newNode = new ListNode(val);
        newNode->next = fakeHead->next;
        fakeHead->next = newNode;
        size++;
    }

    void addAtTail(int val) {
        ListNode*  newNode = new ListNode(val), *cur = fakeHead;
        while (cur->next != nullptr)
        {
			cur = cur->next;
		}
        cur->next = newNode;
		size++;
    }

    void addAtIndex(int index, int val) {
        if (index < 0) {
            addAtHead(val);
            return;
        }
        else if (index > size) {
			return;
		}
        else
        {
            ListNode* newNode = new ListNode(val), *cur = fakeHead;
            while (index--)
            {
				cur = cur->next;
			}
			newNode->next = cur->next;
			cur->next = newNode;
			size++;
        }
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        ListNode* cur = fakeHead;
        while (index--)
        {
            cur = cur->next;
        }
        ListNode* temp = cur->next;
        cur->next = cur->next->next;
        delete temp;
        temp = nullptr;
        size--;
    }

    void printLinkedList() {
        ListNode* cur = fakeHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
};
翻转链表
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
/// 迭代版
ListNode* Reverse(ListNode* head) {
	if (head == nullptr || head->next == nullptr)
	{
		return head;
	}
	else
	{
		ListNode* newHead = nullptr, *cur = head;
		while (cur != nullptr)
		{
			// 记录下一个节点
			ListNode* after = cur->next;
			// 拆
			cur->next = newHead;
			// 更新newHead
			newHead = cur;
			// 更新cur
			cur = after;
		}
		return newHead;
	}
}
/// 递归法

两两交换链表节点
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
/// 迭代版
ListNode* swapPairs(ListNode* head) {
	ListNode* tempHead = new ListNode(-1, head);
	if (head == nullptr || head->next == nullptr)
	{
		return tempHead->next;
	}
	// ...tH(prev) -> a(head) -> b -> c(nextPair) -> ...
	
	ListNode* cur = tempHead;
	while (cur != nullptr && cur->next != nullptr && cur->next->next != nullptr)
	{
		ListNode* a = cur->next;
		ListNode* b = a->next;
		ListNode* c = b->next;
		// ...tH(prev) -> a(head) -> b -> c(nextPair) -> ...
		cur->next = b;
		b->next = a;
		a->next = c;
		// ...tH(prev) -> b -> a(head) -> c(nextPair) -> ...
		cur = a;
	}		
	ListNode* result = tempHead->next;
	delete tempHead;
	return result;
}

/// 递归版本
ListNode* swapPairs(ListNode* head) {
	// ...->nullptr
	// head->nullptr
    // 1.终止条件检查
	if (head == nullptr || head->next == nullptr)
	{
		return head;
	}
    // 2.1对当前问题进行一些处理或简化，准备下一步递归
	ListNode* next = head->next;
    // 2.2递归调用自身，解决更小或更简化的问题
	head->next = swapPairs(next->next);
    // 2.3使用递归得到的结果来构建当前问题的解
	next->next = head;
    // 3.返回当前问题的解
	return next;
}
删除链表倒数N个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

ListNode* removeNthFromEnd(ListNode* head, int n) {
	ListNode* tempHead = new ListNode(-1, head);
	ListNode* slow = tempHead,*fast = tempHead;
	// Move fast pointer to the nth node from the beginning, move n+1 steps
	n=n+1;
	while ((n--) && fast != nullptr)
	{
		fast = fast->next;
	}
	// Move fast to the end, maintaining the gap
	while (fast != nullptr) {
		slow = slow->next;
		fast = fast->next;
	}
	// Remove the nth node from the end
	ListNode* temp = slow->next;
	slow->next = slow->next->next;
	delete temp;
	return tempHead->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
37
38
39
40
41
42
43
44
45
46
int GetLength(ListNode* head)
{
	int length = 0;
	while (head != nullptr)
	{
		length++;
		head = head->next;
	}
	return length;
}

ListNode* Move(ListNode* head, int step)
{
	while (step--)
	{
		head = head->next;
	}
	return head;
}

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
	int lengthA = GetLength(headA);
	int lengthB = GetLength(headB);
	ListNode* newA_start = headA;
	ListNode* newB_start = headB;

	if (lengthA > lengthB)
	{
		newA_start = Move(headA, lengthA - lengthB);
	}
	else
	{
		newB_start = Move(headB, lengthB - lengthA);
	}

	while (newA_start != nullptr && newB_start != nullptr)
	{
		if (newA_start == newB_start)
		{
			return newA_start;
		}
		newA_start = newA_start->next;
		newB_start = newB_start->next;
	}
	return nullptr;
}
环链表

两个问题：是否环；环入口；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ListNode* detectCycle(ListNode* head) {
	ListNode* tmpHead = new ListNode(-1,head);
	ListNode* slow = tmpHead;
	ListNode* fast = tmpHead;

	while (fast != nullptr && fast->next != nullptr) {
		slow = slow->next;
		fast = fast->next->next;
		if (slow == fast) {
			ListNode* slow2 = tmpHead;
			while (slow2 != slow) {
				slow = slow->next;
				slow2 = slow2->next;
			}
			delete tmpHead;
			return slow;
		}
	}
	delete tmpHead;
	return nullptr;
}

快慢指针

83.删除排序链表重复元素

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
void DelNodes(ListNode* head)
{
    while (head != nullptr)
    {
        ListNode* nxt = head->next;
        delete head;
        head = nxt;
    }
}
ListNode* deleteDuplicates(ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;

    while (fast != nullptr)
    {
        if (fast->val != slow->val)
        {
            slow = slow->next;
            slow->val = fast->val;
        }
        fast = fast->next;
    }

    if (slow != nullptr)
    {
        DelNodes(slow->next);
        slow->next = nullptr;
    }
    return head;
}

递归问题解释

递归法解释：

问题定义:QN问题定义: Q_{N} 问题Q能够在NN步递归完成求解，其中Qi(i∈N)Q_{i}(i \in N)指的是第ii步时问题的解，假设递归求解公式Rm(...),m∈MR_{m}(...),m \in M，展开有：

Result=R1(R2(R3(...(RN(minquesetion)...)))Result = R_{1}(R_{2}(R_{3}(...(R_{N}(min_{quesetion})...)))

对∀Qj\forall Q_{j}第jj个问题的解为Rj(...)R_{j}(...), 由于是递归，即每一步处理问题方式是相同的(终止条件时除外)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
recursiveFunction(problem) {
# 1.终止条件检查
if (isBaseCase(problem)) {
 return baseCaseSolution(problem)
}

# 2.1对当前问题进行一些处理或简化，准备下一步递归
smallerProblem = prepareForRecursion(problem)    
# 2.2递归调用自身，解决更小或更简化的问题
result_of_Recursion = recursiveFunction(smallerProblem)

# 2.3使用递归得到的结果来构建当前问题的解
resultForCurrentProblem = SolutionFromRecursion(result_of_Recursion, problem)

# 3.返回当前问题的解
return resultForCurrentProblem
}

所以玩明白递归我们要做的是：

  1. 终止条件是什么？
  2. 当前一层递归要干什么？
  3. 返回给上一层是什么？

二叉树

解释

“动态规划关注整棵「子树」，回溯算法关注节点间的「树枝」，DFS 算法关注单个「节点」”

动归/DFS/回溯算法都可以看做二叉树问题的扩展，只是它们的关注点不同：

  • 动态规划算法属于分解问题的思路，它的关注点在整棵「子树」。
  • 回溯算法属于遍历的思路，它的关注点在节点间的「树枝」。
  • DFS 算法属于遍历的思路，它的关注点在单个「节点」

二叉树解题的思维模式分两类：

1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。

2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。

以上内容来自于labuladong

个人总结

二叉树相关解题思维：1.遍历类型 2.递归子问题类型

个人认为他们二者最大区别就是递归类型可能涉及到子问题解答返回子问题的解，而遍历类型一般不返回东西。其中视作为前序遍历和后序遍历的问题，我们可以把前序遍历看作遍历类型，后序遍历看成递归类型（将我们的函数设置为返回来自于上层的某些值）

实际上，1和2区别就是后者为后序遍历可以获得来自于子问题的解进而构造出当前问题的解，前者为前序遍历，只能处理当前问题。

普通二叉树
226. 翻转二叉树
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
// 分解问题的思维
TreeNode* invertTree(TreeNode* root) {
    // 定义终止条件
    if (root == nullptr)
    {
		return nullptr;
    }
    // 分解子问题: 
    // 子问题是根节点下左子树和右子树交换
	TreeNode* left = invertTree(root->left);
	TreeNode* right = invertTree(root->right);
	// 使用递归得到的结果来构建当前问题的解:合并子问题
	root->left = right;
	root->right = left;
    return root;
}

// 遍历思维
TreeNode* invertTree(TreeNode* root) {
    // 遍历二叉树，交换每个节点的子节点
    traverse(root);
    return root;
}

void traverse(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    // 每一个节点需要做的事就是交换它的左右子节点
    TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;

    // 遍历框架，去遍历左右子树的节点
    traverse(root->left);
    traverse(root->right);
}

116. 填充每个节点的下一个右侧节点指针
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
// BFS
Node* connect(Node* root) {
    if (root == nullptr)
    {
        return nullptr;
    }

    queue<Node*> q;
	q.push(root);

    while (!q.empty())
    {
        int sz = q.size();
        for (int i = 0; i < sz; i++)
        {
            Node* node = q.front();
            q.pop();
            if(node->left!=nullptr)
				q.push(node->left);
			if (node->right != nullptr)
				q.push(node->right);
			if (i == sz - 1)
			{
				node->next = nullptr;
			}
			else
			{
				node->next = q.front();
			}
        }
    }
}
// 递归遍历
Node* connect(Node* root) {
    if (root == nullptr)
        return nullptr;
	connectTriple(root->left, root->right);
}

void connectTriple(Node* leftNode, Node* rightNode)
{
    if (leftNode == nullptr || rightNode == nullptr)
        return;
    leftNode->next = rightNode;
	connectTriple(leftNode->left, leftNode->right);
	connectTriple(rightNode->left, rightNode->right);
	connectTriple(leftNode->right, rightNode->left);
}
114. 二叉树展开为链表
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
/// 遍历
void PLR(TreeNode* root, TreeNode*& curLast) {
    if (root == nullptr)
        return;

    TreeNode* left = root->left;  // 保存左子树
    TreeNode* right = root->right;  // 保存右子树

    if (curLast != nullptr) {
        curLast->right = root;  // 将当前节点接到上一个节点的右子节点
        curLast->left = nullptr;  // 左子节点设为 nullptr
    }
    curLast = root;  // 更新 curLast 为当前节点

    PLR(left, curLast);  // 递归处理左子树
    PLR(right, curLast);  // 递归处理右子树
}

void flatten(TreeNode* root) {
    TreeNode* curLast = nullptr;  // 初始化 curLast
    PLR(root, curLast);
}

// 子问题分解思维

void flatten(TreeNode* root) {
    // base case
    if (root == nullptr) return;

    // 利用定义，把左右子树拉平
    flatten(root->left);
    flatten(root->right);

    // 1、左右子树已经被拉平成一条链表
    TreeNode* left = root->left;
    TreeNode* right = root->right;

    // 2、将左子树作为右子树
    root->left = nullptr;
    root->right = left;

    TreeNode* p = root;
    while (p->right != nullptr) {
        p = p->right;
    }
    p->right = right;
}

543. 二叉树的直径
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int diameterOfBinaryTree(TreeNode* root) {
	if (root == nullptr)
		return 0;
    int maxD = 0;
	traverse(root, maxD);
    return maxD;
}

int traverse(TreeNode* root,int& maxD)
{
    if (root == nullptr)
        return 0;
    int leftMax = traverse(root->left, maxD);
    int rightMax = traverse(root->right, maxD);

	maxD = max(maxD, leftMax + rightMax);
	return max(leftMax, rightMax) + 1;
}
654. 最大二叉树
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
int findMaxNum(vector<int>& nums, int startIndex, int endIndex)
{
	int maxNum = nums[startIndex];
	int maxIndex = startIndex;
	for (int i = startIndex + 1; i <= endIndex; i++)
	{
		if (nums[i] > maxNum)
		{
			maxNum = nums[i];
			maxIndex = i;
		}
	}
	return maxIndex;
}

TreeNode* constructMaximumBinaryTree(vector<int>& nums, int startIndex, int endIndex)
{
	if (startIndex > endIndex)
	{
		return nullptr;
	}
	int maxIndex = findMaxNum(nums, startIndex, endIndex);
	TreeNode* root = new TreeNode(nums[maxIndex]);
	root->left = constructMaximumBinaryTree(nums, startIndex, maxIndex - 1);
	root->right = constructMaximumBinaryTree(nums, maxIndex + 1, endIndex);
	return root;
}


TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
	return constructMaximumBinaryTree(nums, 0, nums.size() - 1);
}
105. 从前序与中序遍历序列构造二叉树
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
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
	return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
}

TreeNode* build(vector<int>& preorder, vector<int>& inorder, int preStart, int preEnd, int inStart, int inEnd)
{
	if (preStart > preEnd || inStart > inEnd)
	{
		return nullptr;
	}
	// 前序遍历的第一个节点就是根节点
	int rootVal = preorder[preStart];
	// 在中序遍历中定位根节点
	int index = 0;
	for (int i = inStart; i <= inEnd; i++)
	{
		if (inorder[i] == rootVal)
		{
			index = i;
			break;
		}
	}
	// 先把根节点建立出来
	TreeNode* root = new TreeNode(rootVal);
	int leftSize = index - inStart;
	// 左子树是在中序遍历中根节点的左边，右子树是在中序遍历中根节点的右边
	root->left = build(preorder, inorder, preStart + 1, preStart + leftSize, inStart, index - 1);
	root->right = build(preorder, inorder, preStart + leftSize + 1, preEnd, index + 1, inEnd);
	return root;
}
106. 从中序与后序遍历序列构造二叉树
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
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
	return build(inorder, postorder, 0, postorder.size() - 1, 0, inorder.size() - 1);
}

TreeNode* build(vector<int>& inorder, vector<int>& postorder, int postStart, int postEnd, int inStart, int inEnd)
{
    if (postStart > postEnd || inStart > inEnd)
    {
        return nullptr;
    }
	// 后序遍历的最后一个节点是根节点
    int rootVal = postorder[postEnd];
	// 在中序遍历中找到根节点的位置
	int index = 0;
	for (int i = inStart; i <= inEnd; i++)
	{
		if (inorder[i] == rootVal)
		{
			index = i;
			break;
		}
	}
    
	// 创建根节点
	TreeNode* root = new TreeNode(rootVal);
	// 左子树的节点个数
	int leftchildSz = index - inStart;
	// 递归构建左子树
	// postStart: 后序遍历的起始位置
	// postStart + leftchildSz - 1: 后序遍历的结束位置
	root->left = build(inorder, postorder, postStart, postStart + leftchildSz - 1, inStart, index - 1);
	// 递归构建右子树
	// postStart + leftchildSz: 后序遍历的起始位置
	// postEnd - 1: 后序遍历的结束位置
	root->right = build(inorder, postorder, postStart + leftchildSz, postEnd - 1, index + 1, inEnd);

	return root;
}
889. 根据前序和后序遍历构造二叉树
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
TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
	return build(preorder, postorder, 0, postorder.size() - 1, 0, preorder.size() - 1);
}

TreeNode* build(vector<int>& preorder, vector<int>& postorder, int postStart, int postEnd, int preStart, int preEnd)
{
	if (preStart > preEnd || postStart > postEnd)
		return nullptr;

	TreeNode* root = new TreeNode(preorder[preStart]);
	if (preStart == preEnd)
		return root;

	int leftRoot = preorder[preStart + 1];
	int leftRootIndex = -1;
	for (int i = postStart; i <= postEnd; i++)
	{
		if (postorder[i] == leftRoot)
		{
			leftRootIndex = i;
			break;
		}
	}
	// leftSize = leftRootIndex - postStart + 1
	// 为什么是leftRootIndex - postStart + 1，因为postStart到leftRootIndex是左子树的节点，leftRootIndex是左子树的根节点
	int leftSize = leftRootIndex - postStart + 1;
	root->left = build(preorder, postorder, postStart, leftRootIndex, preStart + 1, preStart + leftSize);
	root->right = build(preorder, postorder, leftRootIndex + 1, postEnd - 1, preStart + leftSize + 1, preEnd);
	return root;
}

为什么3者计算leftsize不一样？

  1. 前序与后序遍历构建树

在这个函数中：

1
int leftSize = leftRootIndex - postStart + 1;

这里的 +1 是必要的，因为包括了在 postorder 中从 postStart 到 leftRootIndex 的所有元素。这段表示整个左子树，因此需要包括起始点和终止点。

对于构建右子树，你不需要在 preStart + leftSize + 1 时再加一，因为 leftSize 已经正确地计算了左子树的节点数，而 preStart + leftSize 已经指向左子树的最后一个元素，所以 preStart + leftSize + 1 直接就是右子树的起始位置。

  1. 中序与后序遍历构建树

在这个代码中：

1
int leftchildSz = index - inStart;

leftchildSz 表示中序遍历中从 inStart 到找到的根节点的索引（不包含根节点自己）的元素数量。因为中序遍历的根节点把树分成严格的左右两部分，所以这里不需要额外的 +1，其计算已经足够描述左子树的边界。

  1. 前序与中序遍历构建树

这段代码：

1
int leftSize = index - inStart;

与中序与后序遍历构建树相同，leftSize 正确地描述了左子树包含的节点数量，无需额外调整。

652. 寻找重复的子树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
string serialize(unordered_map<string, int>& map, vector<TreeNode*>& res, TreeNode* root)
{
    if (!root)
        return "#";
    string lr = serialize(map, res, root->left);
	string rr = serialize(map, res, root->right);
    string seri = lr + "," + rr + "," + std::to_string(root->val);
    if (map[seri] == 1)
    {
        res.push_back(root);
    }
    map[seri]++;
    return seri;
}

vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
	unordered_map<string, int> map;
	vector<TreeNode*> res;
    serialize(map, res, root);
    return res;
}

101. 对称二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isSymmetric(TreeNode* root) {
	return isSymmetric(root->left, root->right);
}

bool isSymmetric(TreeNode* left, TreeNode* right) {
	if (left == nullptr && right == nullptr) {
		return true;
	}
	if (left == nullptr || right == nullptr) {
		return false;
	}
	return left->val == right->val && isSymmetric(left->left, right->right) && isSymmetric(left->right, right->left);
}

102. 二叉树的层序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
TreeNode* sortedArrayToBST(vector<int>& nums) {
	return createTree(nums, 0, nums.size() - 1);
}

TreeNode* createTree(vector<int>& nums, int left, int right)
{
	if(left>right)
		return nullptr;
	int mid = left + (right-left)/2;
	TreeNode* root = new TreeNode(nums[mid]);
	root->left = createTree(nums,left,mid-1);
	root->right = createTree(nums,mid+1,right);
	return root;
}
98. 验证二叉搜索树
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
bool isValidBST(TreeNode* root) {
	vector<int> res;
	tranverse(root, res);
	for (int i = 0; i < res.size() - 1; i++)
	{
		if (res[i] >= res[i + 1])
		{
			return false;
		}
	}
	return true;
}
void tranverse(TreeNode* root, vector<int>& res)
{
    if (root == nullptr)
    {
		return;
	}
	tranverse(root->left, res);
	res.push_back(root->val);
	tranverse(root->right, res);
}

bool isValidBST(TreeNode* root, TreeNode* min, TreeNode* max) {
    // base case
    if (root == nullptr) return true;
    // 若 root->val 不符合 max 和 min 的限制，说明不是合法 BST
    if (min != nullptr && root->val <= min->val) return false;   
    if (max != nullptr && root->val >= max->val) return false;
    // 限定左子树的最大值是 root->val，右子树的最小值是 root->val
    return isValidBST(root->left, min, root) 
        && isValidBST(root->right, root, max);
}
230. 二叉搜索树中第K小的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
int kthSmallest(TreeNode* root, int k) {
	vector<int> res;
	inorder(root, res);
	return res[k - 1];
}

void inorder(TreeNode* root, vector<int>& res) {
	if (!root) return;
	inorder(root->left, res);
	res.push_back(root->val);
	inorder(root->right, res);
}

199. 二叉树的右视图
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
void BFS(TreeNode* root, vector<int>& mirror)
{
	queue<TreeNode*> q;
	q.push(root);
	while (!q.empty())
	{
		int size = q.size();
		for (int i = 0; i < size; i++)
		{
			TreeNode* node = q.front();
			q.pop();
			if (node!=nullptr && i==size -  1)
			{
				mirror.push_back(node->val);
			}
			if (node != nullptr && node->left != nullptr)
				q.push(node->left);
			if (node != nullptr && node->right != nullptr)
				q.push(node->right);
		}
	}
}

vector<int> rightSideView(TreeNode* root) {
	vector<int> res_mirror;
	BFS(root, res_mirror);
	return res_mirror;
}
437. 路径总和 III
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
class Solution {
public:
    unordered_map<long, long> preSumCount;
    long sum, targetSum;
    long res = 0;

    int pathSum(TreeNode* root, long target) {
        if (root == nullptr) {
            return 0;
        }
        this->sum = 0;
        this->targetSum = target;
        this->preSumCount[0] = 1;
        tranverse(root);
        return res;
    }

    void tranverse(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        sum += root->val;
        res += preSumCount[sum - targetSum];
        preSumCount[sum]++;
        tranverse(root->left);
        tranverse(root->right);
        preSumCount[sum]--;
        sum -= root->val;
    }
};
236. 二叉树的最近公共祖先
1
2
3
4
5
6
7
8
9
10
11
12
13
14
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
	if (root == nullptr || root == p || root == q) {
		return root;
	}
	TreeNode* left = lowestCommonAncestor(root->left, p, q);
	TreeNode* right = lowestCommonAncestor(root->right, p, q);
	if (left == nullptr) {
		return right;
	}
	if (right == nullptr) {
		return left;
	}
	return root;
}
297. 二叉树的序列化与反序列化
1
// 困难题
124. 二叉树中的最大路径和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int max_v = INT_MIN;
int dfs(TreeNode* root)
{
	if (root == nullptr)
	{
		return 0;
	}
	int left_max_v = dfs(root->left);
	int right_max_v = dfs(root->right);

	max_v = std::max(max_v, left_max_v + right_max_v + root->val);
	return std::max(std::max(left_max_v, right_max_v) + root->val,0);
}
int maxPathSum(TreeNode* root) {
	dfs(root);
	return max_v;
}
归并排序

merge 函数的任务是将两个已经排序的连续子数组（nums[left..mid] 和 nums[mid+1..right]）合并成一个有序数组。这是通过比较两个子数组的元素并按顺序选择较小的元素来放入临时数组，然后再将这个临时数组复制回原数组的相应位置来实现的。

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
void my_merge(int nums[], int left, int mid, int right)
{
    int i = left, j = mid + 1, k = 0;
    int* temp = new int[right - left + 1]; // 创建临时数组存储合并后的结果

    while (i <= mid && j <= right)
    {
        if (nums[i] <= nums[j])
        {
            temp[k++] = nums[i++];
        }
        else
        {
            temp[k++] = nums[j++];
        }
    }

    // 处理剩余的元素
    while (i <= mid)
    {
        temp[k++] = nums[i++];
    }
    while (j <= right)
    {
        temp[k++] = nums[j++];
    }

    // 将排序后的数组复制回原数组
    for (i = left, k = 0; i <= right; i++, k++)
    {
        nums[i] = temp[k];
    }

    delete[] temp; // 释放临时数组内存
}

void sort(int nums[], int left, int right)
{
    if (left == right)
    {
        return;
    }
	int mid = (left + right) >> 1;
	sort(nums, left, mid);
	sort(nums, mid + 1, right);
    my_merge(nums, left, mid, right);
}
快速排序
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
int partition(int nums[], int left, int right)
{
	int pivot = nums[right];
	int i = left;
	for (int j = left; j < right; j++)
	{
		if (nums[j] < pivot)
		{
			swap(nums[i], nums[j]);
			i++;
		}
	}
	swap(nums[i], nums[right]);
	return i;
}

void sort(int nums[], int left, int right)
{
    if (left >= right)
    {
        return;
    }
	int p = partition(nums, left, right);
    sort(nums, left, p - 1);
    sort(nums, p + 1, right);
}

BST
BST搜索
1
2
3
4
5
6
7
8
TreeNode* searchBST(TreeNode* root, int target) {
	if (root == nullptr) return nullptr;
    if (root->val == target) return root;
	TreeNode* left = searchBST(root->left, target);
	TreeNode* right = searchBST(root->right, target);
	if (left != nullptr) return left;
	if (right != nullptr) return right;
}
BST的插入
1
2
3
4
5
6
7
8
9
10
11
TreeNode* insertIntoBST(TreeNode* root, int val) {
	if (root == nullptr) return new TreeNode(val);
    if (root->val < val)
    {
		root->right = insertIntoBST(root->right, val);
    }
    else {
		root->left = insertIntoBST(root->left, val);
    }
    return root;
}
BST的删除
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
TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == nullptr) {
        // 如果树为空或者没有找到要删除的节点，返回null
        return root;
    }
    if (key < root->val) {
        // 如果要删除的键小于当前节点的值，则在左子树中继续查找
        root->left = deleteNode(root->left, key);
    } else if (key > root->val) {
        // 如果要删除的键大于当前节点的值，则在右子树中继续查找
        root->right = deleteNode(root->right, key);
    } else {
        // 当前节点就是要删除的节点
        if (root->left == nullptr) {
            // 情况2：当前节点没有左子树
            TreeNode* temp = root->right;
            delete root;  // 释放当前节点的内存
            return temp;
        } else if (root->right == nullptr) {
            // 情况2：当前节点没有右子树
            TreeNode* temp = root->left;
            delete root;  // 释放当前节点的内存
            return temp;
        }
        
        // 情况3：当前节点有两个子节点
        // 找到右子树的最小节点，即当前节点的中序后继
        TreeNode* temp = minValueNode(root->right);

        // 用中序后继的值覆盖当前节点的值
        root->val = temp->val;

        // 删除中序后继节点
        root->right = deleteNode(root->right, temp->val);
    }
    return root;
}

TreeNode* minValueNode(TreeNode* node) {
    TreeNode* current = node;
    while (current && current->left != nullptr) {
        current = current->left; // 一直向左走到底
    }
    return current;
}
96. 不同的二叉搜索树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
unordered_map<string, int> mmo;
int countTree(int left, int right) {
    if (left > right) return 1;
    int res = 0;

	string key = to_string(left) + " " + to_string(right);
	if (mmo.find(key) != mmo.end()) return mmo[key];
	
	for (int i = left; i <= right; i++) {
		int leftCount = countTree(left, i - 1);
		int rightCount = countTree(i + 1, right);
		res += leftCount * rightCount;
	}
	mmo[key] = res;
    return res;
}
int numTrees(int n) { return countTree(1, n); }

95. 不同的二叉搜索树 II
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
std::vector<TreeNode*> generateTrees(int start, int end) {
    std::vector<TreeNode*> allTrees;
    if (start > end) {
        allTrees.push_back(nullptr);
        return allTrees;
    }

    // 选择一个数字作为根节点
    for (int i = start; i <= end; i++) {
        // 构建所有可能的左子树和右子树
        std::vector<TreeNode*> leftTrees = generateTrees(start, i - 1);
        std::vector<TreeNode*> rightTrees = generateTrees(i + 1, end);

        // 与根节点组合
        for (auto& left : leftTrees) {
            for (auto& right : rightTrees) {
                TreeNode* currentTree = new TreeNode(i);
                currentTree->left = left;
                currentTree->right = right;
                allTrees.push_back(currentTree);
            }
        }
    }
    return allTrees;
}

std::vector<TreeNode*> generateTrees(int n) {
    if (n == 0) {
        return std::vector<TreeNode*>();
    }
    return generateTrees(1, n);
}
222. 完全二叉树的节点个数
1
2
3
4
5
int countNodes(TreeNode* root) {
    if (root == nullptr)
        return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

动态规划

解释
题型

哈希

集合 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率
std::set 红黑树 有序 否 否 O(log n) O(log n)
std::multiset 红黑树 有序 是 否 O(logn) O(logn)
std::unordered_set 哈希表 无序 否 否 O(1) O(1)
n数和

见上面数组n数和问题

一般题
242. 有效的字母异位词

用hash判断即可

349. 两个数组的交集
1
2
3
4
5
6
7
8
9
10
11
12
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int>kvm;
    unordered_set<int> result;
    for (auto c : nums1)
        kvm[c]++;
    for (auto c : nums2)
        if (kvm.find(c) != kvm.end())
        {
            result.insert(c);
        }
    return vector<int>(result.begin(), result.end());
}
49. 字母异位词分组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> result;
    for (auto it : strs) {
        string temp = it;
        sort(temp.begin(), temp.end());
        result[temp].push_back(it);
    }

    vector<vector<string>> vecs;
    for (auto& it : result)
    {
        vecs.push_back(it.second);
    }
    return vecs;
}

矩阵

一般题
73. 矩阵置零
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
void setZeroes(vector<vector<int>>& matrix) {
    int row = matrix.size();
    int col = matrix.front().size();

    vector<int> rows(row, 0);
    vector<int> cols(col, 0);


    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            if (matrix[i][j] == 0)
            {
                rows[i] = 1;
                cols[j] = 1;
            }
        }
    }

    for (int i = 0; i < row; i++)
    {
        if (rows[i] == 1)
        {
            /// 该行置为0
            for (int j = 0; j < col; j++)
                matrix[i][j] = 0;
        }
    }

    for (int j = 0; j < col; j++)
    {
        if (cols[j] == 1)
        {
            // 列置为0
            for (int i = 0; i < row; i++)
                matrix[i][j] = 0;
        }
    }
}
矩阵搜索
74. 搜索二维矩阵
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
int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right)
    {
        int mid = (left + right) >> 1;
        if (nums[mid] > target)
        {
            right = mid - 1;
        }
        else if (nums[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int rows = matrix.size();

    for (int i = 0; i < rows; i++)
    {
        int result = search(matrix[i], target);
        if (result != -1)
            return true;
    }
    return false;
}

//还有一种解法就是搜索第一列确顶在哪一行种，然后搜索那一行，时间复杂度将会降低到 log(m) + log(n)?
240. 搜索二维矩阵 II
1
2
3
4
// 可以用74.解法 nlogn
...  
//

二维数组旋转排布问题
48. 旋转图像
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
void Tranverse(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix.front().size();

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

void Reverse(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix.front().size();

    for (int i = 0; i < m; i++)
    {
        int left = 0, right = n - 1;
        while (left < right)
        {
            int temp = matrix[i][right];
            matrix[i][right] = matrix[i][left];
            matrix[i][left] = temp;
            left++;
            right--;
        }
    }
}

void rotate(vector<vector<int>>& matrix) {
    Tranverse(matrix);
    Reverse(matrix);
}
54. 螺旋矩阵
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> spiralOrder(vector<vector<int>>& matrix) {
    if (matrix.empty()) return {};
    vector<int> result;
    int top = 0, bottom = matrix.size() - 1;
    int left = 0, right = matrix[0].size() - 1;

    while (top <= bottom && left <= right) {
        for (int j = left; j <= right; ++j) result.push_back(matrix[top][j]);
        ++top;
        for (int i = top; i <= bottom; ++i) result.push_back(matrix[i][right]);
        --right;

        if (top <= bottom) {
            for (int j = right; j >= left; --j) result.push_back(matrix[bottom][j]);
        }
        --bottom;
        if (left <= right) {
            for (int i = bottom; i >= top; --i) result.push_back(matrix[i][left]);
        }
        ++left;
    }
    
    return result;
}

栈

20. 有效的括号
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
bool isValid(string s) {
    stack<char> st;
    for (int i = 0; i < s.size(); i++)
    {
		if (s[i] == '(' || s[i] == '[' || s[i] == '{')
        {
			st.push(s[i]);
		}
        else
        {
            if (st.empty())
            {
				return false;
			}
            if (s[i] == ')' && st.top() != '(')
            {
				return false;
			}
            if (s[i] == ']' && st.top() != '[')
            {
				return false;
			}
            if (s[i] == '}' && st.top() != '{')
            {
				return false;
			}
			st.pop();
		}
    }
    return st.empty();
}
155. 最小栈
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
class MinStack {
	vector<int> v;
	int min = INT_MAX;
	void updateMin() {
		for (int i = 0; i < v.size(); i++) {
			if (v[i] < min) {
				min = v[i];
			}
		}
	}
public:
    MinStack() {

    }

    void push(int val) {
		v.push_back(val);
        if (val < min) {
            min = val;
        }
    }

    void pop() {
        if (v[v.size() - 1] == min)
        {
            v.pop_back();
            min = INT_MAX;
            updateMin();
        }
		else
		{
			v.pop_back();
		}
    }

    int top() {
		return v[v.size() - 1];
    }

    int getMin() {
		updateMin();
		return min;
    }
};
394. 字符串解码
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
string decodeString(string s) {
	stack<mpair> st;
	mpair p;

	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] >= '0' && s[i] <= '9')
		{
			p.num = p.num * 10 + s[i] - '0';
		}
		else if (s[i] == '[')
		{
			st.push(p);
			p.num = 0;
			p.str = "";
		}
		else if (s[i] == ']')
		{
			mpair top = st.top();
			st.pop();
			for (int j = 0; j < top.num; j++)
			{
				top.str += p.str;
			}
			p.str = top.str;
		}
		else
		{
			p.str += s[i];
		}
	}
	return p.str;
}
739. 每日温度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> dailyTemperatures(vector<int>& temperatures) {
    std::vector<int> ans(temperatures.size(), 0);
    std::stack<int> indexStack;

    for (int i = 0; i < temperatures.size(); i++) {
        while (!indexStack.empty() &&
            temperatures[i] > temperatures[indexStack.top()]) {
            int index = indexStack.top();
            indexStack.pop();
            ans[index] = i - index;
        }
        indexStack.push(i);
    }
    return ans;
}
84. 柱状图中最大的矩形
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

int largestRectangleArea(vector<int>& heights) {
	const int sze = heights.size();
	vector<int> width(sze, 1);

	stack<int> st;
	for (int i = 0; i < sze; i++) {
		while (!st.empty() && heights[st.top()] >= heights[i]) {
			st.pop();
		}

		if (st.empty())
		{
			width[i] += i;
		}
		else
		{
			width[i] += i - st.top() - 1;
		}
		st.push(i);
	}

	while (!st.empty()) {
		st.pop();
	}

	int ret = 0;
	for (int i = sze - 1; i >= 0; i--) {
		while (!st.empty() && heights[st.top()] >= heights[i]) {
			st.pop();
		}

		if (st.empty())
		{
			width[i] += sze - i - 1;
		}
		else
		{
			width[i] += st.top() - i - 1;
		}
		st.push(i);

		ret = max(ret, width[i] * heights[i]);
	}
	return ret;
}

堆

215. 数组中的第K个最大元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>>
        pq; // 小顶堆，堆顶是最小元素
    for (int e : nums) {
        // 每个元素都要过一遍二叉堆
        pq.push(e);
        // 堆中元素多于 k 个时，删除堆顶元素
        if (pq.size() > k) {
            pq.pop();
        }
    }
    // pq 中剩下的是 nums 中 k 个最大元素，
    // 堆顶是最小的那个，即第 k 个最大元素
    return pq.top();
}
347. 前 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
vector<int> topKFrequent(vector<int>& nums, int k) {
	unordered_map<int, int> freq;
	for (int num : nums) {
		freq[num]++;
	}

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	for (auto it = freq.begin(); it != freq.end(); it++) {
		if (pq.size() == k) {
			if (it->second > pq.top().first) {
				pq.pop();
				pq.push({ it->second, it->first });
			}
		}
		else {
			pq.push({ it->second, it->first });
		}
	}
	vector<int> res;
	while (!pq.empty()) {
		res.push_back(pq.top().second);
		pq.pop();
	}
	return res;
}
295. 数据流的中位数
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 MedianFinder {
	priority_queue<int, vector<int>, less<int>> maxHeap;
	priority_queue<int, vector<int>, greater<int>> minHeap;

public:
    MedianFinder() {

    }

    void addNum(int num) {
        if (minHeap.size() > maxHeap.size())
        {
			minHeap.push(num);
			maxHeap.push(minHeap.top());
			minHeap.pop();
		}
        else
        {
			maxHeap.push(num);
			minHeap.push(maxHeap.top());
			maxHeap.pop();
        }
    }

    double findMedian() {
		if (minHeap.size() == maxHeap.size())
		{
			return (minHeap.top() + maxHeap.top()) / 2.0;
		}
		else
		{
			return minHeap.top();
		}
    }
};

其它

136. 只出现一次的数字
  1. 交换律：a ^ b ^ c <=> a ^ c ^ b
  2. 任何数于0异或为任何数 0 ^ n => n
  3. 相同的数异或为0: n ^ n => 0
1
2
3
4
5
6
7
8
int singleNumber(vector<int>& nums) {
    int tr = 0;
    for (int i = 0; i < nums.size(); i++)
    {
        tr ^= nums[i];
    }
    return tr;
}
169. 多数元素
  1. 遍历给定的数组 nums 中的每一个数 num。
  2. 如果 count 为 0，表示当前没有候选者或者前一个候选者的支持度已经被完全抵消，因此将当前的数 num 设为新的候选者。
  3. 然后，如果当前的数 num 等于候选者 candidate，则 count 增加 1（增加支持度）；否则 count 减少 1（减少支持度）
1
2
3
4
5
6
7
8
9
10
11
int majorityElement(vector<int>& nums) {
    int count = 0;
    int candidate = 0;
    for (int i = 0; i < nums.size(); i++)
    {
        if (count == 0)
            candidate = nums[i];
		count += (nums[i] == candidate) ? 1 : -1;
    }
    return candidate;
}
75. 颜色分类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void sortColors(vector<int>& nums) {
    int c0 = 0, c1 = 0, c2 = 0;
    for (int i = 0;i<nums.size();i++)
    {
        if (nums[i] == 0)
        {
            nums[c2++] = 2;
            nums[c1++] = 1;
            nums[c0++] = 0;
        }
        else if (nums[i] == 1)
        {
            nums[c2++] = 2;
            nums[c1++] = 1;
        }
        else
        {
            nums[c2++] = 2;
        }
    }
}
31. 下一个排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void nextPermutation(vector<int>& nums) {
    int n = nums.size();
    int i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i == -1)
    {
		/// 找不到这样的顺序队列，说明已经是最大的排列，直接翻转
		reverse(nums.begin(), nums.end());
		return;
    }
    int j = n - 1;
	// 从后往前找到第一个比nums[i]大的数
    while (nums[j] <= nums[i])j--;
	// 交换两个数, 交换后i后面的数仍然是降序排列的, 所以直接翻转
	swap(nums[i], nums[j]);
	// 翻转i后面的数
	reverse(nums.begin() + i + 1, nums.end());
}

287. 寻找重复数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int findDuplicate(vector<int>& nums) {
	int slow = nums[0];
	int fast = nums[nums[0]];

	while (slow != fast)
	{
		slow = nums[slow];
		fast = nums[nums[fast]];
	}

	slow = 0;

	while (slow != fast)
	{
		slow = nums[slow];
		fast = nums[fast];
	}

	return slow;
}

练习

LCH 100

链表
160.相交链表
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
int GetLength(ListNode* head) {
    int length = 0;
    while (head != nullptr)
    {
        head = head->next;
        length++;
    }
    return length;
}

ListNode* MoveSteps(ListNode* head,int steps = 0) {
    while (steps--)
    {
        head = head->next;
    }
    return head;
}   

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
    int lengthA = GetLength(headA);
    int lengthB = GetLength(headB);

    ListNode* newStartA = headA;
    ListNode* newStartB = headB;


    int moveStep = 0;
    if (lengthA > lengthB) {
        moveStep = lengthA - lengthB;
        newStartA = MoveSteps(newStartA, moveStep);
    }
    if (lengthB >= lengthA)
    {
        moveStep = lengthB - lengthA;
        newStartB = MoveSteps(newStartB, moveStep);
    }

    while (newStartA != nullptr && newStartB != nullptr) {
        if (newStartA == newStartB)
            return newStartA;
        newStartA = newStartA->next;
        newStartB = newStartB->next;
    }
    return nullptr;
}
206.反转链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 迭代法
ListNode* reverseList_It(ListNode* head) {
    ListNode* tempHead = new ListNode(-1, nullptr);
    ListNode* cur = head;

    while (cur != nullptr) {
        ListNode* nxt = cur->next;
        cur->next = tempHead->next;
        tempHead->next = cur;
        cur = nxt;
    }
    ListNode* he = tempHead->next;
    delete tempHead;
    return he;
}

// 递归法 : 具体请参看总结部分
ListNode* reverseList_rec(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode* res = reverseList_rec(head->next);
    head->next->next = head;
    head->next = nullptr;
    return res;
}
234.回文链表
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
// 解法1
// 1.找中间点
// 2.逆序后半部分
// 3.对比查找
    int GetLength(ListNode* head)
{
    int len = 0;
    while (head != nullptr)
    {
        len++;
        head = head->next;
    }
    return len;
}

ListNode* Get(ListNode* head,int index)
{
    while (index--)
    {
        head = head->next;
    }
    return head;
}

ListNode* reverse(ListNode* head) {
    if (head == nullptr) return head;
    if (head->next == nullptr) return head;

    ListNode* lastLayerResult = reverse(head->next);

    head->next->next = head;
    head->next = nullptr;
    return lastLayerResult;
}

bool isPalindrome(ListNode* head) {
    int halfLen = GetLength(head) >> 1;
   if (halfLen == 0) return true;
    ListNode* previousHalfNode = Get(head, halfLen-1);
    ListNode* halfNode = previousHalfNode->next;
    previousHalfNode->next = nullptr;

    halfNode = reverse(halfNode);

    while (halfNode != nullptr && head != nullptr)
    {
        if (halfNode->val == head->val)
        {
            halfNode = halfNode->next;
            head = head->next;
        }
        else
        {
            return false;
        }
        
    }
    return true;
}
141.环链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool hasCycle(ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast!=nullptr && fast->next!= nullptr && slow != nullptr)
    {
        fast = fast->next->next;
        slow = slow->next;

        if (fast == slow)
        {
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode* detectCycle(ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast != nullptr && fast->next != nullptr && slow != nullptr)
    {
        fast = fast->next->next;
        slow = slow->next;

        if (fast == slow)
        {
            slow = head;
            while (slow != fast)
            {
                slow = slow->next;
                fast = fast->next;
            }
            return fast;
        }
    }
    return nullptr;
}
21.有序链表合并
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
// 1.优先级队列解法
// 小顶堆 >
struct my_greater {
    bool operator()(const ListNode const *lf,const ListNode const *rg)
    {
        return lf->val > rg->val;
    }
};

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    std::priority_queue<ListNode*, vector<ListNode*>, my_greater> pq;
    while (list1 != nullptr)
    {
        ListNode* node = list1;
        list1 = list1->next;

        node->next = nullptr;
        pq.push(node);
    }

    while (list2 != nullptr)
    {
        ListNode* node = list2;
        list2 = list2->next;

        node->next = nullptr;
        pq.push(node);
    }
    ListNode* mt = new ListNode(-1, nullptr);
    ListNode* cur = mt;
    while (!pq.empty())
    {
        ListNode* n = pq.top();
        cur->next = n;
        cur = n;
        pq.pop();
    }
    ListNode* f = mt->next;
    delete mt;
    return f;
}
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
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
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* cur1 = l1; ListNode* cur2 = l2;

    ListNode* result = new ListNode(-1, nullptr);
    ListNode* curR = result;

    // sum
    while (cur1!=nullptr && cur2!=nullptr)
    {
        ListNode* newNode = new ListNode(cur1->val +cur2->val, nullptr);
        curR->next = newNode;
        curR = curR->next;

        cur1 = cur1->next;
        cur2 = cur2->next;
    }   
    if (cur1 == nullptr) {
        curR->next = cur2;
    }
    if (cur2 == nullptr)
    {
        curR->next = cur1;
    }

    
    //step
    ListNode* cur_step = result->next;
    int step = 0;
    while (cur_step!=nullptr)
    {
        cur_step->val += step;
        step = 0;
        if (cur_step->val >= 10)
        {
            step = 1;
            cur_step->val %= 10;
        }
        else
        {

        }
        cur_step = cur_step->next;
    }

    // get last
    cur_step = result;
    while (cur_step->next!=nullptr)
    {
        cur_step = cur_step->next;
    }

    if (step == 1)
    {
        cur_step->next = new ListNode(1, nullptr);
        cur_step = cur_step->next;
    }
    cur_step = nullptr;
    ListNode* r = result->next;
    delete result;
    return r;
}
19.删除倒数节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* tempHead = new ListNode(-1, head);
    ListNode* fast = tempHead, * slow = tempHead;
    n += 1;
    while (n--)
    {
        fast = fast->next;
    }
    while (fast != nullptr)
    {
        slow = slow->next;
        fast = fast->next;
    }
    ListNode* toDel = slow->next;
    slow->next = toDel->next;
    delete toDel;

    ListNode* he = tempHead->next;
    delete tempHead;
    return he;
}
24.两辆交换
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
// 1.循环
void swap(ListNode* prev) {
    ListNode* left = prev->next;
    ListNode* right = prev->next->next;
    left->next = right->next;
    right->next = left;
    prev->next = right;
}

bool CheckPair(ListNode* head)
{
    if (head != nullptr && head->next != nullptr && head->next->next != nullptr)
        return true;
    return false;
}

ListNode* swapPairs(ListNode* head) {
    ListNode* tempHead = new ListNode(-1, head);
    ListNode* cur = tempHead;
    while (CheckPair(cur))
    {
        swap(cur);
        cur = cur->next->next;
    }
    ListNode* toRet = tempHead->next;
    delete tempHead;
    return toRet;
}
// 2.递归
// head is pair's head  ...->head->left->right->...
ListNode* swapPairs(ListNode* head) {
    if (head == nullptr || head->next == nullptr)
        return head;  // 如果列表为空或只有一个节点，直接返回头节点
    // 进行节点交换
    ListNode* first = head;
    ListNode* second = head->next;
    // 递归调用函数交换后续节点
    first->next = swapPairs(second->next);
    // 交换当前的两个节点
    second->next = first;
    // 'second' 成为这一对的新头部
    return second;
}

25.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
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
// 1.迭代法 
// 假设区间为[a,b),反转该区间内的元素
ListNode* Reverse(ListNode* head, ListNode* end)
{
    ListNode* tempHead = new ListNode(-1, nullptr);
    ListNode* cur = head;
    /// 记录原首节点（反转必为末节点）
    ListNode* last = head;
    while (cur != end)
    {
        ListNode* nxt = cur->next;
        cur->next = tempHead->next;
        tempHead->next = cur;
        cur = nxt;
    }
    /// 原首节点（末节点）衔接上end以及后的元素
    last->next = cur;
    ListNode* he = tempHead->next;
    delete tempHead;
    return he;
}

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* tempHead = new ListNode(-1, head);
    ListNode* cur = tempHead;
    ListNode* start = tempHead;
    int count = k;
    while (cur!=nullptr)
    {
        if (count == 0)
        {
            // 记录原首节点
            ListNode* first = start->next;
            // 反转[start.next, cur.next)部分
            ListNode* newStart = Reverse(start->next, cur->next);
            // 将反转后头与上一尾相连
            start->next = newStart;
            // 更新start 到为尾节点
            start = first;
            // 置 k
            count = k;
        }
        count--;
        cur = cur->next;
    }
    ListNode* re = tempHead->next;
    delete tempHead;
    return re;
}

// 2.递归法
ListNode reverseKGroup(ListNode head, int k) {
    // 终止条件检查
    if (head == null) return null;
    // 对当前问题进行一些处理或简化，准备下一步递归
    ListNode a, b;
    a = b = head;
    for (int i = 0; i < k; i++) {
        // 不足 k 个，不需要反转，base case
        if (b == null) 
            return head;
        b = b.next;
    }  
    // 反转前 k 个元素
    ListNode newHead = reverse(a, b);
    // 递归反转后续链表并连接起来 -  递归调用自身，解决更小或更简化的问题
    a.next = reverseKGroup(b, k);
    return newHead;
}
138.随即链表复制
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
Node* Copy1(Node* head)
{
    Node* tempHead = new Node(-1);
    Node* cur = head;
    Node* curT = tempHead;
    while (cur != nullptr)
    {
        Node* newNode = new Node(cur->val);
        curT->next = newNode;
        curT = curT->next;

        cur = cur->next;
    }
    Node* re = tempHead->next;
    delete tempHead;
    return re;
}

int FindPos(Node* head, Node* node)
{
    if (node == nullptr)
        return 0;
    Node* cur = head;
    int count = 1;
    while (cur != nullptr)
    {
        if (cur == node)
            break;
        cur = cur->next;
        count++;
    }
    return count;
}

Node* GetNodeByPos(Node* head, int pos)
{
    if (pos <= 0)
        return nullptr;
    Node* tempHead = new Node(-1);
    tempHead->next = head;
    Node* cur = tempHead;
    while (pos-- && cur != nullptr)
    {
        cur = cur->next;
    }
    delete tempHead;
    return cur;
}

void Copy2(Node* head, Node* lst)
{
    Node* curH = head;
    Node* curL = lst;

    while (curH!=nullptr)
    {
        int pos = FindPos(head, curH->random);
        Node* rand = GetNodeByPos(lst, pos);
        curL->random = rand;
        curH = curH->next;
        curL = curL->next;
    }
}
Node* copyRandomList(Node* head) {
    Node* newN = Copy1(head);
    Copy2(head, newN);
    return newN;
}
148.排序链表
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
/// 链表排序
// 1.堆法
struct my_greater{
    bool operator()(const ListNode* const l, const ListNode* const r)
    {
        return l->val > r->val;
    }
};

ListNode* Sort1(ListNode* head)
{
    priority_queue<ListNode*, vector<ListNode*>, my_greater> pq;
    ListNode* cur = head;
    while (cur != nullptr)
    {
        pq.push(cur);
        cur = cur->next;
    }

    ListNode* temphead = new ListNode(-1, nullptr);
    ListNode* curT = temphead;
    while (!pq.empty())
    {
        ListNode* n = pq.top();
        curT->next = n;
        n->next = nullptr;
        curT = curT->next;

        pq.pop();
    }
    ListNode* re = temphead->next;
    delete temphead;
    return re;
}
// 2. 原地置换法
ListNode* insertSorted(ListNode* sortedHead, ListNode* newNode) {
    if (sortedHead == nullptr || sortedHead->val >= newNode->val) {
        newNode->next = sortedHead;
        return newNode;
    }

    ListNode* current = sortedHead;
    while (current->next != nullptr && current->next->val < newNode->val) {
        current = current->next;
    }

    newNode->next = current->next;
    current->next = newNode;
    return sortedHead;
}

ListNode* sortList(ListNode* head) {
    ListNode* sortedHead = nullptr;
    ListNode* current = head;
    while (current != nullptr) {
        ListNode* next = current->next;
        sortedHead = insertSorted(sortedHead, current);
        current = next;
    }
    return sortedHead;
}
23.合并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
26
27
28
29
30
31
32
33
34
struct my_greater {
    bool operator()(const ListNode* const l, const ListNode* const r)
    {
        return l->val > r->val;
    }
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, my_greater> pq;
    for (auto it = lists.begin(); it != lists.end(); it++) {
        ListNode* head = *it;
        while (head != nullptr)
        {
            pq.push(head);
            head = head->next;
        }

    }

    ListNode* temphead = new ListNode(-1, nullptr);
    ListNode* curT = temphead;
    while (!pq.empty())
    {
        ListNode* n = pq.top();
        curT->next = n;
        n->next = nullptr;
        curT = curT->next;

        pq.pop();
    }
    ListNode* re = temphead->next;
    delete temphead;
    return re;
}
146.LRU
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
class LRUCache {
private:
    list<pair<int, int>> lst; // 存储 (key, value) 对
    unordered_map<int, list<pair<int, int>>::iterator> kvm;
    int cap;

public:
    LRUCache(int capacity) : cap(capacity) {}

    int get(int key) {
        auto it = kvm.find(key);
        if (it == kvm.end()) {
            return -1;
        } else {
            // 将元素移动到列表前端
            lst.splice(lst.begin(), lst, it->second);
            return it->second->second;
        }
    }

    void put(int key, int value) {
        auto it = kvm.find(key);
        if (it != kvm.end()) {
            // 更新值并移动到列表前端
            it->second->second = value;
            lst.splice(lst.begin(), lst, it->second);
        } else {
            if (lst.size() == cap) {
                // 删除最久未使用的元素
                auto last = lst.back();
                kvm.erase(last.first);
                lst.pop_back();
            }
            // 插入新元素到列表前端
            lst.emplace_front(key, value);
            kvm[key] = lst.begin();
        }
    }

    void print() {
        for (auto& p : lst) {
            cout << p.first << ":" << p.second << " ";
        }
        cout << endl;
    }
};
1
2
3
4
5
6
7
8
9
10
11
void splice( const_iterator pos, list& other);
void splice( const_iterator pos, list&& other);

void splice( const_iterator pos, list& other, const_iterator it);
void splice( const_iterator pos, list&& other, const_iterator it);

void splice( const_iterator pos, list& other, const_iterator first, const_iterator last);
void splice( const_iterator pos, list&& other, const_iterator first, const_iterator last );
//第一组是将other链表中的所有要素转移到当前链表，插入位置为pos指向的位置之前，执行此操作后，other容器将为空。
//第二组是将other链表中迭代器it所指的要素转移给当前链表，插入位置为pos指向的位置之前。
//第三组是将other链表中[first, end)范围内的要素转移给当前链表，同样插入位置为pos指向的位置之前
总结:基本操作之反转

根据上述刷题总结，我们得到最爱考查的是链表反转问题，其中链表反转有又有2种变型，现总结如下：

  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
    // 迭代法
    ListNode* reverseList_It(ListNode* head) {
        ListNode* tempHead = new ListNode(-1, nullptr);
        ListNode* cur = head;

        while (cur != nullptr) {
            ListNode* nxt = cur->next;
            cur->next = tempHead->next;
            tempHead->next = cur;
            cur = nxt;
        }
        ListNode* he = tempHead->next;
        delete tempHead;
        return he;
    }

    // 递归法
    ListNode* reverseList_rec(ListNode* head) {
        // 递归终止边界条件
        if (head == nullptr || head->next == nullptr) return head;
        // 递归调用自身，解决更小或更简化的问题
        ListNode* start_node_after_reverse = reverseList_rec(head->next);
        // 使用递归得到的结果来构建当前问题的解
        head->next->next = head;
        head->next = nullptr;
        //返回当前问题的解
        return start_node_after_reverse;
    }

  2. 区间反转

    这个在于区间反转其中某部分，我们可能会需要start和end

    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
    // 迭代法 假设区间为[a,b)
    ListNode* Reverse(ListNode* head, ListNode* end)
    {
        ListNode* tempHead = new ListNode(-1, nullptr);
        ListNode* cur = head;
        /// 记录原首节点（反转必为末节点）
        ListNode* last = head;
        while (cur!=end)
        {
            ListNode* nxt = cur->next;
            cur->next = tempHead->next;
            tempHead->next = cur;
            cur = nxt;
        }
        /// 原首节点（末节点）衔接上end以及后的元素
        last->next = cur;
        ListNode* he = tempHead->next;
        delete tempHead;
        return he;
    }
    // 递归法
    // 1.反转前n节点
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        // 当不需要反转，或者链表为空时，直接返回原链表
        if (m == n) return head;

        static ListNode* successor = nullptr;  // 用来保存第 n + 1 个节点

        if (m == 1) {
            // 从第一个节点开始反转
            return reverseN(head, n);
        }

        // 递归处理，直到找到起始反转的节点
        head->next = reverseBetween(head->next, m - 1, n - 1);
        return head;
    }

    ListNode* successor = nullptr;
    // 反转链表的前 n 个节点
    ListNode* reverseN(ListNode* head, int n) {
        if (n == 1) {
            successor = head->next;  // 保存第 n + 1 个节点
            return head;
        }
        ListNode* last = reverseN(head->next, n - 1);
        head->next->next = head;
        head->next = successor;
        return last;
    }

  3. K组反转 - 迭代&递归 参考25.

    1
    2
    // 迭代法(略)
    // 递归法(略)
数组
283.移动0

(见数组基础问题章节)

1.两数和

(见数组基础问题章节)

15.三数和

(见数组基础问题章节)

35.插入位置

(见数组基础问题章节)

283.移动零

(见数组基础问题章节)

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

(见数组基础问题章节)