数据结构与算法-入门

发表于 | 更新于: | 分类于 |
字数统计: 13.9k | 阅读时长 ≈ 59

数组

数组，将元素存储到内存的连续位置中，是最基本的数据结构。数组数据结构的主要优点是如果知道索引就可以通过 O(l) 进行快速搜索，但是在数组中添加和删除元素的速度会很慢，因为数组一旦被创建，就无法更改其大小。如果需要创建更长或更短的数组，得先创建一个新数组，再把原数组中的所有元素复制到新创建的数组中。

解决数组相关问题的关键是要熟悉数组的数据结构和基本的构造，如循环、递归等等；

给定一个 1-100 的整数数组，请找到其中缺少的数字。

解决方法与代码：https://javarevisited.blogspot.com/2014/11/how-to-find-missing-number-on-integer-array-java.html

两种思路：
（1）如果只缺少一个数字，n*(n+1)/2 - sum 就是缺失的数字；
（2）缺失多个数字或是某些数字重复出现，则只能遍历一遍，记录哪些数字出现过，可用List或BitSet来记录。

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
/**
 * 给定一个 1-n 的整数数组，请找到其中缺少的数字
 *
 * @author austin
 * @since 2019/7/30 14:31
 */
public class FindMissingNumber {

    /**
     * 支持多个重复或是缺失多个情况
     *
     * @param arr   数组
     * @param count n
     */
    public static void printMissingNumber(int[] arr, int count) {
        int missingCount = count - arr.length;
        BitSet bitSet = new BitSet(count);

        for (int i : arr) {
            bitSet.set(i - 1);
        }

        int lastIndex = 0;
        for (int i = 0; i < missingCount; i++) {
            lastIndex = bitSet.nextClearBit(lastIndex);
            System.out.println(++lastIndex);
        }
    }

    /**
     * 只支持缺失1个情况
     */
    public static void printSingleMissingNumber(int[] arr, int count) {
        int exceptedSum = count * (count + 1) / 2;
        int sum = 0;
        for (int i : arr) {
            sum += i;
        }
        System.out.println(exceptedSum - sum);
    }

    public static void main(String[] args) {
        // 缺失一个数字
        printMissingNumber(new int[] {1, 2, 3, 4, 6}, 6);

        // 缺失3个数字
        printMissingNumber(new int[] {1, 2, 3, 4, 6, 9, 8}, 10);

        // 缺失一个数字
        printSingleMissingNumber(new int[] {1, 2, 3, 4, 6}, 6);
    }

}

在给定的成对整数数组中，请找出所有总和等于给定数字的组合。

解决方法与代码：http://javarevisited.blogspot.com/2014/08/how-to-find-all-pairs-in-array-of-integers-whose-sum-equal-given-number-java.html

三种思路：
（1）两层循环，时间复杂度O(n^2);
（2）存储到HashTable里，在HashTable里找（sum - arr[i]）值， 时间复杂度： O(n), 空间复杂度： O(n);
（3）先排序O(nlogn), 然后首尾想加，往中间靠；

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
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 在给定的成对整数数组中，请找出所有总和等于给定数字的组合
 *
 * @author austin
 * @since 2019/7/30 15:35
 */
public class ComposeSum {

    /**
     * 可输出全部组合
     * 两层循环
     */
    public static void printPairs(int[] array, int sum) {
        for (int i = 0; i < array.length; i++) {
            int first = array[i];
            for (int j = i + 1; j < array.length; j++) {
                int second = array[j];
                if ((first + second) == sum) {
                    System.out.printf("(%d, %d) %n", first, second);
                }
            }
        }
    }

    /**
     * map方式
     */
    public static void printPairsUsingSet(int[] numbers, int n) {
        if (numbers.length < 2) {
            return;
        }
        Set set = new HashSet(numbers.length);
        for (int value : numbers) {
            int target = n - value; // if target number is not in set then add
            if (!set.contains(target)) {
                set.add(value);
            } else {
                System.out.printf("(%d, %d) %n", value, target);
            }
        }
    }

    /**
     * 先排序 O(n log(n))
     */
    public static void printPairsUsingTwoPointers(int[] numbers, int k) {
        if (numbers.length < 2) {
            return;
        }
        Arrays.sort(numbers);
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == k) {
                System.out.printf("(%d, %d) %n", numbers[left], numbers[right]);
                left = left + 1;
                right = right - 1;
            } else if (sum < k) {
                left = left + 1;
            } else if (sum > k) {
                right = right - 1;
            }
        }
    }



    public static void main(String[] args){
        printPairs(new int[]{ 2, 4, 3, 5, 6, -2, 4, 7, 8, 9 }, 12);
        System.out.println();

        printPairsUsingSet(new int[]{ 2, 4, 3, 5, 6, -2, 4, 7, 8, 9 }, 12);
        System.out.println();

        printPairsUsingTwoPointers(new int[]{ 2, 4, 3, 5, 6, -2, 4, 7, 8, 9 }, 12);
    }
}

数组中重复的数据

给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。

找到所有出现两次的元素。

你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？

示例：

输入:

1
[4,3,2,7,8,2,3,1]

输出:

1
[2,3]

解题思路：
这个题目开头暗示了n的范围，所以可以加以利用，将元素转换成数组的索引并对应的将该处的元素乘以-1； 若数组索引对应元素的位置本身就是负数，则表示已经对应过一次；在结果列表里增加该索引的正数就行；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> dupliacates = new ArrayList<Integer>();
        for(int i : nums){
            if(i < 0){
                i = -i;
            }
            
            if(nums[i-1] < 0){  // 已经重复过
                dupliacates.add(i);
                continue;
            }
            nums[i-1] = -1 * nums[i-1];
        }
        return dupliacates;
    }
}

快速排序

快排采用的是分治的思想。

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
import java.util.Arrays;

/**
 * 快速排序
 *
 * @author austin
 * @since 2019/7/30 20:05
 */
public class QuickSort {

    public static void sort(int[] nums) {
        if (null == nums || nums.length == 0) {
            return;
        }

        quickSort(nums, 0, nums.length - 1);
    }

    private static void quickSort(int[] nums, int low, int high) {
        // 选取中位数
        int pivot = nums[low + (high - low) / 2];
        int left = low;
        int right = high;
        while (left <= right) {
            while (nums[left] < pivot) {
                left++;
            }

            while (nums[right] > pivot) {
                right--;
            }

            if (left <= right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                left++;
                right--;
            }
        }

        if (low < right) {
            quickSort(nums, low, right);
        }

        if (high > left) {
            quickSort(nums, left, high);
        }
    }

    public static void main(String[] args){
        int[] unsorted = {6, 5, 3, 1, 8, 7, 2, 4};
        System.out.println("Unsorted array :" + Arrays.toString(unsorted));
        sort(unsorted);
        System.out.println("Sorted array :" + Arrays.toString(unsorted));
    }
}

前缀和技巧：和为K的子数组个数

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

思路很简单，我把所有子数组都穷举出来，算它们的和，看看谁的和等于 k 不就行了。

关键是，如何快速得到某个子数组的和呢，比如说给你一个数组nums，让你实现一个接口sum(i, j)，这个接口要返回nums[i..j]的和，而且会被多次调用，你怎么实现这个接口呢？

因为接口要被多次调用，显然不能每次都去遍历nums[i..j]，有没有一种快速的方法在 O(1) 时间内算出nums[i..j]呢？这就需要前缀和技巧了。

  • 前缀和
    前缀和的思路是这样的，对于一个给定的数组nums，我们额外开辟一个前缀和数组进行预处理：
1
2
3
4
5
6
int n = nums.length;
// 前缀和数组
int[] preSum = new int[n + 1];
preSum[0] = 0;
for (int i = 0; i < n; i++)
    preSum[i + 1] = preSum[i] + nums[i];

这个前缀和数组preSum的含义也很好理解，preSum[i]就是nums[0..i-1]的和。那么如果我们想求nums[i..j]的和，只需要一步操作preSum[j+1]-preSum[i]即可，而不需要重新去遍历数组了。

回到这个子数组问题，我们想求有多少个子数组的和为 k，借助前缀和技巧很容易写出一个解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int subarraySum(int[] nums, int k) {
        int[] preSum = new int[nums.length + 1];
        // 构造前缀和
        for(int i = 0; i < nums.length; i++){
            preSum[i+1] = preSum[i] + nums[i];
        }

        int count = 0;
        // 穷举所有子数组
        for(int i = 0; i < preSum.length; i++){
            for(int j = i + 1; j < preSum.length; j++){
                if(preSum[j] - preSum[i] == k){
                    count++;
                }
            }
        }
        return count;
    }
}

这个解法的时间复杂度空间复杂度，并不是最优的解法。不过通过这个解法理解了前缀和数组的工作原理之后，可以使用一些巧妙的办法把时间复杂度进一步降低.

  • 优化解
    优化的思路是：我直接记录下有几个sum[j]和sum[i]-k相等，直接更新结果，就避免了内层的 for 循环。我们可以用哈希表，在记录前缀和的同时记录该前缀和出现的次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int subarraySum(int[] nums, int k) {
        // <前缀和, 该前缀和出现次数>
        HashMap<Integer, Integer> preSum = new HashMap<>();
        preSum.put(0, 1);
        
        int count  = 0;
        int currentSum = 0;
        for(int num : nums){
            currentSum += num;
            int sum = currentSum - k;
            // 该数之前已经有符合条件的前缀和
            if(preSum.containsKey(sum)){
                count += preSum.get(sum);
            }
            
            if(!preSum.containsKey(currentSum)){
                preSum.put(currentSum, 0);
            }
            preSum.put(currentSum, preSum.get(currentSum) + 1);
        }
        return count;
    }
}

来源：【LeetCode】 560. 和为K的子数组
参考：前缀和技巧：解决子数组问题

交换数组两部分

比如数组【1,2,3,4,5】，要将【1,2,3】和【4,5】交换，得到【4,5,1,2,3】

先看一道类似的 LeetCode 题目：

Given an array, rotate the array to the right by k steps, where k is non-negative.

举个例子：

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

题目很好理解，实际上就是交换数组的两部分，只是换成“rotate k steps”的说法而已。等价于“把数组的最后 k 个元素和其他元素交换”。

一个细节区别就是，这里的 k 可以大于数组的长度，但只要让 k 与数组长度求模（余数）就行了，又转换成了“交换数组的两部分”这个问题。

  • 思路一，想办法构造一个环

    可以把这个数组转化成一个链表，然后把这个链表首尾相接，形成一个环，然后在适当的地方把这个环重新断开成为一个链表，最后把这个新得到的链表转换成数组，这个数组就是结果了。至于应该在什么地方重新断开这个环，跟 k 有关.

  • 思路二，这个问题具有递归结构
    首先，如果交换的两部分元素数量一样（k == 数组长度 / 2），那么就比较简单，直接对应元素逐个互换就行了。（递归的 base case）

    但是两部分元素如果不一样多，难点就来了，长的那部分交换会有剩余，这个剩余区域还需要和长区域经过交换的那个区域交换，以还原长区域的原始顺序，然后这个交换过程又会产生长短不一的问题，然后请重新阅读这段话。（递归调用）

  • 思路三，终极解法
    这个解法简单得让人诧异，只需要进行三次数组反转就行了：首先把数组的这两部分分别反转，然后把整个数组反转，就得到了答案。

其实，“交换数组的两部分”经过简单的变形，就变成了谷歌公司的一道面试题：

给你一个英文句子字符串，对它进行完全倒装（不允许使用额外空间）

比如说给面试者一句话：

A cycle of boom and bust.

请你倒装成：

bust and boom of cycle A.

原地倒装，不允许使用额外存储空间。

这个面试题问倒了不少面试者，因为正常人的思维总会陷入如何交换不同长度的单词，陷入复杂的条件判定和无限的细节中，这个人类看起来如此简单的问题对计算机来说似乎是个不可能完成的任务。但是你应该很容易想到解法：先把整个句子反转，再将每个单词分别反转，就得到了答案。

接雨水

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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

  • 双指针解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int trap(int[] height) {
        if(height.length <= 2){
            return 0;
        }
        int lMax = height[0];
        int rMax = height[height.length - 1];
        int count  = 0, left = 0, right = height.length - 1;

        while(left <= right){
            lMax = Math.max(lMax, height[left]);
            rMax = Math.max(rMax, height[right]);

            if(lMax < rMax){
                count += lMax - height[left];
                left++;
            }else{
                count += rMax - height[right];
                right--;
            }
        }
        return count;
    }
}

参考：
【LeetCode42】 接雨水

详解一道高频面试题：接雨水

字符串

最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例 2：
输入: “cbbd”
输出: “bb”

  • 中心扩展法
    寻找回文串的问题核心思想是：从中间开始向两边扩散来判断回文串。对于最长回文子串，就是这个意思：
1
2
3
for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    更新答案

但是呢，我们刚才也说了，回文串的长度可能是奇数也可能是偶数，如果是abba这种情况，没有一个中心字符，上面的算法就没辙了。所以我们可以修改一下：

1
2
3
4
for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    找到以 s[i] 和 s[i+1] 为中心的回文串
    更新答案

按照上面的思路，先要实现一个函数来寻找最长回文串:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String longestPalindrome(String s) {
        String longest = "";
        for(int i = 0; i < s.length(); i++){
            // 以s[i]为中心的最长回文子串
            String one = palindrome(s, i, i);
            // 以s[i], s[i+1]为中心的最长回文子串
            String two = palindrome(s, i, i+1);
            longest = longest.length() > one.length() ? longest : one;
            longest = longest.length() > two.length() ? longest : two;
        }
        return longest;
    }

    public String palindrome(String s, int left, int right){
        while(left >=0 && right < s.length() 
            && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    }
}

【LeetCode】5. 最长回文子串

最长回文子序列

给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。

示例 1:
输入:
“bbbab”
输出:
4

一个可能的最长回文子序列为 “bbbb”。

示例 2:
输入:
“cbbd”
输出:
2

一个可能的最长回文子序列为 “bb”。

模板解题思路

  • 1、第一种思路模板是一个一维的 dp 数组：

    1
    2
    3
    4
    5
    6
    7
    8
    int n = array.length;
    int[] dp = new int[n];

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] = 最值(dp[i], dp[j] + ...)
        }
    }

    举个我们写过的例子最长递增子序列，在这个思路中 dp 数组的定义是：

    在子数组 array[0..i] 中，以 array[i] 结尾的目标子序列（最长递增子序列）的长度是dp[i]。

    为啥最长递增子序列需要这种思路呢？前文说得很清楚了，因为这样符合归纳法，可以找到状态转移的关系。

  • 2、第二种思路模板是一个二维的 dp 数组：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int n = arr.length;
    int[][] dp = new dp[n][n];

    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n; j++) {
            if (arr[i] == arr[j]) 
                dp[i][j] = dp[i][j] + ...
            else
                dp[i][j] = 最值(...)
        }
    }

    这种思路运用相对更多一些，尤其是涉及两个字符串/数组的子序列。本思路中 dp 数组含义又分为「只涉及一个字符串」和 「涉及两个字符串」 两种情况。

    • 2.1 涉及两个字符串/数组时（比如最长公共子序列），dp 数组的含义如下：
      在子数组 arr1[0..i] 和子数组 arr2[0..j] 中，我们要求的子序列（最长公共子序列）长度为 dp[i][j]。

    • 2.2 只涉及一个字符串/数组时（比如本文要讲的最长回文子序列），dp 数组的含义如下：
      在子数组 array[i..j] 中，我们要求的子序列（最长回文子序列）的长度为dp[i][j]。

  • 本题思路
    dp 数组的定义是：在子串 s[i..j] 中，最长回文子序列的长度为 dp[i][j]。

    具体来说，如果我们想求 dp[i][j]，假设你知道了子问题 dp[i+1][j-1] 的结果（s[i+1..j-1]中最长回文子序列的长度），你是否能想办法算出 dp[i][j] 的值（s[i..j] 中，最长回文子序列的长度）呢？
    可以！这取决于s[i]和 s[j] 的字符：

    • 如果它俩相等，那么它俩加上 s[i+1..j-1] 中的最长回文子序列就是 s[i..j] 的最长回文子序列;

    • 如果它俩不相等，说明它俩不可能同时出现在 s[i..j] 的最长回文子序列中，那么把它俩分别加入 s[i+1..j-1] 中，看看哪个子串产生的回文子序列更长即可;

      以上两种情况写成代码就是这样：

      1
      2
      3
      4
      5
      6
      if (s[i] == s[j])
          // 它俩一定在最长回文子序列中
          dp[i][j] = dp[i + 1][j - 1] + 2;
      else
          // s[i+1..j] 和 s[i..j-1] 谁的回文子序列更长？
          dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

至此，状态转移方程就写出来了，根据 dp 数组的定义，我们要求的就是dp[0][n - 1]，也就是整个s的最长回文子序列的长度。

  • Java实现
    首先明确一下 base case，如果只有一个字符，显然最长回文子序列长度是 1，也就是 dp[i][j] = 1,(i == j)。

    因为i肯定小于等于j，所以对于那些i > j的位置，根本不存在什么子序列，应该初始化为 0。

    另外，看看刚才写的状态转移方程，想求dp[i][j]需要知道dp[i+1][j-1]，dp[i+1][j]，dp[i][j-1]这三个位置；为了保证每次计算 dp[i][j]，左、下、左下三个方向的位置已经被计算出来，只能斜着遍历或者反着遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int[][] dp = new int[len][len];
        // base case dp[i][i] = 1
        for(int i = 0; i < len; i++){
            dp[i][i] = 1;
        }
        
        // 从左下角向右上角遍历
        for(int i = len - 1; i >= 0; i--){
            for(int j = i + 1; j < len; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = 2 + dp[i+1][j-1];
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][len-1];
    }
}

来源：LeetCode 516. 最长回文子序列

参考：子序列解题模板：最长回文子序列

链表

链表是另一种常见的数据结构，和数组相似，链表也是线性的数据结构并且以线性方式存储元素。而与数组不同的是，链表不是将元素存储在连续的位置中，而是可以存储在任意位置，彼此之间通过节点相互连接。

链表也可以说就是一个节点列表，每个节点中包含存储的值和下一个节点的地址。也正是因为这种结构，在链表里添加和删除元素很容易，你只需要更改链接而不用创建新的数组。但是搜索会很困难，并且在单链表中找到一个元素就需要 O（n）个时间。

链表有多种形式，如：单链表，允许你在一个方向上进行遍历；双链表，可以在两个方向上进行遍历；循环链表，最后节点的指针指向第一个节点从而形成一个环形的链；因为链表是一种递归数据结构，所以在解决链表问题时，熟练掌握递归算法就显得更加重要了。

判断单链表是否存在环及求环入口点

    1. 先判断是否有环
      设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则为无环链表)
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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode quick = head;
        while(null != quick){
            if(quick.next != null && null != quick.next.next){
                quick = quick.next.next;
            }else{
                return false;
            }
            slow = slow.next;
            if(slow == quick){
                return true;
            }
        }
        return false;
    }
}

此问题可扩展至：

求循环链表任一节点“对面的”（最远端）的节点

算法同上，当quick到达起始节点或起始节点next时，slow指示的就是最远端的节点。

    1. 经过第1步确认存在环后，寻找环入口点：

算法描述：

当quick若与slow相遇时，slow肯定没有走遍历完链表，而quick已经在环内循环了n圈(1<=n)。
假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：

1
2
2s = s + nr
s = nr

设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。

1
2
3
4
5
a + x = s = nr

a + x = (n–1)r + r = (n-1)r + L - a

a = (n-1)r + (L – a – x)

(L – a – x) 为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-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
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode quick = head.next.next;
        // 一定有环， 寻找相遇点
        while(slow != quick){
            slow = slow.next;
            quick = quick.next.next;
        }
        
        // quick指针重新指向head节点
        quick = head;
        while(slow != quick){
            slow = slow.next;
            quick = quick.next;
        }
        return slow;
    }
}

此问题可扩展至：

判断两个单链表是否相交，如果相交，给出相交的第一个点（两个链表都不存在环）。

根据问题描述，两个单链表自相交点起，将合并为一个单链表，这是理解算法的关键。

算法描述：

将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(null == headA || null == headB){
            return null;
        }
        
        // 先将一个链表构成环
        ListNode tail = headA;
        while(tail.next != null){
            tail = tail.next;
        }
        tail.next = headA;
        
        ListNode slow = headB;
        ListNode quick = headB;
        while(quick != null){
            if(null != quick.next && null != quick.next.next){
                quick = quick.next.next;
            }else{
                tail.next = null;
                return null;
            }
            slow = slow.next;
            if(slow == quick){
                break;
            }
        }
        
        // 能够执行到此处一定是有环
        quick = headB;
        while(slow != quick){
            slow = slow.next;
            quick = quick.next;
        }
        tail.next = null;
        return slow;
    }
}

单链表相交

找到两个单链表相交的起始节点。

注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解题思路：双指针法

  1. 创建两个指针 pA 和 pB，分别初始化为链表 A 和 B 的头结点。然后让它们向后逐结点遍历。
  2. 当 pA 到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B); 类似的，当 pB 到达链表的尾部时，将它重定位到链表 A 的头结点。
  3. 若在某一时刻 pA 和 pB 相遇，则 pA/pB 为相交结点。

想弄清楚为什么这样可行, 可以考虑以下两个链表: A={1,3,5,7,9,11} 和 B={2,4,9,11}，相交于结点 9。
由于 B.length (=4) < A.length (=6)，pB 比 pA 少经过 2 个结点，会先到达尾部。将 pB 重定向到 A 的头结点，pA 重定向到 B 的头结点后，pB 要比 pA 多走 2 个结点。因此，它们会同时到达交点。
如果两个链表存在相交，它们末尾的结点必然相同。因此当 pA/pB 到达链表结尾时，记录下链表 A/B 对应的元素。若最后元素不相同，则两个链表不相交。

复杂度分析

时间复杂度 : O(m+n)O(m+n)。
空间复杂度 : O(1)O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }
        
        ListNode pA = headA, pB = headB;
        // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头,         
        // 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
        while(pA != pB){
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

反转单链表

两种思路：
（1）迭代
假设存在链表 1 → 2 → 3 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3。

在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode next = null;
        while(cur != null){
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

复杂度分析

时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度是 O(n)。
空间复杂度：O(1)。

（2）递归
核心思想：

1
head.next.next = head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}

复杂度分析

时间复杂度：O(n)，假设 n 是列表的长度，那么时间复杂度为 O(n)。
空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间。递归深度可能会达到 n 层。

删除链表的倒数第N个节点

双指针法：
第一个指针从列表的开头向前移动 n+1n+1 步，而第二个指针将从列表的开头出发。现在，这两个指针被 n 个结点分开。我们通过同时移动两个指针向前来保持这个恒定的间隔，直到第一个指针到达最后一个结点。此时第二个指针将指向从最后一个结点数起的第 n 个结点。我们重新链接第二个指针所引用的结点的 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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) { 
        ListNode dummy = new ListNode(0); // 哑指针，防止极端情况
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        // Advances first pointer so that the gap between first and second is n nodes apart
        for (int i = 1; i <= n + 1; i++) {
            first = first.next;
        }
        // Move first to the end, maintaining the gap
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}

二叉树

二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。

对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们平常所说的层次遍历。

因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁，而对于广度遍历来说，需要其他数据结构的支撑，比如堆了。所以，对于一段代码来说，可读性有时候要比代码本身的效率要重要的多。

二叉树深度遍历

  • 递归方式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* 前序遍历
*/ 
public void preOrderTraverse1(TreeNode root) {
		if (root != null) {
			System.out.print(root.val+"  ");
			preOrderTraverse1(root.left);
			preOrderTraverse1(root.right);
		}
}

/**
* 中序遍历
*/ 
public void inOrderTraverse1(TreeNode root) {
		if (root != null) {
			inOrderTraverse1(root.left);
			System.out.print(root.val+"  ");
			inOrderTraverse1(root.right);
		}
}

/**
* 后序遍历
*/ 
public void postOrderTraverse1(TreeNode root) {
		if (root != null) {
			postOrderTraverse1(root.left);
			postOrderTraverse1(root.right);
			System.out.print(root.val+"  ");
		}
}
  • 非递归方式
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
/**
* 前序遍历
*/
public void preOrderTraverse(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            System.out.println(cur.val);
            stack.push(cur);
            cur = cur.left;
        } else {
            cur = stack.pop();
            cur = cur.right;
        }
    }
}

/**
* 中序遍历
*/
public void midOrderTraverse(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.left;
        } else {
            cur = stack.pop();
            System.out.println(cur.val);
            cur = cur.right;
        }
    }
}

/**
* 后序遍历
*/
public void postOrderTraverse(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            stack.push(cur);
            cur = cur.right;
        } else {
            cur = stack.pop();
            System.out.println(cur.val);
            cur = cur.left;
        }
    }
}

二叉树层遍历

层次遍历的代码比较简单，只需要一个队列即可，先在队列中加入根结点。之后对于任意一个结点来说，在其出队列的时候，访问之。同时如果左孩子和右孩子有不为空的，入队列。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void levelTraverse(TreeNode root){
    if(root == null){
        return;
    }
    
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    TreeNode cur;
    while (!queue.isEmpty()){
        cur = queue.poll();
        System.out.print(cur.val);
        if (cur.left != null){
            queue.offer(cur.left);
        }
        
        if (cur.right != null){
            queue.offer(cur.right);
        }
    }
}

堆排序

https://www.jianshu.com/p/a20e5ec158b3

回溯算法

解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：

  • 1、路径：也就是已经做出的选择。

  • 2、选择列表：也就是你当前可以做的选择。

  • 3、结束条件：也就是到达决策树底层，无法再做选择的条件。

如果你不理解这三个词语的解释，没关系，我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思，现在你先留着印象。

代码方面，回溯算法的框架：

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」，特别简单。

参考：https://leetcode-cn.com/problems/n-queens/solution/hui-su-suan-fa-xiang-jie-by-labuladong/

全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入:

[1, 2, 3]

输出:

[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

  • 解题思路
    其实这就是回溯算法，我们高中无师自通就会用，或者有的同学直接画出如下这棵回溯树：

    只要从根遍历这棵树，记录路径上的数字，其实就是所有的全排列。我们不妨把这棵树称为回溯算法的「决策树」。

    为啥说这是决策树呢，因为你在每个节点上其实都在做决策。比如说你站在下图的红色节点上：

    你现在就在做决策，可以选择 1 那条树枝，也可以选择 3 那条树枝。为啥只能在 1 和 3 之中选择呢？因为 2 这个树枝在你身后，这个选择你之前做过了，而全排列是不允许重复使用数字的。

    现在可以解答开头的几个名词：[2] 就是「路径」，记录你已经做过的选择；[1,3] 就是「选择列表」，表示你当前可以做出的选择；「结束条件」就是遍历到树的底层，在这里就是选择列表为空的时候。

    如果明白了这几个名词，可以把「路径」和「选择」列表作为决策树上每个节点的属性，比如下图列出了几个节点的属性：

    我们定义的 backtrack 函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个全排列。

  • java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        LinkedList<Integer> track = new LinkedList<Integer>();
        backTrack(nums, track, res);
        return res;
    }

    /**
    * 路径track: 记录已选路径
    * 选择列表nums
    * 结束条件： nums中无元素
    */
    private void backTrack(int nums[], LinkedList<Integer> track, List<List<Integer>> res){
        // 触发结束条件
        if(track.size() == nums.length){
            res.add(new LinkedList<Integer>(track));
            return;
        }

        for(int i = 0; i < nums.length; i++){
            // 排除不合法的选择
            if(track.contains(nums[i])){
                continue;
            }

            // 做选择
            track.add(nums[i]);
            // 进入下一层决策树
            backTrack(nums, track, res);
            // 取消选择
            track.removeLast();
        }
    }
}

N皇后问题

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

上图为 8 皇后问题的一种解法。

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

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

  • 解题思路

  • java实现

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
public class Solution {

    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        String[][] queues = new String[n][n]; // 存储当前摆放方式
        backTrack(queues, 0, res);
        return res;
    }

    /**
     * 路径: queues中小于row的那些行都已经成功放置了皇后
     * 选择列表： 第row行所有列都是纺织皇后的选择
     * 结束条件： row == queues最后一行
     */
    private void backTrack(String[][] queues, int row, List<List<String>> res) {
        // 触发结束条件
        if (row == queues.length) {
            res.add(this.formatResult(queues));
            return;
        }

        int n = queues[row].length;
        for (int col = 0; col < n; col++) {
            // 排除不合法选择
            if (this.isUnderAttack(queues, row, col)) {
                continue;
            }

            // 做选择
            queues[row][col] = "Q";
            // 进入下一个决策树
            backTrack(queues, row + 1, res);
            // 撤销选择
            queues[row][col] = ".";
        }
    }

    // 判断当前摆放位置是否和已经摆放的冲突
    private boolean isUnderAttack(String[][] queues, int row, int col) {
        // 检查列是否有冲突
        for (int i = 0; i < row; i++) {
            if ("Q".equals(queues[i][col])) {
                return true;
            }
        }

        // 检查左上方是否有冲突
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if ("Q".equals(queues[i][j])) {
                return true;
            }
        }

        int n = queues.length;
        // 检查右上方是否有冲突
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if ("Q".equals(queues[i][j])) {
                return true;
            }
        }
        return false;
    }

    private List<String> formatResult(String[][] queues) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < queues.length; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < queues[0].length; j++) {
                if ("Q".equals(queues[i][j])) {
                    sb.append(" ♦️ ");
                } else {
                    sb.append(" O ");
                }
            }
            res.add(sb.toString());
        }
        return res;
    }
}

动态规划

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = “abcde”, text2 = “ace”
输出：3
解释：最长公共子序列是 “ace”，它的长度为 3。

示例 2:

输入：text1 = “abc”, text2 = “abc”
输出：3
解释：最长公共子序列是 “abc”，它的长度为 3。

示例 3:

输入：text1 = “abc”, text2 = “def”
输出：0
解释：两个字符串没有公共子序列，返回 0。

提示:

1 <= text1.length <= 1000
1 <= text2.length <= 1000

输入的字符串只含有小写英文字符。

  • 动态规划解法

dp[i][j] 的含义是：对于s1[1..i]和s2[1..j]，它们的 LCS 长度是dp[i][j]。

公式：

dp[ i ][ j ] = dp[ i-1 ][ j-1 ] + 1 ; s[i] == s[j]
dp[ i ][ j ] = max(dp[ i-1 ][ j ], dp[ i ][ j-1 ]); s[i] ≠ s[j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i = 0; i <= m ; i++){
            dp[i][0] = 0;
        }

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

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(text1.charAt(i-1) == text2.charAt(j-1)){ 
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
}

参考：
【LeetCode】1143. 最长公共子序列

经典面试题：最长公共子序列

括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

  • 思路
    当我们清楚所有 i<n 时括号的可能生成排列后，对与 i=n 的情况，我们考虑整个括号排列中最左边的括号。它一定是一个左括号，那么它可以和它对应的右括号组成一组完整的括号 “( )”，我们认为这一组是相比 n-1 增加进来的括号。

    那么，剩下的括号要么在这一组新增的括号内部，要么在这一组新增括号的外部（右侧）。既然知道了 i<n 的情况，那我们就可以对所有情况进行遍历：

    “(“ + 【i=p时所有括号的排列组合】 + “)” + 【j=(n-1-p)时所有括号的排列组合】

    其中 p <= n-1，且为非负整数。当上述 p 从 0 取到 n-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
class Solution {
    public List<String> generateParenthesis(int n) {
        List<List<String>> dp = new ArrayList<>();
        dp.add(Arrays.asList(""));
        // dp[n] = '(' + dp[i] + ')' + dp[j];  i + j = n-1
        for(int k = 1; k <= n; k++){
           dp.add(combine(dp, k-1));
        }
        return dp.get(n);
    }

    private List<String> combine(List<List<String>> dp, int total){
        if(total == 0){
            return Arrays.asList("()");
        }

        List<String> list = new ArrayList<String>();
        for(int i = 0; i <= total; i++){
            for(String first : dp.get(i)){
                String sb = "(" + first + ')';
                for(String second : dp.get(total - i)){
                    list.add(sb + second);
                }
            }
        }
        return list;
    }
}

参考:
【LeetCode】22. 括号生成

零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3
输出: -1

说明:你可以认为每种硬币的数量是无限的。

  • 动态规划(自顶向下)

假设我们知道 F(S) ，对于金额 S 最少的硬币数，最后一枚硬币的面值是 C。那么由于问题的最优子结构以下方程应为：

F(S) = F(S - C) + 1

但我们不知道最后一枚硬币的面值是多少。我们计算每个硬币 c0, c1, …, cn​, 并选择其中的最小值。下列递推关系成立：

-w502

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0){
            return 0;
        }

        int min = Integer.MAX_VALUE;
        for(int coin : coins){
            // 金额不可达
            if(amount - coin < 0){
                continue;
            }
            int res = coinChange(coins, amount - coin);
            if(res == -1){ // 子问题无解
                continue;
            }
            min = Math.min(res + 1, min);
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
}
  • 动态规划(自下向上)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0){
            return 0;
        }

        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); // 一定需要初始化，并不是每一个金额都有兑换方案
        
        dp[0] = 0;
        for(int i = 1; i < dp.length; i++){
            for(int coin : coins){
                if(i < coin){
                    continue;
                }
                dp[i] = Math.min(dp[i], dp[i-coin] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

编辑距离

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

示例 1:

输入:

word1 = “horse”, word2 = “ros”

输出:

3

解释:

horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)

示例 2:

输入:

word1 = “intention”, word2 = “execution”

输出:

5

解释:

intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)

  • 解题思路

编辑距离算法被数据科学家广泛应用，是用作机器翻译和语音识别评价标准的基本算法。

最简单的方法是检查所有可能的编辑序列，从中找出最短的一条。但这个序列总数可能达到指数级，但完全不需要这么多，因为我们只要找到距离最短的那条而不是所有可能的序列。

动态规划

我们的目的是让问题简单化，比如说两个单词 horse 和 ros 计算他们之间的编辑距离 D，容易发现，如果把单词变短会让这个问题变得简单，很自然的想到用 D[n][m] 表示输入单词长度为 n 和 m 的编辑距离。

具体来说，D[i][j] 表示 word1 的前 i 个字母和 word2 的前 j 个字母之间的编辑距离。

当我们获得 D[i-1][j]，D[i][j-1] 和 D[i-1][j-1] 的值之后就可以计算出 D[i][j]。

每次只可以往单个或者两个字符串中插入一个字符

那么递推公式很显然了

如果两个子串的最后一个字母相同，word1[i] = word2[i] 的情况下：

D[i][j]=1 + min(D[i−1][j], D[i][j−1], D[i−1][j−1]−1)

否则，word1[i] != word2[i] 我们将考虑替换最后一个字符使得他们相同：

D[i][j]=1 + min(D[i−1][j], D[i][j−1], D[i−1][j−1])

所以每一步结果都将基于上一步的计算结果，示意如下：

同时，对于边界情况，一个空串和一个非空串的编辑距离为 D[i][0] = i 和 D[0][j] = j。

  • 递归实现

从头部开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {

    /**
    * 当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
    * 当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
    */
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        if(len1 == 0 || len2 == 0){
            return len1 == 0 ? len2 : len1;
        }

        int minDistance = 0;
        if(word1.charAt(0) == word2.charAt(0)){
            minDistance = minDistance(word1.substring(1), word2.substring(1));
        } else {
            int replace = minDistance(word1.substring(1), word2.substring(1));
            int insert = minDistance(word1, word2.substring(1));
            int delete = minDistance(word1.substring(1), word2);
            minDistance = Math.min(Math.min(replace, insert), delete) + 1;
        }
        return minDistance;

    }
}
  • 动态规划实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int minDistance(String word1, String word2) {
        int l1 = word1.length();
        int l2 = word2.length();

        int[][] dp = new int[l1 + 1][l2 + 1];
        for(int i = 1; i <= l1; i++){
            dp[i][0] = i;
        }

        for(int i = 1; i <= l2; i++){
            dp[0][i] = i;
        }

        for(int i = 1; i <= l1; i++){
            for(int j = 1; j <= l2; j++){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]));
                }
            }
        }
        return dp[l1][l2];
    }
}

扩展

既然每个dp[i][j]只和它附近的三个状态有关，空间复杂度是可以压缩成 O(min(M,N)) 的（M，N 是两个字符串的长度）。不难，但是可解释性大大降低。

你可能还会问，这里只求出了最小的编辑距离，那具体的操作是什么？
这个其实很简单，代码稍加修改，给 dp 数组增加额外的信息即可：

1
2
3
4
5
6
7
8
9
10
11
// int[][] dp;
Node[][] dp;

class Node {
    int val;
    int choice;
    // 0 代表啥都不做
    // 1 代表插入
    // 2 代表删除
    // 3 代表替换
}

val属性就是之前的 dp 数组的数值，choice属性代表操作。在做最优选择时，顺便把操作记录下来，然后就从结果反推具体操作。

我们的最终结果不是dp[m][n]吗，这里的val存着最小编辑距离，choice存着最后一个操作.

参考： 详解一道腾讯面试题：编辑距离

贪心算法（Greedy Algorithm)

贪心算法，又名贪婪法，是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。{看着这个名字，贪心，贪婪这两字的内在含义最为关键。这就好像一个贪婪的人，他事事都想要眼前看到最好的那个，看不到长远的东西，也不为最终的结果和将来着想，贪图眼前局部的利益最大化，有点走一步看一步的感觉。}

贪婪法的基本步骤：

  • 步骤1：从某个初始解出发；

  • 步骤2：采用迭代的过程，当可以向目标前进一步时，就根据局部最优策略，得到一部分解，缩小问题规模；

  • 步骤3：将所有解综合起来。

最优子结构
　
当一个问题的最优解包括其子问题的最优解时，称此问题具有最优子结构性质。

运用贪心策略在每一次转化时都取得了最优解。问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。动态规划主要运用于二维或三维问题，而贪心一般是一维问题.

买卖股票最佳时机

给定一个数组，它的第i个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]
输出: 7

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4

解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。

注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]
输出: 0

解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

  • 方法一：暴力法
    这种情况下，我们只需要计算与所有可能的交易组合相对应的利润，并找出它们中的最大利润。
class Solution {
    public int maxProfit(int[] prices) {
        return maxProfit(prices, 0);
    }

    private static int maxProfit(int[] prices, int start){
        if(start >= prices.length){  // 到最后一天不能买入
            return 0;
        }

        int max = 0;
        for(int i = start; i < prices.length; i++){
            int curProfilt = 0;
            for(int j = i + 1; j < prices.length; j++){
                if(prices[i]  < prices[j]){
                    int profilt = maxProfit(prices, j+1) + prices[j] - prices[i];
                    if(profilt > curProfilt){
                        curProfilt = profilt;
                    }
                }
            }

            if(max < curProfilt){
                max = curProfilt;
            }
        }
        return max;
    }
}

  • 方法二：峰谷法
    假设给定的数组为：

    [7, 1, 5, 3, 6, 4]

    如果我们在图表上绘制给定数组中的数字，我们将会得到:

如果我们分析图表，那么我们的兴趣点是连续的峰和谷。用数学语言描述为：
![-w419](/images/al_peak_gongshi.jpg)

关键是我们需要考虑到紧跟谷的每一个峰值以最大化利润。如果我们试图跳过其中一个峰值来获取更多利润，那么我们最终将失去其中一笔交易中获得的利润，从而导致总利润的降低。

例如，在上述情况下，如果我们跳过 `peak_ipeak_j` 和 `valley_jvalley_j`

试图通过考虑差异较大的点以获取更多的利润，获得的净利润总是会小与包含它们而获得的静利润，因为 C 总是小于 A+B。 

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        int maxProfit = 0;
        int vallege = prices[0];
        int peak = prices[0];
        int i = 0;
        while(i < prices.length - 1){
            // 寻找波谷
            while(i+1 < prices.length && prices[i] >= prices[i+1]){
                i++;
            }
            vallege = prices[i];
            // 寻找波峰
            while(i+1 < prices.length && prices[i] <= prices[i+1]){
                i++;
            }
            peak = prices[i];
            maxProfit += peak - vallege;
        }
        return maxProfit;
    }
}

  • 方法三：简单的一次遍历

    该解决方案遵循 方法二 的本身使用的逻辑，但有一些轻微的变化。
    在这种情况下，我们可以简单地继续在斜坡上爬升并持续增加从连续交易中获得的利润，而不是在谷之后寻找每个峰值。最后，我们将有效地使用峰值和谷值，但我们不需要跟踪峰值和谷值对应的成本以及最大利润，但我们可以直接继续增加加数组的连续数字之间的差值，如果第二个数字大于第一个数字，我们获得的总和将是最大利润。这种方法将简化解决方案。

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for(int i = 0; i < prices.length - 1; i++){
            if (prices[i] < prices[i+1]){
                maxProfit += prices[i+1] - prices[i];
            }
        }
        return maxProfit;
    }
}

参考： 【LeetCode】122. 买卖股票的最佳时机 II

常见思路

10亿个数字里里面找最小的10个

(1) 分治(Hash拆分) + topK
(2) 先取10个构建最大堆，在循环更新（TopK）

有1亿个数字，其中有2个是重复的，快速找到它，时间和空间要最优

(1) BitSet

2亿个随机生成的无序整数,找出中间大小的值

https://flykite.me/?p=41
(1) 二分思想
在最开始的时候，以0为分界线，对所有整数进行遍历并统计小于0的整数个数和大于等于0的整数个数，假设小于0的整数有94,632,563个，那么大于等于0的数就有105,367,437个，这也就意味着，我们需要的那两个数是大于等于0的。

接下来我们就可以向第一次遍历那样对数据进行拆分了，我们知道int类型正整数最大值是2^31 ，那么第二次遍历我们就以2^30 作为分界线吧，统计小于2^30 的数与大于等于2^30 的数，假设小于2^30 的数有36,524,163个，大于2^30 次方的数有68,843,274个，那么我们需要的那两个数处于0到2^30 -1这个闭区间内。

按照这个方法，一次又一次第进行遍历，当我们统计出我们需要的那两个数处于某一个区间内，并且这个区间内的数比较少，至少能让我们直接在内存中进行排序时，我们就可以将符合这个区间的数全部读取到内存中排序

（2）如果数据不重复，可采用位图排序
位图排序是一种空间换时间的排序算法，时间复杂度仅为O(n)，但它的限制很多，比如数据不能有重复项，在排序之前必须知道数据的范围（最小值及最大值，或者大致范围），范围越宽广，占用的内存空间就越大。

打个比方，假设有一万个不重复的整数，已知这些整数里最小的数为0，最大的数为100,000，这时候，我们可以申请一个长度为100,001位的内存空间（即97.66KB），然后遍历这一万个整数并且将内存空间中对应位置的位设为1，在遍历结束后排序也已经结束了。

可能这段话还不是很能让你理解透彻，这样吧，把数据量再缩小一些，比如有[19, 36, 3, 42, 11, 26, 5, 9, 24]这样一个数组，假设我们已经知道这个数组最小值为3，最大值为42，这时候我们就可以申请一个长度为40位的内存空间，如下：

00000 00000 00000 00000 00000 00000 00000 00000

（为了看起来方便，这里以5位相隔一个空格来表示）

对该数组进行遍历，并且将每个整数的值减去3之后，将对应位置设为1，结果如下：

10100 01010 00000 01000 01010 00000 00010 00001

从这串0和1中，我们能看到这里的第0位、第2位、第6位都为1，这几个1的位置加上数组中的最小值3则表示的是3, 5, 9这几个数。

给一个不知道长度的(可能很大)输入字符串，设计一种方案，将重复的字符排重

定义一个字符数组记录字符出现次数 int[] a = new int[256];
再遍历一遍，删除重复字符

有2n+1个数，其中有n个数出现过2次，找出其中只出现一次的数

算法的原理就是：任何数异或0值不变，任何数与自己异或值为0

有3n+1个数字，其中n个数出现过3次，只有1个是不重复的

（1）这个用异或不可以
可以设置一个长度为32的int数组。统计每位上出现1的次数，如果次数能被3整除，说明x该位上为0，否则为1
https://blog.csdn.net/u011960402/article/details/17750993