labuladong

labuladong 查看完整档案

长沙编辑清华大学  |  计算机 编辑字节跳动  |  算法工程师 编辑 labuladong.gitbook.io/algo 编辑
编辑

公众号 labuladong,致力于把算法讲清楚!

个人动态

labuladong 发布了文章 · 2020-12-23

回文的最小插入次数

读完本文,你可以去力扣拿下如下题目:

1312.让字符串成为回文串的最少插入次数

-----------

回文串就是正着读反着读都一样的字符,在笔试面试中经常出现这类问题。

之前有好几篇讲解回文问题的文章,是判断回文串或者寻找最长回文串/子序列的:

[判断回文链表]

[计算最长回文子串]

[计算最长回文子序列]

本文就来研究一道构造回文串的问题,难度 Hard 计算让字符串成为回文串的最少插入次数:

输入一个字符串 s,你可以在字符串的任意位置插入任意字符。如果要把 s 变成回文串,请你计算最少要进行多少次插入?

函数签名如下:

int minInsertions(string s);

比如说输入 s = "abcea",算法返回 2,因为可以给 s 插入 2 个字符变成回文串 "abeceba" 或者 "aebcbea"。如果输入 s = "aba",则算法返回 0,因为 s 已经是回文串,不用插入任何字符。

思路解析

首先,要找最少的插入次数,那肯定得穷举喽,如果我们用暴力算法穷举出所有插入方法,时间复杂度是多少?

每次都可以在两个字符的中间插入任意一个字符,外加判断字符串是否为回文字符串,这时间复杂度肯定爆炸,是指数级。

那么无疑,这个问题需要使用动态规划技巧来解决。之前的文章说过,回文问题一般都是从字符串的中间向两端扩散,构造回文串也是类似的。

我们定义一个二维的 dp 数组,dp[i][j] 的定义如下:对字符串 s[i..j],最少需要进行 dp[i][j] 次插入才能变成回文串

我们想求整个 s 的最少插入次数,根据这个定义,也就是想求 dp[0][n-1] 的大小(ns 的长度)。

同时,base case 也很容易想到,当 i == jdp[i][j] = 0,因为当 i == js[i..j] 就是一个字符,本身就是回文串,所以不需要进行任何插入操作。

接下来就是动态规划的重头戏了,利用数学归纳法思考状态转移方程。

状态转移方程

状态转移就是从小规模问题的答案推导更大规模问题的答案,从 base case 向其他状态推导嘛。如果我们现在想计算 dp[i][j] 的值,而且假设我们已经计算出了子问题 dp[i+1][j-1] 的值了,你能不能想办法推出 dp[i][j] 的值呢

既然已经算出 dp[i+1][j-1],即知道了 s[i+1..j-1] 成为回文串的最小插入次数,那么也就可以认为 s[i+1..j-1] 已经是一个回文串了,所以通过 dp[i+1][j-1] 推导 dp[i][j] 的关键就在于 s[i]s[j] 这两个字符

这个得分情况讨论,如果 s[i] == s[j] 的话,我们不需要进行任何插入,只要知道如何把 s[i+1..j-1] 变成回文串即可:

翻译成代码就是这样:

if (s[i] == s[j]) {
    dp[i][j] = dp[i + 1][j - 1];
}

如果 s[i] != s[j] 的话,就比较麻烦了,比如下面这种情况:

最简单的想法就是,先把 s[j] 插到 s[i] 右边,同时把 s[i] 插到 s[j] 右边,这样构造出来的字符串一定是回文串:

PS:当然,把 s[j] 插到 s[i] 左边,然后把 s[i] 插到 s[j] 左边也是一样的,后面会分析。

但是,这是不是就意味着代码可以直接这样写呢?

if (s[i] != s[j]) {
    // 把 s[j] 插到 s[i] 右边,把 s[i] 插到 s[j] 右边
    dp[i][j] = dp[i + 1][j - 1] + 2;
}

不对,比如说如下这两种情况,只需要插入一个字符即可使得 s[i..j] 变成回文:

所以说,当 s[i] != s[j] 时,无脑插入两次肯定是可以让 s[i..j] 变成回文串,但是不一定是插入次数最少的,最优的插入方案应该被拆解成如下流程:

步骤一,做选择,先将 s[i..j-1] 或者 s[i+1..j] 变成回文串。怎么做选择呢?谁变成回文串的插入次数少,就选谁呗。

比如图二的情况,将 s[i+1..j] 变成回文串的代价小,因为它本身就是回文串,根本不需要插入;同理,对于图三,将 s[i..j-1] 变成回文串的代价更小。

然而,如果 s[i+1..j]s[i..j-1] 都不是回文串,都至少需要插入一个字符才能变成回文,所以选择哪一个都一样:

那我怎么知道 s[i+1..j]s[i..j-1] 谁变成回文串的代价更小呢?

回头看看 dp 数组的定义是什么,dp[i+1][j]dp[i][j-1] 不就是它们变成回文串的代价么?

步骤二,根据步骤一的选择,将 s[i..j] 变成回文

如果你在步骤一中选择把 s[i+1..j] 变成回文串,那么在 s[i+1..j] 右边插入一个字符 s[i] 一定可以将 s[i..j] 变成回文;同理,如果在步骤一中选择把 s[i..j-1] 变成回文串,在 s[i..j-1] 左边插入一个字符 s[j] 一定可以将 s[i..j] 变成回文。

那么根据刚才对 dp 数组的定义以及以上的分析,s[i] != s[j] 时的代码逻辑如下:

if (s[i] != s[j]) {
    // 步骤一选择代价较小的
    // 步骤二必然要进行一次插入
    dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
}

综合起来,状态转移方程如下:

if (s[i] == s[j]) {
    dp[i][j] = dp[i + 1][j - 1];
} else {
    dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
}

这就是动态规划算法核心,我们可以直接写出解法代码了。

代码实现

首先想想 base case 是什么,当 i == jdp[i][j] = 0,因为这时候 s[i..j] 就是单个字符,本身就是回文串,不需要任何插入;最终的答案是 dp[0][n-1]n 是字符串 s 的长度)。那么 dp table 长这样:

又因为状态转移方程中 dp[i][j]dp[i+1][j]dp[i]-1]dp[i+1][j-1] 三个状态有关,为了保证每次计算 dp[i][j] 时,这三个状态都已经被计算,我们一般选择从下向上,从左到右遍历 dp 数组:

完整代码如下:

int minInsertions(string s) {
    int n = s.size();
    // 定义:对 s[i..j],最少需要插入 dp[i][j] 次才能变成回文
    vector<vector<int>> dp(n, vector<int>(n, 0));
    // base case:i == j 时 dp[i][j] = 0,单个字符本身就是回文
    // dp 数组已经全部初始化为 0,base case 已初始化

    // 从下向上遍历
    for (int i = n - 2; i >= 0; i--) {
        // 从左向右遍历
        for (int j = i + 1; j < n; j++) {
            // 根据 s[i] 和 s[j] 进行状态转移
            if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1];
            } else {
                dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
            }
        }
    }
    // 根据 dp 数组的定义,题目要求的答案
    return dp[0][n - 1];
}

现在这道题就解决了,时间和空间复杂度都是 O(N^2)。还有一个小优化,注意到 dp 数组的状态之和它相邻的状态有关,所以 dp 数组是可以压缩成一维的:

int minInsertions(string s) {
    int n = s.size();
    vector<int> dp(n, 0);
    
    int temp = 0;
    for (int i = n - 2; i >= 0; i--) {
        // 记录 dp[i+1][j-1]
        int pre = 0;
        for (int j = i + 1; j < n; j++) {
            temp = dp[j];
            
            if (s[i] == s[j]) {
                // dp[i][j] = dp[i+1][j-1];
                dp[j] = pre;
            } else {
                // dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;
                dp[j] = =min(dp[j], dp[j - 1]) + 1;
            }
            
            pre = temp;
        }
    }
    
    return dp[n - 1];
}

至于这个状态压缩是怎么做的,我们前文 状态压缩技巧 详细介绍过,这里就不展开了。

查看原文

赞 0 收藏 0 评论 0

labuladong 发布了文章 · 2020-12-23

动态规划之打家劫舍

读完本文,你可以去力扣拿下如下题目:

198.打家劫舍

213.打家劫舍II

337.打家劫舍III

-----------

有读者私下问我 LeetCode 「打家劫舍」系列问题(英文版叫 House Robber)怎么做,我发现这一系列题目的点赞非常之高,是比较有代表性和技巧性的动态规划题目,今天就来聊聊这道题目。

打家劫舍系列总共有三道,难度设计非常合理,层层递进。第一道是比较标准的动态规划问题,而第二道融入了环形数组的条件,第三道更绝,把动态规划的自底向上和自顶向下解法和二叉树结合起来,我认为很有启发性。如果没做过的朋友,建议学习一下。

下面,我们从第一道开始分析。

House Robber I

title

public int rob(int[] nums);

题目很容易理解,而且动态规划的特征很明显。我们前文「动态规划详解」做过总结,解决动态规划问题就是找「状态」和「选择」,仅此而已

假想你就是这个专业强盗,从左到右走过这一排房子,在每间房子前都有两种选择:抢或者不抢。

如果你抢了这间房子,那么你肯定不能抢相邻的下一间房子了,只能从下下间房子开始做选择。

如果你不抢这件房子,那么你可以走到下一间房子前,继续做选择。

当你走过了最后一间房子后,你就没得抢了,能抢到的钱显然是 0(base case)。

以上的逻辑很简单吧,其实已经明确了「状态」和「选择」:你面前房子的索引就是状态,抢和不抢就是选择

1

在两个选择中,每次都选更大的结果,最后得到的就是最多能抢到的 money:

// 主函数
public int rob(int[] nums) {
    return dp(nums, 0);
}
// 返回 nums[start..] 能抢到的最大值
private int dp(int[] nums, int start) {
    if (start >= nums.length) {
        return 0;
    }
    
    int res = Math.max(
            // 不抢,去下家
            dp(nums, start + 1), 
            // 抢,去下下家
            nums[start] + dp(nums, start + 2)
        );
    return res;
}

明确了状态转移,就可以发现对于同一 start 位置,是存在重叠子问题的,比如下图:

2

盗贼有多种选择可以走到这个位置,如果每次到这都进入递归,岂不是浪费时间?所以说存在重叠子问题,可以用备忘录进行优化:

private int[] memo;
// 主函数
public int rob(int[] nums) {
    // 初始化备忘录
    memo = new int[nums.length];
    Arrays.fill(memo, -1);
    // 强盗从第 0 间房子开始抢劫
    return dp(nums, 0);
}

// 返回 dp[start..] 能抢到的最大值
private int dp(int[] nums, int start) {
    if (start >= nums.length) {
        return 0;
    }
    // 避免重复计算
    if (memo[start] != -1) return memo[start];
    
    int res = Math.max(dp(nums, start + 1), 
                    nums[start] + dp(nums, start + 2));
    // 记入备忘录
    memo[start] = res;
    return res;
}

这就是自顶向下的动态规划解法,我们也可以略作修改,写出自底向上的解法:

 int rob(int[] nums) {
    int n = nums.length;
    // dp[i] = x 表示:
    // 从第 i 间房子开始抢劫,最多能抢到的钱为 x
    // base case: dp[n] = 0
    int[] dp = new int[n + 2];
    for (int i = n - 1; i >= 0; i--) {
        dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);
    }
    return dp[0];
}

我们又发现状态转移只和 dp[i] 最近的两个状态有关,所以可以进一步优化,将空间复杂度降低到 O(1)。

int rob(int[] nums) {
    int n = nums.length;
    // 记录 dp[i+1] 和 dp[i+2]
    int dp_i_1 = 0, dp_i_2 = 0;
    // 记录 dp[i]
    int dp_i = 0; 
    for (int i = n - 1; i >= 0; i--) {
        dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i;
}

以上的流程,在我们「动态规划详解」中详细解释过,相信大家都能手到擒来了。我认为很有意思的是这个问题的 follow up,需要基于我们现在的思路做一些巧妙的应变。

House Robber II

这道题目和第一道描述基本一样,强盗依然不能抢劫相邻的房子,输入依然是一个数组,但是告诉你这些房子不是一排,而是围成了一个圈

也就是说,现在第一间房子和最后一间房子也相当于是相邻的,不能同时抢。比如说输入数组 nums=[2,3,2],算法返回的结果应该是 3 而不是 4,因为开头和结尾不能同时被抢。

这个约束条件看起来应该不难解决,我们前文「单调栈解决 Next Greater Number」说过一种解决环形数组的方案,那么在这个问题上怎么处理呢?

首先,首尾房间不能同时被抢,那么只可能有三种不同情况:要么都不被抢;要么第一间房子被抢最后一间不抢;要么最后一间房子被抢第一间不抢。

3

那就简单了啊,这三种情况,那种的结果最大,就是最终答案呗!不过,其实我们不需要比较三种情况,只要比较情况二和情况三就行了,因为这两种情况对于房子的选择余地比情况一大呀,房子里的钱数都是非负数,所以选择余地大,最优决策结果肯定不会小

所以只需对之前的解法稍作修改即可:

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(robRange(nums, 0, n - 2), 
                    robRange(nums, 1, n - 1));
}

// 仅计算闭区间 [start,end] 的最优结果
int robRange(int[] nums, int start, int end) {
    int n = nums.length;
    int dp_i_1 = 0, dp_i_2 = 0;
    int dp_i = 0;
    for (int i = end; i >= start; i--) {
        dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
        dp_i_2 = dp_i_1;
        dp_i_1 = dp_i;
    }
    return dp_i;
}

至此,第二问也解决了。

House Robber III

第三题又想法设法地变花样了,此强盗发现现在面对的房子不是一排,不是一圈,而是一棵二叉树!房子在二叉树的节点上,相连的两个房子不能同时被抢劫,果然是传说中的高智商犯罪:

title

整体的思路完全没变,还是做抢或者不抢的选择,去收益较大的选择。甚至我们可以直接按这个套路写出代码:

Map<TreeNode, Integer> memo = new HashMap<>();
public int rob(TreeNode root) {
    if (root == null) return 0;
    // 利用备忘录消除重叠子问题
    if (memo.containsKey(root)) 
        return memo.get(root);
    // 抢,然后去下下家
    int do_it = root.val
        + (root.left == null ? 
            0 : rob(root.left.left) + rob(root.left.right))
        + (root.right == null ? 
            0 : rob(root.right.left) + rob(root.right.right));
    // 不抢,然后去下家
    int not_do = rob(root.left) + rob(root.right);
    
    int res = Math.max(do_it, not_do);
    memo.put(root, res);
    return res;
}

这道题就解决了,时间复杂度 O(N),N 为数的节点数。

但是这道题让我觉得巧妙的点在于,还有更漂亮的解法。比如下面是我在评论区看到的一个解法:

int rob(TreeNode root) {
    int[] res = dp(root);
    return Math.max(res[0], res[1]);
}

/* 返回一个大小为 2 的数组 arr
arr[0] 表示不抢 root 的话,得到的最大钱数
arr[1] 表示抢 root 的话,得到的最大钱数 */
int[] dp(TreeNode root) {
    if (root == null)
        return new int[]{0, 0};
    int[] left = dp(root.left);
    int[] right = dp(root.right);
    // 抢,下家就不能抢了
    int rob = root.val + left[0] + right[0];
    // 不抢,下家可抢可不抢,取决于收益大小
    int not_rob = Math.max(left[0], left[1])
                + Math.max(right[0], right[1]);
    
    return new int[]{not_rob, rob};
}

时间复杂度 O(N),空间复杂度只有递归函数堆栈所需的空间,不需要备忘录的额外空间。

你看他和我们的思路不一样,修改了递归函数的定义,略微修改了思路,使得逻辑自洽,依然得到了正确的答案,而且代码更漂亮。这就是我们前文「不同定义产生不同解法」所说过的动态规划问题的一个特性。

实际上,这个解法比我们的解法运行时间要快得多,虽然算法分析层面时间复杂度是相同的。原因在于此解法没有使用额外的备忘录,减少了数据操作的复杂性,所以实际运行效率会快。

查看原文

赞 1 收藏 0 评论 0

labuladong 发布了文章 · 2020-12-23

如何实现LRU算法

读完本文,你可以去力扣拿下如下题目:

146.LRU缓存机制

-----------

一、什么是 LRU 算法

就是一种缓存淘汰策略。

计算机的缓存容量有限,如果缓存满了就要删除一些内容,给新内容腾位置。但问题是,删除哪些内容呢?我们肯定希望删掉哪些没什么用的缓存,而把有用的数据继续留在缓存里,方便之后继续使用。那么,什么样的数据,我们判定为「有用的」的数据呢?

LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used,也就是说我们认为最近使用过的数据应该是是「有用的」,很久都没用过的数据应该是无用的,内存满了就优先删那些很久没用过的数据。

举个简单的例子,安卓手机都可以把软件放到后台运行,比如我先后打开了「设置」「手机管家」「日历」,那么现在他们在后台排列的顺序是这样的:

jietu

但是这时候如果我访问了一下「设置」界面,那么「设置」就会被提前到第一个,变成这样:

jietu

假设我的手机只允许我同时开 3 个应用程序,现在已经满了。那么如果我新开了一个应用「时钟」,就必须关闭一个应用为「时钟」腾出一个位置,关那个呢?

按照 LRU 的策略,就关最底下的「手机管家」,因为那是最久未使用的,然后把新开的应用放到最上面:

jietu

现在你应该理解 LRU(Least Recently Used)策略了。当然还有其他缓存淘汰策略,比如不要按访问的时序来淘汰,而是按访问频率(LFU 策略)来淘汰等等,各有应用场景。本文讲解 LRU 算法策略。

二、LRU 算法描述

LRU 算法实际上是让你设计数据结构:首先要接收一个 capacity 参数作为缓存的最大容量,然后实现两个 API,一个是 put(key, val) 方法存入键值对,另一个是 get(key) 方法获取 key 对应的 val,如果 key 不存在则返回 -1。

注意哦,get 和 put 方法必须都是 O(1) 的时间复杂度,我们举个具体例子来看看 LRU 算法怎么工作。

/* 缓存容量为 2 */
LRUCache cache = new LRUCache(2);
// 你可以把 cache 理解成一个队列
// 假设左边是队头,右边是队尾
// 最近使用的排在队头,久未使用的排在队尾
// 圆括号表示键值对 (key, val)

cache.put(1, 1);
// cache = [(1, 1)]
cache.put(2, 2);
// cache = [(2, 2), (1, 1)]
cache.get(1);       // 返回 1
// cache = [(1, 1), (2, 2)]
// 解释:因为最近访问了键 1,所以提前至队头
// 返回键 1 对应的值 1
cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// 解释:缓存容量已满,需要删除内容空出位置
// 优先删除久未使用的数据,也就是队尾的数据
// 然后把新的数据插入队头
cache.get(2);       // 返回 -1 (未找到)
// cache = [(3, 3), (1, 1)]
// 解释:cache 中不存在键为 2 的数据
cache.put(1, 4);    
// cache = [(1, 4), (3, 3)]
// 解释:键 1 已存在,把原始值 1 覆盖为 4
// 不要忘了也要将键值对提前到队头

三、LRU 算法设计

分析上面的操作过程,要让 put 和 get 方法的时间复杂度为 O(1),我们可以总结出 cache 这个数据结构必要的条件:查找快,插入快,删除快,有顺序之分。

因为显然 cache 必须有顺序之分,以区分最近使用的和久未使用的数据;而且我们要在 cache 中查找键是否已存在;如果容量满了要删除最后一个数据;每次访问还要把数据插入到队头。

那么,什么数据结构同时符合上述条件呢?哈希表查找快,但是数据无固定顺序;链表有顺序之分,插入删除快,但是查找慢。所以结合一下,形成一种新的数据结构:哈希链表。

LRU 缓存算法的核心数据结构就是哈希链表,双向链表和哈希表的结合体。这个数据结构长这样:

HashLinkedList

思想很简单,就是借助哈希表赋予了链表快速查找的特性嘛:可以快速查找某个 key 是否存在缓存(链表)中,同时可以快速删除、添加节点。回想刚才的例子,这种数据结构是不是完美解决了 LRU 缓存的需求?

也许读者会问,为什么要是双向链表,单链表行不行?另外,既然哈希表中已经存了 key,为什么链表中还要存键值对呢,只存值不就行了?

想的时候都是问题,只有做的时候才有答案。这样设计的原因,必须等我们亲自实现 LRU 算法之后才能理解,所以我们开始看代码吧~

四、代码实现

很多编程语言都有内置的哈希链表或者类似 LRU 功能的库函数,但是为了帮大家理解算法的细节,我们用 Java 自己造轮子实现一遍 LRU 算法。

首先,我们把双链表的节点类写出来,为了简化,key 和 val 都认为是 int 类型:

class Node {
    public int key, val;
    public Node next, prev;
    public Node(int k, int v) {
        this.key = k;
        this.val = v;
    }
}

然后依靠我们的 Node 类型构建一个双链表,实现几个需要的 API(这些操作的时间复杂度均为 O(1)):

class DoubleList {  
    // 在链表头部添加节点 x,时间 O(1)
    public void addFirst(Node x);

    // 删除链表中的 x 节点(x 一定存在)
    // 由于是双链表且给的是目标 Node 节点,时间 O(1)
    public void remove(Node x);
    
    // 删除链表中最后一个节点,并返回该节点,时间 O(1)
    public Node removeLast();
    
    // 返回链表长度,时间 O(1)
    public int size();
}

PS:这就是普通双向链表的实现,为了让读者集中精力理解 LRU 算法的逻辑,就省略链表的具体代码。

到这里就能回答刚才“为什么必须要用双向链表”的问题了,因为我们需要删除操作。删除一个节点不光要得到该节点本身的指针,也需要操作其前驱节点的指针,而双向链表才能支持直接查找前驱,保证操作的时间复杂度 O(1)

有了双向链表的实现,我们只需要在 LRU 算法中把它和哈希表结合起来即可。我们先把逻辑理清楚:

// key 映射到 Node(key, val)
HashMap<Integer, Node> map;
// Node(k1, v1) <-> Node(k2, v2)...
DoubleList cache;

int get(int key) {
    if (key 不存在) {
        return -1;
    } else {        
        将数据 (key, val) 提到开头;
        return val;
    }
}

void put(int key, int val) {
    Node x = new Node(key, val);
    if (key 已存在) {
        把旧的数据删除;
        将新节点 x 插入到开头;
    } else {
        if (cache 已满) {
            删除链表的最后一个数据腾位置;
            删除 map 中映射到该数据的键;
        } 
        将新节点 x 插入到开头;
        map 中新建 key 对新节点 x 的映射;
    }
}

如果能够看懂上述逻辑,翻译成代码就很容易理解了:

class LRUCache {
    // key -> Node(key, val)
    private HashMap<Integer, Node> map;
    // Node(k1, v1) <-> Node(k2, v2)...
    private DoubleList cache;
    // 最大容量
    private int cap;
    
    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    
    public int get(int key) {
        if (!map.containsKey(key))
            return -1;
        int val = map.get(key).val;
        // 利用 put 方法把该数据提前
        put(key, val);
        return val;
    }
    
    public void put(int key, int val) {
        // 先把新节点 x 做出来
        Node x = new Node(key, val);
        
        if (map.containsKey(key)) {
            // 删除旧的节点,新的插到头部
            cache.remove(map.get(key));
            cache.addFirst(x);
            // 更新 map 中对应的数据
            map.put(key, x);
        } else {
            if (cap == cache.size()) {
                // 删除链表最后一个数据
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            // 直接添加到头部
            cache.addFirst(x);
            map.put(key, x);
        }
    }
}

这里就能回答之前的问答题“为什么要在链表中同时存储 key 和 val,而不是只存储 val”,注意这段代码:

if (cap == cache.size()) {
    // 删除链表最后一个数据
    Node last = cache.removeLast();
    map.remove(last.key);
}

当缓存容量已满,我们不仅仅要删除最后一个 Node 节点,还要把 map 中映射到该节点的 key 同时删除,而这个 key 只能由 Node 得到。如果 Node 结构中只存储 val,那么我们就无法得知 key 是什么,就无法删除 map 中的键,造成错误。

至此,你应该已经掌握 LRU 算法的思想和实现了,很容易犯错的一点是:处理链表节点的同时不要忘了更新哈希表中对节点的映射。

查看原文

赞 0 收藏 0 评论 0

labuladong 发布了文章 · 2020-12-23

字符串乘法

读完本文,你可以去力扣拿下如下题目:

43.字符串相乘

-----------

对于比较小的数字,做运算可以直接使用编程语言提供的运算符,但是如果相乘的两个因数非常大,语言提供的数据类型可能就会溢出。一种替代方案就是,运算数以字符串的形式输入,然后模仿我们小学学习的乘法算术过程计算出结果,并且也用字符串表示。

需要注意的是,num1num2 可以非常长,所以不可以把他们直接转成整型然后运算,唯一的思路就是模仿我们手算乘法。

比如说我们手算 123 × 45,应该会这样计算:

计算 123 × 5,再计算 123 × 4,最后错一位相加。这个流程恐怕小学生都可以熟练完成,但是你是否能把这个运算过程进一步机械化,写成一套算法指令让没有任何智商的计算机来执行呢?

你看这个简单过程,其中涉及乘法进位,涉及错位相加,还涉及加法进位;而且还有一些不易察觉的问题,比如说两位数乘以两位数,结果可能是四位数,也可能是三位数,你怎么想出一个标准化的处理方式?这就是算法的魅力,如果没有计算机思维,简单的问题可能都没办法自动化处理。

首先,我们这种手算方式还是太「高级」了,我们要再「低级」一点,123 × 5123 × 4 的过程还可以进一步分解,最后再相加:

现在 123 并不大,如果是个很大的数字的话,是无法直接计算乘积的。我们可以用一个数组在底下接收相加结果:

整个计算过程大概是这样,有两个指针 i,jnum1num2 上游走,计算乘积,同时将乘积叠加到 res 的正确位置

现在还有一个关键问题,如何将乘积叠加到 res 的正确位置,或者说,如何通过 i,j 计算 res 的对应索引呢?

其实,细心观察之后就发现,num1[i]num2[j] 的乘积对应的就是 res[i+j]res[i+j+1] 这两个位置

明白了这一点,就可以用代码模仿出这个计算过程了:

string multiply(string num1, string num2) {
    int m = num1.size(), n = num2.size();
    // 结果最多为 m + n 位数
    vector<int> res(m + n, 0);
    // 从个位数开始逐位相乘
    for (int i = m - 1; i >= 0; i--)
        for (int j = n - 1; j >= 0; j--) {
            int mul = (num1[i]-'0') * (num2[j]-'0');
            // 乘积在 res 对应的索引位置
            int p1 = i + j, p2 = i + j + 1;
            // 叠加到 res 上
            int sum = mul + res[p2];
            res[p2] = sum % 10;
            res[p1] += sum / 10;
        }
    // 结果前缀可能存的 0(未使用的位)
    int i = 0;
    while (i < res.size() && res[i] == 0)
        i++;
    // 将计算结果转化成字符串
    string str;
    for (; i < res.size(); i++)
        str.push_back('0' + res[i]);
    
    return str.size() == 0 ? "0" : str;
}

至此,字符串乘法算法就完成了。

总结一下,我们习以为常的一些思维方式,在计算机看来是非常难以做到的。比如说我们习惯的算术流程并不复杂,但是如果让你再进一步,翻译成代码逻辑,并不简单。算法需要将计算流程再简化,通过边算边叠加的方式来得到结果。

俗话教育我们,不要陷入思维定式,不要程序化,要发散思维,要创新。但我觉得程序化并不是坏事,可以大幅提高效率,减小失误率。算法不就是一套程序化的思维吗,只有程序化才能让计算机帮助我们解决复杂问题呀!

也许算法就是一种寻找思维定式的思维吧,希望本文对你有帮助。

查看原文

赞 0 收藏 0 评论 0

labuladong 发布了文章 · 2020-12-23

学习算法和刷题的思路指南

-----------

通知:如果本站对你学习算法有帮助,请收藏网址,并推荐给你的朋友。由于 labuladong 的算法套路太火,很多人直接拿我的 GitHub 文章去开付费专栏,价格还不便宜。我这免费写给你看,多宣传原创作者是你唯一能做的,谁也不希望劣币驱逐良币对吧?

这是好久之前的一篇文章「学习数据结构和算法的框架思维」的修订版。之前那篇文章收到广泛好评,没看过也没关系,这篇文章会涵盖之前的所有内容,并且会举很多代码的实例,教你如何使用框架思维。

首先,这里讲的都是普通的数据结构,咱不是搞算法竞赛的,野路子出生,我只会解决常规的问题。另外,以下是我个人的经验的总结,没有哪本算法书会写这些东西,所以请读者试着理解我的角度,别纠结于细节问题,因为这篇文章就是希望对数据结构和算法建立一个框架性的认识。

从整体到细节,自顶向下,从抽象到具体的框架思维是通用的,不只是学习数据结构和算法,学习其他任何知识都是高效的。

一、数据结构的存储方式

数据结构的存储方式只有两种:数组(顺序存储)和链表(链式存储)

这句话怎么理解,不是还有散列表、栈、队列、堆、树、图等等各种数据结构吗?

我们分析问题,一定要有递归的思想,自顶向下,从抽象到具体。你上来就列出这么多,那些都属于「上层建筑」,而数组和链表才是「结构基础」。因为那些多样化的数据结构,究其源头,都是在链表或者数组上的特殊操作,API 不同而已。

比如说「队列」、「栈」这两种数据结构既可以使用链表也可以使用数组实现。用数组实现,就要处理扩容缩容的问题;用链表实现,没有这个问题,但需要更多的内存空间存储节点指针。

「图」的两种表示方法,邻接表就是链表,邻接矩阵就是二维数组。邻接矩阵判断连通性迅速,并可以进行矩阵运算解决一些问题,但是如果图比较稀疏的话很耗费空间。邻接表比较节省空间,但是很多操作的效率上肯定比不过邻接矩阵。

「散列表」就是通过散列函数把键映射到一个大数组里。而且对于解决散列冲突的方法,拉链法需要链表特性,操作简单,但需要额外的空间存储指针;线性探查法就需要数组特性,以便连续寻址,不需要指针的存储空间,但操作稍微复杂些。

「树」,用数组实现就是「堆」,因为「堆」是一个完全二叉树,用数组存储不需要节点指针,操作也比较简单;用链表实现就是很常见的那种「树」,因为不一定是完全二叉树,所以不适合用数组存储。为此,在这种链表「树」结构之上,又衍生出各种巧妙的设计,比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等,以应对不同的问题。

了解 Redis 数据库的朋友可能也知道,Redis 提供列表、字符串、集合等等几种常用数据结构,但是对于每种数据结构,底层的存储方式都至少有两种,以便于根据存储数据的实际情况使用合适的存储方式。

综上,数据结构种类很多,甚至你也可以发明自己的数据结构,但是底层存储无非数组或者链表,二者的优缺点如下

数组由于是紧凑连续存储,可以随机访问,通过索引快速找到对应元素,而且相对节约存储空间。但正因为连续存储,内存空间必须一次性分配够,所以说数组如果要扩容,需要重新分配一块更大的空间,再把数据全部复制过去,时间复杂度 O(N);而且你如果想在数组中间进行插入和删除,每次必须搬移后面的所有数据以保持连续,时间复杂度 O(N)。

链表因为元素不连续,而是靠指针指向下一个元素的位置,所以不存在数组的扩容问题;如果知道某一元素的前驱和后驱,操作指针即可删除该元素或者插入新元素,时间复杂度 O(1)。但是正因为存储空间不连续,你无法根据一个索引算出对应元素的地址,所以不能随机访问;而且由于每个元素必须存储指向前后元素位置的指针,会消耗相对更多的储存空间。

二、数据结构的基本操作

对于任何数据结构,其基本操作无非遍历 + 访问,再具体一点就是:增删查改。

数据结构种类很多,但它们存在的目的都是在不同的应用场景,尽可能高效地增删查改。话说这不就是数据结构的使命么?

如何遍历 + 访问?我们仍然从最高层来看,各种数据结构的遍历 + 访问无非两种形式:线性的和非线性的。

线性就是 for/while 迭代为代表,非线性就是递归为代表。再具体一步,无非以下几种框架:

数组遍历框架,典型的线性迭代结构:

void traverse(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        // 迭代访问 arr[i]
    }
}

链表遍历框架,兼具迭代和递归结构:

/* 基本的单链表节点 */
class ListNode {
    int val;
    ListNode next;
}

void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next) {
        // 迭代访问 p.val
    }
}

void traverse(ListNode head) {
    // 递归访问 head.val
    traverse(head.next)
}

二叉树遍历框架,典型的非线性递归遍历结构:

/* 基本的二叉树节点 */
class TreeNode {
    int val;
    TreeNode left, right;
}

void traverse(TreeNode root) {
    traverse(root.left)
    traverse(root.right)
}

你看二叉树的递归遍历方式和链表的递归遍历方式,相似不?再看看二叉树结构和单链表结构,相似不?如果再多几条叉,N 叉树你会不会遍历?

二叉树框架可以扩展为 N 叉树的遍历框架:

/* 基本的 N 叉树节点 */
class TreeNode {
    int val;
    TreeNode[] children;
}

void traverse(TreeNode root) {
    for (TreeNode child : root.children)
        traverse(child);
}

N 叉树的遍历又可以扩展为图的遍历,因为图就是好几 N 叉棵树的结合体。你说图是可能出现环的?这个很好办,用个布尔数组 visited 做标记就行了,这里就不写代码了。

所谓框架,就是套路。不管增删查改,这些代码都是永远无法脱离的结构,你可以把这个结构作为大纲,根据具体问题在框架上添加代码就行了,下面会具体举例

三、算法刷题指南

首先要明确的是,数据结构是工具,算法是通过合适的工具解决特定问题的方法。也就是说,学习算法之前,最起码得了解那些常用的数据结构,了解它们的特性和缺陷。

那么该如何在 LeetCode 刷题呢?之前的文章算法学习之路写过一些,什么按标签刷,坚持下去云云。现在距那篇文章已经过去将近一年了,我不说那些不痛不痒的话,直接说具体的建议:

先刷二叉树,先刷二叉树,先刷二叉树

这是我这刷题一年的亲身体会,下图是去年十月份的提交截图:

公众号文章的阅读数据显示,大部分人对数据结构相关的算法文章不感兴趣,而是更关心动规回溯分治等等技巧。为什么要先刷二叉树呢,因为二叉树是最容易培养框架思维的,而且大部分算法技巧,本质上都是树的遍历问题

刷二叉树看到题目没思路?根据很多读者的问题,其实大家不是没思路,只是没有理解我们说的「框架」是什么。不要小看这几行破代码,几乎所有二叉树的题目都是一套这个框架就出来了

void traverse(TreeNode root) {
    // 前序遍历
    traverse(root.left)
    // 中序遍历
    traverse(root.right)
    // 后序遍历
}

比如说我随便拿几道题的解法出来,不用管具体的代码逻辑,只要看看框架在其中是如何发挥作用的就行。

LeetCode 124 题,难度 Hard,让你求二叉树中最大路径和,主要代码如下:

int ans = INT_MIN;
int oneSideMax(TreeNode* root) {
    if (root == nullptr) return 0;
    int left = max(0, oneSideMax(root->left));
    int right = max(0, oneSideMax(root->right));
    ans = max(ans, left + right + root->val);
    return max(left, right) + root->val;
}

你看,这就是个后序遍历嘛。

LeetCode 105 题,难度 Medium,让你根据前序遍历和中序遍历的结果还原一棵二叉树,很经典的问题吧,主要代码如下:

TreeNode buildTree(int[] preorder, int preStart, int preEnd, 
    int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inMap) {

    if(preStart > preEnd || inStart > inEnd) return null;

    TreeNode root = new TreeNode(preorder[preStart]);
    int inRoot = inMap.get(root.val);
    int numsLeft = inRoot - inStart;

    root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, 
                          inorder, inStart, inRoot - 1, inMap);
    root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, 
                          inorder, inRoot + 1, inEnd, inMap);
    return root;
}

不要看这个函数的参数很多,只是为了控制数组索引而已,本质上该算法也就是一个前序遍历。

LeetCode 99 题,难度 Hard,恢复一棵 BST,主要代码如下:

void traverse(TreeNode* node) {
    if (!node) return;
    traverse(node->left);
    if (node->val < prev->val) {
        s = (s == NULL) ? prev : s;
        t = node;
    }
    prev = node;
    traverse(node->right);
}

这不就是个中序遍历嘛,对于一棵 BST 中序遍历意味着什么,应该不需要解释了吧。

你看,Hard 难度的题目不过如此,而且还这么有规律可循,只要把框架写出来,然后往相应的位置加东西就行了,这不就是思路吗。

对于一个理解二叉树的人来说,刷一道二叉树的题目花不了多长时间。那么如果你对刷题无从下手或者有畏惧心理,不妨从二叉树下手,前 10 道也许有点难受;结合框架再做 20 道,也许你就有点自己的理解了;刷完整个专题,再去做什么回溯动规分治专题,你就会发现只要涉及递归的问题,都是树的问题

再举例吧,说几道我们之前文章写过的问题。

动态规划详解说过凑零钱问题,暴力解法就是遍历一棵 N 叉树:

def coinChange(coins: List[int], amount: int):

    def dp(n):
        if n == 0: return 0
        if n < 0: return -1

        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coin)
            # 子问题无解,跳过
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)
        return res if res != float('INF') else -1
    
    return dp(amount)

这么多代码看不懂咋办?直接提取出框架,就能看出核心思路了:

# 不过是一个 N 叉树的遍历问题而已
def dp(n):
    for coin in coins:
        dp(n - coin)

其实很多动态规划问题就是在遍历一棵树,你如果对树的遍历操作烂熟于心,起码知道怎么把思路转化成代码,也知道如何提取别人解法的核心思路。

再看看回溯算法,前文回溯算法详解干脆直接说了,回溯算法就是个 N 叉树的前后序遍历问题,没有例外。

比如 N 皇后问题吧,主要代码如下:

void backtrack(int[] nums, LinkedList<Integer> track) {
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (track.contains(nums[i]))
            continue;
        track.add(nums[i]);
        // 进入下一层决策树
        backtrack(nums, track);
        track.removeLast();
    }

/* 提取出 N 叉树遍历框架 */
void backtrack(int[] nums, LinkedList<Integer> track) {
    for (int i = 0; i < nums.length; i++) {
        backtrack(nums, track);
}

N 叉树的遍历框架,找出来了把~你说,树这种结构重不重要?

综上,对于畏惧算法的朋友来说,可以先刷树的相关题目,试着从框架上看问题,而不要纠结于细节问题

纠结细节问题,就比如纠结 i 到底应该加到 n 还是加到 n - 1,这个数组的大小到底应该开 n 还是 n + 1 ?

从框架上看问题,就是像我们这样基于框架进行抽取和扩展,既可以在看别人解法时快速理解核心逻辑,也有助于找到我们自己写解法时的思路方向。

当然,如果细节出错,你得不到正确的答案,但是只要有框架,你再错也错不到哪去,因为你的方向是对的。

但是,你要是心中没有框架,那么你根本无法解题,给了你答案,你也不会发现这就是个树的遍历问题。

这种思维是很重要的,动态规划详解中总结的找状态转移方程的几步流程,有时候按照流程写出解法,说实话我自己都不知道为啥是对的,反正它就是对了。。。

这就是框架的力量,能够保证你在快睡着的时候,依然能写出正确的程序;就算你啥都不会,都能比别人高一个级别。

四、总结几句

数据结构的基本存储方式就是链式和顺序两种,基本操作就是增删查改,遍历方式无非迭代和递归。

刷算法题建议从「树」分类开始刷,结合框架思维,把这几十道题刷完,对于树结构的理解应该就到位了。这时候去看回溯、动规、分治等算法专题,对思路的理解可能会更加深刻一些。

查看原文

赞 0 收藏 0 评论 0

labuladong 发布了文章 · 2020-12-22

信封嵌套问题

读完本文,你可以去力扣拿下如下题目:

354.俄罗斯套娃信封问题

-----------

很多算法问题都需要排序技巧,其难点不在于排序本身,而是需要巧妙地排序进行预处理,将算法问题进行转换,为之后的操作打下基础。

信封嵌套问题就需要先按特定的规则排序,之后就转换为一个 最长递增子序列问题 的技巧来解决了。

一、题目概述

信封嵌套问题是个很有意思且经常出现在生活中的问题,先看下题目:

title

这道题目其实是最长递增子序列(Longes Increasing Subsequence,简写为 LIS)的一个变种,因为很显然,每次合法的嵌套是大的套小的,相当于找一个最长递增的子序列,其长度就是最多能嵌套的信封个数。

但是难点在于,标准的 LIS 算法只能在数组中寻找最长子序列,而我们的信封是由 (w, h) 这样的二维数对形式表示的,如何把 LIS 算法运用过来呢?

0

读者也许会想,通过 w × h 计算面积,然后对面积进行标准的 LIS 算法。但是稍加思考就会发现这样不行,比如 1 × 10 大于 3 × 3,但是显然这样的两个信封是无法互相嵌套的。

二、解法

这道题的解法是比较巧妙的:

先对宽度 w 进行升序排序,如果遇到 w 相同的情况,则按照高度 h 降序排序。之后把所有的 h 作为一个数组,在这个数组上计算 LIS 的长度就是答案。

画个图理解一下,先对这些数对进行排序:

1

然后在 h 上寻找最长递增子序列:

2

这个子序列就是最优的嵌套方案。

这个解法的关键在于,对于宽度 w 相同的数对,要对其高度 h 进行降序排序。因为两个宽度相同的信封不能相互包含的,逆序排序保证在 w 相同的数对中最多只选取一个。

下面看代码:

// envelopes = [[w, h], [w, h]...]
public int maxEnvelopes(int[][] envelopes) {
    int n = envelopes.length;
    // 按宽度升序排列,如果宽度一样,则按高度降序排列
    Arrays.sort(envelopes, new Comparator<int[]>() 
    {
        public int compare(int[] a, int[] b) {
            return a[0] == b[0] ? 
                b[1] - a[1] : a[0] - b[0];
        }
    });
    // 对高度数组寻找 LIS
    int[] height = new int[n];
    for (int i = 0; i < n; i++)
        height[i] = envelopes[i][1];

    return lengthOfLIS(height);
}

关于最长递增子序列的寻找方法,在前文中详细介绍了动态规划解法,并用扑克牌游戏解释了二分查找解法,本文就不展开了,直接套用算法模板:

/* 返回 nums 中 LIS 的长度 */
public int lengthOfLIS(int[] nums) {
    int piles = 0, n = nums.length;
    int[] top = new int[n];
    for (int i = 0; i < n; i++) {
        // 要处理的扑克牌
        int poker = nums[i];
        int left = 0, right = piles;
        // 二分查找插入位置
        while (left < right) {
            int mid = (left + right) / 2;
            if (top[mid] >= poker)
                right = mid;
            else
                left = mid + 1;
        }
        if (left == piles) piles++;
        // 把这张牌放到牌堆顶
        top[left] = poker;
    }
    // 牌堆数就是 LIS 长度
    return piles;
}

为了清晰,我将代码分为了两个函数, 你也可以合并,这样可以节省下 height 数组的空间。

此算法的时间复杂度为 O(NlogN),因为排序和计算 LIS 各需要 O(NlogN) 的时间。

空间复杂度为 O(N),因为计算 LIS 的函数中需要一个 top 数组。

三、总结

这个问题是个 Hard 级别的题目,难就难在排序,正确地排序后此问题就被转化成了一个标准的 LIS 问题,容易解决一些。

其实这种问题还可以拓展到三维,比如说现在不是让你嵌套信封,而是嵌套箱子,每个箱子有长宽高三个维度,请你算算最多能嵌套几个箱子?

我们可能会这样想,先把前两个维度(长和宽)按信封嵌套的思路求一个嵌套序列,最后在这个序列的第三个维度(高度)找一下 LIS,应该能算出答案。

实际上,这个思路是错误的。这类问题叫做「偏序问题」,上升到三维会使难度巨幅提升,需要借助一种高级数据结构「树状数组」,有兴趣的读者可以自行搜索。

有很多算法问题都需要排序后进行处理,阿东正在进行整理总结。希望本文对你有帮助。

查看原文

赞 0 收藏 0 评论 0

labuladong 发布了文章 · 2020-12-22

洗牌算法

读完本文,你可以去力扣拿下如下题目:

384.打乱数组

-----------

我知道大家会各种花式排序算法,但是如果叫你打乱一个数组,你是否能做到胸有成竹?即便你拍脑袋想出一个算法,怎么证明你的算法就是正确的呢?乱序算法不像排序算法,结果唯一可以很容易检验,因为「乱」可以有很多种,你怎么能证明你的算法是「真的乱」呢?

所以我们面临两个问题:

  1. 什么叫做「真的乱」?
  2. 设计怎样的算法来打乱数组才能做到「真的乱」?

这种算法称为「随机乱置算法」或者「洗牌算法」。

本文分两部分,第一部分详解最常用的洗牌算法。因为该算法的细节容易出错,且存在好几种变体,虽有细微差异但都是正确的,所以本文要介绍一种简单的通用思想保证你写出正确的洗牌算法。第二部分讲解使用「蒙特卡罗方法」来检验我们的打乱结果是不是真的乱。蒙特卡罗方法的思想不难,但是实现方式也各有特点的。

一、洗牌算法

此类算法都是靠随机选取元素交换来获取随机性,直接看代码(伪码),该算法有 4 种形式,都是正确的:

// 得到一个在闭区间 [min, max] 内的随机整数
int randInt(int min, int max);

// 第一种写法
void shuffle(int[] arr) {
    int n = arr.length();
    /******** 区别只有这两行 ********/
    for (int i = 0 ; i < n; i++) {
        // 从 i 到最后随机选一个元素
        int rand = randInt(i, n - 1);
        /*************************/
        swap(arr[i], arr[rand]);
    }
}

// 第二种写法
    for (int i = 0 ; i < n - 1; i++)
        int rand = randInt(i, n - 1);

// 第三种写法
    for (int i = n - 1 ; i >= 0; i--)
        int rand = randInt(0, i);

// 第四种写法
    for (int i = n - 1 ; i > 0; i--)
        int rand = randInt(0, i);

分析洗牌算法正确性的准则:产生的结果必须有 n! 种可能,否则就是错误的。这个很好解释,因为一个长度为 n 的数组的全排列就有 n! 种,也就是说打乱结果总共有 n! 种。算法必须能够反映这个事实,才是正确的。

我们先用这个准则分析一下第一种写法的正确性:

// 假设传入这样一个 arr
int[] arr = {1,3,5,7,9};

void shuffle(int[] arr) {
    int n = arr.length(); // 5
    for (int i = 0 ; i < n; i++) {
        int rand = randInt(i, n - 1);
        swap(arr[i], arr[rand]);
    }
}

for 循环第一轮迭代时,i = 0rand 的取值范围是 [0, 4],有 5 个可能的取值。

第一次

for 循环第二轮迭代时,i = 1rand 的取值范围是 [1, 4],有 4 个可能的取值。

第二次

后面以此类推,直到最后一次迭代,i = 4rand 的取值范围是 [4, 4],只有 1 个可能的取值。

最后一次

可以看到,整个过程产生的所有可能结果有 n! = 5! = 5*4*3*2*1 种,所以这个算法是正确的。

分析第二种写法,前面的迭代都是一样的,少了一次迭代而已。所以最后一次迭代时 i = 3rand 的取值范围是 [3, 4],有 2 个可能的取值。

// 第二种写法
// arr = {1,3,5,7,9}, n = 5
    for (int i = 0 ; i < n - 1; i++)
        int rand = randInt(i, n - 1);

所以整个过程产生的所有可能结果仍然有 5*4*3*2 = 5! = n! 种,因为乘以 1 可有可无嘛。所以这种写法也是正确的。

如果以上内容你都能理解,那么你就能发现第三种写法就是第一种写法,只是将数组从后往前迭代而已;第四种写法是第二种写法从后往前来。所以它们都是正确的。

如果读者思考过洗牌算法,可能会想出如下的算法,但是这种写法是错误的

void shuffle(int[] arr) {
    int n = arr.length();
    for (int i = 0 ; i < n; i++) {
        // 每次都从闭区间 [0, n-1]
        // 中随机选取元素进行交换
        int rand = randInt(0, n - 1);
        swap(arr[i], arr[rand]);
    }
}

现在你应该明白这种写法为什么会错误了。因为这种写法得到的所有可能结果有 n^n 种,而不是 n! 种,而且 n^n 不可能是 n! 的整数倍。

比如说 arr = {1,2,3},正确的结果应该有 3!= 6 种可能,而这种写法总共有 3^3 = 27 种可能结果。因为 27 不能被 6 整除,所以一定有某些情况被「偏袒」了,也就是说某些情况出现的概率会大一些,所以这种打乱结果不算「真的乱」。

上面我们从直觉上简单解释了洗牌算法正确的准则,没有数学证明,我想大家也懒得证明。对于概率问题我们可以使用「蒙特卡罗方法」进行简单验证。

二、蒙特卡罗方法验证正确性

洗牌算法,或者说随机乱置算法的正确性衡量标准是:对于每种可能的结果出现的概率必须相等,也就是说要足够随机。

如果不用数学严格证明概率相等,可以用蒙特卡罗方法近似地估计出概率是否相等,结果是否足够随机。

记得高中有道数学题:往一个正方形里面随机打点,这个正方形里紧贴着一个圆,告诉你打点的总数和落在圆里的点的数量,让你计算圆周率。

正方形

这其实就是利用了蒙特卡罗方法:当打的点足够多的时候,点的数量就可以近似代表图形的面积。通过面积公式,由正方形和圆的面积比值是可以很容易推出圆周率的。当然打的点越多,算出的圆周率越准确,充分体现了大力出奇迹的真理。

类似的,我们可以对同一个数组进行一百万次洗牌,统计各种结果出现的次数,把频率作为概率,可以很容易看出洗牌算法是否正确。整体思想很简单,不过实现起来也有些技巧的,下面简单分析几种实现思路。

第一种思路,我们把数组 arr 的所有排列组合都列举出来,做成一个直方图(假设 arr = {1,2,3}):

直方图

每次进行洗牌算法后,就把得到的打乱结果对应的频数加一,重复进行 100 万次,如果每种结果出现的总次数差不多,那就说明每种结果出现的概率应该是相等的。写一下这个思路的伪代码:

void shuffle(int[] arr);

// 蒙特卡罗
int N = 1000000;
HashMap count; // 作为直方图
for (i = 0; i < N; i++) {
    int[] arr = {1,2,3};
    shuffle(arr);
    // 此时 arr 已被打乱
    count[arr] += 1;
}
for (int feq : count.values()) 
    print(feq / N + " "); // 频率

这种检验方案是可行的,不过可能有读者会问,arr 的全部排列有 n! 种(n 为 arr 的长度),如果 n 比较大,那岂不是空间复杂度爆炸了?

是的,不过作为一种验证方法,我们不需要 n 太大,一般用长度为 5 或 6 的 arr 试下就差不多了吧,因为我们只想比较概率验证一下正确性而已。

第二种思路,可以这样想,arr 数组中全都是 0,只有一个 1。我们对 arr 进行 100 万次打乱,记录每个索引位置出现 1 的次数,如果每个索引出现的次数差不多,也可以说明每种打乱结果的概率是相等的。

void shuffle(int[] arr);

// 蒙特卡罗方法
int N = 1000000;    
int[] arr = {1,0,0,0,0};
int[] count = new int[arr.length];
for (int i = 0; i < N; i++) {
    shuffle(arr); // 打乱 arr
    for (int j = 0; j < arr.length; j++) 
        if (arr[j] == 1) {
            count[j]++;
            break;
        }
}
for (int feq : count) 
    print(feq / N + " "); // 频率

直方图

这种思路也是可行的,而且避免了阶乘级的空间复杂度,但是多了嵌套 for 循环,时间复杂度高一点。不过由于我们的测试数据量不会有多大,这些问题都可以忽略。

另外,细心的读者可能发现一个问题,上述两种思路声明 arr 的位置不同,一个在 for 循环里,一个在 for 循环之外。其实效果都是一样的,因为我们的算法总要打乱 arr,所以 arr 的顺序并不重要,只要元素不变就行。

三、最后总结

本文第一部分介绍了洗牌算法(随机乱置算法),通过一个简单的分析技巧证明了该算法的四种正确形式,并且分析了一种常见的错误写法,相信你一定能够写出正确的洗牌算法了。

第二部分写了洗牌算法正确性的衡量标准,即每种随机结果出现的概率必须相等。如果我们不用严格的数学证明,可以通过蒙特卡罗方法大力出奇迹,粗略验证算法的正确性。蒙特卡罗方法也有不同的思路,不过要求不必太严格,因为我们只是寻求一个简单的验证。

查看原文

赞 0 收藏 0 评论 0

labuladong 发布了文章 · 2020-12-22

学习数据结构和算法读什么书

-----------

通知:如果本站对你学习算法有帮助,请收藏网址,并推荐给你的朋友。由于 labuladong 的算法套路太火,很多人直接拿我的 GitHub 文章去开付费专栏,价格还不便宜。我这免费写给你看,多宣传原创作者是你唯一能做的,谁也不希望劣币驱逐良币对吧?

咱们的公众号有很多硬核的算法文章,今天就聊点轻松的,就具体聊聊我非常“鼓吹”的《算法4》。这本书我在之前的文章多次推荐过,但是没有具体的介绍,今天就来正式介绍一下。。

我的推荐不会直接甩一大堆书目,而是会联系实际生活,讲一些书中有趣有用的知识,无论你最后会不会去看这本书,本文都会给你带来一些收获。

首先这本书是适合初学者的。总是有很多读者问,我只会 C 语言,能不能看《算法4》?学算法最好用什么语言?诸如此类的问题。

经常看咱们公众号的读者应该体会到了,算法其实是一种思维模式,和你用什么语言没啥关系。我们的文章也不会固定用某一种语言,而是什么语言写出来容易理解就用什么语言。再退一步说,到底适不适合你,网上找个 PDF 亲自看一下不就知道了?

《算法4》看起来挺厚的,但是前面几十页是教你 Java 的;每章后面还有习题,占了不少页数;每章还有一些数学证明,这些都可以忽略。这样算下来,剩下的就是基础知识和疑难解答之类的内容,含金量很高,把这些基础知识动手实践一遍,真的就可以达到不错的水平了。

我觉得这本书之所以能有这么高的评分,一个是因为讲解详细,还有大量配图,另一个原因就是书中把一些算法和现实生活中的使用场景联系起来,你不仅知道某个算法怎么实现,也知道它大概能运用到什么场景,下面我就来介绍两个图算法的简单应用。

一、二分图的应用

我想举的第一个例子是二分图。简单来说,二分图就是一幅拥有特殊性质的图:能够用两种颜色为所有顶点着色,使得任何一条边的两个顶点颜色不同。

明白了二分图是什么,能解决什么实际问题呢?算法方面,常见的操作是如何判定一幅图是不是二分图。比如说下面这道 LeetCode 题目:

你想想,如果我们把每个人视为一个顶点,边代表讨厌;相互讨厌的两个人之间连接一条边,就可以形成一幅图。那么根据刚才二分图的定义,如果这幅图是一幅二分图,就说明这些人可以被分为两组,否则的话就不行。

这是判定二分图算法的一个应用,其实二分图在数据结构方面也有一些不错的特性

比如说我们需要一种数据结构来储存电影和演员之间的关系:某一部电影肯定是由多位演员出演的,且某一位演员可能会出演多部电影。你使用什么数据结构来存储这种关系呢?

既然是存储映射关系,最简单的不就是使用哈希表嘛,我们可以使用一个 HashMap<String, List<String>> 来存储电影到演员列表的映射,如果给一部电影的名字,就能快速得到出演该电影的演员。

但是如果给出一个演员的名字,我们想快速得到该演员演出的所有电影,怎么办呢?这就需要「反向索引」,对之前的哈希表进行一些操作,新建另一个哈希表,把演员作为键,把电影列表作为值。

对于上面这个例子,可以使用二分图来取代哈希表。电影和演员是具有二分图性质的:如果把电影和演员视为图中的顶点,出演关系作为边,那么与电影顶点相连的一定是演员,与演员相邻的一定是电影,不存在演员和演员相连,电影和电影相连的情况。

回顾二分图的定义,如果对演员和电影顶点着色,肯定就是一幅二分图:

如果这幅图构建完成,就不需要反向索引,对于演员顶点,其直接连接的顶点就是他出演的电影,对于电影顶点,其直接连接的顶点就是出演演员。

当然,对于这个问题,书中还提到了一些其他有趣的玩法,比如说社交网络中「间隔度数」的计算(六度空间理论应该听说过)等等,其实就是一个 BFS 广度优先搜索寻找最短路径的问题,具体代码实现这里就不展开了。

二、套汇的算法

如果我们说货币 A 到货币 B 的汇率是 10,意思就是 1 单位的货币 A 可以换 10 单位货币 B。如果我们把每种货币视为一幅图的顶点,货币之间的汇率视为加权有向边,那么整个汇率市场就是一幅「完全加权有向图」。

一旦把现实生活中的情景抽象成图,就有可能运用算法解决一些问题。比如说图中可能存在下面的情况:

图中的加权有向边代表汇率,我们可以发现如果把 100 单位的货币 A 换成 B,再换成 C,最后换回 A,就可以得到 100×0.9×0.8×1.4 = 100.8 单位的 A!如果交易的金额大一些的话,赚的钱是很可观的,这种空手套白狼的操作就是套汇。

现实中交易会有种种限制,而且市场瞬息万变,但是套汇的利润还是很高的,关键就在于如何快速找到这种套汇机会呢?

借助图的抽象,我们发现套汇机会其实就是一个环,且这个环上的权重之积大于 1,只要在顺着这个环交易一圈就能空手套白狼。

图论中有一个经典算法叫做 Bellman-Ford 算法,可以用于寻找负权重环。对于我们说的套汇问题,可以先把所有边的权重 w 替换成 -ln(w),这样「寻找权重乘积大于 1 的环」就转化成了「寻找权重和小于 0 的环」,就可以使用 Bellman-Ford 算法在 O(EV) 的时间内寻找负权重环,也就是寻找套汇机会。

《算法4》就介绍到这里,关于上面两个例子的具体内容,可以自己去看书,公众号后台回复关键词「算法4」就有 PDF

三、最后说几句

首先,前文说对于数学证明、章后习题可以忽略,可能有人要抬杠了:难道习题和数学证明不重要吗?

那我想说,就是不重要,起码对大多数人来说不重要。我觉得吧,学习就要带着目的性去学,大部分人学算法不就是巩固计算机知识,对付面试题目吗?如果是这个目的,那就学些基本的数据结构和经典算法,明白它们的时间复杂度,然后去刷题就好了,何必和习题、证明过不去?

这也是我从来不推荐《算法导论》这本书的原因。如果有人给你推荐这本书,只可能有两个原因,要么他是真大佬,要么他在装大佬。《算法导论》中充斥大量数学证明,而且很多数据结构是很少用到的,顶多当个字典用。你说你学了那些有啥用呢,饶过自己呗。

另外,读书在精不在多。你花时间《算法4》过个大半(最后小半部分有点困难),同时刷点题,看看咱们的公众号文章,算法这块真就够了,别对细节问题太较真。

查看原文

赞 0 收藏 0 评论 0

labuladong 发布了文章 · 2020-12-22

算法学习之路

-----------

之前发的那篇关于框架性思维的文章,我也发到了不少其他圈子,受到了大家的普遍好评,这一点我真的没想到,首先感谢大家的认可,我会更加努力,写出通俗易懂的算法文章。

有很多朋友问我数据结构和算法到底该怎么学,尤其是很多朋友说自己是「小白」,感觉这些东西好难啊,就算看了之前的「框架思维」,也感觉自己刷题乏力,希望我能聊聊我从一个非科班小白一路是怎么学过来的。

首先要给怀有这样疑问的朋友鼓掌,因为你现在已经「知道自己不知道」,而且开始尝试学习、刷题、寻求帮助,能做到这一点本身就是及其困难的。

关于「框架性思维」,对于一个小白来说,可能暂时无法完全理解(如果你能理解,说明你水平已经不错啦,不是小白啦)。就像软件工程,对于我这种没带过项目的人来说,感觉其内容枯燥乏味,全是废话,但是对于一个带过团队的人,他就会觉得软件工程里的每一句话都是精华。暂时不太理解没关系,留个印象,功夫到了很快就明白了。

下面写一写我一路过来的一些经验。如果你已经看过很多「如何高效刷题」「如何学习算法」的文章,却还是没有开始行动并坚持下去,本文的第五点就是写给你的。

我觉得之所以有时候认为自己是「小白」,是由于知识某些方面的空白造成的。具体到数据结构的学习,无非就是两个问题搞得不太清楚:这是啥?有啥用?

举个例子,比如说你看到了「栈」这个名词,老师可能会讲这些关键词:先进后出、函数堆栈等等。但是,对于初学者,这些描述属于文学词汇,没有实际价值,没有解决最基本的两个问题。如何回答这两个基本问题呢?回答「这是啥」需要看教科书,回答「有啥用」需要刷算法题。

一、这是啥?

这个问题最容易解决,就像一层窗户纸,你只要随便找本书看两天,自己动手实现一个「队列」「栈」之类的数据结构,就能捅破这层窗户纸。

这时候你就能理解「框架思维」文章中的前半部分了:数据结构无非就是数组、链表为骨架的一些特定操作而已;每个数据结构实现的功能无非增删查改罢了。

比如说「列队」这个数据结构,无非就是基于数组或者链表,实现 enqueue 和 dequeue 两个方法。这两个方法就是增和删呀,连查和改的方法都不需要。

二、有啥用?

解决这个问题,就涉及算法的设计了,是个持久战,需要经常进行抽象思考,刷算法题,培养「计算机思维」。

之前的文章讲了,算法就是对数据结构准确而巧妙的运用。常用算法问题也就那几大类,算法题无非就是不断变换场景,给那几个算法框架套上不同的皮。刷题,就是在锻炼你的眼力,看你能不能看穿问题表象揪出相应的解法框架。

比如说,让你求解一个迷宫,你要把这个问题层层抽象:迷宫 -> 图的遍历 -> N 叉树的遍历 -> 二叉树的遍历。然后让框架指导你写具体的解法。

抽象问题,直击本质,是刷题中你需要刻意培养的能力。

三、如何看书

直接推荐一本公认的好书,《算法第 4 版》,我一般简写成《算法4》。不要蜻蜓点水,这本书你能选择性的看上 50%,基本上就达到平均水平了。别怕这本书厚,因为起码有三分之一不用看,下面讲讲怎么看这本书。

看书仍然遵循递归的思想:自顶向下,逐步求精。

这本书知识结构合理,讲解也清楚,所以可以按顺序学习。书中正文的算法代码一定要亲自敲一遍,因为这些真的是扎实的基础,要认真理解。不要以为自己看一遍就看懂了,不动手的话理解不了的。但是,开头部分的基础可以酌情跳过;书中的数学证明,如不影响对算法本身的理解,完全可以跳过;章节最后的练习题,也可以全部跳过。这样一来,这本书就薄了很多。

相信读者现在已经认可了「框架性思维」的重要性,这种看书方式也是一种框架性策略,抓大放小,着重理解整体的知识架构,而忽略证明、练习题这种细节问题,即保持自己对新知识的好奇心,避免陷入无限的细节被劝退。

当然,《算法4》到后面的内容也比较难了,比如那几个著名的串算法,以及正则表达式算法。这些属于「经典算法」,看个人接受能力吧,单说刷 LeetCode 的话,基本用不上,量力而行即可。

四、如何刷题

首先声明一下,算法和数学水平没关系,和编程语言也没关系,你爱用什么语言用什么。算法,主要是培养一种新的思维方式。所谓「计算机思维」,就跟你考驾照一样,你以前骑自行车,有一套自行车的规则和技巧,现在你开汽车,就需要适应并练习开汽车的规则和技巧。

LeetCode 上的算法题和前面说的「经典算法」不一样,我们权且称为「解闷算法」吧,因为很多题目都比较有趣,有种在做奥数题或者脑筋急转弯的感觉。比如说,让你用队列实现一个栈,或者用栈实现一个队列,以及不用加号做加法,开脑洞吧?

当然,这些问题虽然看起来无厘头,实际生活中也用不到,但是想解决这些问题依然要靠数据结构以及对基础知识的理解,也许这就是很多公司面试都喜欢出这种「智力题」的原因。下面说几点技巧吧。

尽量刷英文版的 LeetCode,中文版的“力扣”是阉割版,不仅很多题目没有答案,而且连个讨论区都没有。英文版的是真的很良心了,很多问题都有官方解答,详细易懂。而且讨论区(Discuss)也沉淀了大量优质内容,甚至好过官方解答。真正能打开你思路的,很可能是讨论区各路大神的思路荟萃。

PS:如果有的英文题目实在看不懂,有个小技巧,你在题目页面的 url 里加一个 -cn,即 https://leetcode.com/xxx 改成 https://leetcode-cn.com/xxx,这样就能切换到相应的中文版页面查看。

对于初学者,强烈建议从 Explore 菜单里最下面的 Learn 开始刷,这个专题就是专门教你学习数据结构和基本算法的,教学篇和相应的练习题结合,不要太良心。

最近 Learn 专题里新增了一些内容,我们挑数据结构相关的内容刷就行了,像 Ruby,Machine Learning 就没必要刷了。刷完 Learn 专题的基础内容,基本就有能力去 Explore 菜单的 Interview 专题刷面试题,或者去 Problem 菜单,在真正的题海里遨游了。

无论刷 Explore 还是 Problems 菜单,最好一个分类一个分类的刷,不要蜻蜓点水。比如说这几天就刷链表,刷完链表再去连刷几天二叉树。这样做是为了帮助你提取「框架」。一旦总结出针对一类问题的框架,解决同类问题可谓是手到擒来。

五、道理我都懂,还是不能坚持下去

这其实无关算法了,还是老生常谈的执行力的问题。不说什么破鸡汤了,我觉得解决办法就是「激起欲望」,注意我说的是欲望,而不是常说的兴趣,拿我自己说说吧。

半年前我开始刷题,目的和大部分人都一样的,就是为毕业找工作做准备。只不过,大部分人是等到临近毕业了才开始刷,而我离毕业还有一阵子。这不是炫耀我多有觉悟,而是我承认自己的极度平凡。

首先,我真的想找到一份不错的工作(谁都想吧?),我想要高薪呀!否则我在朋友面前,女神面前放下的骚话,最终都会反过来啪啪地打我的脸。我也是要恰饭,要面子,要虚荣心的嘛。赚钱,虚荣心,足以激起我的欲望了。

但是,我不擅长 deadline 突击,我理解东西真的慢,所以干脆笨鸟先飞了。智商不够,拿时间来补,我没能力两个月突击,干脆拉长战线,打他个两年游击战,我还不信耗不死算法这个强敌。事实证明,你如果认真学习一个月,就能够取得肉眼可见的进步了。

现在,我依然在坚持刷题,而且为了另外一个原因,这个公众号。我没想到自己的文字竟然能够帮助到他人,甚至能得到认可。这也是虚荣心啊,我不能让读者失望啊,我想让更多的人认可(夸)我呀!

以上,不光是坚持刷算法题吧,很多场景都适用。执行力是要靠「欲望」支撑的,我也是一凡人,只有那些看得见摸得着的东西才能使我快乐呀。读者不妨也尝试把刷题学习和自己的切身利益联系起来,这恐怕是坚持下去最简单直白的理由了。

查看原文

赞 0 收藏 0 评论 0

labuladong 发布了文章 · 2020-12-22

双指针技巧

读完本文,你可以去力扣拿下如下题目:

141.环形链表

141.环形链表II

167.两数之和 II - 输入有序数组

-----------

我把双指针技巧再分为两类,一类是「快慢指针」,一类是「左右指针」。前者解决主要解决链表中的问题,比如典型的判定链表中是否包含环;后者主要解决数组(或者字符串)中的问题,比如二分查找。

一、快慢指针的常见算法

快慢指针一般都初始化指向链表的头结点 head,前进时快指针 fast 在前,慢指针 slow 在后,巧妙解决一些链表中的问题。

1、判定链表中是否含有环

这应该属于链表最基本的操作了,如果读者已经知道这个技巧,可以跳过。

单链表的特点是每个节点只知道下一个节点,所以一个指针的话无法判断链表中是否含有环的。

如果链表中不含环,那么这个指针最终会遇到空指针 null 表示链表到头了,这还好说,可以判断该链表不含环。


boolean hasCycle(ListNode head) {
    while (head != null)
        head = head.next;
    return false;
}

但是如果链表中含有环,那么这个指针就会陷入死循环,因为环形数组中没有 null 指针作为尾部节点。

经典解法就是用两个指针,一个跑得快,一个跑得慢。如果不含有环,跑得快的那个指针最终会遇到 null,说明链表不含环;如果含有环,快指针最终会超慢指针一圈,和慢指针相遇,说明链表含有环。

boolean hasCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        
        if (fast == slow) return true;
    }
    return false;
}

2、已知链表中含有环,返回这个环的起始位置

1

这个问题一点都不困难,有点类似脑筋急转弯,先直接看代码:

ListNode detectCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;
    }
    // 上面的代码类似 hasCycle 函数
    slow = head;
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

可以看到,当快慢指针相遇时,让其中任一个指针指向头节点,然后让它俩以相同速度前进,再次相遇时所在的节点位置就是环开始的位置。这是为什么呢?

第一次相遇时,假设慢指针 slow 走了 k 步,那么快指针 fast 一定走了 2k 步,也就是说比 slow 多走了 k 步(也就是环的长度)。

2

设相遇点距环的起点的距离为 m,那么环的起点距头结点 head 的距离为 k - m,也就是说如果从 head 前进 k - m 步就能到达环起点。

巧的是,如果从相遇点继续前进 k - m 步,也恰好到达环起点。

3

所以,只要我们把快慢指针中的任一个重新指向 head,然后两个指针同速前进,k - m 步后就会相遇,相遇之处就是环的起点了。

3、寻找链表的中点

类似上面的思路,我们还可以让快指针一次前进两步,慢指针一次前进一步,当快指针到达链表尽头时,慢指针就处于链表的中间位置。

while (fast != null && fast.next != null) {
    fast = fast.next.next;
    slow = slow.next;
}
// slow 就在中间位置
return slow;

当链表的长度是奇数时,slow 恰巧停在中点位置;如果长度是偶数,slow 最终的位置是中间偏右:

center

寻找链表中点的一个重要作用是对链表进行归并排序。

回想数组的归并排序:求中点索引递归地把数组二分,最后合并两个有序数组。对于链表,合并两个有序链表是很简单的,难点就在于二分。

但是现在你学会了找到链表的中点,就能实现链表的二分了。关于归并排序的具体内容本文就不具体展开了。

4、寻找链表的倒数第 k 个元素

我们的思路还是使用快慢指针,让快指针先走 k 步,然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时,慢指针所在的位置就是倒数第 k 个链表节点(为了简化,假设 k 不会超过链表长度):

ListNode slow, fast;
slow = fast = head;
while (k-- > 0) 
    fast = fast.next;

while (fast != null) {
    slow = slow.next;
    fast = fast.next;
}
return slow;

二、左右指针的常用算法

左右指针在数组中实际是指两个索引值,一般初始化为 left = 0, right = nums.length - 1 。

1、二分查找

前文「二分查找」有详细讲解,这里只写最简单的二分算法,旨在突出它的双指针特性:

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1;
    while(left <= right) {
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; 
        else if (nums[mid] > target)
            right = mid - 1;
    }
    return -1;
}

2、两数之和

直接看一道 LeetCode 题目吧:

title

只要数组有序,就应该想到双指针技巧。这道题的解法有点类似二分查找,通过调节 left 和 right 可以调整 sum 的大小:

int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            // 题目要求的索引是从 1 开始的
            return new int[]{left + 1, right + 1};
        } else if (sum < target) {
            left++; // 让 sum 大一点
        } else if (sum > target) {
            right--; // 让 sum 小一点
        }
    }
    return new int[]{-1, -1};
}

3、反转数组

void reverse(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        // swap(nums[left], nums[right])
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++; right--;
    }
}

4、滑动窗口算法

这也许是双指针技巧的最高境界了,如果掌握了此算法,可以解决一大类子字符串匹配的问题,不过「滑动窗口」稍微比上述的这些算法复杂些。

幸运的是,这类算法是有框架模板的,而且这篇文章就讲解了「滑动窗口」算法模板,帮大家秒杀几道 LeetCode 子串匹配的问题。

查看原文

赞 0 收藏 0 评论 0

认证与成就

  • 获得 5 次点赞
  • 获得 1 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 1 枚铜徽章

擅长技能
编辑

开源项目 & 著作
编辑

注册于 2020-11-03
个人主页被 1.6k 人浏览