阅读整理曾经做过的leetcode

前言

原先做了不少中等难度和简单难度的leetcode题目，都上传到了github上。但是没有总结，现在面试需要的时候就发现很多都想不起来了。所以今天写一个整理总结的类型。

常见数据结构和基本算法（摘抄自halfrost)

数据结构见下，

常见的算法

针对每一种算法的具体实现

针对具体类型的题目做的分类

Array

0001 Two Sum

对常见数据结构的应用

指针的引用

盛最多水的容器 leetcode第11题

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水

三数之和 leetcode第15题

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

四数之和 leetcode第18题

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

树的应用

括号生成。 leetcode第22题

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

450. 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

hash表的应用

两数之和 leetcode第1题

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

无重复字符的最长子串 leetcode第3题

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

缺失的第一个正数 leetcode第41题

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

非常典型的原地hash

数组中重复的数据 leetcode第442题

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

字母异位词分组。 leetcode第49题

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

423. 从英文中重建数字

给定一个非空字符串，其中包含字母顺序打乱的英文单词表示的数字0-9。按升序输出原始的数字。

448. 找到所有数组中消失的数字

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

525. 连续数组

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。

栈的使用

有效的括号 leetcode第20题

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

链表的操作

两数之和 leetcode第2题

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储一位数字。

445. 两数相加 II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

非常常见的栈的题目

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

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

两两交换链表中的节点 leetcode第24题

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

旋转链表 leetcode第61题

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

删除排序链表中的重复元素 II leetcode第82题

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

分隔链表 leetcode第86题

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

206. 反转链表

反转一个单链表。

反转链表 II leetcode92题

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

和下面两个题目一样都是双指针

141. 环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

328. 奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

常见算法的应用

动态规划

最长回文子串。 leetcode第5题

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 实际上本质上就是减少检查的次数，利用原先推到过的结果。

最大子序和。 leetcode第53题

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

简单难度，你竟然没想到。。。。失败啊。

不同路径。 leetcode第62题

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

实际上是个组合数学问题

不同路径2。 leetcode第63题

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

滚动数组问题需要学习

最小路径和。 leetcode第64题

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或者向右移动一步。

解码方法。 leetcode第91题

给定一个只包含数字的非空字符串，请计算解码方法的总数。题目数据保证答案肯定是一个 32 位的整数。

1277. 统计全为 1 的正方形子矩阵

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

最大正方形 leetcode221题

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积

打家劫舍 leetcode198题

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

打家劫舍 II leetcode213

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。

279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

背包问题还要再研究一下

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

第二种方法很有趣，值得再次阅读

322. 零钱兑换

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

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

338. 比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

由此可见，正整数 y 是 2的整数次幂，当且仅当y&(y−1)=0。这个规律很有趣。而且有一个关于1的数目很有趣的特点：

bits[x]=bits[x&(x−1)]+1

375. 猜数字大小 II

我们正在玩一个猜数游戏，游戏规则如下：

我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。

每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。

然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。

396. 旋转函数

给定一个长度为 n 的整数数组 A 。

假设 Bk 是数组 A 顺时针旋转 k 个位置后的数组，我们定义 A 的“旋转函数” F 为：

F(k) = 0 * Bk[0] + 1 * Bk[1] + … + (n-1) * Bk[n-1]。

计算F(0), F(1), …, F(n-1)中的最大值。

这个应该说规律非常明显，难度只有简单才合适

397. 整数替换

给定一个正整数 n ，你可以做如下操作：

如果 n 是偶数，则用 n / 2替换 n 。 如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。 n 变为 1 所需的最小替换次数是多少？

实际上也是很基本的对数字的考察

413. 等差数列划分

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

如果满足以下条件，则称子数组(P, Q)为等差数组：

元素 A[P], A[p + 1], …, A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。

函数要返回数组 A 中所有为等差数组的子数组个数。

486. 预测赢家

给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数，随后玩家 2 继续从剩余数组任意一端拿取分数，然后玩家 1 拿，…… 。每次一个玩家只能拿取一个分数，分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。

给定一个表示分数的数组，预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

背包问题

虽然背包问题一般要么搜索，要么动规，但是出于检索目的单独把背包问题拆出来了。

416. 分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

光看题目非常居有迷惑性，但是想明白两个子集的元素和相等就明白这个实际上是个背包问题了。很有趣也很值得关注的一道题，务必搜索“背包九讲”

474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

494. 目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

322. 零钱兑换

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

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

518. 零钱兑换 II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

递归

从前序与中序遍历序列构造二叉树 leetcode第105题

根据一棵树的前序遍历与中序遍历构造二叉树。

从中序与后序遍历序列构造二叉树 leetcode第106题

根据一棵树的中序遍历与后序遍历构造二叉树。

有序链表转换二叉搜索树 leetcode第109题

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

264. 丑数 II

编写一个程序，找出第 n 个丑数。

丑数就是质因数只包含 2, 3, 5 的正整数。

三指针法的想法得明白咋回事

390. 消除游戏

给定一个从1 到 n 排序的整数列表。 首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。 第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。 我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。 返回长度为 n 的列表中，最后剩下的数字。

剑指 Offer 62. 圆圈中最后剩下的数字

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

上面两个题目本质是约瑟夫环，得学习下

深度搜索(或者说回溯)

这里把深度搜索的算法写下来，方便以后回想

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

括号生成。 leetcode第22题

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

关于这种生成字符串种类的题目通通可以这样子计算，找到了生成的字符串的限制规律，然后让计算机去搜索在规律限制之下能够生成的子串的集合，这东西就是深搜。

组合总和。 leetcode第39题

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。

这种问题实际上就是搜索。

组合总和2。 leetcode第40题

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

电话号码的字母组合。 leetcode第17题

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

全排列。 leetcode第46题

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

回溯实际上就是个不断撞南墙回来的过程，此外这题目的解答里面，有个哥们给了给非常详尽的回溯搜索的见解和相关题目，建议阅读

全排列2。 leetcode第47题

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

排列序列。 leetcode第60题

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况。给定 n 和 k，返回第 k 个排列。

组合。 leetcode第77题

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

子集。 leetcode第78题

给你一个整数数组 nums ，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。

这题有个“DFS 和回溯算法区别”写的挺不错，建议看看，当然，这里需要。

子集2。 leetcode第90题

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

单词搜索。 leetcode第79题

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

复原IP地址。 leetcode第93题

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

二叉树的中序遍历。 leetcode第94题

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

不同的二叉搜索树 II。 leetcode第95题

给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。

路径总和 II。 leetcode第113题

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

二叉树展开为链表。 leetcode第114题

给你二叉树的根结点 root ，请你将它展开为一个单链表： 展开后的单链表应该和先序遍历一致

组合总和 III leetcode216题

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。 解集不能包含重复的组合

完全二叉树的节点个数 leetcode222

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

利用完全二叉树的结构和递归的想法

二叉搜索树中第K小的元素 leetcode 230

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

二叉树的最近公共祖先 leetcode236

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

331. 验证二叉树的前序序列化

存疑

357. 计算各个位数不同的数字个数

给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。(就是组合数学)

377. 组合总和 Ⅳ

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

实际是背包问题，看这个https://leetcode-cn.com/problems/combination-sum-iv/solution/xi-wang-yong-yi-chong-gui-lu-gao-ding-bei-bao-wen-/

386. 字典序排数

给定一个整数 n, 返回从 1 到 n 的字典顺序。

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

可以说是栈，也可以说是深搜。

491. 递增子序列

给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

508. 出现次数最多的子树元素和

给你一个二叉树的根结点，请你找出现次数最多的子树元素和。一个结点的「子树元素和」定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

你需要返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

513. 找树左下角的值

给定一个二叉树，在树的最后一行找到最左边的值

广度搜索

void bfs(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root);
    while (!nodeQueue.empty()) {
        TreeNode* node = nodeQueue.front();
        nodeQueue.pop();
        cout << node->val << " ";

        if (node->left != nullptr) {
            nodeQueue.push(node->left);
        }
        if (node->right != nullptr) {
            nodeQueue.push(node->right);
        }
    }
}

二叉树的层序遍历 leetcode第102题

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

典型的广度搜索

二叉树的锯齿形层序遍历 leetcode第103题

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

二叉树的右视图 leetcode199题

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

419. 甲板上的战舰

给定一个二维的甲板， 请计算其中有多少艘战舰。 战舰用 ‘X’表示，空位用 ‘.’表示。 你需要遵守以下规则：

给你一个有效的甲板，仅由战舰或者空位组成。 战舰只能水平或者垂直放置。换句话说,战舰只能由 1xN (1 行, N 列)组成，或者 Nx1 (N 行, 1 列)组成，其中N可以是任意大小。 两艘战舰之间至少有一个水平或垂直的空位分隔 - 即没有相邻的战舰。

515. 在每个树行中找最大值

您需要在二叉树的每一行中找到最大的值。

542. 01 矩阵

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

贪心算法

跳跃游戏。 leetcode第55题

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

跳跃游戏 II。 leetcode第45题

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

贪心或者动规？

402. 移掉K位数字

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:

num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。

非常简单的贪心，使用单调栈的想法很有趣。

473. 火柴拼正方形

435. 无重叠区间

图算法

课程表 leetcode207

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false

其他

下一个排列。 leetcode第31题

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

排序问题的非常正常的解法，实际上就是个所谓的升序找最小。降低的顺序变为升顺序。

旋转图像。 leetcode第48题

给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。

螺旋矩阵。 leetcode第54题

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

螺旋矩阵2。 leetcode第59题

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

多数元素。 leetcode第169题

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

[颠倒二进制位]。 leetcode第190题

颠倒给定的 32 位无符号整数的二进制位。

本质就是诸位颠倒

位1的个数。 leetcode第191题

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）

[LRU 缓存机制]。 leetcode第146题

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。

从本质来说是hash表和双向链表，因为这个题目很有趣，所以给出代码实现。

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

    int get(int key) {
        if (map.find(key) == map.end()) return -1;
        auto key_value = *map[key];
        cache.erase(map[key]);
        cache.push_front(key_value);
        map[key] = cache.begin();
        return key_value.second;
    }

    void put(int key, int value) {
        if (map.find(key) == map.end()) {
            if (cache.size() == cap) {
                map.erase(cache.back().first);
                cache.pop_back();
            }
        }
        else {
            cache.erase(map[key]);
        }
        cache.push_front({key, value});
        map[key] = cache.begin();
    }
private:
    int cap;
    list<pair<int, int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> map;
};

下面还需要把linux的lru+last chance实现出来。

315. 计算右侧小于当前元素的个数

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

逆序数

矩形面积 leetcode223

在二维平面上计算出两个由直线构成的矩形重叠后形成的总面积。

260. 只出现一次的数字 III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

数学的思想，异或

268. 丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

289. 生命游戏

根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡； 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活； 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡； 如果死细胞周围正好有三个活细胞，则该位置死细胞复活； 下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

319. 灯泡开关

初始时有 n 个灯泡关闭。

第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。

第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。

找出 n 轮后有多少个亮着的灯泡。

334. 递增的三元子序列

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

双指针法

343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

372. 超级次方

你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

382. 链表随机节点

给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

一个随机的想法，值得一看。

389. 找不同

给定两个字符串 s 和 t，它们只包含小写字母。

字符串 t*** 由字符串 **s* 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

421. 数组中两个数的最大异或值

本质还是数学

451. 根据字符出现频率排序

本质还是数学

461. 汉明距离

二进制，数学

476. 数字的补数

二进制，数学

477. 汉明距离总和

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。

计算一个数组中，任意两个数之间汉明距离的总和。

498. 对角线遍历

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

二分

搜索旋转排序数组。 leetcode第33题

升序排列的整数数组 nums 在预先未知的某个点上进行了旋转（例如， [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] ）。请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

在排序数组中查找元素的第一个和最后一个位置。 leetcode第34题

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

搜索二维矩阵。 leetcode第74题

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： 每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。

[ 寻找旋转排序数组中的最小值 leetcode第153题

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。

请找出其中最小的元素。

寻找峰值。 leetcode第162题

峰值元素是指其值大于左右相邻值的元素。

给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞ 。

数组中的第K个最大元素 leetcode215题

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

2的幂 leetcode231

给定一个整数，编写一个函数来判断它是否是 2 的幂次方

搜索二维矩阵 II leetcode240

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。 每列的元素从上到下升序排列。

241. 为运算表达式设计优先级

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

378. 有序矩阵中第 K 小的元素

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

排序

合并区间。 leetcode第56题

给出一个区间的集合，请合并所有重叠的区间。

颜色分类。 leetcode第75题

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

274. H 指数

给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 N - h 篇论文每篇被引用次数 不超过 h 次。

324. 摆动排序 II

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。

你可以假设所有输入数组都可以得到满足题目要求的结果。

347. 前 K 个高频元素

给定一个非空的整数数组，返回其中出现频率前 *k* 高的元素。

373. 查找和最小的K对数字

给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。

找到和最小的 k 对数字 (u1,v1), (u2,v2) … (uk,vk)。

看这个网址https://blog.csdn.net/u013317445/article/details/89680330或者用双指针来做

462. 最少移动次数使数组元素相等 II

给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。

致谢

感谢halfrost同学，

参考资料

https://books.halfrost.com/leetcode/ChapterOne/

结尾

• Previous
  异步程序编写时候的一些小教训
• Next
  从锁和RTE ring与KFIFO说起