动态规划逆推「约瑟夫环」问题 // 题目链接-来源：力扣（LeetCode） 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。 示例 1： 输入: n = 5, m = 3输出: 3 思路：我们手工模拟一次删除过程，希望能找到规律。设 n = 5，m = 3，则（粗体为待删除的元素，由于是循环排列的源泉，所以将开头循环部分拼接到尾部方便查看）第一次 [0,1,2,3,4][0,1,2,3,4]第二次 [3,4,0,1][3,4,0,1]第三次 [1,3,4][1,3,4]第四次 [1,3][1,3]最后 [3]考虑到经过若干次删除后，一定只剩下某个元素，虽然我们不知道这个元素具体是多少（本题中是3），但我们一定能知道元素的下标（最后剩余的元素，由于数组只剩一个元素，下标一定为0）。于是我们记 ...

找规律 // 题目链接-来源：力扣（LeetCode） 从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。 示例 1: 输入: [1,2,3,4,5]输出: True 思路：此题的关键是理清楚「顺子」的充要条件。 首先，不难得出顺子的必要条件，一条顺当中的最大值 max 与最小值 min 之差，一定满足 max - min <= 4。 其次，牌中除了代表「大小王」的 ‘0’ 以外，不得出现重复的牌。其实这两个条件同时满足的话也恰恰构成「顺子」的充要条件。于是我们只要统计 5 个数字当中的最大值，最小值，比较差值是否小于 4，并检查是否有重复值即可。判重的方法有很多，哈希表是通用方法；此外，本例中由于值域仅限于 [1, 13]，非常小，还可直接用「桶」来判重，效率会略快于哈希表。时间复杂度：O(n)空间复杂度：O(1) 实现：1234567891011121314151617181920class Solution { ...

二维动态规划。 // 题目链接-来源：力扣（LeetCode） 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。 你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。 示例 1: 输入: 1输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667] 思路：暴力解法会导致 O(6^n) 的复杂度。因此必须另寻他解。考虑利用动态规划降低复杂度。对于某一个骰子，其结果很简单，单次点数 1 ~ 6 都是 1/6 概率。我们需要掷 n 次骰子，对于第 n 次投掷，总点数为 k 的概率记为 f(n, k)，则有 f(n, k) = f(1, 6) * f(n - 1, k - 6) + f(1, 5) * f(n - 1, k - 5) + … + f(1, 1) * f(n - 1, k - 1)，其中 p(1, x) 即为单词投掷出 x 点的概率，恒等于 1/6。于是有f(n, k) = 1&# ...

用单调队列实现队列最大值的快速查找 // 题目链接-来源：力扣（LeetCode） 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。 若队列为空，pop_front 和 max_value 需要返回 -1 示例 1： 输入:[“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”][[],[1],[2],[],[],[]]输出: [null,null,null,2,1,2] 思路：受前一题启发，前一题的数据工作集是一个「滑动窗口」，而本题的工作集是一个「队列」，较新的元素在一侧，而较旧的元素在另一侧，结构上而言是相似的，因此可以直接套用前一题的思路。max_value 其实就相当于前一题的「滑动窗口」中的最大值，而其余功能都是队列基本的功能。于是我们只需定义一个主队列存储元素，再定义一个「单调队列」辅助查找最大值即可。时间复杂度：O(n)空间复杂度：O(n) 实现：123456 ...

用单调队列解决滑动窗口最大值 // 题目链接-来源：力扣（LeetCode） 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。 示例: 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3输出: [3,3,5,5,6,7]解释: 滑动窗口的位置 最大值 [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 思路：考虑一个窗口内某个数是当前的最大值，我们用某种办法记录它。这个最大值的「有效时间」截止以下两个条件满足任意一个： 1有更大的数字加入窗口，则该数称为新的「最大值」 2这个数字被移出窗口这个特性非常类似「双端队列」，但是我们 ...

简单字符串拼接 // 题目链接-来源：力扣（LeetCode） 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。 示例 1： 输入: s = “abcdefg”, k = 2输出: “cdefgab” 思路：设字符串长度为 n，只要拼接其两段子串 substring(0, k) 与 substring(k, n)即可 时间复杂度：O(n)空间复杂度：O(n) 实现：12345class Solution { public String reverseLeftWords(String s, int n) { return s.substring(n, s.length()) + s.substring(0, n); }}

// 题目链接-来源：力扣（LeetCode） 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。 示例 1： 输入: “the sky is blue”输出: “blue is sky the” 思路：用一前一后两个指针 left 和 right 遍历字符串。同时用 StringBuilder 将收集到的单词（即 left 与 right 形成的子串）插入头部，并用空格隔开即可。对于 left，我们要为其安排一个合适的停止位置（某个单词的起始位置），之后 right 从 left 出发，达到一个合适的停止位置（该单词的结束位置）。可以通过如下规则安排指针的行动， left 和 right 初始化为 0。 当前为空格，left 和 right 同时前进。 当前为字符，left 停止，right 前进直到碰见空格。复制 left 和 right 间的子串进入 StringBuilder 的开头处。细节处理，原字符串第一个单词前（生成的 ...

双指针提升有序数组查找效率 // 题目链接-来源：力扣（LeetCode） 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。 示例 1： 输入：target = 9输出：[[2,3,4],[4,5]] 思路：依然使用双指针法。不同的是，本题中我们并没有一个确切的数组大小，我们需要将其考虑为一个「滑动窗口」。由于我们的目标是连续正整数序列，即便我们的数组是虚拟的，我们只需根据前后指针的大小，用等差数列和公式 sum = (a1 + an) * n / 2 （对于本题，即为 sum = (left + right) * (right - left + 1) / 2）即可求出和。 若 sum < target，则我们需扩大窗口，right 右移即可。 若 sum > target，则缩小窗口，left 右移即可 若 sum = target，窗口整体需要右移，由于 left < right，右移结果 ...

双指针提升有序数组查找效率 // 题目链接-来源：力扣（LeetCode） 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。 示例 1： 输入：nums = [2,7,11,15], target = 9输出：[2,7] 或者 [7,2] 思路：使用两个指针，一个从数组头部向后遍历，一个从数组尾部向前遍历。二者指向的元素之和，可以与 target 作比较。由于数组本身有序，当和较大时，尾指针左移可使和变小，反之头指针右移可使和变大。就这样慢慢逼近 target。 时间复杂度：O(n)空间复杂度：O(1) 实现：12345678910111213141516class Solution { public int[] twoSum(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left < right) { ...

用位运算筛选数组中出现次数不一样的数字 // 题目链接-来源：力扣（LeetCode） 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。 示例 1： 输入：nums = [3,4,3,3]输出：4 思路：首先，与前一题类似，我们很直观地可以用哈希表记录数字遍历的次数。第二轮遍历的时候判断哈希表对应的键值是否为1即可找到该数字。如果要将存储空间降到 O(1)，可以采用与位运算类似的思路，不过由于无关数字出现了奇数次，无法使用异或运算抵消的思路，我们需要考虑更一般的解法。我们仍然将每一个数字视为一个 32 位的二进制数。则对于任意一个出现了 3 次的数字，其每一个位上的数字都出现了 3 次，’0’ 出现 3 次总和还是 ‘0’，而 ‘1’ 出现 3 次后总和为 ‘3’，对 ‘3’ 求余结果均为 0。并且这种结果对所有数字累加后的结果也是成立的，我们只要遍历数组，将每个数字都按二进制位统计该位上 ‘1’ 的个数，最后分别对 ‘3’ 求余，最后拼接成的结果即为「只出现1次的数」的二进制表达。 时间复杂度：O(n)空间复杂度：O ...