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

这篇具有很好参考价值的文章主要介绍了《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_3。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_3,Leetcode,笔记,java,leetcode

😍😍😍 相知

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

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

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

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

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

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

🙌🙌🙌 相识

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

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

😢😢😢 开始刷题

1. LCR 138. 有效数字——表示数值的字符串

题目跳转:https://leetcode.cn/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/description/

边界条件很多

学会函数:

  1. s = s.trim();
  2. char[] res = s.toCharArray();
class Solution {
    public boolean isNumber(String s) {
        if (s == null || s.length() == 0) return false;
        //去掉首尾空格
        s = s.trim();
        boolean numFlag = false;
        boolean dotFlag = false;
        boolean eFlag = false;
        for (int i = 0; i < s.length(); i++) {
            //判定为数字,则标记numFlag
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                numFlag = true;
                //判定为.  需要没出现过.并且没出现过e
            } else if (s.charAt(i) == '.' && !dotFlag && !eFlag) {
                dotFlag = true;
                //判定为e,需要没出现过e,并且出过数字了
            } else if ((s.charAt(i) == 'e' || s.charAt(i) == 'E') && !eFlag && numFlag) {
                eFlag = true;
                numFlag = false;//为了避免123e这种请求,出现e之后就标志为false
                //判定为+-符号,只能出现在第一位或者紧接e后面
            } else if ((s.charAt(i) == '+' || s.charAt(i) == '-') 
            && (i == 0 || s.charAt(i - 1) == 'e' || s.charAt(i - 1) == 'E')) {

                //其他情况,都是非法的
            } else {
                return false;
            }
        }
        return numFlag;
    }
}

2. LCR 139. 训练计划 I——调整数组顺序使奇数位于偶数前面

题目跳转:https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/description/

class Solution {
    public int[] trainingPlan(int[] actions) {
        if(actions==null)return null;
        if(actions.length==0)return new int[0];
        int slow = 0;
        int fast = 0;
        while(fast<actions.length&&slow<actions.length){
            if(actions[slow]%2==0){
                while(fast<actions.length){
                    if(actions[fast]%2==1){
                        int temp = actions[fast];
                        for(int i = fast;i>slow;i--){
                            actions[i] = actions[i-1];
                        }
                        actions[slow] =temp;
                        
                        break;
                    }
                    else fast++;
                }
            }
            slow++;
            fast++;
            
        }
        return actions;
    }
}

《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_3,Leetcode,笔记,java,leetcode

class Solution {
    public int[] trainingPlan(int[] nums) {
        if(nums == null || nums.length == 0){
            return nums;
        }
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
	        while(left < right && nums[left] % 2 != 0) left++;
	        while(left < right && nums[right] % 2 != 1) right--;
	        int temp = nums[left];
	        nums[left] = nums[right];
	        nums[right] = temp;
        }
        return nums;
    }
}

3. LCR 140. 训练计划 II——链表中倒数第k个节点

题目跳转:https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/description/

/**
 * 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 ListNode trainingPlan(ListNode head, int cnt) {
        if(head==null) return null;
        if(head.next == null) return head;
        ListNode result = head;
        int num = 0;
        while(result!=null){
            num++;
            result = result.next;
        }
        num = num - cnt;
        while(num!=0){
            head = head.next;
            num--;
        }
        return head;
    }
}

来个牛逼的

/**
 * 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 ListNode trainingPlan(ListNode head, int cnt) {
        if(head==null) return null;
        if(head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head;
        for(int i = 0;i<cnt;i++){
            if(fast==null)return null;
            fast = fast.next;
        }
        while(fast!=null){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

4. LCR 141. 训练计划 III——反转链表

题目跳转:https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/description/

/**
 * 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 ListNode trainningPlan(ListNode head) {
        ListNode result = new ListNode(0);
        while(head!=null){
            ListNode temp = head;
            head = head.next;
            temp.next= result.next;
            result.next = temp;
        }
        return result.next;
    }
}

递归
《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_3,Leetcode,笔记,java,leetcode

class Solution {
    public ListNode trainningPlan(ListNode head) {
        if(head==null||head.next==null)return head;
        ListNode temp = trainningPlan(head.next);
        head.next.next = head;
        head.next= null;
        return temp;
    }
}

5. LCR 142. 训练计划 IV——合并两个排序的链表

题目跳转:https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/description/

/**
 * 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 ListNode trainningPlan(ListNode l1, ListNode l2) {
        if(l1==null)return l2;
        if(l2==null)return l1;
        ListNode result = new ListNode();
        ListNode temp = result;
        while(l1!=null||l2!=null){
            if(l1!=null&&l2!=null){
                if(l1.val<l2.val){
                    ListNode res = new ListNode(l1.val);
                    temp.next= res;
                    temp =temp.next;
                    l1 = l1.next;
                }
                else
                {
                    ListNode res = new ListNode(l2.val);
                    temp.next= res;
                    temp =temp.next;
                    l2 = l2.next;
                }
            }
            if(l1==null){
                temp.next =l2;
                break; 
            }
            if(l2==null){
                temp.next =l1;
                break; 
            }
        }
        return result.next;
    }
}

递归思路
我们可以如下递归地定义两个链表里的 merge 操作(忽略边界情况,比如空链表等):

{ l i s t 1 [ 0 ] + m e r g e ( l i s t 1 [ 1 : ] , l i s t 2 ) l i s t 1 [ 0 ] < l i s t 2 [ 0 ] l i s t 2 [ 0 ] + m e r g e ( l i s t 1 , l i s t 2 [ 1 : ] ) o t h e r w i s e \left\{ \begin{array}{ll} list1[0] + merge(list1[1:], list2) & list1[0] < list2[0] \\ list2[0] + merge(list1, list2[1:]) & otherwise \end{array} \right. {list1[0]+merge(list1[1:],list2)list2[0]+merge(list1,list2[1:])list1[0]<list2[0]otherwise

也就是说,两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并。

算法

我们直接将以上递归过程建模,同时需要考虑边界情况。

如果 l1 或者 l2 一开始就是空链表 ,那么没有任何操作需要合并,所以我们只需要返回非空链表。否则,我们要判断 l1l2 哪一个链表的头节点的值更小,然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空,递归结束。

class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = trainningPlan(l1.next, l2);
            return l1;
        } else {
            l2.next = trainningPlan(l1, l2.next);
            return l2;
        }
    }
}

6. LCR 143. 子结构判断——树的子结构

题目跳转:https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/description/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null||B==null)return false;
        if(isSub(A,B))return true;
        if(isSubStructure(A.left, B) || isSubStructure(A.right, B)){
            return true;
        }
        return false;
    }
    public boolean isSub(TreeNode TA,TreeNode TB){
        if(TB==null)return true;
        if(TA==null)return false;
        if(TA.val!=TB.val)return false;
        return isSub(TA.left,TB.left)&&isSub(TA.right,TB.right);
    }
}

7. LCR 144. 翻转二叉树——二叉树的镜像

题目跳转:https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/description/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null)return root;
        if(root.right==null&&root.left==null)return root;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        root.right = mirrorTree(root.right);
        root.left = mirrorTree(root.left);
        return root;
    }

}

8. LCR 145. 判断对称二叉树——对称的二叉树

题目跳转:https://leetcode.cn/problems/dui-cheng-de-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 checkSymmetricTree(TreeNode root) {
        if(root==null)return true;
        if(root.left==null&&root.right==null)return true;
        if(root.right==null||root.left==null)return false;
        return check(root.left,root.right);
    }
    public boolean check(TreeNode A,TreeNode B){
        if(A==null&&B==null)return true;
        if(A==null||B==null)return false;
        if(A.val!=B.val)return false;
        return check(A.left,B.right)&&check(A.right,B.left);
    }
}

9. LCR 146. 螺旋遍历二维数组——顺时针打印矩阵

题目跳转:https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/description/

《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_3,Leetcode,笔记,java,leetcode
算法流程

  • 空值处理: 当 array 为空时,直接返回空列表 [] 即可。
  • 初始化: 矩阵 左、右、上、下 四个边界 l , r , t , b ,用于打印的结果列表 res 。
  • 循环打印: “从左向右、从上向下、从右向左、从下向上” 四个方向循环打印;
    • 根据边界打印,即将元素按顺序添加至列表 res 尾部;
    • 边界向内收缩 1 (代表已被打印);
    • 判断边界是否相遇(是否打印完毕),若打印完毕则跳出。
  • 返回值: 返回 res 即可。
打印方向 1. 根据边界打印 2. 边界向内收缩 3. 是否打印完毕
从左向右 左边界l ,右边界 r 上边界 t 加 111 是否 t > b
从上向下 上边界 t ,下边界b 右边界 r 减 111 是否 l > r
从右向左 右边界 r ,左边界l 下边界 b 减 111 是否 t > b
从下向上 下边界 b ,上边界t 左边界 l 加 111 是否 l > r
class Solution {
    public int[] spiralArray(int[][] array) {
        if(array.length == 0) return new int[0];
        int l = 0, r = array[0].length - 1, t = 0, b = array.length - 1, x = 0;
        int[] res = new int[(r + 1) * (b + 1)];
        while(true) {
            for(int i = l; i <= r; i++) res[x++] = array[t][i]; // left to right
            if(++t > b) break;
            for(int i = t; i <= b; i++) res[x++] = array[i][r]; // top to bottom
            if(l > --r) break;
            for(int i = r; i >= l; i--) res[x++] = array[b][i]; // right to left
            if(t > --b) break;
            for(int i = b; i >= t; i--) res[x++] = array[i][l]; // bottom to top
            if(++l > r) break;
        }
        return res;
    }
}

按层模拟:
《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_3,Leetcode,笔记,java,leetcode

class Solution {
    public int[] spiralArray(int[][] array) {
        if (array == null || array.length == 0 || array[0].length == 0) {
            return new int[0];
        }
        int rows = array.length, columns = array[0].length;
        int[] order = new int[rows * columns];
        int index = 0;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                order[index++] = array[top][column];
            }
            for (int row = top + 1; row <= bottom; row++) {
                order[index++] = array[row][right];
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    order[index++] = array[bottom][column];
                }
                for (int row = bottom; row > top; row--) {
                    order[index++] = array[row][left];
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }
}

复杂度分析

  • 时间复杂度:O(mn),其中 m 和 n 分别是输入二维数组的行数和列数。二维数组中的每个元素都要被访问一次。

  • 空间复杂度:O(1)。除了输出数组以外,空间复杂度是常数。


10. LCR 147. 最小栈——包含min函数的栈

题目跳转:https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/description/文章来源地址https://www.toymoban.com/news/detail-834791.html

class MinStack {

    /** initialize your data structure here. */
    int minstack = Integer.MAX_VALUE;;
    Stack<Integer> stack;
    public MinStack() {
        stack = new Stack<Integer>();
    }
    
    public void push(int x) {
        stack.push(minstack);
        minstack = x<minstack?x:minstack;
        stack.push(x);
    }
    
    public void pop() {
        stack.pop();
        minstack = stack.pop();

    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minstack;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

到了这里,关于《剑指Offer》笔记&题解&思路&技巧&优化 Java版本——新版leetcode_Part_3的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 剑指offer题解合集——Week3day6

    题目链接:栈的压入、弹出序列 AC代码 思路: 整体思路 题目链接:不分行从上往下打印二叉树 AC代码 思路: 整体思路

    2024年01月19日
    浏览(44)
  • 剑指offer刷题笔记-链表

    少年何妨梦摘星 敢挽桑弓射玉衡 解决与链表相关的问题总是有大量的指针操作,而指针操作的代码总是容易出错的。很多面试官喜欢出与链表相关的问题,就是想通过指针操作来考察应聘者的编码功底。 题目链接 来自于 AcWing 、 Leetcode (LCR) 目录  从尾到头打印链表 题目

    2024年02月21日
    浏览(35)
  • 剑指offer刷题笔记--Num21-30

    目录 1--调整数组顺序使奇数位于偶数前面(21) 2--链表中倒数第 k 个节点(22) 3--反转链表(24) 4--合并两个排序的链表(25) 5--树的子结构(26) 6--二叉树的镜像(27) 7--对称的二叉树(28) 8--顺时针打印矩阵(29) 9--包含min函数的栈(30) 主要思路:         双指针

    2024年02月12日
    浏览(41)
  • Java 动态规划 剑指 Offer 47. 礼物的最大价值

     代码展示:         进行动态规划的五个步骤:         1.状态表示                 dp[i][j]表示从起点到[i][j]这个位置上能获得礼物的最大价值         2.状态转移方程                 我们分析距离[i][j]最近的位置,根据题意我们到达[i][j]位置只能从[i-1][j]向下移动或

    2024年02月13日
    浏览(39)
  • 【剑指offer刷题记录 java版】数组双指针 之 其它题目

    本系列文章记录labuladong的算法小抄中剑指offer题目 题目链接:https://leetcode.cn/problems/XltzEq/ 题目链接:https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/ 题目链接:https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/ 题目链接:https://leetcode.cn/problems/he-wei-sde-

    2024年02月11日
    浏览(46)
  • 【剑指offer刷题记录 java版】数组双指针 之 滑动窗口

    本系列文章记录labuladong的算法小抄中剑指offer题目 题目链接:https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/ 题目链接:https://leetcode.cn/problems/MPnaiL/ 题目链接:https://leetcode.cn/problems/VabMRr/ 题目链接:https://leetcode.cn/problems/wtcaE1/ 题目链接:https://leetcode.cn/pr

    2024年02月09日
    浏览(50)
  • 【LeetCode】剑指 Offer Ⅱ 第1章:整数(5道题) -- Java Version

    题库链接 :https://leetcode.cn/problem-list/e8X3pBZi/ 题目 解决方案 剑指 Offer II 001. 整数除法 快速除 ⭐ 剑指 Offer II 002. 二进制加法 模拟:StringBuilder ⭐ 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数 动规:res[i] = res[i (i-1)] + 1 ⭐ 剑指 Offer II 004. 只出现一次的数字 位运算:按位取模

    2024年02月15日
    浏览(59)
  • 【LeetCode】剑指 Offer Ⅱ 第8章:树(12道题) -- Java Version

    题库链接 :https://leetcode.cn/problem-list/e8X3pBZi/ 类型 题目 解决方案 二叉树的深搜 剑指 Offer II 047. 二叉树剪枝 递归(深搜):二叉树的后序遍历 (⭐) 剑指 Offer II 048. 序列化和反序列化二叉树 递归(深搜):二叉树的前序遍历(⭐) 剑指 Offer II 049. 从根节点到叶节点的路径

    2024年02月06日
    浏览(46)
  • 剑指 Offer 33. 二叉搜索树的后序遍历序列(java解题)

    目录 1. 题目 2. 解题思路 3. 数据类型功能函数总结 4. java代码 5. 踩坑小记 递归调用,显示 StackOverflowError 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二

    2023年04月22日
    浏览(39)
  • 【LeetCode】剑指 Offer Ⅱ 第5章:哈希表(6道题) -- Java Version

    题库链接 :https://leetcode.cn/problem-list/e8X3pBZi/ 类型 题目 解决方案 哈希表的设计 剑指 Offer II 030. 插入、删除和随机访问都是O(1) 的容器 HashMap + ArrayList ⭐ 剑指 Offer II 031. LRU 缓存 HashMap + 双向链表 ⭐ 哈希表的应用 剑指 Offer II 032. 有效的变位词 哈希表:数组模拟哈希表 ⭐ 剑指

    2024年02月10日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包