©2020-2024 ioDraw All rights reserved,
Privacy Policy
1.分发饼干
得排序一下。
class Solution { public int findContentChildren(int[] g, int[] s) { int
count1=0;//用来记录满足了几个人 int count2=s.length;//记录一下，我们的饼干还剩多少
Arrays.sort(g);//这里得排序一下 Arrays.sort(s); for(int i=0;i<s.length;i++){ for(int
j=0;j<g.length;j++) if(s[i]>=g[j]&&g[j]!=0&&count2>0){ count1++; g[j]=0;
count2--; break;//这里得break一下，因为里面这个饼干找到了主人 } } return count1; } }
2.摆动序列
这个序列里，差值一正一负的。
class Solution { //只需要让当前差值与上一个差值，符号不一样即可。 public int wiggleMaxLength(int[]
nums) { if (nums.length <= 1) { return nums.length; } //当前差值 int curDiff = 0;
//上一个差值 int preDiff = 0; int count = 1; for (int i = 1; i < nums.length; i++) {
//得到当前差值 curDiff = nums[i] - nums[i - 1]; //所有的差值，可以看成一个新的数组。如果i这个位置满足，那就
count++;如果不满足那就下一个i+1 if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 &&
preDiff >= 0)) { count++; preDiff = curDiff; } } return count; } }
3.最大子序和（一组数连续相邻和的最大值）
累加的结果为负数，直接让count等于0。重新开始累加。
从-2出发的，为什么不从1那里重新出发，然后加呢？
其实从1那里，count已经<0了，已经从1那里从头开始了。然后1和-3的和小于0。
因为4之前的结果累加是负数。
class Solution { //思路:遇到负数，一定要重头开始count //我的卡壳：我认为，卡壳的时候得回到区间起始的地方的下一位。得两层for
public int maxSubArray(int[] nums) { if (nums.length == 1){ return nums[0]; }
int sum = Integer.MIN_VALUE;//让sum取最小值先。 int count =
0;//记录增长的数量，当增长降到0以下的时候。就是最大和 for (int i = 0; i < nums.length; i++){ count +=
nums[i]; sum = Math.max(sum, count); // 取区间累计的最大值（相当于不断确定最大子序终止位置） if (count <=
0){ count = 0; //确保了重新开始的地方，如果不从这重新开始，前面的负数累积和，可能会拖累整体的结果。 } } return sum; } }
4.买卖股票的最佳时机
思路：只需要把相邻两天的利润做成一张表。只收集正利润即可。
class Solution { //看看差值最大呗。但是这个差值可以累计。
//先挑一天，最大差值的那一天，算上这个差值。然后再从这一天继续出发。找它之后最大的差值。再相加 public int maxProfit(int[]
prices) { int[] profit=new int [prices.length-1]; for(int
i=0;i<prices.length-1;i++){ profit[i]=prices[i+1]-prices[i]; } int sum=0;
for(int i=0;i<profit.length;i++){ if(profit[i]>0){ sum+=profit[i]; } } return
sum; } }
5.跳跃问题
思路：在能跳的范围内，看看跳的最远能不能超过最后一位的下标。
class Solution { public boolean canJump(int[] nums) { if(nums.length==1){
return true; } int len=0;//能跳多远。 //在能跳范围内，更新最大的能跳范围 for(int i=0;i<=len;i++){
len=Math.max(len,i+nums[i]);//求出来，活动范围。 if(len>=nums.length-1){ return true; }
} return false; }
注意这里，for的上限，是能跳的范围。这个能跳的范围会逐步更新。
6.跳跃问题二
如果第一步的覆盖范围，走到了尽头，还没有到终点，那就开始走第二步，判断第二步的覆盖范围，是否包括终点。
思路：走当前的层。当走到当前层最后一个地方，还是没能到终点，就到跳到下一层。
走当前层的时候，每走一步都会更新下一层最远到的地方，走到当前层的最后一个地方，下一层要走的，也就更新完毕了。
class Solution { public int jump(int[] nums) { if (nums == null || nums.length
== 0 || nums.length == 1) { return 0; } int count=0;//当前步数。 int
curDistance=0;//站在起点能走的最远的。第一层 int
maxDistance=0;//走完第一层，最大的就会更新。然后走第二层。count++。如果走第二层时，maxDisrance刷新了，>=终点下标。
for(int i=0;i<nums.length;i++){
maxDistance=Math.max(maxDistance,i+nums[i]);//max，是这层走完，下层要走的。
if(maxDistance>=nums.length -1){ count++; return count; } if(i==curDistance){
curDistance=maxDistance;//进入下个区域 count++; } } return count; } }
7.k次取反后最大数组和
情况分好，一步步做就行。
class Solution { //排序一下，找到正负分割的地方，如果有0，记录0的位置。 //情况1，负数的个数》=k，从前到后全部反转。
//情况2，负数的个数《k,取反的次数会多余，2.1：如果剩余次数是2的倍数，不用管。2.2如果或剩余次数对2取余为1，那么，如果有0，全部作用于0；如果没有0，比较正负分割的那两个数的下标的值。看看哪个小，让哪个变成负数。
//情况3，如果没有负数，就看看k对二取余的情况。 public int largestSumAfterKNegations(int[] nums, int
k) { int fu=0;//负数的个数 Boolean flag=false;//看看是否有0这个位。 Arrays.sort(nums);
for(int i=0;i<nums.length;i++){ if(nums[i]==0){ flag=true; } if(nums[i]<0){
fu++; } } if(fu>=k){ for(int i=0;i<k;i++){ nums[i]=-nums[i]; } }else
if(fu>0&&fu<k){ int work=fu; for(int i=0;i<work;i++){ nums[i]=-nums[i]; } int
a=(k-work)%2; if(a==0){ return sum(nums); }else{ if(flag){ return sum(nums);
}else{ if(fu<nums.length){//存在正数 if(nums[fu-1]>=nums[fu]){ nums[fu]=-nums[fu];
return sum(nums); }else{ nums[fu-1]=-nums[fu-1]; return sum(nums); }
}else{//不存在整数 nums[fu-1]=-nums[fu-1]; return sum(nums); } } } }else if(fu==0){
int a=k%2; if(a==0){ return sum(nums); }else{//对k取余为1时。 if(flag){ return
sum(nums); }else{ nums[0]=-nums[0]; return sum(nums); } } } return sum(nums); }
int sum(int[] nums){ int s=0; for(int num:nums){ s+=num; } return s; } }
8.加油站（不好理解）
C++的暴力解法，挨个走一遍。
class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>&
cost) { for (int i = 0; i < cost.size(); i++) { int rest = gas[i] - cost[i]; //
记录剩余油量 int index = (i + 1) % cost.size(); while (rest > 0 && index != i) { //
模拟以i为起点行驶一圈 rest += gas[index] - cost[index]; index = (index + 1) %
cost.size(); } // 如果以i为起点跑一圈，剩余油量>=0，返回该起始位置 if (rest >= 0 && index == i)
return i; } return -1; } };
一个for循环的优化。
// 思路，cursum来记录从开始点出发，剩余的油量。 //当前油量如果小于0了，那么就让下一站作为起始点curSum =
0;。如果走剩下几站，油箱里累加多出来的，能填补前面几站产生的负数，那就说明，能走一圈。 class Solution { public int
canCompleteCircuit(int[] gas, int[] cost) { int curSum=0; int totalSum=0; int
index=0;//用来记录出发的起点 for(int i=0;i<gas.length;i++){ curSum+=gas[i]-cost[i];
totalSum+=gas[i]-cost[i]; if(curSum<0){ curSum=0;
index=(i+1)%gas.length;//i的下一站就是出发点。 } } if(totalSum<0) return
-1;//即便这样，最后走完，也没能填补之前的负数。 return index; } }
9.柠檬水找零
class Solution { public boolean lemonadeChange(int[] bills) { int
count5=0;//记录5美元的数量 int count10=0;//记录10美元的数量 for(int i=0;i<bills.length;i++){
if(bills[i]==5){ count5++; } if(bills[i]==10){ count5--; count10++;
if(count5<0){ return false; } } if(bills[i]==20){
if(count5>=1&&count10>=1){//先找给别人10块的，没10再给5。 count5--; count10--; continue;
}else{ if(count5>=3){//优先找10块。 count5-=3; }else{ return false; } } } } return
true; } }
10.根据身高重建队列
遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。
queue[j] = [hj, kj] 。people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于
hi 的人。
先确定还是k先确定h呢，也就是究竟先按h排序呢，还先按照k排序呢？
思路：先把身高都排好序，然后按身高H的优先级。重新往队列里插入。按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。
那为什么让k当下标插入呢？因为已经让最高的先进去了。后面来的矮的位次就由k决定了。
class Solution { public int[][] reconstructQueue(int[][] people) { //
身高从大到小排（身高相同k小的站前面） Arrays.sort(people, (a, b) -> { if (a[0] == b[0]) return
a[1] - b[1]; return b[0] - a[0]; }); LinkedList<int[]> que = new
LinkedList<>(); //后面按k插入，k就是插入的下标。 for (int[] p : people) {
que.add(p[1],p);//LinkedList这个add方法（本质是链表的插入）。插入，就伴随着后面元素都往后移动一位。 } return
que.toArray(new int[people.length][]); } }
11.分发糖果
刚开始的错误思路：给所有的孩子都一个，挨个遍历相邻，谁大，就再给谁一个。这个思路错误的，如果是1，2，3，这3个孩子最终得到的糖果是，1+2+3=6，而不是5+2。
正确思路：每次比较两个，确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。
遇到两个维度权衡的时候，一定要先确定一个维度，再确定另一个维度。
先从左到右，考虑右边的。确定左孩子大于右孩子的情况一定要从后向前遍历！
如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个。
class Solution { public int candy(int[] ratings) { int len=ratings.length;
int[] a=new int[len];//整个数组记录孩子们的奖励情况 a[0]=1; //先处理右边，从左到右，每俩只看右边。 for(int
i=0;i<len-1;i++){ if(ratings[i+1]>ratings[i]){ a[i+1]=a[i]+1; }else{ a[i+1]=1;
} } //再处理左边，从右到左，每俩只看左边。 for(int i=len-1;i>=1;i--) if(ratings[i-1]>ratings[i]){
if(a[i-1]<a[i]+1)
//反例子，123452，比右边比完的时候，比左面。如果这俩人，左面那个人的糖已经大于右边的那个+1，那就没有必要再赋值。如果小于右边那个+1，就让它等于右边那个+1。
a[i-1]=a[i]+1; } int sum=0; for(int num:a){ sum+=num; } return sum; } }
12.用最少的箭射爆气球。
首先得对这这个气球数组，排序一下。按照第一个元素排序。
13,24，这俩就是可以被连续射爆的，区间有交集。每次判断相邻两个，如果能有交集，就能一起被射爆。
如果没有交集，只能多一发箭，继续判断剩下的相邻。
注意：13，24，56，如果在5.6位，没能一起射爆，那第一箭也影响不到后面的气球，因为已经排序了。
class Solution { //如果有交集，17，26，34算一只箭。每次判断为同一只箭后，将气球的第二元素，改成第一箭的第二元素。 public
int findMinArrowShots(int[][] points) { //o1,o2长度为2的数组，代表气球的区间。
Arrays.sort(points,(o1,o2)->Integer.compare(o1[0],o2[0]));
//从第二位开始判断，第一位肯定要射出一发箭。 int count=1; for(int i=1;i<points.length;i++){
//判断后面那个是否于前面那个有交集,如果后面的第一个元素，大于前面的第二个元素，这俩没有交集。
if(points[i][0]>points[i-1][1]){ count++; }else{
//如果有交集，那就让后面这个气球，的第二个元素，记录一下，这一箭的边界。边界就是前一个的第二个元素。
points[i][1]=Math.min(points[i][1],points[i-1][1]); } } return count; } }
13.移除重叠区间
首先得让区间都按规则排序一下，然后挨个比较。如果重叠，则count+1.
如果没有重叠更新右边界。
下面算法比较右边界的，所以让右边界升序即可。。
class Solution { public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals,(a,b)->{ return a[1]-b[1];//让右边界排，按升序， }); int count=0;
//如果是比较右边界的，让右边界升序。 //找个变量记录一下右边界。如果下一个区间的，左边界，大于记录的右边界，那么它就重叠了。就除掉它。 int
edge=Integer.MIN_VALUE; for(int i=0;i<intervals.length;i++){ //没有重叠，更新右边界
if(edge<=intervals[i][0]){ edge=intervals[i][1]; }else{ count++; } } return
count; } }
14.划分字母区间
class Solution { //思路:比如我们在找a的结尾的时候，不可避免的让别的字母也进来了。比如b，最终要到的右边界在变大。
//右边界在找a的结尾时，不断变大,当我们亲自走到这个这个边界的时候，就说明，这个时候该add了。 public List<Integer>
partitionLabels(String s) { List<Integer> list=new ArrayList<>();
Map<Character,Integer> map=new HashMap<>(); for(int i=0;i<s.length();i++){ char
c=s.charAt(i); map.put(c,i); }//记录每一个字符最后出现的位置。 int max=0;//用max来记录最大范围。 int
len=0; for(int i=0;i<s.length();i++){ len++; char c=s.charAt(i); int
a=map.get(c); if(a>max) max=a;//不断的更新最大的终点，当来到最大的地方的时候，就add进去。 if(i==max){
list.add(len); len=0; continue; } } return list; } }
15.合并区间
合并所有重叠的区间，返回一个不重叠的。先将区间排序一下，如果这俩有交集，新生成一个大区间。
class Solution { public int[][] merge(int[][] intervals) { LinkedList<int[]>
list=new LinkedList<>(); Arrays.sort(intervals,(a,b)->{ if(a[0]==b[0]) return
a[1]-b[1]; return a[0]-b[0]; }); //这里严格排序一下。 list.addLast(intervals[0]);
//考虑重复重叠的问题。不断与栈顶的数组做比较 for(int i=1;i<intervals.length;i++){ int[]
work=list.peekLast(); if(intervals[i][0]<=work[1]){ list.removeLast(); int[]
a=new int[2]; a[0]=work[0]; a[1]=Math.max(work[1],intervals[i][1]);
list.addLast(a); }else{ list.addLast(intervals[i]); } } int[][] result=new
int[list.size()][2]; for(int i=0;i<list.size();i++){ result[i]=list.get(i);
//把结果从list里放进数组。 } return result; } }
16.单调递增的数字
有暴力解法。从后往前，挨个判断是否是最近的递增。
class Solution { public int monotoneIncreasingDigits(int n) { int k=n;
while(true){ if(work(k)){ break; } k--; } return k; } //判断k是否单调递增。 Boolean
work(int k){ List<Integer> list=new ArrayList<>(); while(k!=0){ list.add(k%10);
k=k/10; } for(int i=0;i<list.size()-1;i++){ if(list.get(i)<list.get(i+1)){
return false; } } return true; } }
非暴力解法：在数组上进行修改，找到最左面那个开始大于后面的下标，让它减1。然后这个下标之后的都为9。
class Solution { //找到start位，让它减1，然后后面的全都变成9，就行。 public int
monotoneIncreasingDigits(int n) { String s = String.valueOf(n); char[] chars =
s.toCharArray(); int start9 = s.length(); for (int i = s.length() - 2; i >= 0;
i--) { if (chars[i] > chars[i + 1]) {//找到最左面开始不满足的位，让那个位减1。 chars[i]--; /
start9 = i+1;//9开始的地方。 } //最终让最左面的那个地方停在start。让start位减了1。 } for (int i =
start9; i < s.length(); i++) { chars[i] = '9'; } return
Integer.parseInt(String.valueOf(chars)); } }
17.监控整个二叉树
摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。
此时，大体思路就是从低到上，先给叶子节点父节点放个摄像头，然后隔两个节点放一个摄像头，直至到二叉树头结点。
此时这道题目还有两个难点：
* 二叉树的遍历：用后序，可以从底到上。
* 如何隔两个节点放一个摄像头。
第二个难点：结点有3个情况。
情况1：该结点已经被摄像头覆盖，有覆盖
情况2：这个结点已经有摄像头。
情况3：这个结点没有被摄像头覆盖，没覆盖
那如果访问到空结点，它是什么状态？
空结点，不能是没覆盖，不然它上面一层的叶子结点，就得安摄像头了。所以访问到空结点的时候，返回它是被覆盖的。
// 空节点，该节点有覆盖 if (cur == NULL) return 2;
我们从下往上整。
有4种情况。
1：左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了（从下网上呗）。
// 左右节点都有覆盖 if (left == 2 && right == 2) return 0;
2.左右子至少有一个没有被覆盖。这个时候，这个中间结点就必须得安摄像头了。
if (left == 0 || right == 0) { result++; return 1; }
3.左右孩子至少有一个有摄像头。
那这个左右孩子的父亲就得改成是覆盖的状态了。
4.整个过程处理完了之后，最后对根结点，判断一下。是否被覆盖。
如果没有被覆盖，就给他加一个摄像头。
这种情况是，两个子都是被覆盖的，而不是有一个摄像头。
int minCameraCover(TreeNode* root) { result = 0; if (traversal(root) == 0) {
// root 无覆盖 result++; } return result; } class Solution { int res=0; public
int minCameraCover(TreeNode root) { if(travel(root)==0){ res++; } return res; }
//三种状态，0表示无覆盖，1表示有摄像头，2表示被覆盖。只要子里没被覆盖，就要安摄像头。 int travel(TreeNode root){
if(root==null){ return 2;//避免叶子结点被安摄像头，让叶子结点的儿子，返回2。 } int
left=travel(root.left); int right=travel(root.right);
if(left==2&&right==2){//如果俩都被覆盖了，说明这个结点肯定还没被覆盖到。 return 0; }else
if(left==0||right==0){//如果有一个没覆盖的，就要装一波摄像头。 res++; return 1; }else
{//除了上面两种情况，剩下的都是至少有一个摄像头的。记住上面俩种情况即可 return 2; } } }
18. 盛最多水的容器
找两根线，看这两根线能构成的最大的容器量。
1.用双指针来做，i开始指向最左端，j指向最右端。
2.然后移动 i 或者 j
3.左移或者右移动，容器底部长度都会减1，我们尽量保留比较高的边，移动边小的那一端，
因为保留较高那条边更容易出最大值。
class Solution { //找最后一个大于它的位置，和第一个它小于的位置。 public int maxArea(int[] height) {
int i=0; int j=height.length-1; int maxSpacity=0;
//左移或者右移动，容器底部长度都会减1，我们尽量保留比较高的边，移动边小的那一端，更容易出最大值。 while(j>i) { int
num1=Math.min(height[i],height[j])*(j-i); maxSpacity=Math.max(num1,maxSpacity);
int num2=height[i]; int num3=height[j]; if(num2>num3) { j--; }else{ i++; } }
return maxSpacity; } }