《剑指Offer》笔记&题解&思路&技巧&优化_Part_6

😍😍😍 相知

刷题不要一上来就直接干，先看题，明白题说的什么意思，然后想一下用什么现成的算法和数据结构可以快速解决，如果还是无从下手，建议先去看视频，不要直接翻评论或官方代码实现，看完视频，自己在idea中模拟敲几遍代码，如果跑通了，先别急着上leetcode黏贴，而是再回顾一下要点，然后确定自己完全懂了后，在leetcode中手敲，注意是手敲下来！！！ 目前我就是采用的这种方法，虽然慢，但是可以维持一周忘不掉它，如果要想长期不忘，只能隔段时间就review一下了，就算是大牛，知道方法，长时间不碰，也不可能保证一次到位把代码敲完一遍过！！！

这是我上一篇博客的，也希望大家多多关注！

1. 《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_1
2. 《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_2
3. 《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_3
4. 《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_4
5. 《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_5

🙌🙌🙌 相识

根据题型可将其分为这样几种类型：

1. 结构概念类（数组，链表，栈，堆，队列，树）
2. 搜索遍历类（深度优先搜索，广度优先搜索，二分遍历）
3. 双指针定位类（快慢指针，指针碰撞，滑动窗口）
4. 排序类（快速排序，归并排序）
5. 数学推理类（动态规划，数学）

😢😢😢 开始刷题

🟡1.LCR 168. 丑数—— 丑数

题目跳转：https://leetcode.cn/problems/chou-shu-lcof/description/

class Solution {
   
    public int nthUglyNumber(int n) {
   
        if (n <= 0)
            return -1;
        int[] dp = new int[n];
        dp[0] = 1;
        int id2 = 0, id3 = 0, id5 = 0;
        for (int i = 1; i < n; i++) {
   
            dp[i] = Math.min(dp[id2] * 2, Math.min(dp[id3] *3, dp[id5] * 5));
            // 这里不用else if的原因是有可能id2(3) * 2 == id3(2) * 3
            // 这种情况两个指针都要后移
            if (dp[id2] * 2 == dp[i])
                id2 += 1;
            if (dp[id3] * 3 == dp[i])
                id3 += 1;
            if (dp[id5] * 5 == dp[i])
                id5 += 1; 
        }
        return dp[n - 1];
    }
}

🟢2. LCR 169. 招式拆解 II——第一个只出现一次的字符

题目跳转：https://leetcode.cn/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/description/

class Solution {
   
    public char dismantlingAction(String arr) {
   
        if(arr.length()==0) return ' ';
        if(arr.length()==1) return arr.charAt(0);
        int [] array =new int[26];
        for(int i = 0;i<arr.length();i++){
   
            array[arr.charAt(i)-'a']++;
        }
        for(int i = 0;i<arr.length();i++){
   
            if(array[arr.charAt(i)-'a']==1)return arr.charAt(i);
        }
        return ' ';
    }
}

🔴3. LCR 170. 交易逆序对的总数——数组中的逆序对

题目跳转：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/

冒泡排序

每检查一次交换一次 就可以产生一次逆序对

归并排序

class Solution {
   
	public int reversePairs(int[] nums) {
   
		if(nums == null || nums.length <= 1){
   
			return 0;
		}
		return mergeSort(nums, 0, nums.length - 1);
	}
	int mergeSort(int[] nums, int left, int right){
   
		if(left >= right){
   
			return 0;
		}
		int mid = (right - left) / 2 + left;
		int x1 = mergeSort(nums, left, mid);
		int x2 = mergeSort(nums, mid + 1, right);
		int x3 = merge(nums, left, mid, mid+1, right);
		return x1 + x2 + x3;
	}
	int merge(int[] nums, int l1, int r1, int l2, int r2){
   
		int[] temp = new int[r2 - l1 + 1];
		int count = 0;
		int i = l1, j = l2, k = 0;
		while(i <= r1 && j <= r2){
   
			if(nums[i] > nums[j]){
   
				count = count + (l2 - i);
				temp[k++] = nums[j++];
			}else{
   
				temp[k++] = nums[i++];
			}
		}
		while(i <= r1) temp[k++] = nums[i++];
		while(j <= r2) temp[k++] = nums[j++];
		// 把临时数组复制回原数组
		k = 0;
		for(i = l1; i <= r2; i++){
   
			nums[i] = temp[k++];
		}
		return count;
	}
}

🟢4. LCR 171. 训练计划 V——两个链表的第一个公共节点

题目跳转：https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/description/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
   
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
   
        if(headA==null||headB==null)return null;
        ListNode tempA = headA;
        ListNode tempB = headB;
        boolean a = false;
        boolean b = false;
        while(tempA!=tempB){
   
            if(tempA.next==null){
   
                tempA = headB;
                if(a)return null;
                a = true;
            }
            else{
   
                tempA = tempA.next;
            }
            if(tempB.next==null){
   
                tempB = headA;
                if(b)return null;
                b = true;
            }
            else{
   
                tempB = tempB.next;
            }

        }
        return tempA;
    }
}

原来不会死循环

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
   
        
        ListNode h1 = headA, h2 = headB;
        while (h1 != h2) {
   

            h1 = h1 == null ? headB : h1.next;
            h2 = h2 == null ? headA : h2.next;
        }

        return h1;  
    }

🟢5. LCR 172. 统计目标成绩的出现次数——在排序数组中查找数字

题目跳转：https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/description/

二分查找

class Solution {
   
    public int countTarget(int[] scores, int target) {
   
        int left = 0;
        int right = scores.length-1;
        int mid = 0;
        int conut = 0;
        while(left<right){
   
            mid = (right-left)/2+left;
            if(target <= scores[mid]) right = mid;
            else left = mid+1;
        }
        while(left<scores.length&&scores[left++]==target)conut++;
        return conut;
        
    }
}

🟢6. LCR 173. 点名——0~ n-1中缺失的数字

题目跳转：https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/

位运算

class Solution {
   
    public int takeAttendance(int[] records) {
   
        if(records[records.length-1]==records.length-1) return records.length;
        int result = 0;
        for(int i = 0;i<records.length;i++){
   
            result ^=records[i];
            result ^=i;
        }
        result^=records.length;
        return result;
    }
}

二分查找

class Solution {
   
    public int takeAttendance(int[] records) {
   
        if(records[records.length-1]==records.length-1) return records.length;
        int left = 0;
        int right =records.length-1;
        while(left<right){
   
            int mid = (right-left)/2 +left;
            if(records[mid]==mid){
   
                left = mid+1;
            }
            else{
   
                right = mid;
            }
        }
        return left;
    }
}

🟢7. LCR 174. 寻找二叉搜索树中的目标节点——二叉搜索树的第k大节点

题目跳转：https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/description/
作为一个普通人，我来分析下这题。

1. 假设，你花了点时间，练习了二叉树的三种遍历方式： a. 前序遍历 b. 中序遍历 c. 后续遍历
2. 你也学习了二叉搜索树，深入研究了二叉树搜索树的特性，并且深刻知道二叉搜索树的一个特性：通过中序遍历所得到的序列，就是有序的。

好，有了以上两点知识，我认为你必须能想到（如果想不到，以上两点知识肯定没有学扎实）：中序遍历二叉搜索树，遍历的同时，把遍历到的节点存到一个可变数组里（Java的话，可以用ArrayList)。 思路转化为代码，如下：

class Solution {
   
    public int findTargetNode(TreeNode root, int cnt) {
   
        if(root==null)return -1;
        if(root.left==null&root.right==null)return root.val;
        ArrayList<Integer> list = new ArrayList<>();
        dfs(root,list);
        return list.get(list.size()-cnt);

    }
    public void dfs(TreeNode root,ArrayList<Integer> list){
   
        if(root==null)return;
        if(root.left==null&root.right==null){
   
            list.add(root.val);
            return ;
        }
        if(root.left!=null)dfs(root.left,list);
        list.add(root.val);
        if(root.right!=null)dfs(root.right,list);
    }
}

class Solution {
   
    public int findTargetNode(TreeNode root, int cnt) {
   
        if(root==null)return -1;
        if(root.left==null&root.right==null)return root.val;
        ArrayList<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
   
            TreeNode temp = stack.peek();
            if(temp==null){
   
                stack.pop();
                list.add(stack.pop().val);
            }
            else{
   
                stack.pop();
                if(temp.right!=null) stack.push(temp.right);
                stack.push(temp);
                stack.push(null);
                if(temp.left!=null)stack.push(temp.left);
            }
        }
        return list.get(list.size()-cnt);

    }
}

🟢8. LCR 175. 计算二叉树的深度——二叉树的深度

题目跳转：https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/description/

class Solution {
   
    int max = 0;
    public int calculateDepth(TreeNode root) {
   
        int deep = 0;
        
        max = dfs(root,deep);
        return max;

    }
    public int dfs(TreeNode root,int num){
   
        if(root==null)return num;
        if(root.left==null&root.right==null){
   
            return num+1;
        }
        if(root.left!=null) max = Math.max(max,dfs(root.left,num+1));
        if(root.right!=null) max = Math.max(max,dfs(root.right,num+1));
        return max;
    }
}

class Solution {
   
    public int calculateDepth(TreeNode root) {
   
        int max = 0;
        if(root ==null)return 0;
        if(root.left == null&&root.right == null)return 1;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(null);
        while(!queue.isEmpty()){
   
            TreeNode temp = queue.poll();
            if(temp==null){
   
                max++;
                if(!queue.isEmpty())queue.add(null);
            }
            else{
   
                
                if(temp.right!=null) queue.add(temp.right);
                if(temp.left!=null)queue.add(temp.left);
            }
        }
        return max;
    }
}

🟢9. LCR 176. 判断是否为平衡二叉树——平衡二叉树

题目跳转：https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/description/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
   
    
    public boolean isBalanced(TreeNode root) {
   
        if(root==null) return true;
        if(root.left==null&&root.right==null)return true;
        if(Math.abs(getHigh(root.left)-getHigh(root.right))<=1){
   
            return isBalanced(root.left)&&isBalanced(root.right);
        }
        return false;
    }
    public int getHigh(TreeNode root)
    {
   
        if(root==null) return 0;
        return Math.max(getHigh(root.left),getHigh(root.right))+1;

    }
}

🟡10. LCR 177. 撞色搭配——数组中数字出现的次数I

题目跳转：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/description/

相同的数异或为0，不同的异或为1。0和任何数异或等于这个数本身。

所以，数组里面所有数异或 = 目标两个数异或 。 由于这两个数不同，所以异或结果必然不为0。

假设数组异或的二进制结果为10010，那么说明这两个数从右向左数第2位是不同的

那么可以根据数组里面所有数的第二位为0或者1将数组划分为2个。

这样做可以将目标数必然分散在不同的数组中，而且相同的数必然落在同一个数组中。

这两个数组里面的数各自进行异或，得到的结果就是答案

class Solution {
   
    public int[] sockCollocation(int[] nums) {
   
        int x = 0; // 用于记录 A B 的异或结果
        
        /** 得到A^B的结果 
            基于异或运算的以下几个性质 
                1. 交换律 
                2. 结合律 
                3. 对于任何数x，都有x^x=0，x^0=x 
        */
        for (int val : nums) x ^= val;

        // x & (-x)本身的作用是得到最低位的1，
        int flag = x & (-x); 
        // 而我们所需要的做到的是：利用这个1来进行分组，也就是做到将A和B区分开
        // 前面已经知道，x是我们需要的结果数A和B相异或的结果，也就是说，x的二进制串上的任何一个1，都能成为区分A和B的条件
        // 因此我们只需要得到x上的任意一个1，就可以做到将A和B区分开来
        

        int res = 0; // 用于记录A或B其中一者

        // 分组操作
        for (int val : nums) {
   
            // 根据二进制位上的那个“1”进行分组
            // 需要注意的是，分组的结果必然是相同的数在相同的组，且还有一个结果数
            // 因此每组的数再与res=0一路异或下去，最终会得到那个结果数A或B
            // 且由于异或运算具有自反性，因此只需得到其中一个数即可
            if ((flag & val) != 0) {
   
                res ^= val;
            }
        }
        // 利用先前的x进行异或运算得到另一个，即利用自反性
        return new int[] {
   res, x ^ res};
            

    }
}

🟡11. LCR 178. 训练计划 VI——数组中数字出现的次数II

题目跳转：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/description/

排序

class Solution {
   
    public int trainingPlan(int[] actions) {
   
        int n = actions.length;
        Arrays.sort(actions);
        for(int i = 0;i<n-1;i = i+3){
   
            if(actions[i]!=actions[i+2])
            {
   
                return actions[i];
            }
        }
        return  actions[n-1];
    }
}

哈希表

class Solution {
   
    public int singleNumber(int[] actions) {
   
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int number : actions) map.put(number, map.getOrDefault(number, 0) + 1);
        for (int number : map.keySet()) if (map.get(number) == 1) return number;
        return 0;
    }
}

class Solution {
   
	public int singleNumber(int[] nums) {
   
		int[] res = new int[32];
		int m = 1;
		int sum = 0;
		for(int i = 0; i < 32; i++){
   
			for(int j = 0; j < nums.length; j++){
   
				if((nums[j] & m) != 0){
   
				res[i]++;
				}
			}
			res[i] = res[i] % 3;
			sum = sum + res[i] * m;
			m = m << 1;
		}
		return sum;
	}
}