用哈希表降低查找的复杂度。 // 1. 题目链接-来源：力扣（LeetCode） （简单） 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。 示例 1： 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 ####思路：给定条件查找数据的问题，很容易想到哈希表。建立一个HashMap存储nums中的数值 value 以及对应下标 index1，然后遍历数组值，再查找哈希表中 target - nums[i] 对应的 index2，打包输出即可。 注意index1和index2不能相同。时间复杂度：O(n)空间复杂度：O(n) 实现：1234567891011121314151617class Solution { publ ...

以树的遍历为载体，查找节点的公共祖先至此，剑指Offer(第2版)刷题小记 告一段落。之后将继续更新力扣主站的刷题记录。 // 题目链接-来源：力扣（LeetCode） 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4] 示例 1: 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出: 3解释: 节点 5 和节点 1 的最近公共祖先是节点 3。 思路：对比上题 BST，其未经优化的解法即是对应一般二叉树的通解。时间复杂度：O(n)空间复杂度：O(n) 实现：1234567891011121314151617181920class Solution { public Tree ...

以树的遍历为载体，查找节点的公共祖先 // 题目链接-来源：力扣（LeetCode） 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5] 示例 1: 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8输出: 6解释: 节点 2 和节点 8 的最近公共祖先是 6。 思路：本质这类题目上还是以树的遍历为载体，进行后续的判定。 空结点立即返回 null。 若当前节点为 p 或者 q，则立即返回当前节点。 对于当前节点，我们检查左右子树的返回值，若均不为空，证明一个节点在左侧，另一个在右侧，于是返回当前节点。 若左右子树有一个不空，则返回这个子树的返回值。解释：这个返回值可以是 p 或者 q ...

字符串转换整数，处理大数越界问题 // 题目链接-来源：力扣（LeetCode） 写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。 当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。 该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。 在任何情况下，若函数不能进行有效的转换时，请返回 0。 说明： 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。 示例 1: 输入: “42”输出: 4 ...

用双向动态规划，避免连续的动态规划被中断 // 题目链接-来源：力扣（LeetCode） 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。 示例: 输入: [1,2,3,4,5]输出: [120,60,40,30,24] 思路：由于不能用除法（实际上，给出的数组元素中会出现 0，如果我们使用除法的话也需要考虑很多额外判断），我们考虑用动态规划实现，避免每次暴力计算乘积。动态规划的阻碍在于，每次计算乘积 B[i] 的时候我们需要忽略 A[i]，将其视为 1 作积，相当于一段连乘被中断于 A[i] 处。但我们注意到， A[0] 到 A[i - 1] 仍然是连乘，我们记 f(0,i - 1) 为 A[0] 到 A[i - 1] 的连乘，则有f(0, i - 1) = f(0, i - 2) * A[i - 1] 。同理，对于 A[i] 右侧元素，有f(i + 1, n - ...

用位运算模拟全加器的实现 // 题目链接-来源：力扣（LeetCode） 写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。 示例: 输入: a = 1, b = 1输出: 2 思路：禁用四则运算实现加法，则我们不用另辟蹊径，可以直接回归计算机的本质，利用位运算实现一个全加器。全加器的实现需要按位进行，为了方便计算进位，我们可以从最低位开始。每一轮循环，我们需要 3 个参数，当前位的「加数」 ba、「被加数」bb，以及前一位的「进位」Cin。利用这些参数，我们需要生成 当前位的和 bit，以及当前位的进位 Cout，同时将 bit 累加到结果 res 当中。我们可以用一个辅助参数 digit 记录当前所在的位，初始为 1，每一轮左移，用其分别与 a、b 作「与」运算，即可获得当前位的 ba、bb。当前位的和 bit 可以通过 ba、bb、Cin 作「异或」运算获得。由于我们的 bit 每次都在不同的位上，所以累加操作可以通过与 res 直接进行 「或」运算实现。进位 Cout 的计算也不难，我们需要 b ...

利用条件运算的短路性质中止递归 // 题目链接-来源：力扣（LeetCode） 求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 示例输入: n = 3输出: 6 1： 思路：首先不能使用循环语句的话，无法通过迭代操作计算；乘除法也封死了我们套公式的捷径。考虑递归，但递归需要终止条件，但我们无法使用条件语句，似乎到这里也堵死了。考虑条件运算的性质，有一条「短路」特性：当 与运算符「&&」的左表达式结果为 false，则右侧的表达式不会被执行；同理，当 或运算符「||」的左表达式结果为 true，则右侧表达式同样不会被执行。于是我们只要想办法将递归的终止条件放在 条件运算符 的左侧，而递归语句放在右侧，当终止条件不满足时，递归语句被执行；满足终止条件时，条件运算会自动跳出，跳过递归语句，执行初始化语句。条件运算符可以选用「||」，则左侧放置 「递归终止条件」；也可以选用「&&」，则左侧放置「递归终止条件的否定」。 时间复杂度：O(n)空间复杂度：O(n ...

动态规划解决无序数组的最大差值 // 题目链接-来源：力扣（LeetCode） 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？ 示例 1: 输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 思路：记动态规划的状态 f(i) 为第 i 天可以获得的利润，则必有 f(0) = 0 （第 0 天只能买，没有卖出）。 同时 f(i) = p[i] - min(p[0] : p[i - 1])其中 min(p[0] : p[i - 1]) 我们不需要每次都计算，直接简化成一个 min 变量来记录更新即可。 时间复杂度：O(n)空间复杂度：O(1) 实现：12345678910class Solution { public int maxProfit(int[] pr ...

动态规划逆推「约瑟夫环」问题 // 题目链接-来源：力扣（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 { ...