一个专门用来刷leetcode的仓库 以前的leetcode记录已丢失o(╥﹏╥)o
31: 下一个排列 m
32: 最长有效括号 m
35: 搜索插入位置 e
42: 取水 h
45: 跳跃游戏2 m
53: 最大子数组和 m
54: 螺旋矩阵 m
55: 跳跃游戏 m
56: 合并区间 m
59: 螺旋矩阵2 m
62: 不同路径 m
64: 最小路径和 m
69: x的平方根 e
73: 矩阵置0 m
77: 组合 m
82: 删除序列列表中重复节点 m
91: 解码方法 m
96: 不同的二叉搜索树 m
98: 检验二叉搜索树 m
99: 恢复二叉搜索树 m
118: 杨辉三角 e
119: 杨辉三角II e
120: 三角形最短路径 m
122: 买卖股票的最佳时机2 m
123: 买卖股票的最佳时机3 h
136: 只出现一次得数 e
146: LRUCache m
200: 岛屿数量 m
206: 课程表 m
209: 长度最小的子数组 m
210: 课程表2 m
274: H指数 m
318: 最大单词长度乘积 m
460: LFUCache h
605: 种花问题 e
695: 最大的岛屿面积 m
1155: 掷骰子等于目标和的方案数 m
1402 做菜顺序 h
1488: 避免洪水泛滥 m
1726: 同积元组 m
2304: 网络中的最小路径代价 m
2316: 统计无向图中无法互相到达点对数 m
2512: 最优秀的k位同学 m
2530: 执行k次操作后的最大分数 m
2558: 从数量最多的堆中取走礼物 e
2562: 找到数组的串联值 e
2578: 最小和分割 e
2582: 枕头传递 e
2652: 倍数求和 e
2760: 最长奇偶子序列 e
100042:和为目标值的最长子序列的长度 m
100097:合法组数的最小组数 m
100104:使二进制字符变美丽的最小修改数 m
100133:购买水果所需的最小金币数 m
LRU:
159: 库存管理III e
难度:困难
思路:
维护栈中保留一个最近的无法匹配的')'的下标.
- 当pop后为空时,说明将最近的一个')'弹出了,无法匹配,所以压入当前位置,当前位置即最近的无法匹配的')'
- 当pop不为空,说明弹出的肯定不是')',是'(',所以匹配上了,这时候可以计算长度i-peek()
- 起始状态时压入-1模拟最近的无法匹配的下标
二分查找的注意点:
- 当中间有值与之相等时,会搜到,直接返回
- 当中间无值与之相等时,最后会落入仅a,b两项的局面
- 若a,b均非首尾值,则目标值在其之间
- 若a是首值,则目标值可能等于小于a
- 若b是尾部值,则目标值可能大于等于b
- 本来原队列就只有两个数
难度:中等
思路:
- 时间复杂度O(n^2),从后往前规约,第i位到终点需要多少步;
第i位到终点最少需要 Min(nums[i+1],nums[i+2]....nums[i+nums[i]])+1步 - 时间复杂度O(n),贪心算法加动态规划:
难度:中等
思路:
滑动窗口.
难度:中等
思路:
从外到内剥开矩阵,每一次剥记录left,top,right,bottom.然后依次取出上右下左的元素
注意点:
当right=left时,就不取出right的元素
当bottom=top时,就不取出bottom的元素
难度:中等
思路:
逆向思维.不断记录能跳到终点的最小下标位置
只要中间不会中断,可以到0即可.
public boolean canJump(int[] nums) {
//最小下标位置初始化为len-1,即最后一位
int canIdx=nums.length-1;
for (int idx = nums.length-2; idx >=0 ; --idx) {
//如果当前位置能到达,最小下标位置;则最小下标位置更新
if(idx+nums[idx]>= canIdx){
canIdx=idx;
}
//如果当前位置不能到达则继续向左边遍历即可
}
return canIdx==0;
}
难度:中等
思路:
首先要对区间根据左边界排序,这样能够合并的区间必然是连续的.
遍历有序区间同时维护一个区间,若遍历区间与维护区间有重复,则合并,重新确定右边界;
若遍历区间与维护区间不重复,则维护区间加入结果,维护当前遍历区间.
记得遍历结束把最后一个维护区间也加入.
难度:中等
思路:
54题按层模拟的思想依然可行
难度:中等
- f(m,n)=f(m-1,n)+f(m,n-1) 这里使用递归,是会出现重复的计算的.所以要使用"备忘录"将一些已经计算过的进行存储 - 上面方法的变式.逆向思维 - 需要向右m-1步,向下n-1步.共m+n-2步,就是在这m+n-2步中确定向下的n-1步即可(排列组合) 注意要先除小的数难度:中等
回溯. f(m,n)=Math.min(f(m+1,n),f(m,n+1))+grid[m][n]; 难度:简单 x范围是0~2^31-1 本题ac不难.主要是如何ac得更优雅 - 从0开始遍历.i*i=x时返回i,i\*i>x时返回i-1 **当x=2^31-1时,最后i\*i绝对会溢出**考虑用除法 - 当x/i=i时返回i,x/i 73: 矩阵置0难度:中等
思路:第一遍,用两个set记录一下那些行/列有0,第二遍置0
难度:中等
思路:
要深刻体会dfs,
要选择ArrayList,而不是LinkedList,因为经常要使用list的size
难度:中等
思路:
滑动窗口思路可解
难度:中等
思路:
当s.charAt(i)不为0,f(i)+=f(i-1);即在原本的组合上新加上第i位独自组成的码
i-1,i组成的数<26时
- 当s.charAt(i-1)为0时,不变(第i-1位和第i位无法组成一个码)
- 当i-1位不为0时,且i-1位和i位组成的数<=26时,f(i)+=f(i-2)(第i-1位和第i位可以组成一个码)
难度:中等
思路:
以n个节点1~n能组成的二叉搜索树的个数.
f(i,j)+=f(i,j-1)
f(i,j)+=f(i+1,j)
f(i,j)+=f(i,k-1)*f(k+1,j) i<k<j
提高效率:
在f(i,j)算出之前,算出f(i,m),f(m,j);
for(int j=0;j<n;++j){
for(int i=j-1;j>=0;--j){
...
}
}
难度:中等
思路:
新建一个boolean check(TreeNode root,int max,int min);
对于每一个节点的检验,都有上下界.
易错点:左节点只有上界,右节点只有下界. (a的左节点b可能也在c的右边(当a在c右边时),因此左节点也有下界)
难度:中等
思路:
如何检测二叉搜索树中出现了错误.中序遍历
正常的二叉搜索树,左节点<父节点<右节点.那么其中序遍历应该是单调递增的.
因此中序遍历并根据遍历结果,找到那两个点破坏了单调性:两种情况:
- 两个连续点调换: 1 2 3 4 6 8 11 9 13 14 将11和9调换即可
- 两个调换的点中间有其他节点: 1 2 4 6 7 13 9 10 8 15 17 13-9 10-8两个地方破坏了单调性,将第一队的前节点和第二对的后节点调换
最后返回的时候再扩展成为完整的一行
for循环的过程中也不需要记录每一行,记录上一行就可以
正确思路:
状态转移.四个状态buy1,sell1,buy2,sell2;
向后遍历:
buy1=max{buy1,-price[i]}
sell1=max{sell1,buy1+price[i]}
buy2=max{buy2,sell1-price[i]}
sell2=max{sell2,buy2+price[i]}
private class MapNode{
int key;
int value;
MapNode prev;
MapNode next;
public MapNode() {}
public MapNode(int key,int value){
this.key=key;
this.value=value;
}
}
private HashMap<Integer,MapNode> linkedMap;
private MapNode head;
private MapNode tail;
private int capacity;
private int size;
难度:中等
思路:
dp+背包问题(任意选1~k放入被背包中,要求和为定值target,数量为n(全部放),问方案数)
dp[j]是当前和为j的方案数
dp[j]=dp[j-1]+dp[j-2]+...+dp[j-k]/dp[0] (等号右边都是上一个状态的(即筛子数减一时的方案数),所以要逆序遍历,即先更新dp[m],在更新dp[n],m>n)
背包问题:
f(m,n):到m层n下标元素的最小路径和
f(m,n) = min (f(m-1,i)+move_price[grid[m-1][i]][n]) i属于0~wid
public UnionFind(int cap){
pres=new int[cap];
for(int i=0;i<cap;++i){
pres[i]=i;
}
}
public int find(int i){
if(pres[i]==i){
return i;
}
//路径压缩
pres[i]=find(pres[i]);
/*
不压缩
return find(pres[i]);
*/
return pres[i];
}
public void join(int x,int y){
int fx=find(x);
int fy=find(y);
pres[fx]=fy;
}
}
2. 深度优先搜索
<h2 id="2512">2512:最优秀的k位同学 </h2>
难度:中等
思路:
哈希表(计算得分)+堆排(topk问题)
<h2 id="2530">2530:执行k次操作后的最大分数 </h2>
难度:中等
思路:
贪心(每次取最大的)(优先队列实现)
细节:
优先队列的添加优先使用offer(e),add(e)调的还是offer(e)
public boolean add(E e) { return offer(e); }
实现ceil m/n: 即大于或等于m/n的最小整数
对于整数型 m/n,默认是得到小于或等于m/n的最大整数.
public int ceil(m,n){ return (m+n-1)/n; }
<h2 id="2558">2558:从最大的堆中取走礼物 </h2>
难度:简单
思路:
用**优先队列**记录一下最大堆即可,快速存取.
<h2 id="2562">2562:找到数组的串联值 </h2>
难度:简单
思路:
双指针,判断奇偶情况
<h2 id="2578">2578:最小和分割 </h2>
难度:简单
思路:
要重新排列后的两数和最小,那么应该分成位数均匀地两数(即使和的位数也尽量少);本质上是为每一个位的数字赋予基础值(1,10,100...)且每个基础值只能被赋两次,
为两个大的数字赋予同一小的基础值(即 将两个大数字放到较低的位数).
因此将数字排列,并根据排列结果赋予基础值求和.
注意点:
- 得到数字排列时,
long i=1; for(;i<=num;i*=10); i/=10;
这段代码应该注意i溢出的问题,使用long
<h2 id="2582">2582: 枕头传递 </h2>
难度:简单
思路:
一定要先取余数,将前面的重复传递过程略去
<h2 id="2652">2652: 倍数求和</h2>
难度:简单
思路:
容斥原理.f(n,3)+f(n,5)+f(n,7)-f(n,15)-f(n,21)-f(n,35)+f(n,105)
f(n,m):1~n能被m整除的数:是一个等差数列 第一项:m,最后一项m*(n/m),
<h2 id="2760">2760: 最长奇偶子序列 </h2>
难度:简单
思路:
滑动窗口,left和right;
位运算快速判断
<h2 id="100042">100042: 和为目标值的最长子序列的长度</h2>
难度:中等
思路:背包问题
每个值取1/0次,和为定值,最多取多少个值
dp[i][j]:从0~i中取子序列和为j的最长长度
<h2 id="100097">100097: 合法分组的最小组数</h2>
难度:中等
思路:
先遍历一遍,使用HashMap记录每个数出现的次数.
找到最小次数min.
从min+1开始往1遍历i,判断i,i-1能够作为组中人数来分组,如果可以,计算分出的组数.
>这里注意不能用二分法,因为可能不能以数量x,x-1分组,但是可能能以x+m,x+m-1为组数
> 例:有4个1,5个2;
> 不能用3,4,但是能用4,5
<h2 id="100104">100104: 将字符串变美丽的最小修改数</h2>
难度:中等
思路:
贪心
<h2 id="100133">100133: 购买水果所需的最小金币数</h2>
难度:中等
思路:
dp,背包变式
状态转移方程:
dp[i]表示出钱购买第i个水果,并且得到后面的所有水果所需的最小金币数
dp[i] = prices[i] + min(dp[i+1],dp[i+2].......dp[2*i],dp[2*i+1])
<h1>LRU题库</h1>
<h2 id="LRU159">159 库存问题III </h2>
难度:简单
思路:
这是一个经典的TOPk问题,即找出最大/小的k个对象
- 最简易的做法:int[]->IntStream->sorted->limit(k)(取流的前k个数)->toArray()
- 使用堆.java中即使用优先队列(PriorityQueue).用优先队列去维护k个数,而不是n个.
- 快排
>优先队列:继承了队列的性质,
>特殊点:
>普通队列严格FIFO,但是优先队列可以让out有优先级
> 实现:使用堆(堆通常可以认为是完全二叉树的数组表示)