递增子序列
题目：给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
示例:
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
说明:
给定数组的长度不会超过15。
数组中的整数范围是 [-100,100]。
给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
思路：用我做的500+以上题目的经验来说。这个题绝对会卡在超时上。毕竟暴力法还是很容易实现的。我现在的想法就是从头遍历。大于上一个值的往后追加/如果小于上一个值。那么从头开一条路。反正是有个大致的思路，我去实现下试试吧。
超时一点毛病没有。58个测试案例卡在56上我光荣。用事实的教训告诉我们不要暴力破解，还是要讲究方法的。哈哈
其实这个方法在写的过程中一直有隐隐的思路。比如记忆功能啊，甚至dp啊回溯剪枝啊什么的。至于这个去重的话我之前的暴力法的时候是用set把所有的结果集转成字符串记录的，效果杠杠的，当然超时就不说了。但是总体来讲一说到去重set，hash这些还是不可避免的想到。我还是继续去研究下怎么实现吧。
class Solution {
List<Integer> temp = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> findSubsequences(int[] nums) {
dfs(0, Integer.MIN_VALUE, nums);
return ans;
}
//这个last是上一个元素。应该这样比每次都获取list中最后一个元素性能要来的好吧
public void dfs(int cur, int last, int[] nums) {
//当前元素已经没有了，说明这条线到头了。
if (cur == nums.length) {
if (temp.size() >= 2) {
ans.add(new ArrayList<Integer>(temp));
}
return;
}
if (nums[cur] >= last) {
temp.add(nums[cur]);
dfs(cur + 1, nums[cur], nums);
temp.remove(temp.size() - 1);
}
if (nums[cur] != last) {//如果当前元素和上一个元素不相等，那么可以继续往下走。但是等于的话，再走一边就是重复了。
dfs(cur + 1, last, nums);
}
}
}
这个代码是参考题解做的，我觉得自己想不出来了。反正和我第一版本的代码百分之六十逻辑上的相等的。属于都能看懂，就是自己写不出来。就好像我的js代码。反正这个题就是这样的，这个代码我觉得不难，但是巧妙的很，毕竟差不多的思路我就超时了，这个就超过百分百的人了，哎。下一题。
目标和
题目：给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例：
输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
提示：
数组非空，且长度不会超过 20 。
初始的数组的和不会超过 1000 。
保证返回的最终结果能被 32 位整数存下。
思路:这个题思路还是很清楚的。其实简单的想就是每一个元素有+/-两个选择。其实和选/不选是一个性质。感觉可以变种为01背包问题。我是觉得用二维数组所有的可能列出来就可以了。当然了我dp渣也不是一天两天了。我觉得其实用回溯也是可以实现的。每一个元素分两种情况，从第一个开始递归。嘿嘿。甚至跟上一题有点类似。有思路，我去实现下试试。
这个题比我想的还要简单，我直接贴代码：
class Solution {
int temp;
int res = 0;
public int findTargetSumWays(int[] nums, int S) {
temp = S;
dfs(nums, 0, 0);
return res;
}
public void dfs(int[] nums,int cur,int sum){
if(cur == nums.length) {
if(sum == temp) res++;
return;
}
dfs(nums, cur+1, sum+nums[cur]);
dfs(nums, cur+1, sum-nums[cur]);
}
}
感觉题生达到了巅峰，哈哈，最近做的最顺的一道题。当然了这种暴力法性能就不能看了。我仍然觉得这个题是可以用dp来实现的。毕竟动态规划就是记录中间过程的递归。不过具体怎么实现没思路。我打算去看题解了。
(来源于题解)思路：公式推导+一维01背包求方案数。设构成正数的集合为sum(正),构成负数的集合为sum('负')，则有sum(正)-sum('负')=S。 等式两边都加上sum(nums)得：2*sum(正)=S+sum(nums)，当且仅当等式S+sum(nums)为偶数且sum(nums)>=S时，等号成立！于是问题求解就变成先求出sum(正)，再求出数组中哪些元素组合在一起的和为sum(正)的方案数！即剩下的用01背包求方案数即可。
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int len, sum = 0, res = 0;
if (nums == null || (len = nums.length) == 0)
return res;
for (int i = 0; i < len; i++)
sum += nums[i];
if (sum < S || ((sum += S) & 1) == 1) // 若是奇数或者数组元素总和小于S，则无解
return res;
sum >>= 1;
int[] dp = new int[sum + 1];
dp[0] = 1; // 初始状态值：若刚好取到sum，则方案数加1
for (int i = 0; i < len; i++) {
for (int j = sum; j >= nums[i]; j--) // 01背包，一维数组实现，逆序枚举，保证每个元素都被只用一次
dp[j] += dp[j - nums[i]];
}
return dp[sum];
}
}
简单来说感觉看懂dp思路比做这个题本身都难了。哎，这个题解是我觉得比较好理解的一个了。反正我就看看，理解理解就完了，现在我对dp有点绝望了。反正也走不了算法岗，所以简单的会点得了。下一题。
提莫攻击
题目：在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄，他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。现在，给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间，你需要输出艾希的中毒状态总时长。你可以认为提莫在给定的时间点进行攻击，并立即使艾希处于中毒状态。
示例1:
输入: [1,4], 2
输出: 4
原因: 第 1 秒初，提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟，直到第 2 秒末结束。
第 4 秒初，提莫再次攻击艾希，使得艾希获得另外 2 秒中毒时间。
所以最终输出 4 秒。
示例2:
输入: [1,2], 2
输出: 3
原因: 第 1 秒初，提莫开始对艾希进行攻击并使其立即中毒。中毒状态会维持 2 秒钟，直到第 2 秒末结束。
但是第 2 秒初，提莫再次攻击了已经处于中毒状态的艾希。
由于中毒状态不可叠加，提莫在第 2 秒初的这次攻击会在第 3 秒末结束。
所以最终输出 3 。
提示：
你可以假定时间序列数组的总长度不超过 10000。
你可以假定提莫攻击时间序列中的数字和提莫攻击的中毒持续时间都是非负整数，并且不超过 10,000,000。
思路：这个题怎么说呢，可爱的很。当然了，一小部分是因为我年轻的视乎有一段时间很喜欢玩提莫。一大部分原因是因为这个题目比较简单。哈哈。给定的数组是攻击的时间。后面的数值是中毒的时间。这个题比较麻烦的就是中毒重复时间了吧。反正我觉得实现的方法是多种多样的。最最简单的就是创建一个数组用来记录。中毒了值+1.最后统计所有非0的数值的个数。不过这个需要额外空间的。但是这个题没有任何时间空间的限制。当然了，用set也行，中毒时候的秒数扔到set里。利用set的不重复性最后算set的长度、我去实现下试试。
呵，提莫害我！这个题果断的超时了。附上超时代码：
哎，我是觉得思路没问题。我想想这个怎么减少计算吧。
想出了一种不用set每个值，直接计算的方法。附上思路简图：
做是做出来的，通过也通过了，性能也很哇塞。就他妈这个题的测试案例让爷气笑了。时间居然还能从0开始？以为是下标咋的。两个demo都是1开始，我就自动以为是从1开始的了，哎。附上代码：
class Solution {
public int findPoisonedDuration(int[] timeSeries, int duration) {
int sum = 0;
int last = -1;//当前最后一个中毒的秒数
for(int i:timeSeries) {
//如果等于说明也重合了。
sum += last<i?duration:i+duration-1-last;
//最后一个中毒的格子，这个不变
last = i+duration-1;
}
return sum;
}
}
这个题挺简单的。结合我上面的图就不多说什么了。直接下一题。
非重叠矩形中的随机点
题目：给定一个非重叠轴对齐矩形的列表 rects，写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。
提示：
整数点是具有整数坐标的点。
矩形周边上的点包含在矩形覆盖的空间中。
第 i 个矩形 rects [i] = [x1，y1，x2，y2]，其中 [x1，y1] 是左下角的整数坐标，[x2，y2] 是右上角的整数坐标。
每个矩形的长度和宽度不超过 2000。
1 <= rects.length <= 100
pick 以整数坐标数组 [p_x, p_y] 的形式返回一个点。
pick 最多被调用10000次。
示例 1：
输入:
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
输出:
[null,[4,1],[4,1],[3,3]]
示例 2：
输入:
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
输出:
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]
输入语法的说明：
输入是两个列表：调用的子例程及其参数。Solution 的构造函数有一个参数，即矩形数组 rects。pick 没有参数。参数总是用列表包装的，即使没有也是如此。
思路：这个题题目很明确。我觉得所谓的随机就是横纵坐标随机。现在的想法是横纵坐标都有范围。首先第一个random在第几个矩阵。其次random矩阵的横纵坐标。总感觉可能我想的太简单了，我先去试试看看吧。
我上面的想法确实有点问题。落在哪个矩形不应该是一样几率的，因为矩形大小不同。这个题应该是算出所有的可能的点数，随机一个结果，然后去反找这个点：
class Solution {
int[][] rects;
List<Integer> psum = new ArrayList<>();
int tot = 0;
Random rand = new Random();
public Solution(int[][] rects) {
this.rects = rects;
for (int[] x : rects){
tot += (x[2] - x[0] + 1) * (x[3] - x[1] + 1);
psum.add(tot);
}
}
public int[] pick() {
int targ = rand.nextInt(tot);
int lo = 0;
int hi = rects.length - 1;
while (lo != hi) {
int mid = (lo + hi) / 2;
if (targ >= psum.get(mid)) lo = mid + 1;
else hi = mid;
}
int[] x = rects[lo];
int width = x[2] - x[0] + 1;
int height = x[3] - x[1] + 1;
int base = psum.get(lo) - width * height;
return new int[]{x[0] + (targ - base) % width, x[1] + (targ - base) / width};
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(rects);
* int[] param_1 = obj.pick();
*/
我是不太喜欢这个题。难又不难，做又不容易做，哎。下一题。
对角线遍历
题目：给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。
示例:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,4,7,5,3,6,8,9]
思路：这个题我感觉做过类似的，就是过年那段时间刷的，二维数组的旋转，翻转啥的差不多。我感觉技巧也就是看成二维坐标系。横纵坐标的更改吧。我去试试代码。
分两种情况：一种是往上走呢，一种是往下走。比如是d[i][j]。往上走是i-1，j+1. 往下走是i+1.j-1.当然走到边边是要特殊处理的。反正我觉得比较好实现，我去试试。
啧啧，完美的一次过，性能在能接受的范围，起码我思路没错。我先附上代码：
class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
if(matrix==null || matrix.length==0 || matrix[0].length==0) return new int[0];
int m = matrix.length;
int n = matrix[0].length;
int[] res = new int[m*n];
int idx = 0;
int tempM = 0;
int tempN = 0;
int flag = 0;//0是向上走，1是向下走
while(idx<m*n){//元素没填满
res[idx] = matrix[tempM][tempN];
if(flag == 0){//向上走
//只要判断是不是到边上了
if(tempM == 0 || tempN == n-1){
//无法往上走，但是可以往右边走一步然后往下
if(tempM == 0 && tempN !=n-1){
tempN++;
}else{//无法往上走，但是可以往下走一步然后往下
tempM++;
}
flag = 1;//只要到边上就要改变方向
}else{
//每到边上正常往斜上方走。
tempM--;
tempN++;
}
}else{//向下走
//到没到边上
if(tempM == m-1 || tempN == 0){
if(tempN ==0 && tempM != m-1){
tempM++;
}else{
tempN++;
}
flag = 0;
}else{
tempM++;
tempN--;
}
}
idx++;
}
return res;
}
}
这两天做的题太让我有信心了啊，是不是简单的题目都聚在一起了，几乎没有卡顿，都差不多一次过，哈哈。
这个题其实只要分析清楚了，并且把可能遇到的情况都列出来，几乎就没难度。当然了我觉得我这个肯定是写鸡肋了，我去看看性能排行第一的代码：
思路大同小异，实现略有不同，我直接贴上：
class Solution {
int[] res;
int k = 0;
public int[] findDiagonalOrder(int[][] matrix) {
if(matrix.length == 0 || matrix[0].length == 0) return new int[0];
res = new int[matrix.length * matrix[0].length];
if(matrix[0].length == 1) {
for(int i=0; i<matrix.length; i++) {
res[i] = matrix[i][0];
}
return res;
}
if(matrix.length == 1) return matrix[0];
dfs(matrix, 0, 0, true);
return res;
}
private boolean dfs(int[][] matrix, int i, int j, boolean flag) {
if(i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length) return false;
res[k++] = matrix[i][j];
if(i+1 == matrix.length && j+1 == matrix[0].length) return true;
if(flag) {
if(!dfs(matrix, i-1, j+1, flag)) return dfs(matrix, i, j+1, !flag);
} else {
if(!dfs(matrix, i+1, j-1, flag)) return dfs(matrix, i+1, j, !flag);
}
return true;
}
}
下一题了啊。
下一个更大的元素2
题目：给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
注意: 输入数组的长度不会超过 10000。
思路：感觉这个题唯一可能卡住的也就是性能了。这个题单纯的n方遍历肯定是没问题，但是没必要。这个题我暂时的思路肯定是要记录的，但是具体记录什么，怎么记录我先想想。
这里用了栈。毕竟元素之间要么大于，要么小于等于。如果是大于的话，那么当前元素的下一个更大元素直接就知道了。但是如果下一个值小于当前元素，那么存入栈中，继续往下判断。这样能确定栈中的元素肯定是从大到小的。当然了每到一个下一个元素较大的时候要循环一次栈中的元素。看能出几个出几个。大概思路就是这样，代码如下：
class Solution {
public int[] nextGreaterElements(int[] nums) {
int maxIdx = 0;
// 找到最大值的下标
for (int i = 0; i < nums.length; i++)
maxIdx = (nums[maxIdx] > nums[i] ? maxIdx : i);
LinkedList<Integer> stack = new LinkedList<>();
for (int i = nums.length - 1; i >= 0; i--) {
int idx = (i + maxIdx + 1) % nums.length; // 从最大的值开始绕一圈
int idxNum = nums[idx];
while (!stack.isEmpty() && stack.getLast() <= idxNum)
stack.removeLast();
nums[idx] = (stack.isEmpty() ? -1 : stack.getLast());
stack.add(idxNum);
}
return nums;
}
}
本来我是循环了两遍这个数组，不过看了别人的评论所以直接从最大值开始绕圈遍历就好了。这个题只要思路清晰了也不算难。另外也是看了评论才知道这个题暴力解法居然不超时！反正就这样了。
这篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活愉快！
