cjh的博客

优化点主要在找到二元变量相互的影响规则，然后用双指针来处理，此时复杂度是 n（找二元变量影响规则的原因：双指针在每次循环中只移动某个指针，而移动左指针或者右指针需要基于影响规则来确定）1、三元变量转二元变量：nums[i] + nums[j] + nums[k] = 0 ==> num[j] + num[k] = -num[i]2、遍历数组，将每个数指定为 num[i]，再使用双指针扫描下标 i 之后的数据，查找是否存在 num[j] + num[k] = -num[i]唯一可能的三元组和为 0。

通过不断的用Mid二分，根据定理二，将整个数组划分成顺序区间和乱序区间，然后利用定理一判断target是否在顺序区间，如果在顺序区间，下次循环就直接取顺序区间，如果不在，那么下次循环就取乱序区间。在这些场景中，使用二分查找的变种来搜索旋转排序数组是非常有效的，因为它可以在O(log n)的时间复杂度内找到目标元素，大大提高了搜索效率。：在数据恢复场景中，可能需要从损坏的数据文件中提取信息，这些文件可能因为某些操作导致数据的顺序被打乱，形成了旋转排序数组。，则返回它的下标，否则返回。按升序排列，数组中的值。

数据库查询：在数据库查询中，可能需要找出某个字段值排名第K的记录，这时也需要找出数组中的第K个最大元素。算法设计：在设计一些需要排序的算法时，如快速排序、堆排序等，找出第K个最大元素可以作为算法的一部分。网络编程：在网络编程中，可能需要找出传输速度排名第K的节点，这时也需要找出数组中的第K个最大元素。机器学习：在机器学习中，可能需要找出预测结果排名第K的模型，这时也需要找出数组中的第K个最大元素。游戏开发：在一些游戏中，可能需要找出得分排名第K的玩家，这时就需要找出数组中的第K个最大元素。

在这些场景中，使用修改的二分查找算法来寻找旋转排序数组中的最小值是非常有效的，因为它可以在O(log n)的时间复杂度内找到目标值，大大提高了搜索效率。若通过不断的用Mid二分，根据定理二，找乱序区间，如果存在乱序区间，下次循环就直接取乱序区间，如果不存在，那么直接取区域最左值。定理三：每次二分，至多存在一个乱序区间，即要么有一个乱序区间，要么没有乱序区间。原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

本问题主要采用自顶向下的方式思考。（自顶向下，往往意味着在向下传递前先进行逻辑处理）递归处理每个位置的可能字符。考虑2点：什么情况可放置左括号、什么情况可存放右括号。用递归解决问题时，通常是以2个角度来构思解决方案：自底向上、或自顶向下。代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且。

2 和 3 可以形成一组候选，2 + 2 + 3 = 7。注意 2 可以使用多次。本问题主要采用自顶向下的方式思考。（自顶向下，往往意味着在向下传递前先进行逻辑处理）用递归解决问题时，通常是以2个角度来构思解决方案：自底向上、或自顶向下。如果至少一个数字的被选数量不同，则两种组合是不同的。7 也是一个候选， 7 = 7。，并以列表形式返回。中可以使数字和为目标数。对于给定的输入，保证和为。

本问题主要采用自顶向下的方式思考。（自顶向下，往往意味着在向下传递前先进行逻辑处理）给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。用递归解决问题时，通常是以2个角度来构思解决方案：自底向上、或自顶向下。的字符串，返回所有它能表示的字母组合。

幂集中，每个子集里都保持着下标递增的顺序。每次递归，index表示当前子集里最大的下标+1。本问题主要采用自顶向下的方式思考。（自顶向下，往往意味着在向下传递前先进行逻辑处理）用递归解决问题时，通常是以2个角度来构思解决方案：自底向上、或自顶向下。返回该数组所有可能的子集（幂集）。

给定一个不含重复数字的数组 ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1：输入：nums = [1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2：输入：nums = [0,1]输出：[[0,1],[1,0]]示例 3：输入：nums = [1]输出：[[1]] 提示：用递归解决问题时，通常是以2个角度来构思解决方案：自底向上、或自顶向下本问题主要采用自顶向下的方式思考。（自顶向下，往往意

额外空间）展开这棵树吗？你可以使用原地算法（

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

社交网络：在社交网络中，我们可能需要找到最受欢迎的K个话题、最活跃的K个用户等。数据分析：在数据分析中，我们经常需要找到数据集中的第K小的元素。例如，在金融分析中，可能需要找到某个股票价格的历史数据中的第K低的值。在这种情况下，找到第K小的元素可以帮助我们快速定位到满足条件的记录。在这种情况下，找到第K小的元素可以帮助我们快速确定玩家的排名。在这种情况下，找到第K小的元素可以帮助我们快速定位到重要的特征。实时系统：在某些实时系统中，我们需要快速找到第K小的元素。小的值，你将如何优化算法？

二叉搜索树：对于每个节点，都满足其左子树节点小于当前节点，其右子树节点大于当前节点。故我们遍历每个节点时，要把其左子树节点先遍历到。类似于左 中 右的中序遍历方式。根节点的值是 5 ，但是右子节点的值是 4。，判断其是否是一个有效的二叉搜索树。给你一个二叉树的根节点。

二分偏左位置的数字作为根节点。左边的数据递归作为左子树，右边的数据递归作为右子树。二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。排列，请你将其转换为一棵。

二叉树的层序遍历

3.求以当前节点为根节点，二叉树的直径：可以转换成求当前节点左子树深度、和右子树深度，再将左右子树深度进行求和，此时左右子树深度加和 表示 左子树最长分支叶子节点 -》到 右子树最长分支叶子节点的距离。3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。这条路径可能经过也可能不经过根节点。是指树中任意两个节点之间最长路径的。1.二叉树的直径通常出现在叶子节点之间。给你一棵二叉树的根节点，返回该树的。由它们之间边数表示。

为简化代码：我们递归函数中，考虑判断当前对称的2个节点是否相等，而不是判断这2个节点对称的子节点是否相等。你可以运用递归和迭代两种方法解决这个问题吗？给你一个二叉树的根节点。， 检查它是否轴对称。

翻转二叉树，即将二叉树中的每个节点的左右子树互换，这个操作在特定的算法和应用场景中有用。，翻转这棵二叉树，并返回其根节点。给你一棵二叉树的根节点。

对每个节点都进行左右子树的深度搜索，有2个递归终止条件：①当前节点为null；②当前节点为叶子节点，此时要保存最大深度。是指从根节点到最远叶子节点的最长路径上的节点数。

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。在实际应用中，两两交换链表中节点的操作通常是链表排序算法的一部分，而排序算法的选择则取决于具体的应用场景和性能要求。两两交换(交换start、end)其实就是涉及三条指针的调整：p1->start->end->两两交换链表中的节点，即对链表进行排序操作。指针2：start->end 要调整为 start->指针1：p1->start 要调整为 p1->end。指针3：end-> 要调整为 end->start。

则将其所在行和列的所有元素都设为。的矩阵，如果一个元素为。

1.求两个位置之间的元素和。可以转换成 两个位置前缀和之间的差值。2.A+B=k，可以转换成计算 B-k=A。子数组是数组中元素的连续非空序列。

在历史数据分析或项目管理中，如果将时间点或事件表示为数组，并且希望将所有零值（即无效或无关的事件）移动到末尾，可以使用移动零的方法。：对于需要对数组进行特定操作的场景，例如重新排序或统计非零元素的数量，可以先使用移动零的方法来预处理数组。：在某些操作系统或数据库管理系统中，可能需要将一组连续的内存块中的所有零元素移动到一端，以优化内存的使用。然后再最后补齐固定值。：在进行数据处理或数据清洗时，可能需要将数组中的零元素移动到特定位置，比如数组末尾。移动到数组的末尾，同时保持非零元素的相对顺序。

注：如何判断某元素是否为所在分段开头位置：判断该元素-1的数是否存在于哈希表，若不存在，则该元素是所在分段开头位置。：在某些操作系统或数据库管理系统中，可能需要找到一组连续的空闲内存块来满足特定的需求。：在基因测序或蛋白质结构分析中，可能会用到最长连续的DNA序列或氨基酸序列。，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。遍历数组，只要遇到该元素是所在分段的开头位置，则遍历该段的长度。：在某些类型的游戏中，可能需要生成或分析一系列的连续事件或状态。若该元素不是所在分段的开头位置，则忽略。

此时可以用摩尔投票算法（由摩尔在1981年提出，该算法的主要目标是在无序且候选人数不固定的情况下，有效地找出出现次数超过总数量一半的元素。这种算法的时间复杂度为O(n)，空间复杂度为O(1)，其中n是数组的大小。例如，在文本文件中，出现频率最高的单词或字符可以被编码为一个指针，指向该单词或字符在文件中的一个位置，大大减少了存储空间的需求。例如，如果某个查询返回的结果集中，某一列的值出现次数最多，那么数据库可以利用这一信息，只返回该列的值，而不是整个结果集，从而提高查询效率。，返回其中的多数元素。

例如，可以将具有相同字母的单词分组，然后从每个组中选择一个单词作为密码的一部分。例如，可以将具有相同字母的单词分组，然后让学生找出每组中的其他单词。例如，当用户输入“teh”时，系统可以将其与“the”、“then”等单词分组，从而提供正确的建议。例如，我们可以将具有相同字母的单词分组，以便在创建标题、元描述和URL时使用这些关键词。例如，在分析关键词时，可以将具有相同字母的单词分组，从而减少重复计算。②集合间元素的差异性：不同集合的元素，其字母种类不同、或某种字母的个数不同。给你一个字符串数组，请你将。

此时可以用摩尔投票算法（由摩尔在1981年提出，该算法的主要目标是在无序且候选人数不固定的情况下，有效地找出出现次数超过总数量一半的元素。这种算法的时间复杂度为O(n)，空间复杂度为O(1)，其中n是数组的大小。例如，在文本文件中，出现频率最高的单词或字符可以被编码为一个指针，指向该单词或字符在文件中的一个位置，大大减少了存储空间的需求。例如，如果某个查询返回的结果集中，某一列的值出现次数最多，那么数据库可以利用这一信息，只返回该列的值，而不是整个结果集，从而提高查询效率。，返回其中的多数元素。

而本题，只有一个数出现一次，其余数均出现2次，所以整个数组全部异或后，出现2次的数会被相冲为0，最终只剩下只出现一次的数。，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。异或运算：是一种二进制运算，会将两数的同位数据做对比，相同为0，不同为1；要求是：数组的重复数据基于某个规则，可以相冲。线性时间复杂度，查找一批数据中的特殊数。故2个相同的数，异或后，值为0。

若 i>=1,j>=1，dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + nums[i][j];（即第i行j列的方格，可以从上面走下来，或者从左边走下来）若 当前是首行，dp[0][j] = dp[0][j - 1] + nums[0][j];若 当前是首列，dp[i][0] = dp[i - 1][0] + nums[i][0];表示从[0][0]开始，首行只有横向走这一种方法可达；由第2点的状态转移方程可知，本状态可由2个方向的状态转移而来：左、上。

若 i>=1,j>=1，dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + nums[i][j];（即第i行j列的方格，可以从上面走下来，或者从左边走下来）若 当前是首行，dp[0][j] = dp[0][j - 1] + nums[0][j];若 当前是首列，dp[i][0] = dp[i - 1][0] + nums[i][0];表示从[0][0]开始，首行只有横向走这一种方法可达；由第2点的状态转移方程可知，本状态可由2个方向的状态转移而来：左、上。

若 i>=1,j>=1，dp[i][j] = dp[i-1][j] + dp[i][j-1];（即第i行j列的方格，可以从上面走下来，或者从左边走下来）表示从[0][0]开始，首行只有横向走这一种方法可达；由第2点的状态转移方程可知，本状态可由2个方向的状态转移而来：左、上。若 当前是首行，dp[0][j] = 1;（首行的方格只有一种办法可达，即横向的走）若 当前是首列，dp[i][0] = 1;（首列的方格只有一种办法可达，即纵向的走）下标的含义：i，j表示走到第i行第j列方格 的可达路径数量。

B[j - 1]，dp[i][j] = max(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1 （若A串第i个字符、B串第j个字符 不相等，此时① dp[i][j - 1]表示在i位置后面插入字符；② dp[i - 1][j]表示把第i位置上的字符删除；③ dp[i - 1][j - 1]表示把第i位置上的字符替换为B串第j位置的字符）若 A[i - 1] == B[j - 1]，dp[i][j] = dp[i - 1][j - 1];

若 A[i - 1] == B[j - 1]，dp[i][j] = dp[i - 1][j - 1] + 1;= B[j]，dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) （若A串第i个字符、B串第j个字符 不相等，则当前2串的最长公共子序列 = max(A串不含i字符、B串含j字符, A串含i字符、B串不含j字符）下标的含义：i，j表示截止到A串的第i字符，及截止到B串的第j字符，两串的最长公共子序列。horse -> rorse (将 'h' 替换为 'r')

②状态间具备动态规划的三个特性（参考该文完成分析：dp–139. 单词拆分 https://blog.csdn.net/fujuacm/article/details/135408092）dp数组，初始化 dp[0][0] = 1、dp[0][1] = 1，表示当数组没有元素时，乘积默认为1，后续状态的乘积不受dp[0]影响。dp[i][0]，表示截止到第i个元素，数组中乘积最大的非空连续子数组。dp[i][1]，表示截止到第i个元素，数组中乘积最小的非空连续子数组。子数组 [2,3] 有最大乘积 6。

②状态间具备动态规划的三个特性（参考该文完成分析：dp–139. 单词拆分 https://blog.csdn.net/fujuacm/article/details/135408092）①基于问题定义出状态：（参考该文完成分析：dp–139. 单词拆分 https://blog.csdn.net/fujuacm/article/details/135408092）dp数组，初始化为1，表示截止到自己，最长递增子序列长度为1，即子序列中只包括自己。，找到其中最长严格递增子序列的长度。

①基于问题定义出状态：问题是“求截止到最后一个字母所组成的字符串，是否可由字典拼接而成”。则状态就可以定义为“截止到某个字母所组成的字符串，是否可由字典拼接而成”。故该问题也可以用动态规划，虽然题目只求截止到最后一个字母，字典中出现的单词是否能拼接出该字母及前面所组成的字符串 s。1、dp[i] 表示截止到第 i 个字符，所组成的字符串，是否可由字典拼接而成。3、迭代处理截止到的每个字符所组成的字符串，判断字符串是否可由字典拼接而成。不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

①基于问题能定义出状态：问题是“凑成总金额所需的 最少的硬币个数”，而状态就可以定义为“每个金额所需的 最少的硬币个数”。4、dp[amount] 表示凑齐 amount 所需的最少硬币数，若值为无穷大，意味着不可凑齐 返回-1，否则返回 dp[amount]1、将凑齐每个金额对应的最少硬币数初始化为无穷大，意味着未计算出凑齐每个金额所需最少的硬币数，简化dp代码的编写。3、明确i元在本次无法凑齐的2个原因，并记录凑齐i元的最少硬币数。2、动态规划凑齐1~amount，各需要的最少硬币数。

1、定义出状态：可使用问题即答案的方式，借助问题定义状态，比如问题是“一夜之内能够偷窃到的最高金额。一个专业的小偷，计划偷窃沿街的房屋。要求1、在推导后面阶段的状态的时候，我们只关心前面某阶段的状态值，不关心这个状态是怎么一步一步推导出来的。本状态最优解 = Math.max(上一状态最优解, 上上状态最优解 + 本房屋的价值)思考：由2.最优子结构的分析已知，某状态最优解只由上状态最优解、上上状态最优解推导出来。本状态最优解 = Math.max(上一状态最优解, 上上状态最优解 + 本房屋的价值)

2.2、每层除了首、尾，本层j位置的值 = 上层j-1位置的值 + 上层j位置的值。2、每层除了首、尾，本层j位置的值 = 上层j-1位置的值 + 上层j位置的值。2.1、每层的首、尾 2 个位置，直接设置为 1。1、每层的首、尾 2 个位置，直接设置为 1。生成「杨辉三角」的前 numRows。给定一个非负整数 numRows。2、处理指定层数(i层)的数据。1、循环生成杨辉三角的层数。3、将本层结果存入杨辉三角。

动态规划对状态的定义，通常可以先考虑从问题中得到答案。把问题所问的东西 设计为每个状态所代表的值。如问“有多少种不同的方法可以爬到楼顶”，则把状态设置为不同的台阶，状态的值代表有n种方法到达该状态。台阶1为初始状态，即台阶1可达路径数 dp[1]=1台阶2可以从台阶1跳过来，也可以是初始状态，则台阶2可达路径数 dp[2]=2台阶3可以从台阶2、或台阶1跳过来，即台阶3可达路径数 dp[3] = dp[1] + dp[2]