用哈希表优化子串的遍历与跳转，实现剪枝。 // 3. 题目链接-来源：力扣（LeetCode） （中等） 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s = “abcabcbb”输出: 3解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 ####思路：这是一个「滑动窗口」问题。基本思路就是用一个开头下标start和一个结尾下标i来标记当前处理的区域。接下来考虑怎么判断重复问题，最直观的想法就是查找，最快的查找就是哈希表（复杂度O(1)）。那么就考虑维护一个哈希表isRepeated，存储当前子串中的字符，每次i扫过新的字符就查表，如果存在key则说明重复，不存在则将其加入；然后start前进，直到找到重复字符所在的下标，前进的同时逐个删去经过的字符在表中的记录。进一步优化：考虑最坏情况，可能存在”abcdefgg”这样的字符串，start指向’a’，当i扫过第2个’g’的时候，哈希表查到冲突，但是start需要依次扫过abcdefg才能确定冲突的位置，效率太低。优化方案：用HashMap而不是HashSet， ...

链表基本操作 // 2. 题目链接-来源：力扣（LeetCode） （中等） 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例 1： 输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807. ####思路：就是实现一个简单的整数加法，比一些常见的数字处理题要简单，简单之处在于： 链表形式输出，不用考虑溢出问题。 输入是逆序，输出也是逆序，与正常手工计算的顺序相同，很直观。 细节：留意一下进位即可，用一个变量carry记录是否进位 时间复杂度：O(n)空间复杂度：O(n) 实现：12345678910111213141516171819202122232425262728293031323334class Solution { public ListNode addTwoNumb ...

用哈希表降低查找的复杂度。 // 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 ...