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

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

  • 😍😍😍 相知
  • 🙌🙌🙌 相识
  • 😢😢😢 开始刷题
    • 🟡1.LCR 168. 丑数—— 丑数
    • 🟢2. LCR 169. 招式拆解 II——第一个只出现一次的字符
    • 🔴3. LCR 170. 交易逆序对的总数——数组中的逆序对
    • 🟢4. LCR 171. 训练计划 V——两个链表的第一个公共节点
    • 🟢5. LCR 172. 统计目标成绩的出现次数——在排序数组中查找数字
    • 🟢6. LCR 173. 点名——0~ n-1中缺失的数字
    • 🟢7. LCR 174. 寻找二叉搜索树中的目标节点——二叉搜索树的第k大节点
    • 🟢8. LCR 175. 计算二叉树的深度——二叉树的深度
    • 🟢9. LCR 176. 判断是否为平衡二叉树——平衡二叉树
    • 🟡10. LCR 177. 撞色搭配——数组中数字出现的次数I
    • 🟡11. LCR 178. 训练计划 VI——数组中数字出现的次数II

在这里插入图片描述

😍😍😍 相知

刷题不要一上来就直接干,先看题,明白题说的什么意思,然后想一下用什么现成的算法和数据结构可以快速解决,如果还是无从下手,建议先去看视频,不要直接翻评论或官方代码实现,看完视频,自己在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;
	}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/402977.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2022蓝帽杯取证初赛

检材&#xff1a;https://pan.baidu.com/s/1ibOdxyCWeC5x0DQKjwcz7w?pwdvg6g 目录 手机取证1、627604C2-C586-48C1-AA16-FF33C3022159.PNG图片的分辨率是&#xff1f;&#xff08;答案参考格式&#xff1a;19201080&#xff09;2、姜总的快递单号是多少&#xff1f;&#xff0…

C++学习Day09之异常变量的生命周期

目录 一、程序及输出1.1 throw MyException()------catch (MyException e)1.2 throw MyException()------catch (MyException &e)1.3 throw &MyException()------catch (MyException *e)1.4 throw new MyException()------catch (MyException *e) 二、分析与总结 一、程…

QT3作业

1 2. 使用手动连接&#xff0c;将登录框中的取消按钮使用qt4版本的连接到自定义的槽函数中&#xff0c;在自定义的槽函数中调用关闭函数&#xff0c;将登录按钮使用t5版本的连接到自定义的槽函数中&#xff0c;在槽函数中判断ui界面上输入的账号是否为"admin"&#…

【C++初阶】系统实现日期类

目录 一.运算符重载实现各个接口 1.小于 (d1)<> 2.等于 (d1d2) 3.小于等于&#xff08;d1<d2&#xff09; 4.大于&#xff08;d1>d2&#xff09; 5.大于等于&#xff08;d1>d2&#xff09; 6.不等于&#xff08;d1!d2&#xff09; 7.日期天数 (1) 算…

顺序表详解(如何实现顺序表)

文章目录 前言 在进入顺序表前&#xff0c;我们先要明白&#xff0c;数据结构的基本概念。 一、数据结构的基本概念 1.1什么是数据结构 数据结构是由“数据”和“结构”两词组合而来。所谓数据就是&#xff1f;常见的数值1、2、3、4.....、姓名、性别、年龄&#xff0c;等。…

学习总结22

解题思路 简单模拟。 代码 #include <bits/stdc.h> using namespace std; long long g[2000000]; long long n; int main() {long long x,y,z,sum0,k0;scanf("%lld",&n);for(x1;x<n;x)scanf("%lld",&g[x]);for(x1;x<n;x){scanf(&qu…

尚未创建默认 SSL 站点。若要支持不带 SNI 功能的浏览器,建议创建一个默认 SSL 站点。

在 Windows Server 2012 IIS 站点中设置 SSL 证书后&#xff0c;IIS 右上角提示&#xff1a; 尚未创建默认 SSL 站点。若要支持不带 SNI 功能的浏览器&#xff0c;建议创建一个默认 SSL 站点。 该提示客户忽略不管&#xff0c;但是若要支持不带 SNI(Server Name Indication)…

外卖柜平台的设计与实现以及实践与总结

近年来&#xff0c;外卖行业的快速发展推动了外卖配送行业的进步和创新。外卖柜平台作为一种新兴的配送方式&#xff0c;在提高配送效率和服务质量方面具有很大的优势。本文将探讨美团外卖柜平台的设计与实现&#xff0c;以及如何保障其稳定性和安全性。 架构设计 美团外柜平台…

React -- useEffect

React - useEffect 概念理解 useEffect是一个React Hook函数&#xff0c;用于在React组件中创建不是由事件引起而是由渲染本身引起的操作&#xff08;副作用&#xff09;, 比 如发送AJAX请求&#xff0c;更改DOM等等 :::warning 说明&#xff1a;上面的组件中没有发生任何的用…

市场复盘总结 20240222

仅用于记录当天的市场情况&#xff0c;用于统计交易策略的适用情况&#xff0c;以便程序回测 短线核心&#xff1a;不参与任何级别的调整&#xff0c;采用龙空龙模式 一支股票 10%的时候可以操作&#xff0c; 90%的时间适合空仓等待 二进三&#xff1a; 进级率中 25% 最常用…

leetcode日记(32)字符串相乘

做了很久很久……真的太繁琐了&#xff01;&#xff01; class Solution { public:string multiply(string num1, string num2) {string s;string str;if (num1 "0" || num2 "0") return "0";for(int inum2.size()-1;i>0;i--){int c2num2[…

银行项目网上支付接口调用测试实例

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 公司最近有一个网站商城项目要开始开发了&#xff0c;这几天老板和几个同事一起开着需求会议&…

常见消息中间件

ActiveMQ 我们先看ActiveMQ。其实一般早些的项目需要引入消息中间件&#xff0c;都是使用的这个MQ&#xff0c;但是现在用的确实不多了&#xff0c;说白了就是有些过时了。我们去它的官网看一看&#xff0c;你会发现官网已经不活跃了&#xff0c;好久才会更新一次。 它的单机吞…

2024 ,Android 15 预览版来了

日前&#xff0c;Android 15 发布了 Preview 1 预览版&#xff0c;预览计划将从 2024 年 2 月持续到 Android 15 公开发布&#xff08;预计 10 月&#xff09;&#xff0c;3月是开发者预览版 2&#xff0c;4 月将推出 Beta 1&#xff0c;5 月将推出 Beta 2&#xff0c;6 月的 B…

Studio One 6免费下载安装激活教程

一、Studio One 6安装 1.双击Studio One6安装包&#xff08;见文章尾部&#xff09;&#xff0c;如下图&#xff0c;可以切换语言&#xff0c;点击【OK】。 2.根据安装导航&#xff0c;点击【下一步】 3.阅读许可证协议后&#xff0c;点击【我接受】。 4.选择安装位置&#xf…

Java 数据结构篇-深入了解排序算法(动态图 + 实现七种基本排序算法)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 实现冒泡排序 2.0 实现选择排序 2.1 选择排序的改良升级 3.0 实现堆排序 4.0 实现插入排序 5.0 实现希尔排序 6.0 实现归并排序 6.1 递归实现归并排序 6.2 使用…

用了大品牌做流量,用自主品牌做利润。

用国际品牌和有品牌的产品把用户数量做起来&#xff0c;用大品牌做流量&#xff0c;积累用户数据。当你的用户数量达到一定量之后&#xff0c;再做自主品牌&#xff0c;这叫水到渠成。 用户最好的商业模式不需要教育。用别人的品牌去打穿流量&#xff0c;打穿用户&#xff0c;…

SpringBoot基于JWT的token做登录认证

背景 我们在基于Session做登录认证的时候&#xff0c;会有一些问题&#xff0c;因为Session存储到服务器端&#xff0c;然后通过客户端的Cookie进行匹配&#xff0c;如果正确&#xff0c;则通过认证&#xff0c;否则不通过认证。这在简单的系统中可以这么使用&#xff0c;并且…

如何重启docker中运行的镜像

要重启 Docker 中运行的容器&#xff0c;您可以使用 docker restart 命令。首先&#xff0c;您需要知道容器的 ID 或名称&#xff0c;然后使用该信息来重启容器。以下是具体步骤&#xff1a; 找出容器的 ID 或名称 执行 docker ps 命令列出所有正在运行的容器&#xff0c;找到您…

软件常见设计模式

设计模式 设计模式是为了解决在软件开发过程中遇到的某些问题而形成的思想。同一场景有多种设计模式可以应用&#xff0c;不同的模式有各自的优缺点&#xff0c;开发者可以基于自身需求选择合适的设计模式&#xff0c;去解决相应的工程难题。 良好的软件设计和架构&#xff0…
最新文章