• Leetcode--剑指Offer


    在这里插入图片描述

    🎉🎉🎉写在前面:
    博主主页:🌹🌹🌹戳一戳,欢迎大佬指点!
    博主秋秋:QQ:1477649017 欢迎志同道合的朋友一起加油喔💪
    目标梦想:进大厂,立志成为一个牛掰的Java程序猿,虽然现在还是一个小菜鸟嘿嘿
    -----------------------------谢谢你这么帅气美丽还给我点赞!比个心-----------------------------

    在这里插入图片描述


    第一期:

    在这里插入图片描述

    一,两个栈实现队列

    Leetcode传送门!
    在这里插入图片描述

    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(stack1.isEmpty() && stack2.isEmpty()){
                return -1;//两个栈都是空
            }
            
            if(!stack2.isEmpty()){
                //如果stack2不是空,那么队首元素就可以直接pop栈顶元素就好
                return stack2.pop();
            }else{
                //如果是空,那就要从stack1中转元素
                while(!stack1.isEmpty()){
                    //只要stack1不是空,那就把stack1的元素全部转到stack2里面去
                    int val = stack1.pop();//弹出栈顶元素
                    stack2.push(val);
                }
                //然后再次取出栈顶元素
                return stack2.pop();
            }
        }
    }
    
    
    • 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

    【解析:】

    在这里插入图片描述
    根据题目我们可以知道是要用栈来实现队列,但是栈和队列的特性是完全相反的,所以一个栈肯定是满足不了要求,那就只能用两个栈,一个用来存元素,一个用来协助取队首元素。


    二,包含min函数的栈

    Leetcode传送门!
    在这里插入图片描述

    class MinStack {
    
        //就是最小栈问题
        /** initialize your data structure here. */
    
        
        Stack<Integer> stack;
        Stack<Integer> minStack;
    
        public MinStack() {
            stack = new Stack<>();
            minStack = new Stack<>();//保存最小值的栈
        }
        
        public void push(int x) {
            //刚开始两个都是空那就一起放
            if(stack.empty() && minStack.empty()){
                stack.push(x);
                minStack.push(x);
            }else{
                //如果不是,存放最小值的栈入栈是有要求的
                stack.push(x);
                if(x <= minStack.peek()){
                    //如果x比栈顶元素小或者相等那就入栈
                    minStack.push(x);
                }
            }
        }
        
        public void pop() {
            //弹出元素,注意两个都要弹
            if(!stack.empty()){
                int val = stack.pop();
                if(minStack.peek() == val){
                    //如果stack弹出的元素和我们的minStack中的栈顶元素一样的话,那么这边同样也要弹出栈顶元素
                    minStack.pop();
                }
            }
        }
        
        public int top() {
            if(!stack.empty()){
                return stack.peek();//查看一下stack的栈顶元素
            }
            return -1;//如果是空就返回-1
        }
        
        public int min() {
            if(!minStack.empty()){
                return minStack.peek();//最小栈的栈顶元素就是现在的最小值
            }
            return -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
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    【解析:】

    在这里插入图片描述
    特别注意:为什么上面的条件中我们要取到小于等于,这个等于的含义是啥?
    因为比如图示情况,存在两个-2,那么如果要出掉stack的栈顶元素,minStack的栈顶元素如果与stack1的栈顶元素相等的话,minStack那也是要随之出掉这个栈顶元素的,因为最小值会发生变化。但是这里是两个-2,你如果右边只放一个-2,那么左右两边同时出掉之后,左边还有一个-2,但是右边就没有-2了,这个时候的最小值关系就是错的。


    第二期:

    在这里插入图片描述

    一,从尾到头打印链表

    Leetcode传送门!
    在这里插入图片描述

    class Solution {
        public int[] reversePrint(ListNode head) {
            //栈
            // Stack stack = new Stack<>();
            // ListNode cur = head;
            // while(cur != null){
            //     stack.push(cur.val);
            //     cur = cur.next;
            // }
            // int[] arr = new int[stack.size()];
            // int k = 0;
            // while(!stack.empty()){
            //     arr[k] = stack.pop();
            //     k++;
            // }
            // return arr;
            
            //反向填充数组
            ListNode cur = head;
            int len = 0;
            while(cur != null){//求一下链表的长度
                len++;
                cur = cur.next;
            }
            
            int[] arr = new int[len];
            //开始反向填充
            while(head != null){
                arr[--len] = head.val;
                head = head.next;
            }
            return arr;
        }
    }
    
    • 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

    这个题的解法有很多,比如栈顺序压栈之后链表的元素值在栈顶从上往下就是一个倒置的,所以就只需要挨个出栈就行。也可以顺序遍历链表,但是在填充数组的时候,从后往前填充,那么最终也可以达到一个倒置的效果。


    二,反转链表

    Leetcode传送门!
    在这里插入图片描述

    class Solution {
        public ListNode reverseList(ListNode head) {
            ListNode pre = null;
            ListNode cur = head;
            while(cur != null){
                ListNode curNext = cur.next;
                cur.next = pre;
                pre = cur;
                cur = curNext;
            }
            return pre;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    这个题是老朋友了,反转链表的思想在很多时候还是很有用的,大概的解法无非就是这种两个指针遍历链表,或者利用一个虚拟头也是可以的。


    三,复杂链表的复制

    Leetcode传送门!
    在这里插入图片描述

    class Solution {
        public Node copyRandomList(Node head) {
            //利用Map
            //先遍历一遍链表,把数值进行复制,并且存储对应关系
            Node cur = head;
            Map<Node,Node> map = new HashMap<>();//不要用TreeMap因为节点在放进去的
            while(cur != null){
                Node tmp = new Node(cur.val);
                map.put(cur,tmp);
                cur = cur.next;
            }
    
            //然后就可以对next,random进行连接了
            cur = head;
            while(cur != null){
                (map.get(cur)).next = map.get(cur.next);
                (map.get(cur)).random = map.get(cur.random);
                cur = cur.next;
            }
    
            return map.get(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

    这个题要注意,题目所说的复制的过程其实是一个深拷贝的过程,因为你是要定义出新的节点,但是他们之间的连接关系要和以前一样。所以说到这种对应关系,那么自然就会想到Map。解法也即是用Map,两次遍历链表,第一次首先把数值进行拷贝,顺便把新节点与老节点之间的对应关系存储到Map里面,然后第二次遍历链表就是处理next以及random的问题。


    第三期:

    在这里插入图片描述

    一,替换空格

    Leetcode传送门!
    在这里插入图片描述

    class Solution {
        public String replaceSpace(String s) {
            //可以用StringBuilder 遇到空格就append("%20"),但是如果不利用额外空间呢就要用双指针
            
            StringBuilder stringBuilder = new StringBuilder();
            for(int i = 0;i < s.length();i++){
                if(s.charAt(i) != ' '){
                    stringBuilder.append(s.charAt(i));//append()方法是有重载的
                }else{
                    stringBuilder.append("%20");
                }
            }
            return stringBuilder.toString();
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    二,左旋转字符串

    Leetcode传送门!
    在这里插入图片描述

    class Solution {
    
        public void reverseString(int s,int e,char[] arr){
            int left = s;
            int right = e;
            while(left < right){
                char tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
                left++;
                right--;
            }
        }
        public String reverseLeftWords(String s, int n) {
            // StringBuilder stringBuilder = new StringBuilder();
            // String ret1 = s.substring(0,n%s.length());
            // String ret2 = s.substring(n%s.length());
            // stringBuilder.append(ret2);
            // stringBuilder.append(ret1);
            // return stringBuilder.toString();
    
            //如果说不让用库方法,以及额外空间
            //左旋问题 前半部分倒置 后半部分倒置 整个字符串倒置
            char[] arr = new char[s.length()];
            for(int i = 0;i < s.length();i++){
                arr[i] = s.charAt(i);//拷贝到字符数组里面,因为字符串不可变
            }
    
            reverseString(0,n%s.length()-1,arr);
            reverseString(n%s.length(),s.length()-1,arr);
            reverseString(0,s.length()-1,arr);
            String ret = new String(arr);
            return ret;
        }
    }
    
    • 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

    第四期:

    在这里插入图片描述

    一,数组中重复的数字

    Leetcode传送门!
    在这里插入图片描述

    class Solution {
        public int findRepeatNumber(int[] nums) {
            HashSet<Integer> set = new HashSet<>();
            int ret = 0;
            for(int i = 0;i < nums.length;i++){
                if(!set.contains(nums[i])){
                    set.add(nums[i]);
                }else{
                    ret = nums[i];
                }
            }
            return ret;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    二,在排序数组中查找数字

    Leetcode传送门!
    在这里插入图片描述

    class Solution {
        public int search(int[] nums, int target) {
            //二分查找只能应用于有序的数组
            //两次二分查找
    
            int leftBoundary = 0;
            int rightBoundary = 0;
            int i = 0;
            int j = nums.length - 1;
            //1.寻找右边界
            while(i <= j){
                int mid = (i + j)/2;
                if(nums[mid] > target){
                    j = mid - 1;
                }else{
                    //即使相等,区间继续往右边压缩,寻找右边界
                    i = mid + 1;
                }
            }
            //跳出循环的时候就说明找到了右边界
            rightBoundary = i;
    
            //2.寻找左边界
            //优化:先判断一下到底存不存在target
            if(j >= 0 && nums[j] != target){
                return 0;
            }
    
            i = 0;
            j = rightBoundary - 1;//寻找左边界就没有必要寻找整个数组了
            while(i <= j){
                int mid = (i + j)/2;
                if(nums[mid] < target){
                    i = mid + 1;
                }else{
                    j = mid - 1;
                }
            }
            //跳出循环就是找到了左边界
            leftBoundary = j;//也有可能直接是-1了,不过不影响后面计算结果还是0
    
            //之间的差值就是出现的次数
            return rightBoundary - leftBoundary - 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
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    【解析:】

    在这里插入图片描述
    如图,这是寻找右边界的过程,那么其实寻找左边界的过程差不多,一直往左边压缩区间就好,最终找到的左边界是在下标为2的地方。所以最终8出现的次数就是rightBoundary - leftBoundary - 1。 其中有两个优化的点,就是在找到右边界之后可以先判断一下存不存在target,因为按理来说此时nums[j](j要大于等于0)就是等于target的,所以如果nums[j] != target就可以直接返回0了。另外如果存在target,在找左边界就可以直接从 [0,rightBoundary-1 ]之间找了。


    三,0~n-1中缺失的数字

    Leetcode传送门!
    在这里插入图片描述

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

    【解析:】

    在这里插入图片描述
    这个题题目说的很绕,你把n-1看成一个整体,其实就是让你找到0到这个整体数值之间缺失的一个数字。
    整体的思想其实还是二分查找,一般说数据有序,然后让你找某一个数值,基本都可以往二分查找上靠。这里只不过一个很重要的点就是下标与数值的对应关系,如果不存在缺失的话,那么下标和值一定是相等的。所以我们在二分查找的时候,去比较的就是nums[mid]与mid的大小关系,如果相等,那就说明mid之前是没有发生缺失数字的,所以就把区间往后面压缩,left = mid+1。如果不相等,就说明当前mid以后都是有问题的,所以mid的前面肯定是发生了缺失,则right = mid-1。最终整个循环结束的时候left的值就是我们缺失的元素。(其实也可以理解为一个找边界的过程,只不过找的是即将发生缺失的边界,也就是最终right的值就是最后一个正常的元素,它的下一个元素就不正常了)。


    今天关于剑指Offer刷题的总结分享就到这了,后序会继续更新总结,一起加油刷题!最后如果觉得还总结的不错的话,还请帮忙点点赞呢!🥰🥰🥰
    在这里插入图片描述

  • 相关阅读:
    element ui 中 el-button重新渲染后disabled属性失效
    PyTorch 之 Dataset 类入门学习
    Redis数据库安装(Windows)
    压六类双绞线网线水晶头,
    TCP Reno/Westwood 的效率和公平
    自己实现 SpringMVC 底层机制 系列之-实现任务阶段 7- 完成简单视图解析
    Yukon对气象观测数据的处理方法
    @FeignClient(contextId = “remoteLogService“, value = ServiceNameConstants.UPMS)
    医院药品管理系统丨医药商城系统(Java+Web+MySQL)
    8位ADC模板实例
  • 原文地址:https://blog.csdn.net/qq_61688804/article/details/126282188