Codetop题库

算法题

1 数组中的第K个最大元素 给你数组nums和整数k，请返回数组中第k个最大的元素。

方法一，用快速选择算法。步骤，先选择一个枢轴，从数组中选择一个元素作为枢轴。将数组分成两个部分，一部分是比枢轴大的元素，另一部分是比枢轴小的元素。根据k的值和枢轴的位置决定下一步在哪部分递归搜索。

方法二，最小堆。用容量为k的最小堆，依次遍历数组，将元素入堆。当堆大小超过k时，弹出堆顶，这样堆始终保留最大的k个元素。遍历结束后，堆顶就是第k大元素。

2 无重复字符的最长子串 给你一个字符串s，请找出其中不含有重复字符的最长子串的长度。子串是连续的。

思路，用滑动窗口。用set记录当前窗口中的字符，用left和right维护窗口，当right指向的是重复字符时，删除left对应元素，并移动left指针缩小窗口，直到没有重复字符。while的条件是right小于字符串长度，遍历每个可能的right。

4 lru缓存 请你实现lru cache类，以正整数capacity初始化lru缓存，get方法，如果关键字key存在于缓存中，则返回关键字值，否则返回-1。put方法如果key已经存在则覆盖值value。如果不存在，则向缓存中插入key value。如果缓存已满，则应 逐出 最久未使用的关键字。get和put必须以O 1 时间运行。

思路，用哈希表和双向链表实现。哈希表用于快速查找，双向链表用于维护元素使用顺序。双向链表有辅助方法，addToHead将节点添加到链表头部，removeNode从链表移除节点，moveToHead将节点移动到链表头部，popTail移除并返回链表尾部节点。

get方法查找键值，如果存在则移动节点到链表头部moveToHead并返回值，否则返回-1。put方法如果健存在则更新值并移动到链表头部moveToHead，如果键不存在则插入新节点addToHead，并在超过容量时，删除尾部节点popTail。

import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    public void put(int key, int value) {
        super.put(key, value);
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 当缓存元素个数超过容量时，移除最⽼的元素
        return size() > capacity;
    }
    public static void main(String[] args) {
        // 创建⼀个容量为3的LRU缓存
        LRUCache<Integer, String> lruCache = new LRUCache<>(3);
        // 添加数据
        lruCache.put(1, "One");
        lruCache.put(2, "Two");
        lruCache.put(3, "Three");
        // 此时缓存为：{1=One, 2=Two, 3=Three}
        // 访问某个元素，使其成为最近访问的元素
        String value = lruCache.get(2);
        // 此时缓存为：{1=One, 3=Three, 2=Two}
        // 添加新的数据，触发淘汰
        lruCache.put(4, "Four");
        // 此时缓存为：{3=Three, 2=Two, 4=Four}
        // 元素1被淘汰，因为它是最近最少访问的元素
    }
}

LRU缓存+过期时间（字节）

5 K个一组翻转链表 困难题 给你链表头结点head，每k个节点一组进行翻转，请你返回修改后链表。如果节点总数不是k的整数倍，那么将最后剩余节点保持原有顺序。

思路，计算链表长度，反转每k个节点的子链表，连接反转后的子链表。创建一个虚拟头结点dummy。在翻转子链表时，有groupHead，groupTail，nextGroup，preGroupTail四个重要变量，记录子链表头，子链表尾，下一组子链表头，上一组子链表尾。在翻转子链表时，要断开当前组，将groupTail的next指针设为null。

某区间内两个一组反转链表（小红书）

先找到区间起点left的前驱prev，计算区间长度len，即right减去left加1，实际要翻转的组数为len除以2，依次对这几组节点进行两两翻转。翻转后，prev前进两步到翻转后的这一对的尾部，curr指向下次翻转的首节点。

6 三数之和 给你一个整数数组nums，判断是否存在 nums i nums j nums k满足i j k互不相同且相加为0.返回所有三元组。

思路，先对数组进行排序，遍历数组，固定一个数，然后用双指针寻找其他两个数，利用两个指针分别从当前固定位置的右边开始向中间移动。固定一个数时，要跳过重复的数字以避免重复三元组，方法是当前数字等于前一个数字则跳过。找到和为0的数组时，也要跳过重复数字，只要left右边和right左边的数字等于left，right，那么不停移动left，right。

有序数组找三数之和，使得a+b=c（腾讯音乐）

双指针法，枚举所有的c，在左侧子数组0到k减1中用左右指针i、j做两数之和，时间复杂度O n的平方。

7 最大子数组和 给你一个整数数组nums，找出一个具有最大和的连续子数组，返回最大和。 注意和第81题最长连续子序列区分。

思路，动态规划，dp i等于dp i减去1加nums i和nums i的最大值。可以优化，只用两个变量，currNum和maxSum，分别是以前位置i结尾的最大子数组和，以及截止当前位置的全局最大子数组和。

9 合并两个有序链表 将两个升序链表list1和list2合并为一个新的 升序 链表并返回。

思路，双指针法。创建一个current指针指向list1和list2中较小的节点，然后遍历两个链表，用while循环比较两个链表当前值， 将较小的节点接到current的next，并移动指针 。然后将不为null的链表连接到current的next上。

10 两数之和 给你一个整数数组nums和一个整数目标值target，请在该数组中找到 和为目标值的那两个整数 ，并返回他们的数组下标。你可以假设只有一个答案，并且不能两次用相同元素。

思路。用哈希表实现。这道题要返回的是下标，因此不能排序，如果返回的是这两个整数，那么就先排序再用滑动窗口，和第6题三数之和很像。步骤，创建一个哈希表，存储数组中每个整数和索引的映射。遍历数组，对于每个元素num，计算target减去num，如果这个值在哈希表中存在，并且不等于当前索引i，那么直接返回这两个索引。

11 最长回文子串 给你一个字符串s，找到s中最长的回文子串。

思路，用中心拓展法，从每个字符i以及两个字符i和i加一开始拓展。步骤，遍历字符，通过expand方法拓展，比较奇数和偶数长度的回文，expand方法while条件是left和right的字符相等，然后不停向左向右拓展，返回right减去left减去1，减一是因为这时候两个指针已经出界了。用lenth计算start时是i减去len减去1除以2，而end是i加上len除以2。

12 二叉树层序遍历 给你二叉树根节点root，返回其节点值的 层序遍历 ，每一层放到一个List里面。

思路，方法一，用两个队列实现，创建两个队列currentLevel和nextLevel。while条件是currentLevel队列不为空，从current队列移除一个节点，加入level List里面，然后将当前节点左右子节点加入nextLevel队列里。当currentLevel为空时，把level List添加到result列表里，并新建level List，同时把currentLevel置为nextLevel，把nextLevel置为新的队列。

方法二，dfs，先序遍历时传入当前深度depth，每到新高度就在res加一个空列表，然后将当前节点值放进去。

13 搜索旋转排序数组 整数数组nums按升序排列，数组中值互不相同，nums在某个下标k上进行了旋转，如 0 1 2 3 4 5 6 7在下标3处旋转后变为4 5 6 7 0 1 2。给你旋转后数组nums和整数target，如果target存在，则返回它的下标。 时间要求O log n。

思路，用修改后的二分查找。步骤，如果mid的元素等于target直接返回，检查中间元素是否大于 或等于 左端元素，如果大于则左边有序，如果目标在左边，即left小于 或等于 target，target小于mid，则转到该半边搜索，否则转到另一半。对于右边也是这样。注意的点是，所有判断大于小于要带上等号。

14 岛屿数量 给你一个由字符1和0组成的二维网格，请你计算网格中岛屿数量。

思路，用dfs。步骤，对网格每个单元格进行遍历，当遇到一个1的单元格时，增加岛屿计数count，并通过dfs访问相邻的单元格。在dfs中，先判断当前单元格是否有效索引，并判断当前网格是否为1，然后递归检查当前单元格上下左右的网格。

15 有效的括号 给你一个只包括小括号中括号大括号的字符串s，判断字符串是否有效，返回true或false。

思路，用栈。步骤，遍历字符串每个字符，如果是左括号，推入栈中。如果是右括号，检查栈是否为空，为空则无效返回false。如果栈不为空，则弹出栈顶元素，判断栈顶元素是否和当前右括号匹配，如果不匹配返回false。遍历完所有字符后，检查栈是否为空，为空则有效true，不为空则返回false。

17 买卖股票的最佳时机 给你一个数组prices，你只能选择 某一天 买入股票，并在 未来一个不同的日子卖出股票 ，给出你能获得的最大利润。

思路，初始化两个变量min price和max profit，遍历价格数组，更新min price为当前价格和之前的min price较小值。计算如果当前卖出的利润price i减去min price，更新max profit。

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

思路，用递归。递归参数，root，p，q。如果当前节点为null或者等于其中一个节点则返回当前节点。递归在左右子树中查找p和q。如果p和q分别位于当前节点的左右子树中，那么当前节点就是pq的最近公共祖先。如果p和q都位于左子树，那么返回 左子树的递归结果 。注意这里是左子树递归结果，不是左孩子。如果pq都位于右子树，那么返回右子树的递归结果。

19 合并两个有序数组 给你两个按 非递减顺序 排列的整数数组nums1和nums2，两个整数m n，代表两数组元素数目。请你合并nums2到nums1中，使合并后的数组同样按非递减排列。

思路，用从后往前的双指针实现时间复杂度 O m加n，空间O 1。初始化i j指向nums1和nums2最后一个元素。维护指针k指向nums1的真正末尾。比较nums1 i和nums2 j大小，如果nums1 i更大，将nums1 i放入nums1 k，i k递减，如果nums2 j更大就把他放入。如果nums2还有剩余元素，复制到nums1.

20 全排列 给你一个不含重复数字的数组nums，返回所有可能得全排列，你可以按任意顺序返回答案。

思路，用递归生成所有可能的全排列。index参数控制从哪个位置开始填数字。每次递归时，从index位置到末尾所有数字交换，然后递归调用，注意传入的参数是index加一，而不是i加一。一旦index等于数组长度，说明找到一种排列，把这时的nums填到result里。

21 二叉树的锯齿形层序遍历 给你二叉树根节点root，返回其节点值的锯齿形层序遍历。

思路，用两个队列层序遍历二叉树并用一个布尔型变量direction控制方向。和第2题层序遍历一样。用两个队列实现，创建两个队列currentLevel和nextLevel。while条件是currentLevel队列不为空，从current队列移除一个节点，加入level List里面，然后将当前节点左右子节点加入nextLevel队列里。当currentLevel为空时，把level List添加到result列表里，当direction为false的时候，把level list翻转一下再放到result里，并新建level List，同时把currentLevel置为nextLevel，把nextLevel置为新的队列。

22 反转链表II 给你单链表头指针head和两个整数left和right，请你翻转从位置left到right的链表节点，返回反转后的链表。

思路，注意要用虚拟头结点dummy。先找到反转起点，遍历链表找到第left个节点前一个节点preLeft，并记录left节点，他将是反转后的尾节点。从left位置开始进行直到right位置反转。完成反转后，将preLeft的next指针指向反转函数返回值，同时将原来left节点的next指向right节点之后的节点。

23 螺旋矩阵 给你一个m行n列矩阵matrix，按照顺时针螺旋顺序，返回矩阵中所有元素。

思路，用四个指针限定矩阵当前边界top bottom left right。然后按照顺时针螺旋遍历矩阵，并逐渐调整这四个边界。从左到右遍历top行，然后top自增。从上到下遍历right列，然后right自减。从右到左遍历bottom行然后bottom自减。从下到上遍历left列，然后left自增。上面四步都要检查四个变量没有越界。

在后两个循环中，要判断top是否小于等于bottom，left是否小于等于right，应对矩阵只有一行，一列的情况。

24 相交链表 给你两个单链表头结点headA和headB，请你找出并返回两个单链表相交的节点，如果不相交，返回null。

思路，用双指针法。两个指针分别从两个链表头开始遍历，当其中一个指针到达链表末端时，将其重定向到另一个链表头部继续遍历，这样，两个指针会相遇在相交节点处或者都指向null。这样两个指针会遍历相同数量的节点。

次优解法，用集合，将一个链表节点存储到哈希集合中，再遍历另一个链表，如果某个节点在哈希集合中，则返回这个节点，否则遍历完所有节点返回null。

25 合并K个升序链表 给你一个链表数组，每个链表已经按升序排列，请你将所有链表合并到一个升序链表中，返回合并后的链表。

思路，用优先队列。最小堆需要自定义new Comparator。用一个dummy和current节点记录。将所有链表头结点放入最小堆中。每次从堆中取出最小节点，current指向这个节点，current后移。然后如果其下一个节点存在的话，入堆。时间复杂度N log k，空间复杂度k。

思路2，用分治。将k个链表分成两半，分别递归合并，最终将两个有序链表合并。时间复杂度N log k，空间复杂度log k。

26 字符串相加 给你两个字符串形式的非负整数num1和num2，计算他们的和并以字符串形式返回。

大数加法

思路，蛮力法。初始化StringBuilder存储result，并用carry记录进位。从两个字符串尾部开始逐位相加，对于每一位取出两字符串当前位数字加上进位，计算出当前位结果和新的进位。如果最后还有进位，需要加到结果前面。

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

思路，动态规划。dp i记录以元素i结尾的最长递增子序列的长度。遍历每个元素时要向前看所有j元素，并更新dp i。对于每个i从1到n减一，遍历j从0到i减一，如果nums i大于numsj，则dp i取dp j加一和dp i的最大值。

动态规划是O n平方复杂度，可以用贪心加二分搜索实现O n log n时间（大厂要求），《维护一个List sub，位置为i的元素保存长度为i加一的递增子序列的最小末尾元素》，遍历每个nums i，用二分查找在sub找到第一个大于等于nums i的位置，如果找到，则替换该元素，因为更小的元素可能带来更长的递增子序列，如果没有找到，将nums i加到sub的末尾。sub的长度就是最长递增子序列长度。贪心加二分搜索的时间复杂度是O n log n是因为内部的while循环是二分。

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

思路，动态规划。创建两个数组leftmax和rightmax，分别记录每个柱子左边和右边最高的柱子高度。从左往右遍历数组填充leftmax数组，leftmax i取leftmax i减一和nums i的最大值。从右往左遍历数组填充rightmax数组。最后再遍历每个柱子，计算每个位置可以积水的量。

29 重排链表 给你一个单链表的头结点head，单链表表示为L0L1到Ln减一Ln请将其重排序为L0LnL1Ln减一。

思路，找到链表中点，用快慢指针。然后反转链表的后半部分，最后合并链表前半部分和反转后的后半部分，将链表前半部分和反转后的后半部分交替合并，方法是用first和second两个指针指向前后部分，while second不为空，temp1和temp2记录fitst和second的下一个节点，将first的next指向second，将second的next指向temp1，也就是first原来的下一个节点，然后更新first和second为temp1和temp2。

注意和第9题合并两个有序链表不一样，合并两个有序链表每次遍历只移动两个指针中的一个，而这题交替合并两个指针都要移动。

31 环形链表II 给你一个链表头结点head，返回链表开始入环的第一个节点，如果无环，则返回null。

思路，方法一，用双指针法。初始化快慢指针，都指向头结点head。slow每次移动一步，fast每次移动两步，如果链表中有环，那么slow会追上fast，当相遇时，再将slow拿到head，然后slow和fast每次移动一步，当他们再相遇时，所在的节点就是环的入口。方法二，用hashset存储访问过的节点，如果访问过，则说明这是换的入口，直接返回。

证明：设头结点到环的入口点距离为a，环入口点到相遇点距离为x，环长为r，相遇时fast绕了n圈，则有2乘以a加上x等于a加n乘以r加上x，也就是a等于n乘以r减去x，所以如果fast从相遇点移动，那么他们会在环入口点相遇。

32 合并区间 给你数组intervals表示若干个区间的集合，其中一个区间为start end，请你合并所有重叠的区间，并返回一个不重叠的区间数组。

思路，按照起始位置排序，然后遍历并合并区间。首先将所有区间按照起始位置升序排序，然后初始化一个空列表存放合并后的区间结果。对于每一个区间，如果他与结果列表中的最后一个区间重叠，也就是当前区间的起始位置小于等于最后一个区间的结束位置，则将他们合并，取两个区间结束位置最大值作为合并区间后的结束位置。如果不重叠，直接将当前区间添加到结果列表。

33 二叉树中的最大路径和 二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边，该路径至少包含一个节点，且不一定经过根节点。路径和事路径中各节点值的总和，给你二叉树根节点root，返回其最大路径和。

思路，递归，对于每个节点，计算该节点的最大路径和，三种情况，仅包含当前节点，包含当前节点和左子树最大路径，包含当前节点和右子树最大路径。 对于每个节点，我们也要计算如果该路径作为一条从父节点传入路径一部分，它的最大贡献，就是节点值加上左右子树较大路径的值。 注意，在当前节点为null时，返回0，而在队规计算左右子树最大路径时，只能取正值，和0之间去最大值。

34 编辑距离 给你两个单词word1和word2，请返回word1转化成word2所需的最少操作数。有三种操作，插入一个字符，删除一个字符，替换一个字符。

思路，动态规划。dp i j表示从word1前i个字符串到word2前j个字符串所需的最少操作数。状态转移方程如下：如果当前两个字符相同，则不需要额外操作，dp i j为dp i减去1 j减去1。 如果当前两个字符不同，考虑三种操作，插入一个字符到word1，dp i j为dp i j减去1 加一。从word1删除一个字符，dp i j为dp i减去1 j加一。替换当前字符，dp i j为dp i减去1 j减去1加一。最后dp 最后一行最后一列元素就是将word1转化到word2所需最少操作数。

35 删除链表的倒数第N个节点 给你一个链表，删除链表的倒数第n个节点，返回链表头结点

思路，用双指针。先创建一个哨兵dummy，指向head，初始化fast和slow，都指向dummy，将fast向前移动n加一步，这样fast和slow就有n加一个节点的距离。同时移动fast和slow，直到fast为空，此时slow指向倒数第n加一个节点，直接删除slow下个节点，不需要对删除头结点的情况做额外判断。

36 复原IP地址 给你一个只包含数字的字符串s，表示一个IP地址，返回所有可能的有效IP地址，这些地址可通过在s中插入点号完成。（百度）

思路，用递归。参数有String s，start当前所在字符位置，List String curr当前的结果，以及result列表。递归的出口是curr的size为4且start到达串末尾。然后遍历当前位可以有1到3个字符，取出这个子串，判断是否有效，有效则进行递归，把StringBuilder加上当前子串。

37 最长公共子序列 给你两个字符串text1和text2，返回这两个字符串的最长 公共子序列的长度。如果不存在公共子序列返回0。子序列可以不连续。

思路，用动态规划。创建dp i j表示text1前i个字符和text2前j个字符的最长公共子序列的长度。dp 0 j和dp i 0都初始化为0，因为任何字符串与空串的LCS长度为0。如果text1 i减去1与text2 j减去1相等，则dp i j为dp i减去1 j减去1加一。否则dp i j取dp i减去1 j和dp i j减去1的最大值。

总结，如果要求字符连续，动态规划转移方程只在字符匹配时更新，字符不匹配时重置为0。如果不要求连续，则动态规划转移方程在字符匹配和不匹配时都更新，匹配时dp i j为dp i减一 j减一 加一，不匹配时取dp i减一 j和dp i j减一的最大值。

37 最长公共子序列 变种，不输出最长公共子序列长度，而是输出所有最大长度的公共字符串

还是动态规划，dp[i][j] 表示以 s1[i-1] 和 s2[j-1] 结尾的最长公共后缀的长度。若此长度大于当前 maxLen，更新 maxLen 并清空结果集合，将当前子串加入；若等于 maxLen，则将该子串加入结果集合（利用 Set 去重）。

两个数组的最大公共子序列

相比字符串，多了一个额外的遍历过程。

38 二叉树的中序遍历 给你一个二叉树根节点返回中序遍历

思路，和后面的前序遍历差不多，用栈模拟遍历过程，current变量记录当前节点，while条件是current不为空且stack非空。内层while循环当current不为空时，往栈里面丢元素。然后从栈顶取节点作为current，把current放入list结果里面，然后把current指向current的right。

39 删除链表中的重复元素 II 给定一个已排序的链表的头head，删除原始链表中 所有重复 数字的节点， 只留下不同的数字 ，返回链表头结点。

思路，用两个指针跟踪当前节点和下一个节点。步骤，创建一个虚拟头结点dummy，next指向head。使用prev和current指针。prev指向当前非重复节点前一个节点，current指向当前节点。遍历链表，检查当前节点是否重复的， 如果重复跳过所有重复节点，跳出循环后将prev的next指向current的next，也就是prev的next指向下一个不同的节点。如果当前节点不是重复的，把prev更新为prev的next。最后更新current为current的next。返回dummy的next。

41 二叉树的右视图 给你一个二叉树根节点root，想象自己站在它右侧，按照从顶部到底部顺序，返回从右侧能看到的节点值。

思路，层序遍历。两个队列遍历当前层节点和下一层节点，要用双端队列。和12题，21题类似的思路。

42 下一个排列 给你一个整数数组nums，找出nums的下一个排列，下一个排列是指整数的下一个字典序更大的排列。空间要求O 1。

思路，蛮力法。先从后向前找，找到第一个满足nums i小于nums i加一的位置i，i是要进行处理位置的起点，因为nums i加一到末尾都是降序排列的。如果找到了这样的i，则从数组末尾开始向前找，找到第一个大于nums i的数字，设这个位置为j，然后交换nums i和nums j。将位置i加一到数组末尾部分反转，获得该部分最小排列。如果数组完全是降序排列，也就是没找到满足条件的i，则反转整个数组。

43 寻找两个正序数组的中位数 困难题 给你两个大小分别为m和n的正序数组nums1和nums2，请你找出并返回这两个正序数组的 中位数 。时间要求O log m加n。

思路，用二分查找。先确保nums1是较小的数组，如果不是，交换一下nums1和nums2。m，n为nums1 nums2的长度。初始化二分查找范围，在nums1中，我们设置left和right，初始化为0和m。进行二分查找，计算nums1的分割点partition1，left加right除以2，在nums2中计算分割点partition2，m加n加1除以2减去partition1。确定四个关键元素，nums1中左侧最大元素maxLeft1为nums1 partition1减1，如果越界设为负无穷，nums1右侧最小元素minRight1为nums1 partition1，如果越界设为正无穷，nums2左侧最大元素maxLeft2为nums2 partition2减1，如果越界设为负无穷，nums2右侧最小元素minRight2为nums2 partition2，如果越界设为正无穷。检查并调整分割，如果maxLeft1小于等于minRight2且maxLeft2小于等于minRight1，那么正确分割找到，如果总元素个数是奇数，中位数是maxLeft1和maxLeft2的最大值，如果是偶数，中位数是maxLeft1，maxLeft2的最大值，加上minRight1和minRight2的最小值除以2。如果上面条件不满足，比如maxLeft1大于minRight2，说明partition1太大，向左调整，right取值为partition1减一，如果maxLeft2大于minRight1，说明partition1太小，向右调整，left取值为partition1加一。while条件是left小于等于right。

44 排序链表 给你链表头结点head，请将其按升序排列并返回 排序后的链表 。时间要求O n log n，空间要求O 1。

思路，用归并排序。寻找中点，用快慢指针找到链表后半段开头，将前后链表中间断开，然后递归的排序左右两部分，最后用merge方法合并有序链表，merge方法参数是两个链表头结点，返回合并后的链表，可以参考第9题。

45 用栈实现队列 请你仅用两个栈实现先入先出队列，队列应支持一般队列所支持的所有操作push pop peek和empty。

思路，用两个栈实现一个先进先出队列，两个栈反转元素的顺序模拟队列的行为。其中一个栈用于输入push，另一个栈用于输出pop和peek。当输出栈为空时，将输入栈所有元素转移到输出栈。

46 字符串转换整数 请你实现一个函数，将字符串转化成一个32位有符号整数。算法如下，读入并丢弃无用前导空格，检查正负符号，跳过前导零读取整数，如果整数超过32位有符号整数范围则要截断。

思路，蛮力法。溢出判断，在进行乘10以及加法之前，判断当前result本身不会超过Integer MAX value除以10，如果大于这个值那么我们截断，当当前result本身等于Integer MAX value除以10时，还要考虑当前读入的digit这一位，如果digit大于Integer max value对10取余，那么result乘以10加上digit会溢出，我们也要截断。截断直接return。

47 x的平方根 给你一个非负整数x，计算并返回x的算数平方根。

思路，用二分查找。初始化左边界left，right为1和x，注意平方square变量，left和right都用long，可能溢出，如果square等于x返回mid，如果小于x，left移动到mid加一，如果大于x，right移动到mid减一。

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

思路，用递归。backtrack方法参数，n，left，right，当前字符串StringBuilder cur，结果List result。left代表当前左括号数量，right代表右括号数量。如果当前cur字符串长度达到了2乘n，说明我们找到了一个有效组合将cur加入result，如果left小于n，则可以继续加入一个左括号，然后递归调用backtrack，传入的left加一，然后把cur加入的左括号删除。如果 right小于left ，注意这里不是right小于n，要保证括号有效，则可以继续加入一个右括号，然后递归调用backtrack，传入的right加一，然后把cur加入的右括号删除。

49 两数相加 给你两个 非空 链表，表示两个非负的整数，他们每位数字都是按照逆序方式存储，请你将两个数相加，并以相同形式返回一个表示和的链表。

思路，逐位相加考虑进位。创建一个dummy节点，cur指向dummy节点，while两个链表 只要有一个不为空 ，如果当前一个链表已经遍历完，当前节点值用0代替，计算当前位的和，更新进位carry，创建新的节点保存当前位的结果，移动到下一个节点。如果最后还有进位，需要创建一个新的节点。

50 爬楼梯 假设你正在爬楼梯，需要n阶才能到达楼顶，每次你可以爬1或2个台阶，你有多少种不同方法爬到楼顶？

思路，动态规划。dp i表示爬到第i阶的方法总数。dp i等于dp i减一加上dp i减二，dp 1等于1，dp 2等于2。

51 滑动窗口最大值 困难题 给你一个整数数组nums，有一个大小为k的滑动窗口从数组最左侧移动到数组最右侧，你只可以看到滑动窗口内的k个数字，每次向右移动一位，返回滑动窗口中的最大值。

思路，用双端队列deque实现，用双端队列存储窗口内的潜在最大值索引，从而在每次滑动窗口时快速找到最大值。步骤，初始化双端队列，保证从队列前端到后端，元素对应数组值是递减的，遍历数组，移除旧的元素，检查队列前端，如果队列中存储的元素索引已不在滑动窗口中，则从队列前端移除。 在添加新element之前，从队列后端开始，移除所有比当前元素小的元素的索引，确保队列前端始终是当前窗口中的最大值。 将当前element的索引添加到队列后端。 当窗口的长度首次达到k时开始记录，每次移动窗口时，队列的前端element就是当前窗口的最大值。

52 比较版本号 给你两个版本号字符串，version1和version2，请你比较他们，版本号由英文点 分隔开的修订号组成，修订号的值是 它转化为整数并忽略前导0。 比较版本号时，从左到右比较修订号，如果其中一个修订号较少，缺失的修订号视为0。如果version1小于version2返回-1，如果大于返回1，相等返回0.

思路，使用String split方法将版本号分割成修订号数组。如果某个版本号较短并且当前位置没有版本号，手动在末尾添加0。 遍历修订号数组，直到发现不相等的位置或者全部遍历完成。

53 缺失的第一个正数 困难题 给你一个未排序的整数数组nums，找出其中没有出现的最小的正整数。时间要求 O n，空间要求 O 1。

思路，用 原地哈希 实现，用数组本身作为哈希表，将每个数字尝试放在其应有的位置上，即数字1 放在索引0的位置，数字2放在索引1的位置。这种方法通过交换元素逐步将数组整理成接近有序的状态，通过索引判断缺失的最小正整数。步骤，预处理，遍历数组，将所有小于等于0的数字改为N+1，消除负数和零的干扰。 原地哈希，再次遍历数组，对于每个数字，如果其值在1到N范围内，将其放在正确的位置，如果目标位置已经有正确数字，则不需要交换，注意交换操作在一个while循环内，可能交换之后仍然不满足条件。 最后遍历数组，检查每个位置i是否包含数字i+1，第一个不符合条件的位置就是缺失的最小正整数。

54 零钱兑换 给你一个整数数组coins，表示不同面额的硬币以及一个整数amount，表示总金额，计算并返回可以凑成amount所需的 最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1，你可以认为每种硬币数量无限。

思路，动态规划，dp i代表凑成金额i所需的最少硬币数量。步骤，初始化dp数组，创建一个大小为amount+1的数组，初始值设为amount加一，代表所需硬币数无限大，dp 0为0，金额为0不需要任何硬币。 状态转移，对于每个金额 i 从1到amount，对每个硬币coin，如果coin小于等于i，则更新dp x为 dp x减coin 再加一。 返回结果如果dp amount没有更新则返回-1，否则返回dp amount。

55 训练计划II 给你一个头结点为head的链表，查找并返回倒数第cnt个节点。

思路，用双指针。初始化两个指针slow和fast，都指向head，移动fast指针，先让fast指针向前移动cnt步，这样fast和slow会保持cnt步的距离。 同时移动fast和slow指针，直到fast到达末尾，这时slow指针指向链表中倒数第cnt个节点。

56 最小覆盖字符串 困难题 给你一个字符串s，一个字符串t，返回s中覆盖t中所有字符的最小子串，连续的，如果s中不存在涵盖t中所有字符的子串，返回空字符串。

思路，用滑动窗口法。用两个哈希表，记录字符串t中每个字符出现次数，另一个记录当前窗口中每个字符出现次数，定义left和right表示当前考察的窗口的左右边界。移动右指针right增大窗口，直到窗口中包含了t中所有字符。一旦找到一个有效窗口，尝试移动left左指针来收缩窗口，同时保证窗口依然有效，当窗口有效时，检查当前窗口长度是否是最小窗口，是的话更新结果。重复上面步骤，直到右指针right遍历完字符串s。

57 子集 给你一个整数数组nums，数组中元素互不相同，返回数组中所有可能的子集。

思路，用回溯法，从空集开始，逐步添加数组中每个元素，生成所有可能的子集，每个元素可以选择加入当前子集或者不加入。

58 从前序与中序遍历序列构造二叉树 给你两个整数数组preorder和inorder，请构造二叉树并返回其根节点。

思路，用递归和哈希表构造树。用index记录当前处理前序遍历的元素索引，map存储中序遍历数组每个元素值和对应的索引的哈希表，用于快速定位根节点。 递归参数，preorder数组，left，right。步骤，如果left大于right，表示子数组没有元素，返回null。选择当前index指向的值作为根节点，递增index，使用map查找当前根节点在中序遍历中的索引，递归构建左子树，使用中序遍历左边部分，递归构建右子树，使用中序遍历右半部分。

59 最长有效括号 困难题 给你一个只包含左括号和右括号的字符串，找出最长连续有效括号子串的长度。

方法一，思路，用栈跟踪未匹配的括号的 索引。创建一个栈，将-1压入栈中，帮助处理第一个括号匹配的情况。 然后遍历字符串，如果是左括号，将索引压入栈。 如果是右括号，先弹出栈顶元素，对应最近一个未匹配的左括号。然后判断栈如果为空，将当前字符索引入栈，这表示之前所有括号都匹配完毕，而当前的右括号没有找到匹配。 判断栈不为空，则计算有效子串长度，当前索引减去栈顶元素，因为栈顶元素下一个索引到当前索引之间的子串是有效的。难点是用栈保存索引以及碰到右括号该怎么处理。

方法二，动态规划，dp i表示以位置i结尾的最长合法子串的长度。如果s i为左括号，则dp i为0，如果s i为右括号时，如果前一个字符是左括号，则dp i等于dp i减2加2，如果前一个字符是右括号，则dp i等于dp i减1加2加dp i减dp i减1减2。

60 字符串相乘 给你两个以字符串形式表示的非负整数num1和num2，返回num1和num2的乘积，他们的乘积也表示为字符串形式。不能用BigInteger库。

思路，暴力法。创建一个数组result，长度为num1和num2长度之和。反转num1和num2，保存到StringBuilder里面，然后遍历两个字符串每一位，将他们相乘，并加到result数组i+j位置上，然后处理进位，把对10取余的结果保存在result i+j位置上，把除以10的结果保存在result i+j+1位置上。 遍历完成后，从后往前遍历result数组，去掉前导零，然后再把他丢到StringBuilder里面，返回toString。

最小覆盖子串 给你一个字符串s、一个字符串t，返回s中包含t的所有字符的最小子串。

用滑动窗口。先用need统计目标串每个字符需求数量。left，right两个指针初始化为0，先向右移动right，每遇到一个在need中的字符，就在window中计数，并当计数达到需求时，将已满足种类数have加1。当have等于所有所需字符数时，尝试收缩left来获得更小窗口，每次收缩前更新最小窗口长度和起始位置，如果移出的字符在need中，则先检查他是否刚好满足需求，如果是则have减一，然后在window中把他的计数减一。如果minLen仍为初始值，说明未找到合适窗口返回空，否则返回记录的最小窗口子串。

61 最小栈 设计一个支持push pop top操作，并能在常数时间检索到最小元素的栈。

思路，用两个栈，主栈和最小栈，元素入栈时如果最小栈为空或者元素值 小于或等于 最小栈的栈顶，那么压入最小栈。元素出栈时，如果最小栈非空并且最小栈的栈顶大于或等于主栈的栈顶，那么要先出栈最小栈，然后才出主栈。这里的push和pop都有个兜底的逻辑。

注：

最大栈（腾讯）

方法一，用两个栈，主栈存储所有元素，最大栈存当前最大元素，每次向主栈push元素时，还要将当前最大值push到最大栈中。

方法二，只用一个栈和额外一个变量最大值，push时，检查当前入栈元素是否大于等于栈中最大值，如果当前值大于等于最大值，则将当前最大值入栈，并更新最大值，然后再把当前值入栈。pop时，先弹出栈顶，如果弹出元素是当前最大值，则要恢复之前的最大值，这时从栈中再弹出一个元素，他是之前的最大值，把他更新到变量中。

62 反转字符串中的单词 给你一个字符串s，反转字符串中单词的顺序，注意字符串可能存在前导空格，尾随空格或者单词之间有多个空格。

思路，先用trim方法去除收尾空白，然后用split方法以及反斜杠反斜杠s加正则表达式根据一个或多个空格分割字符串为单词数组，然后用Collections.reverse方法反转数组列表，最后使用String join方法将反转后单词数组重新组合成一个字符串，单词之间以一个空格分隔。

63 从根节点到叶节点数字之和 每条从根节点到叶节点的路径代表一个数字，如1 2 3 路径代表数字123。

思路，用dfs，参数为当前节点root，当前总和current sum int数组，保存路径对应的数字的列表list，访问一个节点，把current sum乘以10，把当前节点值加到current sum上，然后递归遍历左右子节点，然后复原current sum。把列表里面所有element相加就是答案。

64 对称二叉树 给你一个二叉树的根节点root，检查他是否轴对称。轴对称的概念不是递归的，只能说这个书是轴对称的，不能说左右子树是对称的。

思路，用dfs，参数为左子树left，右子树right，如果两个子树满足他们的根节点值相等，并且左子树的左子树和右子树的右子树是对称的，并且左子树的右子树和右子树的左子树是对称的。

65 二叉树的前序遍历

思路，dfs就是先加到list，再访问左右子树。非递归用栈模拟递归，并用一个current变量存储当前节点root，while循环条件是current或栈不为空，然后内层又有一个while，只要current不为空，往栈，列表list添加current，current不停向left子树移动，然后跳出后取栈顶，current指向栈顶的right子树。

67 平衡二叉树 给你一个二叉树，判断他是否是平衡二叉树

思路，dfs，先写一个获得当前子树高度的方法getDepth，然后先判断当前节点root是否平衡，通过判断左右子树高度差是否小于等于1，然后再递归判断左右子树是否平衡。

68 组合总和 给你一个无重复元素的整数数组candidates和一个目标整数target，找出candidates中可以使数字和为target的所有不同组合，并以列表形式返回。candidates中同一个数字可以无限制重复被选取。

思路，回溯法，参数为当前列表current，当前和cursum，当前索引index，candidates数组，以及result列表。从当前索引index遍历candidates数组，将当前element加入current，并减少cursum，然后递归调用自己尝试找到有效组合。然后把这个element从current中移除撤销选择，并把cursum加上element，以尝试下一个可能的组合。

69 二叉树直径 给你一个二叉树，返回该树的直径，直径是指树中任意两个节点之间最长路径的长度，路径可能不经过根节点root。

思路，dfs，参数为根节点root，结果result，递归计算每个节点左右子树高度，对于每个节点，经过这个节点的最长路径长度通过左子树高度加上右子树高度计算，然后更新全局最大路径长度result，然后递归return当前节点的高度，也就是左右子树高度的较大者加一。

70 在排序数组中查找元素的第一个和最后一个位置

思路，二分查找，先找到第一个位置，找到一个等于target的element时，向左移动右指针right缩小查找范围，当mid减去1的element的值不为target时，mid就是第一个位置。 查找最后一个位置，重复上面的二分查找步骤，但在找到等于target的element时，向右移动左指针left，确定最后一个等于target的位置。

71 用rand7实现rand10

思路，先生成更大的范围，(rand7减去1)*7 + rand7生成1到49的随机数，将rand7的结果视为两位七进制数，其中第1位乘以7。然后拒绝41到49的结果，拿到1到40的结果，用 (result减去1) % 10 + 1来映射到1到10的范围。

72 旋转图像 给定nn矩阵，将矩阵顺时针旋转90度

思路，先将矩阵转置，行列互换，再把每一行的element反转。

73 验证二叉搜索树，看二叉搜索树是否有效，有效是指节点左子树只包含 小于 当前节点的树，右子树只包含大于的，左子树和右子树也必须是二叉搜索树。

思路，dfs传递当前节点值的有效范围最小值，最大值，每次递归调用时，更新节点值应该在的范围。

74 最小路径和 给定mn网格，找出从左上到右下最小的路径，只能向右或向下走。

思路，动态规划，dp i j代表到达i j的最小路径和，第一行第一列直接累加，其他情况，dp i j等于左方和上方的dp最小值加上当前单元格的值。

75 字符串解码。给定一个编码过的字符串，返回解码后的字符串，编码规则是k 中括号 string 中括号，string重复k次，可以认为原始数据不包含数字。

思路，用栈处理，遍历整个字符串，用两个栈，一个存储重复次数，一个存储在每个重复次数之前的字符串部分。还有两个变量，当前重复次数和当前字符串。遇到数字时，算出完整的重复字数，可能有多位，遇到左括号时，将当前重复次数和当前字符串推入栈，并重置次数和字符串。遇到右括号时，从栈中弹出重复次数和之前的字符串，将当前字符串重复相应次数，并拼接到弹出的字符串后面，注意，是拼接到弹出的字符串后面。遇到字母时，加到当前字符串。

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

思路，动态规划，用二维数组dp存储以 i j为右下角的最大正方形的边长。对于矩阵每个element，如果他是1检查它的上方，左方和左上方的dp值，这三个值的最小值加一就是dp i j的值。如果i j元素的值是0，那么dp i j就是0。

77 路径总和 II 给你二叉树根节点root和一个整数目标target，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径

思路，用dfs，参数有result列表，current列表，target int数组，先将当前节点值加到current列表，并把target减去当前节点值，然后如果当前节点已经是叶子结点，左右孩子都为null，那么判断一下target是不是0，是0则把current列表加到result里面，然后递归遍历左节点，右节点，完成探索后，把当前节点的值从current列表中移除，并把target加回当前节点值。

78 搜索二维矩阵 II

思路，借鉴二维版本的二分查找思想。从矩阵右上角开始，设置当前位置为 i j，如果当前i j的值等于target，返回true，如果大于target，说明target不能在当前元素右边，因此j减去1，向左移动，如果小于target，说明target不能在当前元素上边，因此i加上1，向下移动。如果i j超出边界，则返回false。

79 寻找峰值 给你一个nums数组，找到峰值并返回其索引，峰值是严格大于左右相邻。数组可能包含多个峰值，返回任意一个。时间要求 log n。

思路，二分查找，left为0，right为nums的length减一，然后while二分查找，计算中点mid，检查nums mid是否大于其相邻元素，如果nums mid 比 nums mid+1 要大，那么mid左侧必存在一个峰值，right更新为mid。否则峰值在mid+1右侧，将left更新为mid+1。返回left。

80 最长公共前缀 写一个函数找字符串数组中最长公共前缀，如果不存在返回空字符串。

思路，蛮力法。选择第一个字符串作为基准字符串，对于数组中剩下每个字符串，用indexOf方法检查基准是否是该字符串前缀，如果不是，则逐步缩短前缀，就是用substring去掉最后一个字符，直到找到一个公共前缀或者前缀为空。

81 最长连续序列 给定一个未排序nums数组，找出数字连续的最长序列长度，这个序列不需要再原数组中连续，时间要求 O n。

思路，用哈希表解决。先将所有元素加到HashSet中。遍历数组中每一个数字，判断这个数字是否是某个连续序列的起点。一个数字时起点的条件是这个数字前一个数字nums i 减一不在集合中，这一点是关键。如果条件满足，那么他是新序列起点。然后我们循环检查是否存在nums i 加一加二等，然后更新最大长度。

82 回文链表 给你一个单链表头结点head，判断该链表是否为回文链表，是则返回true，否则返回false。

思路，先找到链表中间节点，使用快慢指针，当快指针到链表尾时，慢指针在后半链表的起始节点位置。然后翻转链表后半部分，原地翻转，使用头插法。然后比较两部分链表，如果所有对应位置节点值都相等，则返回true。

84 二叉树最大宽度 给你二叉树根节点root，返回树的最大宽度，最大宽度是所有层最大的宽度

思路，用层序遍历，广度优先，根节点索引是0，左节点索引是2 i +1，右节点是 2 i +2，初始化两个队列双端队列q1，q2，把根节点加入q1，遍历q1中每个element，如果element存在左右子节点，都加入q2，当q1为空时，把q1赋值为q2，并新建一个q2，然后再判断q1是不是空，不是空我们拿出队列头和尾，更新最大宽度。

85 多数元素 给你一个nums数组，返回其中的多数元素，多数元素是指出现次数大于二分之n的元素

思路，用投票算法。原理是多数元素出现频率高于所有其他元素总和，因此即使其他元素与多数元素相抵消，最后剩下的一定是多数元素。步骤，初始化两个变量，result和count，result取值为第一个element，count取值为0，遍历数组中每个元素x，如果count为0，，将result设置为x并将count设为1。如果count不为0，若x等于result则count增加1，否则count减少1。通过上面步骤，result就是多数元素。

86 最大数 给你一组非负整数数组nums，重新排列每个数顺序使它成为一个最大整数

思路，自定义排序，new Comparator自定义compare方法，比较字符串o1+o2和o2+o1的大小，决定o1 o2谁在前面。

87 最长重复子数组 给你两个数组nums1和nums2，返回两个数组中公共长度最长的子数组的长度。子数组是连续的。

思路，动态规划，定义二维dp，dp i j表示以nums i和nums j结尾的最长公共子数组长度，如果nums i 和nums j相等，则dp i j是dp i减去1 j减去1 加一

88 删除链表中重复元素 和39题不一样，这道题是保留重复元素中的一个

思路，判断当前element和后继值是否相同，相同则跳过后继，即当前element的next指向下下个element。

89 基本计算器 II 字符串由整数和加减乘除组成，中间用空格隔开

思路，用一个数字栈，一个字符变量记录最后的操作符，一个变量保存当前数字。如果遇到数字解析整个数字，注意可能有多位。如果遇到一个操作符或者达到字符串结尾，根据前一个操作符更新栈，如果操作符是加减，前一个数字直接入栈，如果操作符是乘除，弹出栈顶与当前数字运算，推回栈中。最后，把栈中所有元素相加。注：坑点是在判断当前字符是数字还是操作符时，不能用if else if而是两个if。

90 不同路径 mn网格机器人从左上角走到右下角有多少不同路径

思路，动态规划，ij的路径由i减去1 j和i j减去1转移，第一行和第一列的值都是1。

91 岛屿的最大面积 给你一个大小m n的二进制矩阵grid，岛屿的面积是岛上值为1的单元格的数目，计算并返回grid中最大的岛屿面积。

思路，用dfs。遍历grid所有元素，如果当前元素值为1，调用dfs计算当前岛屿面积，dfs先判断当前元素是否未越界并值为1，然后将值设为0，然后计算当前位置的岛屿面积，加上上下左右四个方向的面积，然后返回。和14题是同一题。

92 乘积最大子数组 给你一个整数数组nums，请你找出数组中乘积最大的非空 连续 子数组，并返回这个乘积。

思路，动态规划。数组存在负数，所以要同时跟踪当前位置的最大和最小乘积，因为负数乘以一个最小乘积可能会变成最大乘积。定义dpmax和dpmin记录到当前位置的最大乘积和最小乘积。为节省空间也可以只用两个变量，cur max和cur min。初始化cur max和cur min为数组第一个元素，从第二个元素遍历数组，对每个元素，计算包含当前元素的可能最大乘积和最小乘积，取三数中的最大和最小，分别是当前元素本身，当前元素乘以之前的cur max，当前元素乘以之前的cur min。

93 买卖股票的最佳时机 II 给你一个整数数组prices，可以多次购买股票。

思路，贪心。只要第二天股价比第一天高，我们就把这个差值加上利润。和第17题不一样。

94 翻转二叉树 给你一颗二叉树根节点root，翻转这个二叉树，并返回根节点。翻转是递归的，和第64题对称二叉树不同，对称不是递归的。

思路，递归。对每个节点，交换左右子节点值，然后递归调用左右子节点。

95 打家劫舍 你是一个专业小偷，计划偷盗沿街房屋，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警，给你一个代表每个房屋存放金额非负整数数组，计算你不触动报警装置情况下，一夜之内能偷窃到的最高金额。

思路，动态规划。dp i表示偷窃到第i个房屋时，不触发警报情况下可以偷窃到的最大金额，有两种选择，不偷窃当前房屋，或偷窃当前房屋，dp i等于dp i减一与nums i加上dp i减二的最大值。和第50题爬楼梯很像。

96 单词拆分 给你一个字符串s和一个字符串列表wordDict作为字典，如果可以用字典中出现的一个或多个单词拼接处s则返回true。不要求字典中单词全部都使用，且字典中单词可以重复使用。（字节）

思路，动态规划。初始化长度为s length加一的布尔型数组，dp 0为true，表示空字符串可以表示出来，遍历字符串每个位置i，进行下面操作：遍历i前面所有位置j，如果dp j为true，且s j到i存在于wordDict中，则将dp i设为true，跳出。时间复杂度O n平方，空间复杂度O n加m乘以k。

注：如果字典中单词只能用一次呢？

97 和为k的子数组 给你一个整数数组nums和一个整数k，请你统计并返回该数组中和为k的子数组的个数。

思路，用哈希表和前缀和。初始化一个哈希表prefix cnt，记录每个前缀和出现次数，prefix cnt 0为1，遍历nums数组，计算从开始到当前元素的和current sum，计算所需和current sum减去k，如果这个和在哈希表中存在，那么prefix cnt current sum减去k的值就是当前元素结尾的和为k的子数组个数，同时更新哈希表，将current sum的出现次数加一。

98 长度最小的子数组 给你一个含有n正整数的数组和一个正整数target，找出数组中满足总和大于等于target的长度最小的子数组，子数组是连续的，并返回其长度。

思路，滑动窗口。用left和right，表示子数组的起始和结束位置，同时用sum记录窗口中的元素和。移动right以包含更多元素，每次移动增加nums right到sum，当窗口中元素和大于等于target时，移动left减小窗口大小，同时更新满足条件的最小长度，当right指针到达数组末尾时，结束循环。

二叉树的后序遍历

递归遍历。

非递归遍历。用栈，可以用修改版的先序遍历结合头插法。目标是得到左右根的序列。可以先做一种根 右 左的先序遍历，在遍历过程中，把访问到的节点头插到linked List中，最终的结果正好是左 右 根的顺序。

无序数组中位数（数据流中的中位数）

看题目的要求，如果输入是数组，输出是中位数，则用快速选择算法，时间复杂度为O n；如果输入为空，且有另外一个addNum方法，不断往里面加元素，则用一个大根堆和一个小根堆实现，时间复杂度为O log n，加元素时间复杂度为O 1。

280 摆动排序，即让奇数下标的元素小于等于后一位元素，而偶数下标的元素大于等于后一位元素

方法一。一次遍历贪心法。对于偶数下标，希望nums i小于等于nums i加1，如果不满足，交换他们。对于奇数下标，希望nums i大于等于nums i加1，如果不满足，交换他们。时间复杂度O n，空间复杂度O 1。

方法二，先排序，再交换。时间复杂度O n log n，空间复杂度O 1。

208 实现Trie 前缀树

给定一个数n如23121;给定一组数字a如[2 4 9]求由a中元素组成的小于n的最大数（小于n的最大数）（字节）

贪心。把给定数字n转换成字符串s，长度为L。将数组a中的数字排序，方便找不超过某值的最大元素。从s最高位往低位遍历：1.对于位置i，字符为c。2.在a中找所有小于等于c的数字，如果不存在，则说明要借位，将前一位回退到比他小的可用的值，并将当前位置和之后的全部填充成a中最大值。3.如存在等于c的数字，先选他，继续下一位。4.若只存在小于c的数字，则先选大的，然后将后面所有位直接填为a中最大值，得到结果结束。

如果一路都选了相等的，最后就是n本身，此时退而求其次，考虑用少一位数，且全填充为a中的最大值。总时间复杂度为O l log k 加上 k log k，其中l为n的位数，k是数组a长度。

36进制加法（字节）

从字符串末尾对齐，逐位相加，维护进位。每位和取模36得到当前位，整除36得到新的进位。处理完所有位后，去除多余高位0并反转结果。

岛屿数量的翻版，要求打印出所有陆地块的位置（美团）

遍历整个网格，遇到一个未访问过的i j陆地格，就在这里启动一次dfs。在搜索过程中，将所有连通的陆地格坐标收集到一个列表中，并标记为已访问。dfs返回后，得到一个完整的岛屿坐标列表。时间复杂度O m乘以n。

S型遍历矩阵（之字型扫描）（小红书）

把所有元素按行下标加列下标等于k分组，共有k从0到m加n-2条对角线。对于第k条对角线，i的范围是low到high，low取0和k减去（n减一）的最大值，high取k和m减一的最小值。为实现之字型zigzag扫描，当k为偶数时，i从low到high，当k为奇数时，i从high到low。时间复杂度O m乘以n。

数组乱序（字节）

从数组末尾开始，遍历到头部，每一步随机生成一个索引j，范围是0到i，包括两端，将当前元素arr i和arr j交换。最终得到的是等概率的乱序，时间复杂度是O n。

手撕给一个由数字和字母组成的字符串，如”135abf4646dsgk2”，找最大的数字(4646)

一次遍历，用StringBuilder累积当前连续数字字符，遇到字母或字符串末尾时，说明数字串结束。为避免把子串转成整型可能溢出，不直接解析为整数，而是先比较两段数字串长度，长度相同再比较字典序。

二叉树路径和，12345输出为124+125+13=262（美团）

深度优先，用一个变量计算到达当前节点之前已经形成的数字，如果是叶子结点直接把这条路径的数字返回，否则返回左右子树的结果之和。

整数转罗马数字

用贪心算法，从最大数值的罗马字符开始往下减，直到整数为0。

key value解析器，输入aa=bdd&c12=b，输出{aa=bdd, c12=b}，输入&&&==a=b&x=1&y=&=z&&k=v==extra，输出{x=1, k=v==extra}

用&拆分原始字符串为若干token，对每个token，找第一个等于号位置，如果没有等于号或等于号在开头或结尾，则跳过该token，否则，左侧为key，右侧为value。对key和value调用trim方法并且都非空时，放入最终map。

二叉树展开为链表

方法一，递归加尾插法。递归将左子树拉平为链表，得到左子树头结点和尾节点，递归将右子树拉平为链表，得到右子树头结点和尾节点。

方案二，迭代加栈。用栈模拟先序遍历，栈中先压右子节点，再压左子节点。每次从栈弹出一个节点cur，把他接到前驱的right，并把前驱的left置为null。更新前驱，再把cur的right，left入栈。

大数减法

预处理，去掉字符串a b前导0，比较两者大小，如果a小于b，则交换两者，并在结果前加负号。

逐位减法，从低位到高位，依次向高位计算，如果不够减，从更高位借1。

一个有序数组，输入一个数字，求这个数字在这个数组中重复的次数

用二分法，用一次二分法找到目标值最左位置，再用一次二分法肇东目标值最右位置，如果找不到返回0，否则重复次数等于右边界减去左边界加一。

两个线程下交替打印数字

synchronized加wait和notify。共享变量num，由两个线程轮流访问。奇数线程碰到奇数则打印并notify唤醒偶数线程，否则wait。偶数线程逻辑对称。结束后要额外notify一次，防止死锁。

Reentrantlock加两个Condition。将奇数和偶数分别用两个条件队列管理。

两个Semaphore。用两个信号量交替传递令牌，每打印完一次，释放对方信号量，自己阻塞。

堆排序

分为建堆和排序两阶段。建堆，对所有非叶子节点调用heapify，生成最大堆。排序，反复将堆顶最大值取出放到数组末尾，然后对剩余元素重新调整为最大堆。

TODO:牛客top101

求一个数的两个加数，需要满足两个加数的各个位的数字和最大

假设这两个整数是A，B，需要A加B等于N，并使得digit sum A加上digit sum B最大。观察数字相加的数位和关系，如果在某位发生了进位，则总的数位和会多出9，即digit sum A加上digit sum B等于digit sum N加上9乘以总进位次数。所以只要尽可能多产生进位，数位和就最大。时间复杂度O L，其中L为数字N的位数。

找到二叉树中的距离（给定一棵二叉树（普通二叉树，无任何特殊性质），再给定二叉树上任意两个节点a和b，求节点a与b之间的最短距离）（边的数量）

先用一次递归找到节点a和b的最近公共祖先，再分别计算从最近公共祖先到a的边数，以及到b的边数，两者之和即为最短距离。

丢失的数字，给定包含0到n中n个数的数组nums，找出0到n范围内中没有出现在这个数组的那个数（腾讯音乐）

方法一，异或法，先把1到n全部异或一遍，再把数组中出现的数全都异或进去，最后的值就是缺失的数。

方法二，数组求和法，先算1到n的总和，直接用等差数列求和公式，再减去数组中出现的每个数，结果就是缺失的数。

二维矩阵中第k个最大值，矩阵中的元素符合按行递增和按列递增（腾讯音乐）

方法一，二分查找和计数。每次猜测中间的值mid，统计一下矩阵中大于等于mid的元素个数，如果这个个数大于等于k，说明第k大元素大于等于mid，于是向右走；否则向左搜。时间复杂度O m+n乘以log V，其中V是二维矩阵的最大值和最小值的差值。

方法二，维护大小为k的小根堆，堆大小超过k时弹出栈顶，最后堆顶就是第k大的元素。时间复杂度O m乘以n乘以log k。

二叉树的最小深度（腾讯音乐）

方法一，递归，空节点返回0，当某一侧为空时，结果由另一侧子树深度决定。否则取左右子树深度的最小值加一。

方法二，层序遍历，用队列逐层遍历。发现的第一个叶子节点所在层即为最小深度。

两个数组合并得到去重后的数组（腾讯音乐）

用linked hashset，去重保持插入顺序，先后把两个数组元素加入到set，然后将set转为数组返回。

矩阵中的最长递增路径（腾讯音乐）

对每个格子从头开始递归搜索所有可能路径，用记忆化剪枝，dp i j表示从i j出发的最长递增路径长度，时间复杂度O m加n。

重新排列数组，给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,…,xn,y1,y2,…,yn] 的格式排列。请你将数组按 [x1,y1,x2,y2,…,xn,yn] 格式重新排列，返回重排后的数组。（腾讯）

方法一，空间复杂度O n，时间O n，创建结果数组ans，nums i填到ans 2乘以i，nums i加n填到ans 2乘以i加1。

方法二，空间复杂度O 1。因为题目限制了每个元素最大1000，即只会用到int的10个bit，而高位即可用来存储结果数组。

最大间距 给你无序数组nums，返回数组在排序之后，相邻元素之间最大的差值，如果数组元素个数小于2则返回0（腾讯）

用桶排序，时间复杂度O n，空间复杂度O n。先找出数组最大值最小值，将整个数组的元素分配到多个桶里，每个桶大小为max减去min除以n减1，n是数组长度，桶的数量为n减1，每个桶内元素有最大值和最小值，用来计算相邻桶最大差值。

基本计算器 字符串由数字，加减，小括号和空格组成（腾讯）

遍历字符串，遇到数字时累积成完整数字，遇到加减时，将前一个数字和其符号加入结果，并记录新符号，遇到左括号时，将当前结果和符号入栈，重置结果和符号。遇到右括号时，将当前结果和栈顶保存的符号、结果合并，最后将剩余的数字加到结果中。

链表随机节点

蓄水池算法，第k个节点以k分之一的概率替换掉当前选中的元素，保证最终每个节点被选中的概率相同。

注：蓄水池算法的通俗解释，如果池子只有一个数字，那么拿到第一个数字的概率就是100%。两个数字50%，三个数字每个33%以此类推。当我们不知道池子里有多少个数字时，要用蓄水池算法计算。当链表前行到第一个数字，取第一个数字的概率是100%。前进到第二个数字，那么此时取这两个数字的概率是50%，50%概率取新数字，50%概率保留原本数字。第三个数字的时候，33%的概率取当前最新的这个数字，66%的概率保留原本数字。这66%中，原本的数字有50%的概率是1，50%的概率是2。也就是这三个数字的概率都是33%。通过这个算法，就能达到取数的概率均摊。

工行有30万员工，现在要均匀抽出1万员工发奖品，提供一个16位的随机数生成器函数 rand16() 可供随意调用，请写一个函数 selectLuckyStaffs() 实现这个功能（30w员工公平选出10w）（腾讯）

初始化蓄水池，把1到k（即1万或者10万）编号全都选上。对于第i（从k加1到N）个人，以k除以i的概率放入蓄水池，并随机踢出一个已有成员。

交易逆序对的总数（腾讯）

分治，将数组不断二分，分别统计左右两侧的逆序对。在归并左右两个有序子数组时，如果左边当前元素大于右边当前元素，则左子数组中当前元素到末尾的所有元素都与该右元素构成逆序对，累积这些个数即可。时间复杂度O n log n。

寻找重复数 给定一个包含n加1个整数的数组，其数字在1到n范围内，包括1和n，因此至少存在一个重复的整数，假设只有一个重复，请不修改这个数组，并常数空间下返回这个重复的数（shopee）

快慢指针法。将数组看做链表节点，下标i的下一个位置是nums i，由于有重复，必定形成环，用快慢指针他们会相遇到一点，将一个指针从起点走，另一个从相遇点走，两者每次都走一步，再次相遇的位置就是环的入口。

单词搜索 给定m乘n二维字符网格和一个字符串单词，如果字符串存在于网格中，返回true；否则返回false。

dfs。对矩阵中每个格子作为起点，调用dfs。在dfs i j index中，检查当前字符是否匹配，是否越界，是否重复访问，若匹配到末尾元素则返回true；否则标记访问后，沿四个方向递归搜素下一字符，最后回溯，撤销访问标记。时间复杂度O m乘以n乘以4的L次方，L是单词长度。

用Java实现类似python中的String分割的功能

单次循环遍历，时间复杂度O n乘以m，n为输入字符串长度，m为分隔符长度，默认分隔符为任意长度空白串。

一个软件公司，有几种类型的资源(开发，测试，设计人员等)，他会承接多个项目，一个项目包含多个任务，任务需要一种类型的资源以及天数。问给定项目列表和拥有资源数量后，如果能完成所有项目，最少多少天，如果不能，最多完成几个项目？（字节）

这是一个多维01背包问题。在给定D天内，资源每天可用量为R i，m种资源，n个项目，dp k c1 c2 cm表示只考虑前k个项目，在已消耗第i类资源c i的情况下，能完成的最大项目数，他等于两个值的最大值，分别是dp k减1 c1 c2 cm，和dp k减1，c1减w k1，c m减w km加1，分别是选第k个项目和不选第k个项目。

数组中的最长山脉 即递增递减最长长度（拼多多）

方法一，双指针法。从数组第二个元素开始，到倒数第二个元素结束。枚举山顶位置i，仅当a i大于a i减1且a i大于a i加1时才继续搜索。向左扩展统计递增长度，向右拓展统计递减长度。时间复杂度O n。空间复杂度O 1。时间复杂度为O n的原因是如果当前位置是山顶，扩展完两侧后，直接把i等于right加1，跳过了整个山脉，下次不会再重走区间。

方法二，动态规划，维护两个数组，up i为以i结尾的严格递增子数组长度，down i为以i开始的严格递减子数组长度。如果a i大于a i减1，则up i等于up i减1加1。down同理。

按奇偶排序数组 给你数组nums，将数组偶数元素放数组前面，后跟所有奇数元素。

双指针法。用left和right，从头和尾向中间扫描，left指向的如果是奇数，则继续右移，遇到偶数时停下。right指向的如果是偶数，则继续左移，遇到奇数时停下。当left小于right时，交换两者，然后继续。时间复杂度O n，空间复杂度O 1。

分隔链表 给你链表头结点head和给定值x，对链表进行分隔，使得小于x的节点都出现在大于或等于x的节点之前。

双虚拟头结点，small挂载所有小于x的节点，big挂载所有大于等于x的节点。时间复杂度O n，空间复杂度O 1。

排序数组

方法一，快速排序。先用三数取中法，选出left、mid、right三者中的中位数作为枢轴。将枢轴交换到最左边。然后从右往左找小于pivot的，并从左往右找大于pivot的，直到左右指针相遇。最后把pivot和左指针元素互换，然后对左右两部分递归调用快速排序。

最小K个数（美团）

方法一，快速选择。先将中间的元素换到首位，然后对数组进行划分，如果划分的索引大于k则向左继续递归求最小k个数，如果划分的索引小于k则继续递归向右求最小k个数。时间复杂度O n，空间复杂度O log n。

方法二，大小k的最大堆。构建容量为k的最大堆，遍历数组，如果堆未满，则把数组元素放入，如果当前数组元素小于堆顶，则弹出堆顶，并放入数组元素。最后取出堆中元素并返回。时间复杂度O n log k，空间复杂度O k。

打乱数组 给你数组nums，设计方法打乱一个没有重复元素的数组，打乱后数组所有排列应该是等可能的。（字节）

FY洗牌算法。从后往前遍历数组，选择一个从0到i（不包含i）的随机索引j，交换i和j的元素。时间复杂度O n。

设计链表 支持get，addAtHead，addAtTail，addAtIndex，deleteAtIndex方法（元戎启行）

get直接顺序遍历。

addAtHead直接调用addAtIndex方法，传入参数0，val。

addAtTail直接调用addAtIndex方法，传入参数size，val。

addAtIndex，先将size加1，然后顺序遍历找到index的前驱pre，把新创建的节点的next指针指向pre的next，再把pre的next指针指向新创建的节点。

deleteAtIndex，先将size减1，然后顺序遍历找到index的前驱pre，把pre的next指向pre的next的next。

O(1) 时间插入、删除和获取随机元素 实现支持整数的insert、remove、getRandom操作且时间复杂度为O 1的数据结构（爱奇艺）

用ArrayList和Hashmap，实现O 1插入删除随机访问。用List存储元素，实现用索引随机访问。用Map记录每个值在List对应的索引。

插入时，将新值加到List尾部，并在Map中记录其索引。

删除时，找到目标值的索引，将List尾部数据覆盖到该索引位置，更新Map，再删除尾部数据。

随机访问，直接对List的长度取随机索引，返回对应的元素。

IPv4地址转为整数（腾讯）

先用String split将IP地址拆成4段。然后用位运算合成整数值，最左边的段占最高的8位，所以要左移24位。索引1左移16位，索引2左移8位，索引3不移动。然后用按位或累加到long结果中。Java中int是带符号的，不足以表达这个数字，因此用long保存最终结果。