小桥流水78

这个屌丝很懒，什么也没留下！

热门标签

leetcode刷的一些杂题_长度为n的数组,我们要使其分为3组非空子数组,且这3组非空子数组的元素和相等,

作者：小桥流水78 | 2024-06-28 12:20:29

踩

长度为n的数组,我们要使其分为3组非空子数组,且这3组非空子数组的元素和相等,

总结

1：用s.charAt()比较字符是否等于或者不等于某个字符的时候，要用单引号，双引号这个错误就太low了

s.charAt(i) != ' '
1

二维数组排序

  Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
1
2
3
4
5

list转数组

  return merged.toArray(new int[merged.size()][]);
1

Arrays.sort实现降序排序

注意：如果需要改变默认的排列方式，不能使用基本类型（int，char等）定义变量，而应该用对应的类

优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加。对垒中的元素达到默认的大小之后，再压入元素就会进行判断，如果满足压入条件，就会弹出队首元素

实际上是一个堆（不指定Comparator时默认为最小堆），通过传入自定义的Comparator函数可以实现大顶堆。

如果使用默认的小根堆，那么队列中维护的就是比堆顶更大的元素，如果要插入的数比堆顶大，那么用这个数替换堆顶，同时把堆顶弹出，然后优先队列会重新调整这个小根堆，如果要插入的数比堆顶小，那么这个数不能插入队列中

下面这样定义的时候传入比较器，那么我们的优先对垒就是一个大顶堆

 PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) ->b - a);
1

如果使用大根堆，那么队列中维护的就是比堆顶更小的元素，如果要插入的数比堆顶小，那么用这个数替换堆顶，同时把堆顶弹出，然后优先队列会重新调整这个大根堆，如果要插入的数比堆顶大小，那么这个数不能插入队列中

1 9. 回文数

就是这个数把最高位当做个位，第二高位当做百位，酱紫，求出来的数应该等于原来的数

class Solution {
    public boolean isPalindrome(int x) {
       int sum=0; int k=1;
       int temp=x;
       int count=0;
        Stack<Integer>stack=new Stack();
        while(x!=0)
        {
            int a=x%10;
            x=x/10;
            stack.push(a);                
        }
        while(!stack.empty())
        {
            int p=stack.pop();
            sum=p*k+sum;
            k=k*10;
        }
        System.out.println(sum);
        if(temp<0) sum=-sum;
        return sum==temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public boolean isPalindrome(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }
}


作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/palindrome-number/solution/hui-wen-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

2 11. 盛最多水的容器

暴力超时

class Solution {
    public int maxArea(int[] height) {
         int max=0;
          for(int i=0;i<height.length;i++)
          {
              for(int j=0;j<height.length;j++)
              {
                  max=Math.max(max,Math.min(height[i],height[j])*Math.abs(i-j));
              }
          }
          return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4 165. 比较版本号

7 453. 最小操作次数使数组元素相等

给定一个长度为 n 的非空整数数组，每次操作将会使 n - 1 个元素增加 1。找出让数组所有元素相等的最小操作次数。

解题：对原数组进行排序，每次将最小的元素加到和最大的元素相等，那么每一次加完之后，最小的元素都是nums[0],而最大的元素从最后一个元素依次往前移(因为倒数第二个元素加完之后肯定是大于大数第一个元素的)，直到nums[1]

class Solution {
    public int minMoves(int[] nums) {
       int move=0;
       Arrays.sort(nums);
       int min=nums[0];
       for(int i=nums.length-1;i>=1;i--){
          move+=nums[i]-nums[0];       
       } 
       return move; 
    }
}
1
2
3
4
5
6
7
8
9
10
11

在这里插入图片描述

思路2 ：动态规划
把大问题拆分成小问题，每次把2个数移动成相同的

C++ 动态规化

在这里插入图片描述

数组

1 27. 移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

解题思路，前后双指针，左指针指向等于val的数，右指针指向不等于val的数，两者交换，然后后移左指针，前移右指针，直到右指针小于左指针

class Solution {
    public int removeElement(int[] nums, int val) {
       int i=0;int j=nums.length-1;
       while(i<=j){
           while(i<=j&&nums[j]==val){
               j--;
           }
           
           while(i<=j&&nums[i]!=val){
               i++;
           }
           if(i<=j){             
               nums[i]=nums[j];
               i++;
               j--;
           }                        
       }
       return j+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

在这里插入图片描述

从后往前覆盖

class Solution {
    public int removeElement(int[] nums, int val) {
       int left=0;
        for(int right=0;right<nums.length;right++){
            if(nums[right]!=val)
               nums[left++]=nums[right];
        }
        return left;
    }
}
1
2
3
4
5
6
7
8
9
10

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2 66. 加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

我的解题思路

class Solution {
    public int[] plusOne(int[] digits) {
       int carry=0;
       int n=digits.length;
       int num[]=new int[n+1];
      
       for(int i=n-1;i>=0;i--){
           int temp=digits[i]+carry;
           if(i==n-1)
               temp=temp+1;
           carry=temp/10;
           digits[i]=temp%10;
           num[i+1]=temp%10;
       }
       if(carry==1){
           num[0]=1;
       }
       return carry==1?num:digits;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

只要+1求余数，余数不等于0，说明没有进位，直接返回。如果余数等于0，说明有进位，遍历前一个数字，加1再求余数，以此循环。如果for循环都遍历完了，说明最高位也有进位，则重新建立一个数组，初始化为0，将第一位设置为1就可以了，因为，99、999之类的数字加一为100、1000

class Solution {
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] = digits[i] % 10;
            if (digits[i] != 0) return digits;
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

作者：yhhzw
链接：https://leetcode-cn.com/problems/plus-one/solution/java-shu-xue-jie-ti-by-yhhzw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3 26. 删除有序数组中的重复项

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成

输入：nums = [1,1,2]
输出：2, nums = [1,2]

双指针，i指向前面没有重复元素的位置，j向后遍历，把非重复元素前移

class Solution {
    public int removeDuplicates(int[] nums) {
        int i=0;int j=1;
        while(j<nums.length){
            while(j<nums.length&&nums[j]==nums[i]){
                j++;
            }
            if(j<nums.length){
              nums[i+1]=nums[j];
              i++;
            }           
        }
        return i+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在这里插入图片描述
真的是优雅啊啊啊

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for(int j=1;j<nums.length;j++){
            if(nums[i] != nums[j]){
                nums[++i] = nums[j];
            }
        }
        return ++i;
    }
}
1
2
3
4
5
6
7
8
9
10
11

4 56. 合并区间

在这里插入图片描述

解题思路：先排序，然后遍历比较当前区间的左右的值和已经放入list中的左右的值的大小的关系，先比较左区间，再比较右区间

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });
        List<int[]> merged = new ArrayList<int[]>();
        for (int i = 0; i < intervals.length; ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {
                merged.add(new int[]{L, R});
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);
            }
        }
        return merged.toArray(new int[merged.size()][]);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

5 870. 优势洗牌 (田忌赛马问题)

给定两个大小相等的数组 A 和 B，A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

返回 A 的任意排列，使其相对于 B 的优势最大化。

示例 1：

输入：A = [2,7,11,15], B = [1,10,4,11]
输出：[2,11,7,15]

示例 2：

输入：A = [12,24,8,32], B = [13,25,32,11]
输出：[24,32,8,12]

解题思路，类似田忌赛马，如果田忌的最快的马比齐威王最快的马快，就直接干掉齐威王的马
如果田忌的最快的马没有齐威王的最快的马快，就用田忌最弱的马消耗掉齐威王的最快的马。

参考：604，贪心算法解优势洗牌-田忌赛马问题

class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        Arrays.sort(nums1); 
        int len=nums2.length;
        PriorityQueue<int[]>queue=new PriorityQueue<>((a,b)->b[0]-a[0]);
        for(int i=0;i<len;i++){
            queue.add(new int[]{nums2[i],i});//建立大根堆
        }
        int res[]=new int[len];
        int left=0;int right=len-1;
        while(!queue.isEmpty()){
           int arr[]=queue.poll();
           int val=arr[0];
           int index=arr[1]; 
           res[index]=nums1[right]>val?nums1[right--]:nums1[left++];
        }
        return res;            
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

用最大堆是为了让最大的数在堆最上面。然后需要记录每一个数的原来的索引
PriorityQueue默认是最小堆，所以需要重写比较器

6 414. 第三大的数

给你一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。

示例 1：

输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。

示例 2：

输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。

示例 3：

输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

参考：Java：三变量表示第一二三大数，一次遍历，更新三变量

class Solution {
    public int thirdMax(int[] nums) {
        int n=nums.length;
        if(n==1) return nums[0];
        if(n==2) return Math.max(nums[0],nums[1]);
        long max1= Long .MIN_VALUE;
        long  max2=Long.MIN_VALUE;
        long  max3=Long.MIN_VALUE;
        for(int i=0;i<n;i++){
            if(nums[i]==max1||nums[i]==max2) continue;
            if(nums[i]>max1) {
                max3=max2;
                max2=max1;
                max1=nums[i];
            }else if(nums[i]>max2){
                max3=max2;
                max2=nums[i];
            }else if(nums[i]>max3){
                max3=nums[i];
            }
        }
        return max3==Long.MIN_VALUE?(int)max1:(int)max3;//但是如果恰好第3大的就是Integer.MIN_VALUE，就不好处理了，所以，我们取float
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

7 581. 最短无序连续子数组

给你一个整数数组 nums ，你需要找出一个连续子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的最短子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

示例 2：

输入：nums = [1,2,3,4]
输出：0

示例 3：

输入：nums = [1]
输出：0

思路1：排序找相同的左右边界

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int temp[]=nums.clone();
        Arrays.sort(temp);
        int left=0;int right=nums.length-1;
        while(left<=right&&nums[left]==temp[left])left++;//注意有序的时候left会超边界
        while(right>left&&nums[right]==temp[right]) right--;
        return right-left+1;//注意有序的时候left会超边界，right-left=-1,+1=0没毛病
    }
}
1
2
3
4
5
6
7
8
9
10

在这里插入图片描述

注意数组复制的方法，还号可以是 System.arraycopy，Arrays.copyOf

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        //int temp[]=nums.clone();
        //  int temp[]=Arrays.copyOf(nums,nums.length);
        int temp[]=new int[nums.length];
        System.arraycopy(nums, 0, temp, 0, nums.length);
        Arrays.sort(temp);
        int left=0;int right=nums.length-1;
        while(left<=right&&nums[left]==temp[left])left++;//注意有序的时候left会超边界
        while(right>left&&nums[right]==temp[right]) right--;
        return right-left+1;//注意有序的时候left会超边界，right-left=-1,+1=0没毛病
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

在这里插入图片描述

思路2 单调栈找左右边界
解法思路：利用单调栈，从左往右扫一遍找到左边界，再从右往左扫一遍找到右边界，两者相减即可。

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        // 单调栈从前往后遍历一遍可得到左边界
        // 单调栈从后往前遍历一遍可得到右边界
        Deque<Integer> stack = new ArrayDeque<>();
        int left = nums.length;
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i]) {
                left = Math.min(left, stack.pop());
            }
            stack.push(i);
        }

        stack.clear();
        int right = -1;
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                right = Math.max(right, stack.pop());
            }
            stack.push(i);
        }

        return right - left > 0 ? right - left + 1 : 0;
    }
}



作者：tong-zhu
链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/kan-tong-ge-shua-ti-jian-dan-yi-li-jie-d-2ci3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

int findUnsortedSubarray(vector<int>& nums) {
        int n = nums.size();
        int small = nums[n - 1], big = nums[0];
        int l = -1, r = -2;

        for (int i = n - 1; i >= 0; -- i) {
            small = min(small, nums[i]);
            if (nums[i] > small) l = i;
        }

        for (int i = 0; i < n; ++ i) {
            big = max(big, nums[i]);
            if (nums[i] < big) r = i;
        }

        return r - l + 1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

在这里插入图片描述

class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int maxn = Integer.MIN_VALUE, right = -1;
        int minn = Integer.MAX_VALUE, left = -1;
        for (int i = 0; i < n; i++) {
            if (maxn > nums[i]) {
                right = i;
            } else {
                maxn = nums[i];
            }
            if (minn < nums[n - i - 1]) {
                left = n - i - 1;
            } else {
                minn = nums[n - i - 1];
            }
        }
        return right == -1 ? 0 : right - left + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

在这里插入图片描述

8 628. 三个数的最大乘积

给你一个整型数组 nums ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1：

输入：nums = [1,2,3]
输出：6

示例 2：

输入：nums = [1,2,3,4]
输出：24

示例 3：

输入：nums = [-1,-2,-3]
输出：-6

解题思路1 排序，最开始还在想着三数之和那种解法，帧数傻

class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int max=Integer.MIN_VALUE;
        int n=nums.length;
        //取两负一正，或者3正
        if(n==3) return nums[0]*nums[1]*nums[2];
        return Math.max(nums[0]*nums[1]*nums[n-1],nums[n-1]*nums[n-2]*nums[n-3]);
        // for(int i=0;i<n;i++){
        //     if(i>0&&nums[i]==nums[i-1]) continue;
        //     int L=i+1;int R=n-1;
        //     while(L<R){
        //         int temp1=nums[L];
        //         int temp2=nums[R];
        //         if(nums[i]*temp1*temp2>max){
        //             max=nums[i]*temp1*temp2;
        //         }
        //         max=Math.max(max,nums[i]*temp1*temp2);
        //         while(L<R&&nums[++L]==temp1);// L++;
        //         while(L<R&&nums[--R]==temp2); //R--;
        //     }
        // }
      //  return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

在这里插入图片描述

方法二：线性扫描
找到最大的三个数和最小的两个数

class Solution {
    public int maximumProduct(int[] nums) {
        // 最小的和第二小的
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        // 最大的、第二大的和第三大的
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;

        for (int x : nums) {
            if (x < min1) {
                min2 = min1;
                min1 = x;
            } else if (x < min2) {
                min2 = x;
            }

            if (x > max1) {
                max3 = max2;
                max2 = max1;
                max1 = x;
            } else if (x > max2) {
                max3 = max2;
                max2 = x;
            } else if (x > max3) {
                max3 = x;
            }
        }

        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }
}


作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-product-of-three-numbers/solution/san-ge-shu-de-zui-da-cheng-ji-by-leetcod-t9sb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

9 605. 种花问题

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

示例 1：

输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

示例 2：

输入：flowerbed = [1,0,0,0,1], n = 2
输出：false

10 643. 子数组最大平均数 I

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案。

示例 1：

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：

输入：nums = [5], k = 1
输出：5.00000

解题思路1：暴力枚举，超时

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n=nums.length;
        double max=Integer.MIN_VALUE;
        for(int i=0;i<=n-k;i++){
            max=Math.max(max,calAv(nums,i, k));
        }
        return max;
    }
    public double calAv(int arr[],int start,int k){
        double sum=0;
        for(int i=start;i<start+k;i++){
            sum+=arr[i];
        }
        return sum/k;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

在这里插入图片描述

相当于利用队列，每次弹出一个元素，然后压入一个元素，改变sum的大小

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n=nums.length;
        double sum=0.0;
        double avg=0.0;
        for(int i=0;i<k;i++){
            sum+=nums[i];
        }
        avg=sum/k;
        for(int i=1;i<=n-k;i++){
            sum=sum-nums[i-1]+nums[i+k-1];
            avg=Math.max(avg,sum/k);
        }
        return avg;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

记录最大的sum就好啊，为什么每次要计算呢，浪费时间

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n=nums.length;
        double sum=0.0;
        double avg=0.0;
        double max=0.0;
        for(int i=0;i<k;i++){
            sum+=nums[i];
        }
        max=sum;
        for(int i=1;i<=n-k;i++){          
            sum=sum-nums[i-1]+nums[i+k-1];
            max=Math.max(max,sum);
        }
        return max/k;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这个更快，我们以每一个窗口的最后一个元素为标杆啊。。。。。我前面的写法是以每一个窗口的第一个元素为标杆

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int len = nums.length;
        int count = 0;
        for(int i = 0;i < k;i++){
            count += nums[i];
        }
        int sumMax = count;
        for(int j = k;j < len;j++){
            count = count - nums[j-k] + nums[j];
            sumMax = (sumMax > count) ? sumMax : count;
        }

        return 1.0 * sumMax / k;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

11 665. 非递减数列

给你一个长度为 n 的整数数组，请你判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的：对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

示例 1:

输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。

示例 2:

输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

12 674. 最长连续递增序列

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。

连续递增的子序列可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

示例 2：

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int n=nums.length;
        int dp[]=new int[n];
        dp[0]=1;int max=1;
        for(int i=1;i<n;i++){
            dp[i]=nums[i]>nums[i-1]?dp[i-1]+1:1;
            max=Math.max(max,dp[i]);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

双指针

1 58. 最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。单词是指仅由字母组成、不包含任何空格字符的最大子字符串。

解题思路，双指针，右指针从尾遍历，指向单数第一个不为空格的字符，左指针从右指针的前一个开始遍历，指向右指针前面第一个空格，然后right-left就是所求

class Solution {
    public int lengthOfLastWord(String s) {
        int right=s.length()-1;int left=0;
        while(right>=0&&s.charAt(right)==' '){
            right--;
        }
        left=right-1;
        while(left>=0&&s.charAt(left)!=' '){
            left--;
        }
        return right-left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

思路2，直接计数字符个数

class Solution {
    public int lengthOfLastWord(String s) {      
        int count = 0;
        for (int i = s.length() - 1; i >= 0; i--)
        {
            if (s.charAt(i) != ' ') count++;  //检测到字母
            if (s.charAt(i) == ' ' && count != 0) break;  //记完末单词碰到空格就退出，同时解决末单词后面还有空格的情况（"a "）
        }
        return count;
    }   
}
1
2
3
4
5
6
7
8
9
10
11

2 69. x 的平方根

class Solution {
    public int mySqrt(int x) {
       if(x<=1) return x;

        int left=0;int right=x;
        while(left<=right){
            int mid=left+((right-left)>>1);
            if((long)mid*mid>x){//如果x过大，会造成mid*mid溢出
                right=mid-1;
            }
            else if(mid*mid<x){
                left=mid+1;
            }
            else 
              return mid;
        }
        return right;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

链表

1 24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
在这里插入图片描述

思路：从前往后，两两翻转，头指针每次跳两步，当头指针指向的节点为空或者指向的节点的下一个节点为空，则不用翻转

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null)
          return head; 
         ListNode node=head.next.next;        
         ListNode temp= head.next;
         temp.next=head;
         head.next=swapPairs(node);
         return temp;            
    }   
}
1
2
3
4
5
6
7
8
9
10
11

在这里插入图片描述

迭代

class Solution {
    public ListNode swapPairs(ListNode head) {
          if(head==null||head.next==null)
             return head; 
             ListNode newHead=head.next;//暂存新的头结点,新的头结点肯定是第二个节点    
             while(head!=null&&head.next!=null){
                 ListNode node=head.next.next;
                 ListNode node2=head.next;
                 ListNode temp= head.next; 
                 temp.next=head; 
                 if(node==null||node.next==null)
                   head.next=node;
                 else                                  
                    head.next=node.next;                                                       
                 head=node;              
             }                                     
         return newHead;            
    }   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在这里插入图片描述

2 143. 重排链表

3 23. 合并K个升序链表

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0) return null;
         ListNode p=null;
         for(int i=0;i<lists.length;i++){
             p=mergeTwo(p,lists[i]);
         }
        return p;
    }
    public ListNode mergeTwo(ListNode temp1,ListNode temp2){
        if(temp1==null) return temp2;
        if(temp2==null) return temp1;
        ListNode head=temp1.val<=temp2.val?temp1:temp2;
        ListNode temp=head;
        while(temp1!=null&&temp2!=null){
            if(temp1.val<=temp2.val){
                temp.next=temp1;
                temp1=temp1.next;
            }else{
                temp.next=temp2;
                temp2=temp2.next;
            }
            temp=temp.next;
        }
        temp.next=(temp1==null)?temp2:temp1;
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) {
            return lists[l];
        }
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b) {
        if (a == null || b == null) {
            return a != null ? a : b
        }
        ListNode head = new ListNode(0);
        ListNode tail = head, aPtr = a, bPtr = b;
        while (aPtr != null && bPtr != null) {
            if (aPtr.val < bPtr.val) {
                tail.next = aPtr;
                aPtr = aPtr.next;
            } else {
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        return head.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

4 92. 反转链表 II

在这里插入图片描述

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
         int cur=1;
         if(left==1) return subReverse(head,left-1,right);
         ListNode temp=head;
         while(temp!=null){
            if(cur==left-1) {
               temp.next=subReverse(temp.next,cur,right);
               break;
            }else{
             cur++;           
             temp=temp.next;
            }          
        }
        return head;
    }
    public ListNode subReverse(ListNode node,int start,int end){
        if(start==end) return node;       
        ListNode pre=null;
        ListNode temp=node;
        while(start!=end){
            start++;
            ListNode next=temp.next;
            temp.next=pre;
            pre=temp;
            temp=next;
        }
        node.next=temp;//反转的第一个节点指向反转的最后一个节点的下一个节点
        return pre;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

在这里插入图片描述

思路2 创建守卫节点和p，不断改变p.next和g.next
在这里插入图片描述

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // 定义一个dummyHead, 方便处理
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        // 初始化指针
        ListNode g = dummyHead;
        ListNode p = dummyHead.next;

        // 将指针移到相应的位置
        for(int step = 0; step < m - 1; step++) {
            g = g.next; p = p.next;
        }

        // 头插法插入节点
        for (int i = 0; i < n - m; i++) {
            ListNode removed = p.next;
            p.next = p.next.next;

            removed.next = g.next;
            g.next = removed;
        }

        return dummyHead.next;
    }
}


作者：mu-yi-cheng-zhou-2
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/java-shuang-zhi-zhen-tou-cha-fa-by-mu-yi-cheng-zho/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

深度优先搜索

1 200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

在这里插入图片描述

解题思路：一次深搜把一块岛屿的1全部置为0，每深搜一次，岛屿数量加1.

class Solution {
    public int numIslands(char[][] grid) {
  //解题思路，在一次深搜的过程中把所有的能触及到的1都置为0，再从另一个为1的地方开始覆盖
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int count=0;
       for(int i=0;i<grid.length;i++){
           for(int j=0;j<grid[0].length;j++){
               if(grid[i][j]=='1'){
                   count++;
                   dfs(grid,i, j);
               }
           }
       }
       return count; 
    }
    public void dfs(char grid[][],int i,int j){
        if(i<0||i>grid.length-1||j<0||j>grid[0].length-1||grid[i][j]=='0')
           return ;        
        grid[i][j]='0';
        dfs(grid,i+1, j);
        dfs(grid,i-1, j);
        dfs(grid,i, j+1);
        dfs(grid,i, j-1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

在这里插入图片描述

2 47. 全排列 II

在这里插入图片描述

3 463. 岛屿的周长

在这里插入图片描述

解题思路一

在这里插入图片描述

有两点主要注意的地方
1我把遍历过的点设置为2之后，不用再把它还原为1，这样会造成重复计算，因为岛屿的1都是相邻的，我们一次深搜就可以遍历完

2 不用memo数组做记忆化存储，因为不涉及重复计算

class Solution {
    int m;
    int n;
    //Integer memo[][];
    public int islandPerimeter(int[][] grid) {
        m=grid.length;
        n=grid[0].length;
        memo=new Integer[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    return dfs(grid,i,j);
                }
            }
        }
        return 0;
    }
    public int  dfs(int grid[][],int i,int j){
        if(i<0||i>m-1||j<0||j>n-1||grid[i][j]==0)
           return 1;
        if(grid[i][j]==2){
            return 0;//不允许反向回溯
        }
      //  if(memo[i][j]!=null)
         //  return memo[i][j];
        grid[i][j]=2;
        int result= dfs(grid,i+1,j)+dfs(grid,i-1,j)+dfs(grid,i,j+1)+dfs(grid,i,j-1);
       // grid[i][j]=1;
      // return memo[i][j]=result;
       return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

在这里插入图片描述

思路2：广搜应该是个不错的选择，遍历到某个节点就判断这个节点是否与水域相邻，计算边长

思路3 迭代，暴力遍历

class Solution {
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    public int islandPerimeter(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] == 1) {
                    int cnt = 0;
                    for (int k = 0; k < 4; ++k) {
                        int tx = i + dx[k];
                        int ty = j + dy[k];
                        if (tx < 0 || tx >= n || ty < 0 || ty >= m || grid[tx][ty] == 0) {
                            cnt += 1;
                        }
                    }
                    ans += cnt;
                }
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

在这里插入图片描述

思路4：找规律
在这里插入图片描述

只用算右边和下边两个方向的重叠边数，因为我们是从左向右，从上往下遍历的

class Solution {
    public int islandPerimeter(int[][] grid) {
        int row=grid.length,col=grid[0].length;
        int cnt=0,border=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==1){
                    cnt++;
                    if(j<col-1&&grid[i][j+1]==1)border++;
                    if(i<row-1&&grid[i+1][j]==1)border++;
                }
            }
        }
        return 4*cnt-2*border;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

在这里插入图片描述

4 827. 最大人工岛

在这里插入图片描述

解题思路：从每一个0开始搜索，当前0能搜索到的所有的1的最大值加上1（它本身被填海造陆）就是我们的结果了

class Solution {
    int m;
    int n;
    boolean visited[][];
    public int largestIsland(int[][] grid) {
        m=grid.length;
        n=grid[0].length;
        visited=new boolean[m][n];
        int max=0;
        boolean flag=false;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0){
                    flag=true;//表示有0
                    grid[i][j]=1;//不改成1没法dfs，一进去就直接退回来了
                    max=Math.max(max,dfs(grid,i,j)); 
                    recoverVisited() ;//恢复未访问状态                                     
                    grid[i][j]=0;//恢复为0
                }
            }
        }
        return flag==false?m*n:max;//原来grid中可能没有0
    }
    public int dfs(int [][]grid,int i,int j){
        if(i<0||i>m-1||j<0||j>n-1||grid[i][j]==0)
           return 0;
        if(visited[i][j])//访问过
           return 0;
        visited[i][j]=true;
        int result= 1+dfs(grid,i+1,j)+dfs(grid,i-1,j)+dfs(grid,i,j+1)+dfs(grid,i,j-1);      
        return result;
    }
    public void recoverVisited(){
       for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                visited[i][j]=false;
            }
       }
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

超时，逻辑没问题，再加一个记忆化搜索,但是我的每一个dfs表示的是从上一个的某个方向出发经过它的时候，它能接触的岛屿面积的最大数，它实际可以接触到的岛屿数很可能比这个值大，所以直接memo[i][j]=result会出错
在这里插入图片描述

我没想到怎么剪枝，但是看到一个跟我思路一样的老哥的提交通过的代码，修改如下，应该是原来每一次dfs完毕恢复访问状态为false比较耗时吧。

class Solution {
    int m;
    int n;
    public int largestIsland(int[][] grid) {
        m=grid.length;
        n=grid[0].length;      
        int max=0;int timer=3;//记录标志位，用来判断当前坐标元素的
        boolean flag=false;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0){
                    flag=true;//表示有0
                    grid[i][j]=1;
                    max=Math.max(max,dfs(grid,i,j,timer++)); //每一次dfs传入的timer标志位不同，相当于每一次dfs都会改变grid中的元素，被当前0能够搜索到的原来的1会被改成timer
                    //recoverVisited() ;//恢复未访问状态,应该是这耗时了                                   
                    grid[i][j]=0;
                }
            }
        }
        return flag==false?m*n:max;
    }
    public int dfs(int [][]grid,int i,int j,int timer){
        if(i<0||i>m-1||j<0||j>n-1||grid[i][j]==0||grid[i][j]==timer)
           return 0;       
        grid[i][j]=timer;
        int result= 1+dfs(grid,i+1,j,timer)+dfs(grid,i-1,j,timer)+dfs(grid,i,j+1,timer)+dfs(grid,i,j-1,timer);      
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

在这里插入图片描述

5 17. 电话号码的字母组合

在这里插入图片描述

解题思路：每次从digits的每一位数字对应的字母表中求出一个字母进行拼接

class Solution {
    Map<Character,String>map=new HashMap();
    List<String>list=new ArrayList();
    public List<String> letterCombinations(String digits) {
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        if(digits.length()==0)
        return list;
        dfs( digits,"",0);
        return list;
    }
    public void dfs(String digits,String str,int cur){
        if(str.length()==digits.length()){
            list.add(str);
            return;
        }
       // for(int i=cur;i<digits.length();i++){
            String temp=map.get(digits.charAt(cur));
            for(int j=0;j<temp.length();j++){                
                dfs(digits,str+temp.charAt(j),cur+1);
            }
      //  }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

在这里插入图片描述
StringBuilder完胜

class Solution {
    Map<Character,String>map=new HashMap();
    List<String>list=new ArrayList();
    public List<String> letterCombinations(String digits) {
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        if(digits.length()==0)
        return list;
        StringBuilder str=new StringBuilder();
        dfs( digits,str,0);
        return list;
    }
    public void dfs(String digits,StringBuilder str,int cur){
        if(str.length()==digits.length()){
            list.add(str.toString());
            return;
        }
       // for(int i=cur;i<digits.length();i++){
            String temp=map.get(digits.charAt(cur));
            for(int j=0;j<temp.length();j++){                
                str.append(temp.charAt(j));
                dfs(digits,str,cur+1);
                str.delete(str.length()-1,str.length());
            }
      //  }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

在这里插入图片描述

位运算

1 461. 汉明距离

在这里插入图片描述

异或出来的数就是两个数的不同位的1组成的数

class Solution {
    public int hammingDistance(int x, int y) {
          int z=x^y;int count=0;
          while(z>0){              
              if((z&1)==1)
                 count++;
              z=z>>>1;  //这是逻辑右移高位补0，>>是算术右移，高位补1    
          }
          return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int hammingDistance(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s) {
            s &= s - 1;
            ret++;
        }
        return ret;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12

2 190. 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

思路：从后往前依次取出n的二进制位，然后result左移加上取出来的n的二进制位

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int  res=0;
        for(int i=0;i<32;i++){
           res= (res<<1)+(n&1);//n的二进位从后往前取，加到res上就是从前往后加，实现颠倒
           n=n>>1;//n每次右移一位，好让出每一位
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11

在这里插入图片描述

3 67. 二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

输入: a = “11”, b = “1”
输出: “100”

示例 2:

输入: a = “1010”, b = “1011”
输出: “10101”

解题思路，将两个字符串补到相同长度，然后从末尾开始相加，考虑进位，最后反转字符串

class Solution {
    public String addBinary(String a, String b) {
        int len1=a.length();
        int len2=b.length();
        if(len1>len2){
         int mod=len1-len2;
            while(mod>0){
                b="0"+b;
                mod--;
            }
        }
        else if(len1<len2){
           int mod=len2-len1;
            while(mod>0){
               a="0"+a;
               mod--;
            } 
        }
        int carry=0;
        char[]a1=a.toCharArray();
        char[]b1=b.toCharArray();
        String result="";
        for(int i=a1.length-1;i>=0;i--){
            if(a1[i]=='1'&&b1[i]=='1'){
                result+=carry;
                carry=1;
            }else if(a1[i]=='0'&&b1[i]=='0'){
                result+=carry;
                carry=0;
            }else{
                int c=(carry==0)?1:0;
                result+=c;  
               // carry=carry; //carry是0就会变成0，carry是1就还是1             
            }
        }
        if(carry==1)
            result+="1";
        return new StringBuilder(result).reverse().toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

在这里插入图片描述

String改成StringBuilder 2ms，减少String拼接时创建新字符串的花费

class Solution {
    public String addBinary(String a, String b) {
        int len1=a.length();
        int len2=b.length();
        if(len1>len2){
         int mod=len1-len2;
            while(mod>0){
                b="0"+b;
                mod--;
            }
        }
        else if(len1<len2){
           int mod=len2-len1;
            while(mod>0){
               a="0"+a;
               mod--;
            } 
        }
        int carry=0;
        char[]a1=a.toCharArray();
        char[]b1=b.toCharArray();
        StringBuilder result=new StringBuilder();
        for(int i=a1.length-1;i>=0;i--){
            if(a1[i]=='1'&&b1[i]=='1'){
                result.append(carry);
                carry=1;
            }else if(a1[i]=='0'&&b1[i]=='0'){
                result.append(carry);
                carry=0;
            }else{
                int c=(carry==0)?1:0;
                 result.append(c); 
               // carry=carry; //carry是0就会变成0，carry是1就还是1             
            }
        }
        if(carry==1)
           result.append(1);
        return result.reverse().toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

在这里插入图片描述

这个解法真的太优雅了。

class Solution {
    public String addBinary(String nums1, String nums2) {
        StringBuilder ans = new StringBuilder();
		int pos1 = nums1.length() - 1;
		int pos2 = nums2.length() - 1;
		int carry = 0;		
		while(pos1 >= 0 || pos2 >= 0 || carry != 0){			
			int x = (pos1 >= 0 ? nums1.charAt(pos1) - '0' : 0);
			int y = (pos2 >= 0 ? nums2.charAt(pos2) - '0' : 0);
			int result = x + y + carry;
			ans.append(result % 2);
			carry = result / 2;			
			pos1--;
			pos2--;
		}				
		return ans.reverse().toString();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4 371. 两整数之和

给你两个整数 a 和 b ，不使用运算符 + 和 - ，计算并返回两整数之和。

示例 1：

输入：a = 1, b = 2
输出：3

示例 2：

输入：a = 2, b = 3
输出：5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-two-integers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路1
因为整数都是32位的，我们可以在一个32的for循环中搞定，通过右移i位得到该位上的数，然后两数相加考虑进位，再把得到的结果累加到结果中

class Solution {
    public int getSum(int a, int b) {
        int ans = 0;
        // 存储进位
        int carry = 0;
        for (int i = 0; i < 32; i++) {
            // 从低位到高位依次计算
            int x = (a >> i) & 1;
            int y = (b >> i) & 1;
            if (x == 1 && y == 1) {
                // 不管carry是啥，肯定有进位
                ans |= carry << i;
                carry = 1;
            } else if (x == 1 || y == 1) {
                // carry为1则有进位，carry为0则无进位，与现有的carry一致
                ans |= (carry ^ 1) << i;
            } else {
                // 不管carry是啥，肯定没有进位
                ans |= carry << i;
                carry = 0;
            }
        }
        return ans;
    }
}


作者：tong-zhu
链接：https://leetcode-cn.com/problems/sum-of-two-integers/solution/tong-ge-lai-shua-ti-la-yi-ti-liang-jie-m-3uer/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

解题思路2
就是把两数相加拆分成进位部分和非进位部分相加，但是也许不能一次搞定，需要多次迭代或者递归

在这里插入图片描述

class Solution {
    public int getSum(int a, int b) {
        // 011011 011100 011010 010010 000010 100010
        // 000111 000110 001000 010000 100000 000000
        int carry;
        while (b != 0) {
            carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}


作者：tong-zhu
链接：https://leetcode-cn.com/problems/sum-of-two-integers/solution/tong-ge-lai-shua-ti-la-yi-ti-liang-jie-m-3uer/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int getSum(int a, int b) {
      return (b==0)?a:getSum(a^b,(a&b)<<1);
    }
}
1
2
3
4
5

树

1 111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

思路：递归，有左子树和右子树的最小深度决定，需要考虑左右子树为空为不为空的情况

class Solution {
    public int minDepth(TreeNode root) {   
          if(root==null)
          return 0;
          if(root.left==null&&root.right==null)
          return 1;
          if(root.left==null)
           return 1+minDepth(root.right);
          if(root.right==null)
           return 1+minDepth(root.left);
         return 1+Math.min(minDepth(root.left),minDepth(root.right));        
    }          
}
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        //这道题递归条件里分为三种情况
        //1.左孩子和有孩子都为空的情况，说明到达了叶子节点，直接返回1即可
        if(root.left == null && root.right == null) return 1;
        //2.如果左孩子和由孩子其中一个为空，那么需要返回比较大的那个孩子的深度        
        int m1 = minDepth(root.left);
        int m2 = minDepth(root.right);
        //这里其中一个节点为空，说明m1和m2有一个必然为0，所以可以返回m1 + m2 + 1;
        if(root.left == null || root.right == null) return m1 + m2 + 1;
        
        //3.最后一种情况，也就是左右孩子都不为空，返回最小深度+1即可
        return Math.min(m1,m2) + 1; 
    }
}


作者：reals
链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/li-jie-zhe-dao-ti-de-jie-shu-tiao-jian-by-user7208/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        int m1 = minDepth(root.left);
        int m2 = minDepth(root.right);
        //1.如果左孩子和右孩子有为空的情况，直接返回m1+m2+1
        //2.如果都不为空，返回较小深度+1
        return root.left == null || root.right == null ? m1 + m2 + 1 : Math.min(m1,m2) + 1;
    }
}

1
2
3
4
5
6
7
8
9
10
11

剪枝，瞬间效率提升

class Solution {
    private int min=Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        if(root==null)
            return 0;
        helper(root,1);
        return min;
    }

    public void helper(TreeNode root,int level){
        if(root==null||(root.left==null&&root.right==null)){
            min=Math.min(min,level);
        }
        if(level<min){
            if(root.left!=null)
                helper(root.left,level+1);
            if(root.right!=null)
                helper(root.right,level+1);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

访问到每个节点时如果当前深度已经大于等于最小值就直接返回了

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        helper(root, 1);
        return min;
    }
    int min = Integer.MAX_VALUE;
    public void helper(TreeNode root, int deep) {
        if (root == null) return;
        if (deep >= min) return;
        if (root.left == null && root.right == null) min = Math.min(min, deep);
        helper(root.left, deep + 1);
        helper(root.right, deep + 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

思路二，层序遍历

2 100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
         if(p==null&&q==null)
            return true;
        if(p==null||q==null)
          return false;
        if(p.val!=q.val)
          return false;
        return isSameTree( p.left,q.left)&&isSameTree( p.right,q.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11

简化.

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {         
        if(p==null||q==null)
          return p==q;
        if(p.val!=q.val)
          return false;
        return isSameTree( p.left,q.left)&&isSameTree( p.right,q.right);
    }
}
1
2
3
4
5
6
7
8
9

思路2：层序遍历

快速幂

1 50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
在这里插入图片描述

暴力超时解法

class Solution {
    public double myPow(double x, int n) {
        if(n==0)
          return 1;
        int m=n;
        if(n<0) {
            n=-n;
        }
        double sum=1;
        for(int i=1;i<=n;i++){
          sum*=x;
        }
        return m>0?sum:1.0/sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

方法一：快速幂 + 递归

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0) {
            if (N % 2 == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N /= 2;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

为什么一定是2次幂呢，3次幂行不行？我试了一下，是可以的

class Solution {
    public double myPow(double x, int n) {
       if(n==0) return 1;
       return n>0?helper(x,  n):1.0/helper(x,  -n);     
    }
    public double helper(double x, int n){
      if(n==0) return 1;
      if(n%3==0){
       double y=  helper(x,n/3);
       return y*y*y;
    }
    else if(n%3==1){
        double y= helper(x,n/3);
        return y*y*y*x;
    }   
     else{
        double y= helper(x,n/3);
        return y*y*y*x*x;
     }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

在这里插入图片描述

排序

1 75. 颜色分类

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

示例 3：

输入：nums = [0]
输出：[0]

示例 4：

输入：nums = [1]
输出：[1]

解题思路1 ：插入排序

class Solution {
    public void sortColors(int[] nums) {
        for(int i=1;i<nums.length;i++){
            int curIndex=i-1;
            int temp=nums[i];
            while(curIndex>=0&&temp<nums[curIndex]){
               nums[curIndex+1]=nums[curIndex];
               curIndex--;
            }
            nums[curIndex+1]=temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2 215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

解题思路1：暴力排序

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        Arrays.sort(nums);
        return nums[len - k];
    }
}
1
2
3
4
5
6
7

解题思路2：堆排序

建立一个大小为k的小顶堆，堆顶就是第k大的元素
参考：Java 排序 + 小顶堆实现

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //前K个元素原地建小顶堆
        buildHeap(nums, k);
        //遍历剩下元素，比堆顶小，跳过；比堆顶大，交换后重新堆化
        for (int i = k; i < nums.length; i++) {
            if (nums[i] < nums[0]) continue;
            swap(nums, i, 0);
            heapify(nums, k, 0);
        }
        //K个元素的小顶堆的堆顶即是第K大元素
        return nums[0];
    }

    /**
        * 建堆函数
        * 从倒数第一个非叶子节点开始堆化，倒数第一个非叶子节点下标为 K/2-1
        */
    public void buildHeap(int[] a, int k) {
        for (int i = k/2 - 1; i >= 0; i--) {
            heapify(a, k, i);
        }
    }

    /**
        * 堆化函数
        * 父节点下标i，左右子节点的下标分别为 2*i+1 和 2*i+2
        */
    public void heapify(int[] a, int k, int i) {
        //临时变量 minPos 用于存储最小值的下标，先假设父节点最小
        int minPos = i;
        while (true) {
            //和左子节点比较
            if (i*2+1 < k && a[i*2+1] < a[i]) minPos = i*2+1;
            //和右子节点比较
            if (i*2+2 < k && a[i*2+2] < a[minPos]) minPos = i*2+2;
            //如果minPos没有发生变化，说明父节点已经是最小了，直接跳出
            if (minPos == i) break;
            //否则交换
            swap(a, i, minPos);
            //父节点下标进行更新，继续堆化
            i = minPos;
        }
    }

    public void swap(int[] a, int n, int m) {
        int tmp = a[n];
        a[n] = a[m];
        a[m] = tmp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

解题思路3：优先队列

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        // 使用一个含有 k 个元素的最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
        for (int i = 0; i < k; i++) {
            minHeap.add(nums[i]);
        }
        for (int i = k; i < len; i++) {
            // 看一眼，不拿出，因为有可能没有必要替换
            Integer topEle = minHeap.peek();
            // 只要当前遍历的元素比堆顶元素大，堆顶弹出，遍历的元素进去
            if (nums[i] > topEle) {
                minHeap.poll();
                minHeap.offer(nums[i]);
            }
        }
        return minHeap.peek();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

字符串

1 394. 字符串解码

在这里插入图片描述

class Solution {
    public String decodeString(String s) {
        Stack<StringBuilder> stringStack = new Stack();
        Stack<Integer> countStack = new Stack();
        StringBuilder currentString = new StringBuilder();
        int count = 0;
        //遇到数字，就计数需要重复的次数
        //遇到'[',把当前count压入数字栈，当前字符串压入字符串栈
        //遇到字符，就拼接字符串
        //遇到']',弹出一个数字和字符进行拼接
        
        for (char c: s.toCharArray()){
            if (c == '['){
                stringStack.push(currentString);
                countStack.push(count);
                currentString = new StringBuilder();
                count = 0;
            }else if ( c == ']'){
                count = countStack.pop();
                StringBuilder temp = stringStack.pop();
                while (count > 0){
                    temp.append(currentString);
                    count--;
                }
                currentString = temp;
            }else if (Character.isDigit(c)){
                count = count * 10 + c - '0';//避免出现多位整数，12这种一个一个地检测               
            }else {
                currentString.append(c);
            }
        }
        return currentString.toString();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/765964