• Leetcode 20有效的括号、33搜索旋转排序数组

    Top1：Leetcode 20有效的括号

    官方题解：https://leetcode.cn/problems/valid-parentheses/solution/you-xiao-de-gua-hao-by-leetcode-solution/
    题目描述：
    给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

    有效字符串需满足：

    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。

    示例 1：
    输入：s = “()”
    输出：true

    示例 2：
    输入：s = “()[]{}”
    输出：true

    示例 3：
    输入：s = “(]”
    输出：false

    示例 4：
    输入：s = “([)]”
    输出：false

    示例 5：
    输入：s = “{[]}”
    输出：true

    一、双端队列实现堆，实际用来储存左括号，新建一个map的key是右括号，value是左括号。

    每次碰到存在右括号map.containsKey(ch)的时候，判断堆顶元素是否为对应左括号，即value值，return 弹出stack.pop()。else就stack.push(ch)。最后返回stack是否为空。

    • 时间复杂度：O（n）。n为字符串长度
    • 空间复杂度：O(n+∣Σ∣)，其中 \SigmaΣ 表示字符集，本题中字符串只包含 66 种括号，|\Sigma| = 6∣Σ∣=6。栈中的字符数量为 O(n)O(n)，而哈希表使用的空间为 O(|\Sigma|)O(∣Σ∣)，相加即可得到总空间复杂度。

    可通过完整代码：

    public boolean isValid(String s) {
    int n = s.length();
    if (n % 2 == 1) return false;   // 剪枝，减少无用循环
    Map<Character, Character> map = new HashMap<Character, Character>() {   // <>里面不写类型会报错
        {
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }
    };
    Deque<Character> stack = new LinkedList<>();   // 双端队列实现堆【双端队列的peek和pop都是顶上那个、入队First那个】（先进后出，堆东西【刚开始的都被堆到下面了】）
    for (int i = 0; i < n; i++) {   // 碰到{[]}的情况时，第一步[已经加进去了，后面直接判断stack堆顶是否存在（或堆是否为空就行了）
        char ch = s.charAt(i);
        if (map.containsKey(ch)) {
            if (stack.isEmpty() || stack.peek() != map.get(ch)) return false;   // 如果不是相同的类型，或者栈中并没有左括号，那么字符串 s 无效
//                if (stack.peek() != map.get(ch)) return false;   // 【不判stack堆为空，只判断堆顶也可以】
            stack.pop();
        } else {
            stack.push(ch);
        }
    }
    return stack.isEmpty();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    在这里插入图片描述

    Top2：Leetcode 33搜索旋转排序数组

    官方题解：添加链接描述
    题目描述：
    整数数组 nums 按升序排列，数组中的值 互不相同 。

    在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

    给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

    你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

    示例 1：
    输入：nums = [4,5,6,7,0,1,2], target = 0
    输出：4

    示例 2：
    输入：nums = [4,5,6,7,0,1,2], target = 3
    输出：-1

    示例 3：
    输入：nums = [1], target = 0
    输出：-1

    二分查找。nums[0] <= nums[mid]为左有序，例：【456 7 8 123】。else为右有序

    • 时间复杂度：O（logn）。其中 n 为nums 数组的大小。整个算法时间复杂度即为二分查找的时间复杂度 O(logn)。
    • 空间复杂度：O（1）。我们只需要常数级别来存放变量。直接对数组 nums1 原地修改，不需要额外空间。

    可通过完整代码：

    public int search(int[] nums, int target) {   // [3, 1]
    int n = nums.length;
    if (n == 0) return -1;
    if (n == 1) return nums[0] == target ? 0 : -1;   // 二分法需要先n至少为2
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (nums[mid] == target) return mid;
        if (nums[0] <= nums[mid]) {   // 左有序【456 7 8 123】
            if (nums[0] <= target && target < nums[mid]) r = mid - 1;
            else l = mid + 1;   // 相等的情况前第3行，此时已经排除了
        } else {   // 右有序【78 12 3 45】
            if (nums[mid] < target && target <= nums[n - 1]) l = mid + 1;
            else r = mid - 1;
        }
    }
    return -1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    在这里插入图片描述

    Top3：Leetcode 88合并两个有序数组（nums1长度为m+n）

    官方题解：https://leetcode.cn/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetco-rrb0/
    题目描述：
    给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

    请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

    注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

    示例 1：
    输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
    输出：[1,2,2,3,5,6]
    解释：需要合并 [1,2,3] 和 [2,5,6] 。
    合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

    示例 2：
    输入：nums1 = [1], m = 1, nums2 = [], n = 0
    输出：[1]
    解释：需要合并 [1] 和 [] 。
    合并结果是 [1] 。

    示例 3：
    输入：nums1 = [0], m = 0, nums2 = [1], n = 1
    输出：[1]
    解释：需要合并的数组是 [] 和 [1] 。
    合并结果是 [1] 。
    注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

    一、逆向双指针。比较nums1[p1]和nums2[p2]的大小，选择放置到nums1[tail--]的元素。一方p1或p2为-1的时候，直接tail-- = p1--或者tail-- = p2--元素就放完了。

    例：只有两个元素1和2，首先比较放置nums1[tail–] = 2；接着判断p2==-1【不止2个元素的时候就逐渐！=-1加入p1】，防止nums1[tail–] = 1结束

    • 时间复杂度：O（m+n）。一次遍历
    • 空间复杂度：O（1）。常数级空间复杂度

    可通过完整代码：

    public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1, p2 = n - 1;
    int tail = m + n - 1;
    int cur;
    while (p1 >= 0 || p2 >= 0) {   // 假设各有一个元素：比较1 2放置后2的下标变为-1，nums1[tail--] = cur = nums[0--]
        if (p1 == -1) {
            cur = nums2[p2--];
        } else if (p2 == -1) {
            cur = nums1[p1--];
        } else if (nums1[p1] > nums2[p2]) {
            cur = nums1[p1--];
        } else {
            cur = nums2[p2--];
        }
        nums1[tail--] = cur;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    在这里插入图片描述

    Top4：Leetcode 160相交链表

    官方题解：https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/
    题目描述：
    给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

    图示两个链表在节点 c1 开始相交：
    在这里插入图片描述

    一、双指针。走一步由pA变为pA.next。相交的话，当都走了a+b+c之后就会在相交结点相遇

    二、走完各自，因为是从头结点开始，所以走到pA=null之后；继续指向headB的头节点，开始走B的长度

    不相交的话都会变成空值，无论m是否=n，走完m+n后，都会出现pA=pA.next【此时如果不相等，pA已经指向pB上的某个节点了】=null，pB=pB.next【同理】=null的情况，return pA=null

    在这里插入图片描述

    • 时间复杂度：O（m+n）。其中 m 和 n 是分别是链表headA 和 headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。
    • 空间复杂度：O（1）。

    可通过完整代码：

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    while (pA != pB) {   // 走一步由pA变为pA.next
        pA = pA == null ? headB : pA.next;   // 因为同时走完了a+b+c，正好到c的第一个节点，即相交点
        pB = pB == null ? headA : pB.next;   // 例题：都走完a+b+c=8步之后，都到相交点的前一个node
    }
    return pA;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    在这里插入图片描述

    Top5：Leetcode 54螺旋矩阵

    官方题解：https://leetcode.cn/problems/spiral-matrix/solution/luo-xuan-ju-zhen-by-leetcode-solution/
    题目描述：
    给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
    在这里插入图片描述

    一、按层模拟。定义两条线段的端点：left，right；top，bottom。最好画出四个点，注意扫描的for循环边界条件

    在这里插入图片描述

    在这里插入图片描述

    二、横，竖扫描完之后，再使用<左扫上扫防止重复扫描

    在这里插入图片描述

    • 时间复杂度：O（mn）。
    • 空间复杂度：O（1）。除了输出数组以外，空间复杂度是常数。【输出数组不算进计算空间复杂度里面去】

    可通过完整代码：

    public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> order = new ArrayList<>();
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return order;
    int rows = matrix.length, columns = matrix[0].length;   // 行和列
    int left = 0, right = columns - 1, top = 0, bottom = rows - 1;   // 定义两个边的四个点下标
    while (left <= right && top <= bottom) {   // 有等号，因为会出现奇数，只剩下最中间一个的情况
        for (int column = left; column <= right; column++) {
            order.add(matrix[top][column]);
        }
        for (int row = top + 1; row <= bottom; row++) {
            order.add(matrix[row][right]);
        }
        if (left < right && top < bottom) {   // 使用<防止重复扫描
            for (int column = right - 1; column > left; column--) {   // 最短的一条，不包括left
                order.add(matrix[bottom][column]);
            }
            for (int row = bottom; row > top; row--) {   // 从底到次顶
                order.add(matrix[row][left]);
            }
        }
        left++;
        right--;
        top++;
        bottom--;
    }
    return order;
}

    • 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

    在这里插入图片描述

    Top6：Leetcode 415字符相加（不能直接转Int）

    官方题解：https://leetcode.cn/problems/add-strings/solution/zi-fu-chuan-xiang-jia-by-leetcode-solution/
    题目描述：
    给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

    你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

    示例 1：
    输入：num1 = “11”, num2 = “123”
    输出：“134”

    示例 2：
    输入：num1 = “456”, num2 = “77”
    输出：“533”

    示例 3：
    输入：num1 = “0”, num2 = “0”
    输出：“0”

    一、使用线程安全的StringBuffer 来存答案，尽量写的代码少。使用中间变量int x = i < 0 ? 0 : num1.charAt(i--) - '0'; // 因为有j--所以i最小到-1x，y来，最后一次循环可以多一个add！=0。

    使用-‘0’来计算字符表示的数字而不是直接转

    二、加入%，add=/。StringBuffer 的reverse()函数时间复杂度为O（n）

    • 时间复杂度：O（max(len1，len2)）。
    • 空间复杂度：O（1）。除答案外我们只需要常数空间存放若干变量。

    可通过完整代码：

    public String addStrings(String num1, String num2) {
    StringBuffer ans = new StringBuffer();
    int i = num1.length() - 1, j = num2.length() - 1;
    int add = 0;
    while (i >= 0 || j >= 0 || add != 0) {   // 最后都加完如果还有进位也会执行add！=0
        int x = i < 0 ? 0 : num1.charAt(i--) - '0';   // 因为有j--所以i最小到-1
        int y = j < 0 ? 0 : num2.charAt(j--) - '0';
        int result = x + y + add;
        ans.append(result % 10);
        add = result / 10;
    }
    ans.reverse();
    return ans.toString();   // 转为String类返回
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    在这里插入图片描述

    Stringbuffer的reverse()函数源码：

    j = (n-1) >> 1   // 下标除以2

    • 1

    可以看出源码中

    • j = (n-1) >> 1：//j为对应从数组中心开始向左遍历的下标。中间和firstEnd
    • k = n - j：//k为对应从数组中心开始向右遍历的下标。中间和secondStart

    时间复杂度: O(n), 空间复杂度: O(1)
    其代码如下：

    public AbstractStringBuilder reverse() {
    boolean hasSurrogates = false;
    //count为字符串长度
    int n = count - 1;
    //j的初始值是数组长度/2
    for (int j = (n-1) >> 1; j >= 0; j--) {
    //j为对应从数组中心开始向左遍历的下标
    //k为对应从数组中心开始向右遍历的下标
        int k = n - j;
        //将value[j]与value[k]元素互换
        char cj = value[j];
        char ck = value[k];
        value[j] = ck;
        value[k] = cj;
        if (Character.isSurrogate(cj) ||
            Character.isSurrogate(ck)) {
            hasSurrogates = true;
        }
    }
    if (hasSurrogates) {
        reverseAllValidSurrogatePairs();
    }
    return this;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    参考链接：StringBuilder的Reverse()方法源码

  • 相关阅读:
    【历史上的今天】7 月 21 日：施乐退出计算机市场；《世界版权公约》制定；苹果推出 Apple Airport
    冯诺依曼体系各硬件工作原理解析
    vue 添加NProgress进度条插件
    Linux Ubuntu安装配置教程
    Galaxy生信云平台|制作临床信息表/三线表/Table 1
    C代码创建多通道WAV音频文件
    31年前的Beyond演唱会，是如何超清修复的？
    Transmit ：macOS 好用的 Ftp/SFtp 工具
    Playwright for Python：基础用法
    力扣数据库题
  • 原文地址：https://blog.csdn.net/m0_46378271/article/details/125914384