当前位置： 首页 > article >正文

《剑指Offer》笔记题解思路技巧优化 Java版本——新版leetcode_Part_1

article 2024/11/14 18:01:29

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

  • 😍😍😍 相知
  • 🙌🙌🙌 相识
  • 😢😢😢 开始刷题
    • 1. LCR 120. 寻找文件副本——数组中重复元素
    • 2. LCR 121. 寻找目标值 - 二维数组——二维数组中查找
    • 3. LCR 122. 路径加密——替换空格
    • 4. LCR 123. 图书整理 I——从尾到头打印链表
    • 5. LCR 124. 推理二叉树——重建二叉树
    • 6. LCR 125. 图书整理 II——用两个栈实现队列
    • 7. LCR 126. 斐波那契数——斐波那契数列
    • 8. LCR 127. 跳跃训练——青蛙跳台阶问题
    • 9. LCR 128. 库存管理 I——旋转数组的最小值

在这里插入图片描述

😍😍😍 相知

当你踏入计算机科学的大门，或许会感到一片新奇而陌生的领域，尤其是对于那些非科班出身的学子而言。作为一位非科班研二学生，我深知学习的道路可能会充满挑战，让我们愿意迎接这段充满可能性的旅程。

最近，我开始了学习《剑指Offer》和Java编程的探索之旅。这不仅是一次对计算机科学的深入了解，更是对自己学术生涯的一次扩展。或许，这一切刚刚开始，但我深信，通过努力与坚持，我能够逐渐驾驭这门技艺。

在这个博客中，我将深入剖析《剑指Offer》中的问题，并结合Java编程语言进行解析。

让我们一起踏上这段学习之旅，共同奋斗，共同成长。无论你是已经驾轻就熟的Java高手，还是像我一样初出茅庐的学子，我们都能在这里找到彼此的支持与激励。让我们携手前行，共同迎接知识的挑战，为自己的未来打下坚实的基石。

（得了！看吧！一起学习、一起努力！！！）

LeetCode估计版权原因，把剑指Offer系列题都下降了，估计大家根据题目是找不到了，但是LeetCode其实是换汤不换药，把剑指offer的题目和描述改了一下而已，其他的依然不变。按照我的标题继续冲！

🙌🙌🙌 相识

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

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

😢😢😢 开始刷题

1. LCR 120. 寻找文件副本——数组中重复元素

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

  • 这道题在原书上绝对不是简单级别啊！
  • 它考察的是程序员的沟通能力，先问面试官要时间/空间需求！

    • 只是时间优先就用哈希表 时间: O ( n ) O(n) O(n) 空间 O ( n ) O(n) O(n)

      class Solution {
    public int findRepeatDocument(int[] documents) {
        // 定义数据结构
        Map<Integer,Integer> hashmap =  new HashMap<>();
        // 遍历
        for(int temp :documents){
            if(hashmap.containsKey(temp))return temp;     
            else hashmap.put(temp,1);
        }
        return 0;
    }
}

    • 还有空间要求，就用指针+原地排序数组 时间: O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n)) 空间 O ( 1 ) O(1) O(1)

      class Solution {
    public int findRepeatDocument(int[] documents) {
        Arrays.sort(documents);
        for(int i = 0;i<documents.length-1;i++)
        {
            if(documents[i]!=documents[i+1])continue;
            else return documents[i];
        }
        return 0;
    }
}

    • 0 ≤ documents[i] ≤ n-1 由于！这个限制的存在，我们可以利用鸽巢原理，所以我们可以将见到的元素 放到索引的位置，如果交换时，发现索引处已存在该元素，则重复 O ( n ) O(n) O(n)空间 O ( 1 ) O(1) O(1)

      class Solution {
    public int findRepeatDocument(int[] documents) {
        for(int i = 0;i<documents.length;++i){
            while(documents[i]!=i){
                if(documents[i]==documents[documents[i]])return documents[i];
                int k = documents[documents[i]];
                documents[documents[i]] = documents[i];
                documents[i] = k;
            }
        }
        return 0;
    }
}

学会这个思想了嘛？？真的？？？ok！来个难的！
41.缺失的第一个正数 https://leetcode.cn/problems/first-missing-positive/description/

代码给你附上了！

class Solution {
    public int firstMissingPositive(int[] nums) {
        for(int i = 0;i < nums.length;i++){
            while (nums[i]>0&&nums[i]<=nums.length)
            {
                if (nums[i] == nums[nums[i]-1]) break; // 已经在对应位置
                int temp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                 nums[i] = temp;
            }
        }
        
        for(int i = 0;i < nums.length;i++){
            if(i+1!=nums[i])return i+1;
        }
        return  nums.length+1;

    }
}

765.情侣牵手 https://leetcode.cn/problems/couples-holding-hands/description/

class Solution {
    public int minSwapsCouples(int[] row) {
        // /2 是n就是低n对（0开始）
        int result = 0;
        for(int i=1;i<row.length-1;i++){
            if(i%2 == 0)continue;
            if((row[i-1]/2)==(row[i]/2)) continue;
            for(int j = i+1;j<row.length;j++){
                if((row[i-1]/2)==(row[j]/2)){
                    int k = row[j];
                    row[j] = row[i];
                    row[i] = k;
                    result++;
                    break;
                }
            }
            
        }
        return result;
    }
}

2. LCR 121. 寻找目标值 - 二维数组——二维数组中查找

题目跳转：https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/description/

不废话
想到暴搜时间复杂度—— O ( n 2 ) O(n^2) O(n2)
暴搜这么优化啊！想到二分时间复杂度—— O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))

class Solution {
    public boolean findTargetIn2DPlants(int[][] plants, int target) {
        //个人反应
        //暴力搜素
        //二分法
        if(plants.length==0||plants[0].length==0)return false;
        int m = plants.length;
        int n = plants[0].length; 
        int left = 0;
        int right = 0; 
        int mid = 0;
        for(int i = 0;i<m;i++)
        {
            left = 0;
            right = n-1; 
            while(left<=right)
            {
                mid = (right-left)/2+left;
                if(plants[i][mid]==target)return true;
                if(plants[i][mid]<target)left = mid+1;
                else{right = mid-1;}
            }
        }
        return false;
    }
}

再优化一版本！
看图说话！
在这里插入图片描述

class Solution {
    public boolean findTargetIn2DPlants(int[][] plants, int target) {
        if(plants.length==0||plants[0].length==0)return false;
        int m = plants[0].length-1;
        int n = 0; 
        while(m>=0&&m<plants[0].length&&n>=0&&n<plants.length){
            if(plants[n][m]<target) n++;
            else if(plants[n][m]>target) m--;
            else return true;
        }
        
        return false;
    }
}

3. LCR 122. 路径加密——替换空格

题目跳转：https://leetcode.cn/problems/ti-huan-kong-ge-lcof/description/
时间复杂度—— O ( n ) O(n) O(n)，空间复杂度—— O ( n ) O(n) O(n)

class Solution {
    public String pathEncryption(String path) {
        return path.replace("."," ");
    }
}

但是！学一种数据结构！！

class Solution {
    public String pathEncryption(String path) {
        StringBuilder stringBuilder = new StringBuilder();
        for(int i =0;i<path.length();i++){
            stringBuilder.append(path.charAt(i)=='.'?' ':path.charAt(i));
        }
        return stringBuilder.toString();
    }
}

扩容！但是Java本身是不支持这样扩容的 但是模拟一下，加深印象！但是别学！
在这里插入图片描述

class Solution {
    public String pathEncryption(String path) {
        int count = 0;
        for(int i = 0;i<path.length();i++){
            if(path.charAt(i)=='.')count++;
        }
        char[] a = new char[path.length()+(1-1)*count];
        int temp = a.length-1;
        for(int i = path.length()-1;i >= 0;i--){
            if(path.charAt(i)!='.') a[temp--] = path.charAt(i);
            else{
                a[temp--] = ' ';
            }
        }
        return new String(a);
    }
}

4. LCR 123. 图书整理 I——从尾到头打印链表

题目跳转：https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/description/

栈——时间复杂度—— O ( n ) O(n) O(n)，空间复杂度—— O ( n ) O(n) O(n)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[] reverseBookList(ListNode head) {
        if(head==null) return new int[0];
        Stack<Integer> stack = new Stack();
        int count = 0;
        while(head!=null){
            count++;
            stack.push(head.val);
            head = head.next;
        }
        int [] result = new int[count];
        int a = 0;
        while(!stack.isEmpty()){
            result[a++] = stack.peek();
            stack.pop();
        }
        return result;
    }
}

反转链表
反转链表的代码 然后直接顺序都即可
在这里插入图片描述

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head==null||head.next==null) return head;
        ListNode result_zero = null;
        ListNode cur = head;
        while(cur!=null)
        {
            ListNode head_temp = cur.next;
            cur.next = result_zero;
            result_zero= cur;
            cur = head_temp;
        }
        return result_zero;

    }

}
  • 递归反转——时间复杂度—— O ( n ) O(n) O(n)，空间复杂度—— O ( n ) O(n) O(n)
class Solution {
    public ListNode reverseList(ListNode head) {
        // head == null 防止参数Head本身就为null
        // haed.next == null，用来让递归停止到尾结点，就开始返回;
        if (head == null || head.next == null) return head;
        ListNode node = reverseList(head.next); // 保存尾结点;
        head.next.next = head; // 翻转指针;
        head.next = null; // 置空，递归已保存上一个结点，置空不影响连接
        return node; // 返回尾结点
    }
}
  • 原地反转——时间复杂度—— O ( n ) O(n) O(n)，空间复杂度—— O ( 1 ) O(1) O(1)
    请添加图片描述
// 双指针
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
            temp = cur.next;// 保存下一个节点
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}

// 递归 
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }
}

// 从后向前递归
class Solution {
    ListNode reverseList(ListNode head) {
        // 边缘条件判断
        if(head == null) return null;
        if (head.next == null) return head;
        
        // 递归调用，翻转第二个节点开始往后的链表
        ListNode last = reverseList(head.next);
        // 翻转头节点与第二个节点的指向
        head.next.next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head.next = null;
        return last;
    } 
}

倒推数组，反向填充——时间复杂度—— O ( n ) O(n) O(n)，空间复杂度—— O ( 1 ) O(1) O(1)

class Solution {
    public int[] reverseBookList(ListNode head) {
        if(head==null) return new int[0];
        ListNode temp = head;
        int count = 0;
        while(temp!=null){
            count++;
            temp = temp.next;
        }
        int [] result = new int[count];
        for(int i = result.length-1;i>=0;i--){
            result[i]=head.val;
            head= head.next;
        }
        return result;
    }
}

5. LCR 124. 推理二叉树——重建二叉树

题目跳转：https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/description/
知识点：

  • 前序遍历列表：第一个元素永远是根节点 (root)
  • 中序遍历列表：根节点 (root)左边的所有元素都在根节点的左分支，右边的所有元素都在根节点的右分支

算法思路：

  • 通过【前序遍历列表】确定【根节点 (root)】
  • 将【中序遍历列表】的节点分割成【左分支节点】和【右分支节点】
  • 递归寻找【左分支节点】中的【根节点 (left child)】和 【右分支节点】中的【根节点 (right child)】
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //重建一开始是真的有点绕啊，但是其实理清了也还好，无非就是通过每次传进去的两个数组来构建新的二叉树
        //三部曲试一下吧
        //首先是啥时候结束
        //当传入的数组长度为0的时候就该结束了
        int length = preorder.length;
        if(length == 0 ) return null;
        //接下来是我们应该返回什么，那当然就是返回重建子树的根节点咯
        //每一层应该做些什么呢？
        //应该通过传进来的两个数组，根据他们之间的关系，来构建子树，并把新的参数传递下去
        //那么现在传进来了两个数组，一个是前序遍历的数组，那么首位必定是根节点，先拿下
        int rootValue = preorder[0];
        //有了数组的根节点以后我们自然需要的是左右子树，根据中序遍历的特点，只要找到了根节点，那么他两边自然
        //就是他的左右子树了
        //那么先在中序遍历的数组中找到根节点,并把它的坐标保存起来
        int rootIndex = 0;      
        for(int i = 0; i < length; i++){
            if(inorder[i] == rootValue){
                rootIndex = i;
                break;
            }
        }
        //至此我们已经找到了根和左右子树，那么设置一下根节点的左右节点，自然就是递归后返回的左右子树的根节点
        //先把我们的根节点创建出来
        TreeNode root = new TreeNode(rootValue);
        root.left = buildTree(Arrays.copyOfRange(preorder,1,rootIndex + 1),Arrays.copyOfRange(inorder,0,rootIndex));
        root.right = buildTree(Arrays.copyOfRange(preorder,1+rootIndex,length),Arrays.copyOfRange(inorder,rootIndex+1,length));
        //至于传入的数组如何分割可以自己通过测试用例来分析，这里不赘述了
        //至此节点创建，左右节点的设置均已完成，返回root
        return root;
        
    }

}

学会这个函数嗷！以后不能忘啦Arrays.copyOfRange(arr,0,k)截取arr下标0到k-1

6. LCR 125. 图书整理 II——用两个栈实现队列

题目跳转：https://blog.csdn.net/weixin_46225503/article/details/135412406
学会用栈！

class CQueue {
    Stack<Integer> stack_one;
    Stack<Integer> stack_two;
    public CQueue() {
         stack_one  = new Stack<>();
         stack_two  = new Stack<>();
    }
    
    public void appendTail(int value) {
        stack_one.push(value);
    }
    
    public int deleteHead() {
        if(stack_one.isEmpty())return -1;
        while(!stack_one.isEmpty()){
            stack_two.push(stack_one.peek());
            stack_one.pop();
        }
        int value = stack_two.peek();
        stack_two.pop();
        while(!stack_two.isEmpty()){
            stack_one.push(stack_two.peek());
            stack_two.pop();
        }
        return value;
        
    }
}

学会用LinkedList！

class CQueue {
        LinkedList<Integer> stack1;
	LinkedList<Integer> stack2;

	public CQueue() {
		stack1 = new LinkedList<>();
		stack2 = new LinkedList<>();
	}

	public void appendTail(int value) {
		stack1.push(value);
	}

	public int deleteHead() {
		if (stack2.isEmpty()) {
			if (stack1.isEmpty()) return -1;
			while (!stack1.isEmpty()) {
				stack2.push(stack1.pop());
			}
			return stack2.pop();
		} else return stack2.pop();
	}
}

class CQueue {
    LinkedList<Integer> linkedList;
    public CQueue() {
         linkedList  = new LinkedList<>();
    }
    public void appendTail(int value) {
        linkedList.addLast(value);
    }
    public int deleteHead() {
        if(linkedList.isEmpty())return -1;
        return linkedList.removeFirst();
    }
}

学会队列！https://blog.csdn.net/weixin_46225503/article/details/135412739

class CQueue {
    Queue<Integer> queue;
    public CQueue() {
         queue  = new LinkedList<>();
    }  
    public void appendTail(int value) {
        queue.add(value);
    }
    public int deleteHead() {
        if(queue.isEmpty())return -1;
        return queue.poll();   
    }
}

7. LCR 126. 斐波那契数——斐波那契数列

题目跳转：https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/description/
哈希表！

class Solution {
    private Map<Integer,Integer> hashMap = new HashMap();
    private  final int mod = 1000000007;
    public int fib(int n) {

        hashMap.put(0,0);
        hashMap.put(1,1);
        if(hashMap.containsKey(n))return hashMap.get(n);
        else
        {
            int result = 0;
            result = (fib(n-1) + fib(n-2))%mod;
            hashMap.put(n,result);
            return result;
        }
    }
}

数组！

class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1)
            return n;
        int[] ans = new int[n+1];
        ans[0] = 0;
        ans[1] = 1;
        for(int i =2;i<=n;i++)
        {
            ans[i] = (ans[i-1]+ans[i-2])%1000000007;
        }
        return ans[n];
    }
}

那为什么不递归呢？Good Question！
在这里插入图片描述

8. LCR 127. 跳跃训练——青蛙跳台阶问题

题目跳转：https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/description/

与上一题相似

在这里插入图片描述

f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n-1)+f(n-2) f(n)=f(n−1)+f(n−2)

f ( 0 ) = 1 , f ( 1 ) = 1 , f ( 2 ) = 2 f(0)=1, f(1)=1, f(2)=2 f(0)=1,f(1)=1,f(2)=2

class Solution {
    public int trainWays(int num) {
        if(num==0)return 1;
        if(num==1) return 1;
        if(num==2) return 2;
        int[] arr = new int[num+1];
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 2;
        for(int i = 3;i <= num;i++)
        {
            arr[i] = (arr[i-1]+arr[i-2])%1000000007;
        }
        return arr[num];
        
    }
}

9. LCR 128. 库存管理 I——旋转数组的最小值

题目跳转：https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

排序

class Solution {
    public int stockManagement(int[] stock) {
        Arrays.sort(stock);
        return stock[0];
    }
}

如果你想到这个！你别逼我扇你！调用API 虽然顾得，但是还是要写点有实力的东西！
在这里插入图片描述

那好吧~ 换一个！
遍历

class Solution {
    public int stockManagement(int[] stock) {
        if(stock.length==1) return stock[0];
        if(stock.length==2) return Math.min(stock[0],stock[1]);
        int result = stock[0];
        for(int i = 1;i<stock.length;i++)
        {
            if(result>stock[i])result = stock[i];
        }
        return result;

    }
}

没啥营养！
在这里插入图片描述
再换！

class Solution {
    public int stockManagement(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;
        if (numbers[left] < numbers[right]) {
            return numbers[left];
        }
        while (left < right) {
            int mid = (left + right) / 2;
            // 如果右边的比中间的大，那么说明右边的部分一定是有序的。
            if (numbers[right] > numbers[mid]) {
                right = mid;
            // 右边的小于中间的，说明左边的一定是有序的。
            } else if (numbers[right] < numbers[mid]) {
                left = mid + 1;
            // 如果相等，想要判断哪一边是有序的比较难，需要考虑很多临界条件。
            // 上次理解的难点正在这里，这次也在这里卡了思路。
            // 但换个思路就很好解决了。
            // 即：我不需要确认当前的状态，我只需要保证答案在我的区间内，并且逐渐压缩区间，直到出现变动即可。
            // 由于此时numbers[right] == numbers[mid]，所以right --并不会影响答案依旧在left和right的区间内。
            } else {
                right --;
            }
        }
        return numbers[left];
    }
}

要学会二分法！！！！

在这里插入图片描述
简单来个测试 去写一个二分！
在这里插入图片描述

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

http://www.kler.cn/a/234407.html

相关文章：

  • 随时随地编码：香橙派Zero3上安装Code Server远程开发指南
  • WordPress HTTPS 配置问题解决方案
  • Spring Boot 2.x 和 Druid 多数据源整合 dm
  • 蔚来Java面试题及参考答案
  • 32位、64位、x86与x64：深入解析计算机架构
  • BERT配置详解1：构建强大的自然语言处理模型
  • 如何使用 sqlalchemy declarative base 多层次继承
  • springboot/ssm档案管理系统公司设备管理系统Java系统企业配件系统
  • OpenCV基础
  • 每日OJ题_位运算③_力扣面试题 01.01. 判定字符是否唯一
  • java实战：销售订单30分钟未支付自动取消
  • JDK新特性
  • 【MySQL】MySQL表的增删改查（进阶）
  • 计算机网络基本知识（二）
  • Blazor SSR/WASM IDS/OIDC 单点登录授权实例5 - Winform 端授权
  • Cetnos7之修改open files大小引发的故障及处理方式
  • java中使用Lambda表达式实现参数化方法
  • 【操作系统】Ubuntu Swap内存扩容
  • iOS平台如何实现RTSP|RTMP播放端录像？
  • js基础（2）
  • QT+OSG/osgEarth编译之八十三：osgdb_ogr+Qt编译（一套代码、一套框架，跨平台编译，版本：OSG-3.6.5插件库osgdb_ogr）
  • Acwing154滑动窗口
  • Windows10安装PCL1.14.0及点云配准
  • MongoDB聚合：$shardedDataDistribution
  • OOD分类项目训练
  • kyuubi 接入starrocks | doris