leetCode进阶算法题+解析（四十一）
打广告：java技术交流群，130031711，欢迎各位萌新大佬踊跃加入！
说两句题外话，我一直很执着的坚持着按照自己的步伐一点点刷题。不过最近受挫挺多，比如之前的辗转算法。还有昨天刷题遇到的什么费马定理，欧拉定理什么的，真的是，别说会了，听都没听过。然后为了解题而看又浪费时间而且不实用。所以昨天痛定思痛，跳过了那道题。也算是打破了自己的计划。
其实我刷算法百分之六十是兴趣。毕竟作为一个码畜来说，真正工作中用到算法是很少的，可能几乎遇不到，而且面试也不是一个很大的加分项。群里之前也聊过看看源码，看看框架，甚至看看底层或者数据库什么的不香么？香吧。但是也会让我在冥思苦想做出一道题后开心的像个二百斤的傻子么？也会让我为做出一道题而自自豪么？也会让我因为问题卡住，但是在学习的过程中感觉到拨开迷雾时通透又放松么？我觉得是不会的。偶尔也会想要玩游戏，想要偷懒看电视，甚至不想打开电脑只想睡觉，但是大多数时候刷题是一个类似于爱好的乐趣了。游戏打通关和题目做出来，乐趣是一样的。只不过攻略游戏是大多数人的爱好，而刷题可能是少部分人的爱好。我只不过恰好是在这少数人里面而已。
但是我也会相应的减少刷题的时间，毕竟要生活，要进步，最脚踏实地方法还是贴近工作的一些学习。而且现在题目偏难，真的有时候一道难题要想一小天，所以一天三道题打底确实太难了。
之所以这里要写出来，一方面是对自己曾经立下的执念和约定的一个交代。另一方面也是心路历程的一个记录。
但是我仍然要说，算法于我，是个爱好。就好像代码于我也是爱好一般。我享受着用外人所为的“鬼画符”搭建出一个作品的过程，也享受着想出，破解一个题目的过程。
我热爱我的职业，就好像热爱轻风阳光和生活一样的热爱。
好了，今天正好是周五！刷题继续吧！
查找和最小的K对数字。
题目：给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。找到和最小的 k 对数字 (u1,v1), (u2,v2) ... (uk,vk)。
示例 1:
输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
示例 2:
输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
示例 3:
输入: nums1 = [1,2], nums2 = [3], k = 3
输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]
思路：这道题怎么说呢，我感觉最暴力的方法就是分别列出两个数组的每个元素的乘积，然后排序，取前k个数对。但是实践起来肯定是好多无用功的。不过这个题应该是可以用比较的方式来实现的。又因为是递增数组，所以倒是也不用挨个算。我去代码试试吧。
反正是实现了，而且性能挺好，第一次提交就超过百分之九十二的人。我先贴代码再一点点记录思路：
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
int n1 = nums1.length;
int n2 = nums2.length;
if(k==0 || n1 == 0 || n2 == 0) return res;
//下标代表nums1的下标，值代表nums2的下标
int[] d = new int[nums1.length];
int n = 0;//记录有几个元素已经用完了
//当到底k个或者没有元素可用退出循环
while(k>0 && n<n1){
int min = Integer.MAX_VALUE;
int min1 = -1;
for(int i = n;i<nums1.length;i++){
//当对应的nums2中的第一个，则只会越来越大， 没必要继续了。系数肯定是递增的关系
if(i > 0 && d[i-1]==0) break;
//因为d[i]代表nums2的下标，所以不可能大于n2.
if(d[i]<n2 && nums1[i]+nums2[d[i]]<min){//和比最小值小
min = nums1[i]+nums2[d[i]];
min1 = i;
}
}
List<Integer> list = new ArrayList<Integer>();
list.add(nums1[min1]);
list.add(nums2[d[min1]]);
res.add(list);
d[min1]++;
//说明这个数跟对面都匹配完了，
if(d[min1]==n2) n++;
k--;
}
return res;
}
}
因为这个题思路比较乱，所以我注释写的挺全的我觉得。思路就是因为nums1是第一个元素。所以我这里是给nums的元素中添加了一个系数。系数就是乘nums2中的哪个数。其实我感觉这里还有一种更好的做法，就是将nums1，nums2中元素较少的元素记录系数。不过因为结果集中第一个是nums1.所以这样做还要做多判断，可能性能好一点点。但是我嫌麻烦就没这么做。
现在的做法是建立了一个数组，下标代表数组1的下标，值代表数组2的下标。每一轮都是一次判断，判断当前最小的和。另外有个剪枝就是如果上一个元素的系数是0那么直接break。因为两个都是递增数组，所以如果系数都是0的话，不可能再出现更下的了，所以可以直接pass。这块的优化我不确定还能不能做的更好了，反正这个性能我已经满意了。我直接去看性能排行第一的代码了。
！！！！一样一样的代码，我手贱重新提交了下，超过百分百了！！哈哈，还看什么性能排行第一的了啊，就这样了，贴个图嘚瑟下直接下一题了。
性能截图
猜数字大小2
#######题目：我们正在玩一个猜数游戏，游戏规则如下：我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。
示例:
n = 10, 我选择了8.
第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。
游戏结束。8 就是我选的数字。
你最终要支付 5 + 7 + 9 = 21 块钱。
给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。
思路：这个题怎么说呢，我看完题第一反应就是二分法。然后用最坏的可能这个数是最大的。然后用的钱数就是确定能赢的钱数。我去试试思路。好吧，事实证明我把这道题想简单了，随便做了个demo，n=12的时候，如果二分法分别是6,9,11.结果是26.但是测试案例的结果是21.所以猜的方式不对。我再去想想。
额，本来以为挺简单的题目最后难得很啊，我先贴代码再讲：
public class Solution {
public int getMoneyAmount(int n) {
int[][] dp = new int[n + 1][n + 1];
for (int len = 2; len <= n; len++) {
for (int start = 1; start <= n - len + 1; start++) {
int minres = Integer.MAX_VALUE;
for (int piv = start + (len - 1) / 2; piv < start + len - 1; piv++) {
int res = piv + Math.max(dp[start][piv - 1], dp[piv + 1][start + len - 1]);
minres = Math.min(res, minres);
}
dp[start][start + len - 1] = minres;
}
}
return dp[1][n];
}
}
这个题目我是看题解才有的思路。
(1)解释dp[1][1]:
dp[1][1]是指只有一个数字1，我们以1作为分割点(猜的数)，赢得游戏所用钱的最小值，一看就知道，dp[1][1]=0。因为我们只能猜1，答案也只能是1，不用花钱
(2)解释dp[1][2]:
dp[1][2]是指只有两个数字1，2
我们先以1作为分割点(猜的数):
- 猜1：
答案是1，花费0元
答案是2，花费1元
必定赢得游戏，最多花费1元
我们再以2作为分割点(猜的数): - 猜2：
答案是1，花费2元
答案是2，花费2元
必定赢得游戏，最多花费2元
综上，只要进入[1,2]这个区间，我们第一次猜1，只要花费1元，必定可以赢得游戏（假如看不懂，再看一次，细细的品）
所以dp[1][2]=1(只要花1元必定赢得游戏，当第一次猜1时)
(3)解释dp[2][3]:
dp[2][3]是指只有两个数字2，3
有一个小问题，为什么不是从1开始呢？(明白的不用看)
比如n=3，我们第一次猜了1，但是答案是2或者3，反正不是1，我们是不是要到[2,3]区间来寻找答案，即求
dp[2][3]
我们先以2作为分割点(猜的数):
- 猜2：
答案是2，花费0元
答案是3，花费2元
必定赢得游戏，最多花费2元
我们再以3作为分割点(猜的数): - 猜3：
答案是2，花费3元
答案是3，花费0元
必定赢得游戏，最多花费3元
综上，只要进入[2,3]这个区间，我们第一次猜2，只要花费2元，必定可以赢得游戏
所以dp[2][3]=2(只要花2元必定赢得游戏，当第一次猜2时)
(4)解释dp[1][3]:
dp[1][3]是指只有三个数字1，2，3
我们先以1作为分割点(猜的数):
- 猜1：
答案是1，花费0元
答案是2或者3，这个时候会进入另一个区间[2,3]，花费1+dp[2][3]元
必定赢得游戏，最多花费max(0,1+dp[2][3])元
我们再以2作为分割点(猜的数): - 猜2：
答案是1，花费2+dp[1][1]=2+0=2元
答案是2，花费0元
答案是3，花费2+dp[3][3]=2+0=2元
必定赢得游戏，最多花费max(0,2+dp[1][1],2+dp[3][3])元
我们最后以3作为分割点(猜的数): - 猜3：
答案是1或者2,花费3+dp[1][2]元
答案是3，花费0元
必定赢得游戏，最多花费max(0,3+dp[1][2])元
综上，只要进入[1][3]这个区间，我们只要花费min( max(0,1+dp[2][3]) , max(0,2+dp[1][1],2+dp[3][3]) , max(0,3+dp[1][2]) )元必定可以赢的游戏
而dp[1][3]也就等于那个min的值。
可以发现，只要找到dp[1][n]即可。
以上就是这个题的思路。 比较墨迹，不过我觉得认真看都能看懂的。这个题用了好长的时间。就不多说了，下一题了。
摆动序列
题目：如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1:
输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。
示例 2:
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:
输入: [1,2,3,4,5,6,7,8,9]
输出: 2
进阶:
你能否用 O(n) 时间复杂度完成此题?
思路：其实我的想法就是遍历。遍历一遍，一个元素不是按顺序来的，要么是后边的比他大了，当然也有可能是前面的比他小了。如果这个数是较小值，那么取小的，如果是较大值，取大的。保证大值和小值的个数是一样的多与的都去了。我暂时的想法就是这样。我去实现试试。
emmmm...在实现的过程中有了新想法。像我上面说的，大值小值持平就行了。所以其实只要顺着判断就行了。代码如下：
class Solution {
public int wiggleMaxLength(int[] nums) {
if(nums.length<2)return nums.length;
int res = 1;
int up = -1;//0是升序，1是降序
for(int i = 1;i<nums.length;i++){
if(nums[i]>nums[i-1] && up != 0){
up = 0;
res++;
}else if(nums[i]<nums[i-1] && up != 1){
up = 1;
res++;
}
}
return res;
}
}
直接2次ac，性能超过百分之百（我感觉这个题比较简单，只要思路清晰就行了。）重点是如果是升序，则下一个计数的必须是降序。所以既要判断数值又要判断当前的升降序。
不过我在做的过程中其实觉得写法应该可以优化一下，但是因为性能已经百分百了所以就不动了，这个题就这样吧。我去看看评论。
看到一个我想象中但是没写出来的想法，之前做的时候就觉得好像我那么处理应该是有更好的做法。我直接贴代码：
class Solution {
public int wiggleMaxLength(int[] nums) {
int n = nums.length;
if (n < 2) {
return n;
}
int up = 1;
int down = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
}
if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
}
这篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利，生活健健康康！！另外最近在做一个dubbox的项目，有经验的小伙伴能不能加个好友探讨探讨？哈哈，java技术交流群招人。群号130031711，欢迎各位萌新大佬踊跃加入！
