【leetcode】剑指 Offer学习计划（java版本含注释）（下）

前言
第十六天（排序）
- 剑指 Offer 45. 把数组排成最小的数（中等）
- 剑指 Offer 61. 扑克牌中的顺子（简单）
第十七天（排序）
- 剑指 Offer 40. 最小的k个数（简单）
第十八天（搜索与回溯算法）
- 剑指 Offer 55 - I. 二叉树的深度（简单）
- 剑指 Offer 55 - II. 平衡二叉树（简单）*
第十九天（搜索与回溯算法）
- 剑指 Offer 64. 求1+2+…+n（中等）
- 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先（简单）
- 剑指 Offer 68 - II. 二叉树的最近公共祖先（简单）*
第二十天（分治算法）
- 剑指 Offer 07. 重建二叉树（中等）*
- 第二十一天（位运算）
- 剑指 Offer 15. 二进制中1的个数（简单）
- 剑指 Offer 65. 不用加减乘除做加法（简单）*
第二十三天（数学）
- 剑指 Offer 39. 数组中出现次数超过一半的数字（简单）
- 剑指 Offer 66. 构建乘积数组（中等）*
第二十五天
- 剑指 Offer 29. 顺时针打印矩阵（简单）

前言

该链接的学习计划如下：
剑指 Offer学习计划

上一版本的博文链接如下：
【leetcode】剑指 Offer学习计划（java版本含注释）（上）

此贴两年前写的，一直在草稿箱里，今天释放出来，后续有时间完善下！（= - =）

第十六天（排序）

剑指 Offer 45. 把数组排成最小的数（中等）

题目：

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: “102”

示例 2:

输入: [3,30,34,5,9]
输出: “3033459”

提示:

0 < nums.length <= 100

说明:

输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

思路：

关于这部分的具体核心逻辑代码
可参考如下链接：

剑指 Offer 45. 把数组排成最小的数（自定义排序，清晰图解）

class Solution {
    public String minNumber(int[] nums) {
        //新建一个字符数组
        String []s=new String[nums.length];
        //遍历每个数组到字符数组中，具体转类型，通过String.valueOf(nums[i]);
        for(int i=0;i<nums.length;i++){
            s[i]=String.valueOf(nums[i]);
        }
        //通过快排将其排好顺序，运用大小的转换
        quicksort(s,0,s.length-1);

        //通过StringBuilder() 添加数组的，之后输出其toString类型
        StringBuilder res = new StringBuilder();
        for(int i=0;i<s.length;i++){
            res.append(s[i]);
        }
        
        return res.toString();

    }
    public void quicksort(String [] s,int l,int r){
        if(l>=r)return ;
        
        int left=l;
        int right=r;

        //具体快排的方式，主要是通过该逻辑x+y>y+x  则x大于y。如果x+y<y+x  则x小于y
        // 330 大于 303 。也就是30要排在3的后面。用此逻辑将其快排
        while(left<right){
            while(left<right && (s[right]+s[l]).compareTo(s[l]+s[right]) >=0)right--;
            while(left<right && (s[left]+s[l]).compareTo(s[l]+s[left]) <=0)left++;
            swap(s,left,right);
        }
        swap(s,left,l);

        quicksort(s,l,left-1);
        quicksort(s,left+1,r);
    }

    public void swap(String [] s,int left,int right){
        String temp=s[left];
        s[left]=s[right];
        s[right]=temp;
    }
}

剑指 Offer 61. 扑克牌中的顺子（简单）

题目：

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例 1:

输入: [1,2,3,4,5]
输出: True

示例 2:

输入: [0,0,1,2,5]
输出: True

限制：

数组长度为 5

数组的数取值为 [0, 13] .

思路：

class Solution {
    public boolean isStraight(int[] nums) {

        Arrays.sort(nums);//将其数组进行排序
        int res=0;
        //只遍历到最后一个
        for(int i=0;i<4;i++){
            if(nums[i]==0){
                res++;//统计大小王的数量
            }
            //如果有重复的提前返回false
            else if(nums[i+1]==nums[i])
                
                return false;

        }
        //用最后一个值减去 最小值（除了0），如果小于5则是顺子
        return nums[4]-nums[res]<5;
    }
}

或者直接比较最大值最小值即可

class Solution {
    public boolean isStraight(int[] nums) {

        Set<Integer> repeat=new HashSet<>();
        int max=Integer.MIN_VALUE;
        int min=Integer.MAX_VALUE;
        for(int i=0;i<5;i++) {
            if(nums[i] == 0) continue; // 跳过大小王
            max = Math.max(nums[i],max); // 最大牌
            min = Math.min(nums[i],min); // 最小牌
            if(repeat.contains(nums[i])) return false; // 若有重复，提前返回 false
            repeat.add(nums[i]); // 添加此牌至 Set
        }

        return max-min<5;
    }
}

注意这种写法：

int max=Integer.MIN_VALUE;
int min=Integer.MAX_VALUE;

第十七天（排序）

剑指 Offer 40. 最小的k个数（简单）

题目：

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

思路：

可以通过排序，然后在弄，但是复杂度比较高
这道题是简单题
可以使用复杂度比较低一些的
例如
快排

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        quicksort(arr,0,arr.length-1);
        //数组的截取前几个，通过这个函数
        return Arrays.copyOf(arr,k);

    }
    public void quicksort(int [] arr,int l,int r){
        if(l>=r)return;

        //记住左右的节点，因为l作为基准，到时候要替换变成有序的元素
        int left=l;
        int right=r;
        while(left<right){
            while(left<right&&arr[right]>=arr[l])right--;
            while(left<right&&arr[left]<=arr[l])left++;
            swap(arr,left,right);
        }
        //不要忘记更换基准的元素
        swap(arr,left,l);
        
        //中间节点已经有序，继续排左右两边的子数组就好
        quicksort(arr,l,left-1);
        quicksort(arr,left+1,r);
    }
    public void swap(int []arr,int left,int right){
        int temp=arr[left];
        arr[left]=arr[right];
        arr[right]=temp;
    }
}

或者使用大根堆或者小根堆的实现方式
以下使用的是PriorityQueue
大根堆(前 K 小) / 小根堆（前 K 大)

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 默认是小根堆，实现大根堆需要重写一下比较器。
        Queue<Integer> pq = new PriorityQueue<>((o1,o2)->(o2-o1));
        for (int num: arr) {
            if (pq.size() < k) {
                pq.offer(num);
            }else if(num<pq.peek()){
                pq.poll();
                pq.offer(num);
            }
        }
        
        // 返回堆中的元素
        int[] res = new int[pq.size()];
        int idx = 0;
        for(int num: pq) {
            res[idx++] = num;
        }
        return res;
    }
}

第十八天（搜索与回溯算法）

剑指 Offer 55 - I. 二叉树的深度（简单）

题目：略

思路：

递归：

class Solution {
    public int maxDepth(TreeNode root) {
        //从下往上递归，通过递归左右子树，然后将其判断哪个子树大，最后加1。往上遍历即可
        if(root==null)return 0;
        int left=maxDepth(root.left);
        int right=maxDepth(root.right);
        return Math.max(left,right)+1;

    }
}

层次遍历，在每一层加1计数即可

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        //为了方便计数每一层size，也就是最大的深度
        int ans = 0;
        while (!queue.isEmpty()) {
            int n = queue.size();
            for(int i=0;i<n;i++) {
                TreeNode node = queue.poll();
                if (node.left != null)queue.offer(node.left);               
                if (node.right != null)  queue.offer(node.right);
                
                
            }
            ans++;
        }
        return ans;
    }
}

剑指 Offer 55 - II. 平衡二叉树（简单）*

题目：略

思路：

class Solution {
    public boolean isBalanced(TreeNode root) {
        //返回的高度一定是非负整数，如果abs一直大于1，则会有负数的
        return heigh(root)>=0;

    }
    //重新定义一个int类型的函数，主要是为了返回左右子树的最大深度，在中间加一些判断条件
    public int heigh(TreeNode root){
        //终止条件判断，如果叶子节点为null，则直接返回0
        if(root==null)return 0;

        //从上往下递归遍历，一开始在最下面的一层次遍历
        int left=heigh(root.left);
        int right=heigh(root.right);

        //如果左子树或者右子树为-1.则往上层递归直接变为-1。还有一个abs直接大于1
        //不要忽略左右子树，某个数为-1的情况，主要是为了方便传递
        if(left==-1||right==-1||Math.abs(left-right)>1)return -1;

        //往上返回的左右子树最大的一个，直接加1。递归条件
        return Math.max(left,right)+1;
    }
}

第十九天（搜索与回溯算法）

剑指 Offer 64. 求1+2+…+n（中等）

题目：

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

示例 1：

输入: n = 3
输出: 6

示例 2：

输入: n = 9
输出: 45

限制：

1 <= n <= 10000

思路：

除法不能使用（数学中的求和不可使用）
for不能使用

class Solution {
    public int sumNums(int n) {
        int sum=0;
        for(int i=1;i<=n;i++){
            sum+=i;
        }
        return sum;

    }
}

那就通过异或或者递归的方式
该题解主要通过k神
具体解释如下：
面试题64. 求 1 + 2 + … + n（逻辑符短路，清晰图解）

class Solution {
    //定义一个临界值，放于外面，主要是不影响递归的调用
    int sum=0;
    public int sumNums(int n) {
        //x=n>1不可写成n>1因为boolean变量要修饰。
        //主要大于1，是因为1的时候是终止条件。具体的递归通过sumNums(n-1)
        boolean x=n>1&&sumNums(n-1)>1;
        sum+=n;
        return sum;

    }
}

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先（简单）

题目：略

思路：

总体通过root不为null，一个个值比较，如果有两者相等或者不统一，直接返回root节点即可

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
        while(root!=null){
            if(root.val>p.val&&root.val>q.val){
                root=root.left;
            }else if(root.val<p.val&&root.val<q.val){
                root=root.right;
            }else {
                return root;
            }
            
        }
        return null;
        
    }
}

剑指 Offer 68 - II. 二叉树的最近公共祖先（简单）*

题目：
略

思路：

关于该题解，可看k神比较全面的题解：
k神题解

在这里插入图片描述

初始条件以及递归条件以及边界值的返回条件是什么
搞清楚逻辑传递即可

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null; // 如果树为空，直接返回null
        if(root == p || root == q) return root; // 如果 p和q中有等于 root的，那么它们的最近公共祖先即为root（一个节点也可以是它自己的祖先）
        TreeNode left = lowestCommonAncestor(root.left, p, q); // 递归遍历左子树，只要在左子树中找到了p或q，则先找到谁就返回谁
        TreeNode right = lowestCommonAncestor(root.right, p, q); // 递归遍历右子树，只要在右子树中找到了p或q，则先找到谁就返回谁
        if(left == null) return right; // 如果在左子树中 p和 q都找不到，则 p和 q一定都在右子树中，右子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
        else if(right == null) return left; // 否则，如果 left不为空，在左子树中有找到节点（p或q），这时候要再判断一下右子树中的情况，如果在右子树中，p和q都找不到，则 p和q一定都在左子树中，左子树中先遍历到的那个就是最近公共祖先（一个节点也可以是它自己的祖先）
        else return root; //否则，当 left和 right均不为空时，说明 p、q节点分别在 root异侧, 最近公共祖先即为 root
    }
}

第二十天（分治算法）

剑指 Offer 07. 重建二叉树（中等）*

题目：

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

思路：

第二十一天（位运算）

剑指 Offer 15. 二进制中1的个数（简单）

题目：leetcode：剑指 Offer 15. 二进制中1的个数

思路：

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        
        int x=1;
        int sum=0;
        while(n!=0){
            //此处记得括号
            if((n&x)==1){
                sum++;
            }
			
			//可以将上面一步到位
			//  sum += n & 1;
				
            //本题要求把数字 n 看作无符号数，因此使用 无符号右移 操作
            //无符号的移动为>>>
            n=n>>>1;
        }
        return sum;
        
    }
}

剑指 Offer 65. 不用加减乘除做加法（简单）*

题目：leetcode：剑指 Offer 65. 不用加减乘除做加法

思路：
这道题的题解主要参考k神题解
在这里插入图片描述

class Solution {
    public int add(int a, int b) {
        while(b != 0) { // 当进位为 0 时跳出
            int c = (a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
}

第二十三天（数学）

剑指 Offer 39. 数组中出现次数超过一半的数字（简单）

题目：leetcode：剑指 Offer 39. 数组中出现次数超过一半的数字

思路：
可以用哈希统计计算

class Solution {

    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums) {
            map.put(num,map.getOrDefault(num,0)+1);        
        }

//--
        //定义最大值
        int max=Integer.MIN_VALUE;
        //为了保留getKey的值
        int x=0;
        
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() > max) {
                max = entry.getValue();
                x=entry.getKey();
            }
        }

        return x;

//---或者使用如下进行
 Map.Entry<Integer, Integer> majorityEntry = null;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                majorityEntry = entry;
            }
        }

        return majorityEntry.getKey();


    }
}

以及另外一种做法：
题解如下：k神题解

class Solution {

    public int majorityElement(int[] nums) {
        //相同票数则加1，不同票数减1，如果为0的票数，设置众数为当前
        int vote=0;
        int x=0;
        for(int num:nums){
            if(vote==0)x=num;
            vote+= x==num?1:-1;
        }

        return x;
    }
}

剑指 Offer 66. 构建乘积数组（中等）*

题目：leetcode：剑指 Offer 66. 构建乘积数组

大致意思如下：
在这里插入图片描述

思路：

class Solution {
    public int[] constructArr(int[] a) {

        if(a.length==0)return new int [0];

        int []b=new int[a.length];
        //设置第一个初值为1
        b[0]=1;
        //遍历后边的初值条件
        int temp=1;

        //计算从前往后的值，维护b【i】这个数组
        for(int i=1;i<b.length;i++){
            b[i]=b[i-1]*a[i-1];
        }

        for(int i=b.length-2;i>=0;i--){
            //从后往前的遍历，计算另外一边的值
            temp *= a[i + 1];
            b[i] *= temp;
        }

        return b;

    }
}

第二十五天

剑指 Offer 29. 顺时针打印矩阵（简单）

题目：leetcode：剑指 Offer 29. 顺时针打印矩阵

思路：

螺旋模拟矩阵

class Solution {
    public int[] spiralOrder(int[][] matrix) {

        //可能是空数组，所以要多一个判断条件
        if(matrix.length == 0) return new int[0];

        int m=matrix.length;
        int n=matrix[0].length;
        
        //个数用来存放其res的总值
        int []res=new int[m*n];

        int left=0,right=n-1,top=0,bottom=m-1;

        //为了更好的定义，配合数组下标，所以统一减个1
        int num=0,sum=m*n-1;

        while(num<=sum){

            for(int i=left;i<=right && num<=sum;i++){
                res[num++]=matrix[top][i];

            }
            top++;

            for(int i=top;i<=bottom && num<=sum;i++){
                res[num++]=matrix[i][right];

            }
            right--;

            for(int i=right;i>=left && num<=sum;i--){
                res[num++]=matrix[bottom][i];

            }
            bottom--;

            for(int i=bottom;i>=top && num<=sum;i--){
                res[num++]=matrix[i][left];

            }
            left++;
        }

        return res;

    }
}