Top1：Leetcode 206反转链表

官方题解：迭代和递归
题目描述：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

迭代法

一、新建一个prev节点=null，之后while（cur！=null）的时候：例如a-->b-->c，我们先让a.next存起来，然后让a–>null【即curr–>prev】，变为null<--a b-->c。之后调整位置prev=cur【b—>a】，cur=temp也即是c；

再重复同样的操作就ok

• 时间复杂度：O（n）。
• 空间复杂度：O（1）。

可通过完整代码：

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode temp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = temp;
    }
    return prev;
}
1
2
3
4
5
6
7
8
9
10
11

递归法

一、例如12345。返回值为递归到最后一个结点的ListNode，然后head的下一个结点指向head；这时候head还有在指向next的节点，变为指向null。

此时链表为1->2->3<->4<-5，由于3与4互相指向，所以此处要断开3.next=null
1

评论区大神理解：

随后返回上一层递归到head=3这个节点相同操作

可通过完整代码：

// 递归法
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}
1
2
3
4
5
6
7
8

Top2：Leetcode 3无重复字符的最长子串

官方题解：滑动窗口
题目描述：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

一、滑动窗口。ans1时刻保存以i为下标的最长无重复子串。之后ans=Math.max(ans1, r-i)

我们将重复的子串保存起来，然后遍历左指针，不断remove，当为aaa重复的时候，l和r都指向a1，这时remove后，r也会向右移动一个，此时也为1。

原始：

可通过完整代码：

public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int r = 0, ans = 0;
    int n = s.length();
    for (int i = 0; i < n; i++) {   // 滑动窗口
        if (i != 0) {
            set.remove(s.charAt(i - 1));
        }
        while (r < n && !set.contains(s.charAt(r))) {
            set.add(s.charAt(r));
            r++;
        }
        ans = Math.max(ans, r - i);
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

Top3：Leetcode 912排序数组（快速排序）

官方题解：https://leetcode.cn/problems/sort-an-array/solution/pai-xu-shu-zu-by-leetcode-solution/
题目描述：
给你一个整数数组 nums，请你将该数组升序排列。

示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

一、快速排序。先分区，返回pos【主元正确的下标】下标，并将pos位置元素调好，紧接着分左右递归。

二、分区先随机取一个主元【主元元素归到正确升序位置】，接着移动到r方便后续partition

三、for循环l到r-1下标，如果nums[j]>pivot不动，如果<=就移动i=i+1并交换ij【初始i=l-1，当+1后才到l位置】

分区完之后将pivot【主元的值】的r位置与i+1位置大于pivot的元素互换，此时的pivot就在正确位置了

• 快排时间复杂度：O（nlogn）。最好情况下每一次取到的元素下标pos恰好将数组分为大小相等的两部分。参考我之前写的博客：排序算法
  

• 空间复杂度：O（）。参考：排序算法之 快速排序 及其时间复杂度和空间复杂度
  

可通过完整代码：

public int[] sortArray(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
    return nums;
}

private void quickSort(int[] nums, int l, int r) {
    if (l < r) {
        int pos = randomPartition(nums, l, r);
        quickSort(nums, l, pos - 1);   // 此时下标pos已经找到了它应在的位置
        quickSort(nums, pos + 1, r);
    }
}

private int randomPartition(int[] nums, int l, int r) {
    int i = new Random().nextInt(r - l + 1) + l;   // 随机选取一个主元i。// Random().nextInt（n）可以取0到n-1
    swap(nums, r, i);   // 把主元放到最右边r下标
    return partition(nums, l, r);
}

private int partition(int[] nums, int l, int r) {   // 此时r是我们在randomPartition随机选取的主元i
    int pivot = nums[r];
    int i = l - 1;
    for (int j = l; j <= r - 1; j++) {
        if (nums[j] <= pivot) {
            i = i + 1;   // i+1第一个是最左l处
            swap(nums, i, j);   // 反正有小的逐渐往左放就行了，j会往右移动的
        }
    }
    swap(nums, i + 1, r);   // 最后交换主元下标和i + 1下标。这是下标i+1左边全更小，右边全更大
    return i + 1;   // 返回i+1位置
}

private void swap(int[] nums, int r, int i) {
    int temp = nums[r];
    nums[r] = nums[i];
    nums[i] = temp;
}
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

Top4：Leetcode 215数组中的第k个最大元素

官方题解：https://leetcode.cn/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/
题目描述：
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

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

示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

一、简化快排。寻找主元下标，如果==正好，如果小于k所处的index就往右递归【。。。pos。index。。】，否则往左递归。

int pos = randomPartition(nums, l, r);
        if (pos == index) {
            return nums[pos];
        } else {
            return pos < index ? quickSort(nums, pos + 1, r, index) : quickSort(nums, l, pos - 1, index);   // 固定index位置，如果pos小，就往右边找
            // 如果pos位置大，就往左边找
        }
1
2
3
4
5
6
7

• 时间复杂度：O（n）。
• 空间复杂度：O（logn）。

快排可通过完整代码：

public int findKthLargest(int[] nums, int k) {
    return quickSort(nums, 0, nums.length - 1, nums.length - k);   // 第1大下标元素位于n-1下标处
}

private int quickSort(int[] nums, int l, int r, int index) {
    int pos = randomPartition(nums, l, r);
    if (pos == index) {
        return nums[pos];
    } else {
        return pos < index ? quickSort(nums, pos + 1, r, index) : quickSort(nums, l, pos - 1, index);   // 固定index位置，如果pos小，就往右边找
        // 如果pos位置大，就往左边找
    }
}

private int randomPartition(int[] nums, int l, int r) {
    int i = new Random().nextInt(r - l + 1) + l;   // 2-0=2，再-1=1，符合随机出0，1 + l（0）下标
    swap(nums, i, r);
    return partition(nums, l, r);
}

private int partition(int[] nums, int l, int r) {
    int pivot = nums[r];   // 主元的值
    int i = l - 1;
    for (int j = l; j <= r - 1; j++) {   // 小的移动左边，大的不动   // 如果都不动说明pivot最小在i+1=l下标处
        if (nums[j] <= pivot) {
            i = i + 1;
            swap(nums, i, j);
        }
    }
    swap(nums, i + 1, r);
    return i + 1;
}

private void swap(int[] nums, int i, int r) {
    int temp = nums[i];
    nums[i] = nums[r];
    nums[r] = temp;
}
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

Top5：Leetcode 53最大子数组和

官方题解：https://leetcode.cn/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
题目描述：
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

一、动态规划。pre(i)表示每个位置的最大值。我们考虑i时刻的pre，是单独nums[i]成为一段还是加上i-1时刻的pre成为一段。pre = Math.max(pre + x, x);

for(int num:nums)遍历是按照顺序的

可通过完整代码：

public static int maxSubArray(int[] nums) {
    int pre = 0, ans = nums[0];
    for (int x : nums) {
        pre = Math.max(pre + x, x);   // 我们需要考虑目前i的pre函数值，是单独nums[i]成为一段还是加上i-1的那一个pre函数值
        ans = Math.max(pre, ans);
    }
    return ans;
}
1
2
3
4
5
6
7
8

Top6：Leetcode 152乘积最大子数组【先maxF、minF、ans全取nums[0]方便迭代】

官方题解：https://leetcode.cn/problems/maximum-product-subarray/solution/cheng-ji-zui-da-zi-shu-zu-by-leetcode-solution/
题目描述：
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

一、如果使用当前位置，当前位置*前一时刻来做转移方程不对，因为有可能出现相隔较远的两个负数。不满足「最优子结构」

二、我们需要维护两个，上一时刻的最大值maxF和上一时刻的最小值minF。在nums[i]、mx*nums[i]和mn*nums[i]之前取最大值最小值

可通过完整代码：

public int maxProduct(int[] nums) {
    int maxF = nums[0], minF = nums[0], ans = nums[0];
    int length = nums.length;
    for (int i = 1; i < length; i++) {   // f(i)存这一时刻（正）最大和（负）最小
        int mx = maxF, mn = minF;
        maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));   // 如果mn为负，nums[i]也为负，正好mn*nums[i]为此次最大
        minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));   // 上一时刻最大也有可能*负变为这一时刻最小
        ans = Math.max(maxF, ans);
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11

Top7：leetcode 121买卖股票的最佳时机

题目描述：
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

一、示例1，我们绘图如下：

二、初始ans=0，用一个变量记录一个历史最低价格 minprice，碰到更低就更新，else就判断nums[i]-minprice和ans相比哪个更大更新ans

• 时间复杂度：O（n）
• 空间复杂度：O（1）

可通过完整代码：

public int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE;
    int ans = 0;
    for (int i = 0; i < prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else if (prices[i] - minPrice > ans) {   // 可以少遍历一些，去掉无用的循环
            ans = prices[i] - minPrice;
        }
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12