2022.05.03

1. 刷题

• leetcode215 数组中第k个最大元素
• 解题思路：利用最大堆，把数据依次放入，再依次取出，取出第k个数就是第k个最大元素

2022.05.04

1. 刷题

• leetcode33 搜索旋转排序数组
• 解题思路：利用二分法的改良，首先，判断中间位置的值是否就是目标值，是就直接返回；其次，判断起始值是否小于中间位置的值，是则前半部分有序，否则后半部分有序；接着，对于有序部分判断目标值是否在此区间，如果在则移动下标将范围缩减至此区间，如果不在则移动下标，将范围改变至另一区间。
• leetcode300 最长上升子序列（有顺序要求，要求原数组中的子数组必须按照角标从大到小）
• 解题思路：利用动态规划，定义状态dp[i]为以nums[i]结尾的最长子序列长度。如何描述转移方程？在nums[i]处，遍历0到i-1的nums的所有值，判断该值nums[j]是否小于nums[i]，小于则nums[i]可以接在nums[j]后，则dp[i]的值就可以等于dp[j]+1，从所有的dp[j]+1中选择一个最大的，就是以该值结尾的最长子序列的长度。最终从dp数组中选出最大值，就是最长上升子序列的长度。
• leetcode56 合并区间
• 解题思路：利用排序+双指针，首先，将所有的一维数组按照数组第一个下标从小到大的顺序进行排列，并将排序后第一个元素放入结果集中；其次，定义两个指针p1和p2，指针p1指向二维数组中的第二个元素，指针p2指向结果集中的第一个元素，如果p1和p2可以进行合并，则合并，合并后p1后移，如果不可以合并，则将p1指针指向的元素放入结果集中并后移p1，同时移动p2指针指向该元素，重复此过程，直至p1指针走到末尾。
• 注意：由于给定的是二维数组，结果是存放在列表中，所以用for循环的指针代替p1，用list.get(list.size() - 1)代替p2。
• leetcode53 最大子序和（有顺序要求，要求原数组中的子数组必须连续）
• 解题思路：利用动态规划，定义状态dp[i]为以nums[i]结尾的最大子序和。如何描述转移方程？如果dp[i-1]大于0，则以nums[i]为结尾的最大子序和dp[i]就是dp[i-1]+nums[i]，否则dp[i]就是nums[i]。
• leetcode162 寻找峰值
• 解题思路：利用二分法的改良，首先，选中数组中间的数nums[m]，假设nums[m-1] > nums[m]，则说明m之前一定存在峰值，此时将区间缩小为左半部分，假设nums[m] < nums[m+1]，则说明m之后一定存在峰值，此时将区间缩小到右半部分。通过区间的不断缩小，最终区间内只有一个值，这个值比其左边和右边的数都大，所以就是峰值。
• 小技巧：二分法通常用于排好序的数组，但这并不绝对，例如本题由于可以根据中间点的值的某些判断，来缩小区间，所以可以考虑使用二分法。

2. 总结

2.1 数组在什么时候使用动态规划

答：数组中求某一种特殊值的时候，最应该考虑动态规划，比如上述的最长上升子序列长度、最大子序和。

2.2 数组中的动态规划如何定义状态

答：在数组中定义的状态一般是为 ===》 以第i个元素为结尾的…

2022.05.05

• leetcode128 最长连续序列（顺序无要求）
• 解题思路：首先，建立一个Set集合对数组中的元素去重。其次，遍历整个Set集合，对于每一个元素i，看是否Set集合中有i-1存在，如果有则略过，没有则对该元素i遍历寻找以i为起点的连续子序列的长度，并进行比较来存放结果。当遍历完数组即可得到最终结果。
• 思考：本题也想过使用动态规划，定义dp[i]以nums[i]为结尾的最长连续子序列的长度，但是由于dp[i]有可能和dp[i+1]有关，即不满足无后效性，所以无法使用动态规划，只能放弃。
• leetcode739 每日温度
• 解题思路：利用单调栈，即此栈中从栈底到栈顶的元素顺序是依次递减的（按照自定义的规则判断大小）。首先，定义一个栈来存放数组中元素的下标，对数组中的元素进行遍历，如果当前元素的值大于栈顶中的下标对应的数组元素的值，则将栈顶中的下标弹出，并将本元素下标和栈顶下标做差，放入结果数组中该下标的位置，重复此操作，直至当前元素小于栈顶中的下标指向的值或栈空，再将当前元素下标入栈。当数组遍历结束，将栈中依然存在的下标在结果集中置0即可得到最终结果。
• leetcode209 长度最小的子数组
• 解题思路：利用滑动窗口（双指针），定义两个指针start和end同时指向数组中第一个元素，end指针开始移动，同时不断更新窗口内的元素和，直至元素和大于给定值时，end停止移动，更新此时最小数组长度；同时start开始移动，不更新窗口内的元素和和最小数组长度，直至元素和小于给定值时，start停止移动，end指针恢复移动。重复此过程，直至end指针移动到数组结尾，即可得到结果。
• 注意：本题中数组中的元素都是正数，有了这个前提才能使用滑动窗口算法，因为窗口扩大时窗口内元素之和必然增大，窗口缩小时窗口内元素之和必然减小。
• leetcode152 乘积最大子序列（有顺序要求，要求原数组中的子数组必须连续）
• 解题思路：本题实际上是leetcode53最大子序和的进阶版，进阶难点在于负数会导致当前位置的最优解不能仅仅依靠前一个位置的最优解进行求解，需要进行更多的考量。假如当前的元素是一个负数，我们希望以该元素的前一个元素为结尾的元素乘积尽可能地小，这样乘上该负数之后积就会最大。假如当前的元素是一个正数，我们希望以该元素的前一个元素为结尾的元素乘积尽可能地大，这样乘上正数之后积就会最大。因此，我们需要在维护一个以当前元素为结尾的最大连续子数组乘积的动态数组之外，还需要维护一个以当前元素为结尾的最小连续子数组乘积的动态数组。

2022.05.06

• leetcode560 和为K的子数组
• 解题思路：利用前缀和，所谓前缀和就是建立一个新的数组sum，sum[i]代表num[0]+nums[1]+…+nums[i]。本题的题目等价于，在sum中寻找有多少种sum[end]-sum[start]=k的情况。如果直接在此开始枚举，时间复杂度为O(N*N)，于是我们继续进行优化。其实，我们也并不关注究竟是哪两个前缀和满足上面的这个条件，我们只关注等于k的前缀和之差出现的次数，就知道有多少个子数组求和等于k，因此，我们可以建立一个Map集合，让key为当前的前缀和，value为当前的前缀和在遍历nums数组时出现的次数。我们定义一个count来计算符合条件的子数组总数，定义一个k_sum来记录当前的前缀和，并从头开始遍历nums数组，每遍历一个数，就累加一次k_sum并判断当前的Map集合中是否存在key=k_sum-k，如果存在，取出该key的value值将其累加到count中，如果不存在，则count不变化。当nums数组遍历完成，也就得到了最终的结果。
• leetcode55 跳跃游戏
• 解题思路：利用动态规划，状态dp[i]为是否能够跳到nums[i]。则状态方程为要向nums[i] = true，则在dp[0]到dp[i]之间至少有s满足一个dp[s] = true且nums[s] + s >= nums[i]。

2022.05.15

• leetcode15 三数之和
• 解题方法：利用排序+双指针。
• 解题步骤：① 定义result集合存储结果，数组排序 ② 利用指针i遍历整个数组从下标0到length - 3的元素，每次遍历定义两个指针left和right。如果nums[left] + nums[right] = -nums[i]则满足条件，新建集合存储当前数据并加入结果集result中，右移left至下一个不等值并左移right至下一个不等值，去寻找下一组数据；如果nums[left] + nums[right] < -nums[i]，右移left至下一个不等值；如果nums[left] + nums[right] > -nums[i]，左移right至下一个不等值。当left >= right，则结束本次循环，进入下一次遍历。③ 每次遍历都要移动指针i到至下一个不等值，避免重复。