当前位置: 首页 > news >正文

【LeetCode热题100】打卡第44天:倒数第30~25题

文章目录

  • 【LeetCode热题100】打卡第44天:倒数第30~25题
    • ⛅前言
  • 移动零
    • 🔒题目
    • 🔑题解
  • 寻找重复数
    • 🔒题目
    • 🔑题解
  • 二叉树的序列化与反序列化
    • 🔒题目
    • 🔑题解
  • 最长递增子序列
    • 🔒题目
    • 🔑题解
  • 删除无效括号
    • 🔒题目
    • 🔑题解

【LeetCode热题100】打卡第44天:倒数第30~25题

⛅前言

大家好,我是知识汲取者,欢迎来到我的LeetCode热题100刷题专栏!

精选 100 道力扣(LeetCode)上最热门的题目,适合初识算法与数据结构的新手和想要在短时间内高效提升的人,熟练掌握这 100 道题,你就已经具备了在代码世界通行的基本能力。在此专栏中,我们将会涵盖各种类型的算法题目,包括但不限于数组、链表、树、字典树、图、排序、搜索、动态规划等等,并会提供详细的解题思路以及Java代码实现。如果你也想刷题,不断提升自己,就请加入我们吧!QQ群号:827302436。我们共同监督打卡,一起学习,一起进步。

博客主页💖:知识汲取者的博客

LeetCode热题100专栏🚀:LeetCode热题100

Gitee地址📁:知识汲取者 (aghp) - Gitee.com

题目来源📢:LeetCode 热题 100 - 学习计划 - 力扣(LeetCode)全球极客挚爱的技术成长平台

PS:作者水平有限,如有错误或描述不当的地方,恳请及时告诉作者,作者将不胜感激

移动零

🔒题目

原题链接:283.移动零

image-20230724115111666

🔑题解

  • 解法一:暴力枚举即可

    但是我们使用copyOfRange方法存在一个弊端,它会重现创建一个数组,然后将值赋值给新的数组引用,给不是在原有的数组引用上进行赋值,所以这里就导致最终无法修改到我们要实现效果的数组

    image-20230724135719319

    image-20230724140037859

    下方代码,最终输出的nums全部是 0

    /*** @author ghp* @title* @description*/
    class Solution {public void moveZeroes(int[] nums) {List<Integer> list = new ArrayList<>();for (int i = 0; i < nums.length; i++) {if (nums[i] != 0){list.add(nums[i]);}}Arrays.fill(nums, 0);nums =  Arrays.copyOfRange(list.stream().mapToInt(Integer::intValue).toArray(),0, nums.length);}
    }
    

    复杂度分析:

    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( n ) O(n) O(n)

    其中 n n n 为数组中元素的个数

    解决方法:使用for循环,逐个赋值(这里我就是使用lambda表达式实现,效果都是一样的,但是这种更加优雅)

    /*** @author ghp* @title* @description*/
    class Solution {public void moveZeroes(int[] nums) {List<Integer> list = new ArrayList<>();for (int i = 0; i < nums.length; i++) {if (nums[i] != 0) {list.add(nums[i]);}}Arrays.fill(nums, 0);IntStream.range(0, list.size()).forEach(i -> nums[i] = list.get(i));}
    }
    
  • 解法二:双指针

    这个思路是非类似于快排的那个划分左右区间,设置两个指针,使得左区间都比主元小,右区间都比主元大或等。

    这里我们相当于是把0当作主元,左区间都是不等于0的,右区间都是等于0的

    class Solution {public void moveZeroes(int[] nums) {int i = 0;// 遍历数组,将非0元素放到i的左侧for (int j = 0; j < nums.length; j++) {if (nums[j] != 0){// 当前元素不等于0,将非0元素放到i的左侧int t = nums[j];nums[j] = nums[i];nums[i] = t;i++;}}}
    }
    

    复杂度分析:

    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    其中 n n n 为数组中元素的个数

寻找重复数

🔒题目

原题链接:287.寻找重复数

image-20230724141701908

🔑题解

本题总共有以下解法:

  1. 需要额外空间,需要修改原始数组:排序

  2. 需要额外空间,不需要修改原始数组:计数法、哈希表

  3. 不需要额外空间,需要修改原始数组:标记法、索引排序

  4. 不需要额外空间,不需要修改原始数组:暴力枚举、二分查找、位运算、快慢指针

PS:本文只讲解了二分查找、快慢指针、位运算三种能过且比较牛的方法,关于其它方法感兴趣都可以参考这篇文章:9种方法(可能是目前最全的),拓展大家思路 - 寻找重复数 - 力扣(LeetCode)

  • 解法一:快慢指针(Floyd 判圈算法)

    这个算法在前面已经多次遇到了,比如:第33天的环形链表、第34天的排序链表、第35天的相交链表、第40天的回文链表等都能看到快慢指针算法的身影。可能我们一下子无法直接联想到环形链表,这里我们画一个草图,将数组转换成一个环形链表(这是一种数学抽象,类似于七桥问题,把一个问题抽象成另一个与之等价的问题)

    image-20230724151309729

    我们把数值的值当成链表的下一个节点,这个值与索引进行一个映射,从而可以通过上面的链表得到下面这个链表,此时我们把”要数组中的找重复元素“这个问题转换成"要找链表中环的入口节点",说到这里,如果你对环形链表这一题有经验的话,很快就能够解决了。如果你对环形链表不是很懂的话,可以参考这篇文章【LeetCode热题100】打卡第33天:环形链表

    image-20230724151314590

    注意:本题能够使用快慢指针的前提是 1 < = n u m s [ i ] < = n 1<=nums[i]<=n 1<=nums[i]<=n,这样能够保障指针无论如何移动都不会出现索引越界

    这里初略讲解以下如何定位环形链表的入环节点:

    1. 第一次遍历,fast比slow多走一步,寻找到fast和slow相等的节点,然后将fast重置到起始节点
    2. 第二次遍历,fast和slow走相同的步数,寻找到fast和slow相等的节点,此时fast和slow相遇的节点就是入环节点

    至于详细证明思路,可以参考我上面给出的那个链接,链接的那篇文章中已给出比较详细的解答了

    /*** @author ghp* @title* @description*/
    class Solution {public int findDuplicate(int[] nums) {int fast = 0, slow = 0;do {fast = nums[nums[fast]];slow = nums[slow];} while (fast != slow);fast = 0;while (fast != slow) {fast = nums[fast];slow = nums[slow];}return fast;}
    }
    

    复杂度分析:

    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    其中n为数组中元素的个数

  • 解法二:二分查找

    本题主要用到了抽屉原理,简单来说就是把 10 个苹果放进 9 个抽屉,至少有一个抽屉里至少放 2 个苹果。

    其此我们还需要寻找出有序的地方,本题有序的地方是隐式的,即比当前元素小的元素是有序的,只要发现这一点,其实就会变得很简单,但往往这一点一般很慢发现,这也是本题相较于其他显示有序的一个难点

    我们新增一个变量cnt[i]来记录当前数组中小于等于i的数有多少个,然后可以的发现cnt数组是有序的,对于有序数组我们

    ①如果我们将n个数放到n个位置上(数的范围是1~n),这些数不重复,则此时 cnt==mid

    image-20230724173301756

    ②如果我们将n个数放到n+1个位置上(数的范围是1~n),这些数不重复,如果此时 cnt<=mid,则说明重复的数一定在左侧区间,因为数是在1~n这个区间选的,cnt[n]<=mid说明比n小的数不到一半(正常情况是刚好一半的),根据抽屉原理,一定是有一个比mid小的数重复了,这样才会出现cnt[n]<=mid,所以重复的数在mid的左侧

    image-20230724184445756

    ③如果我们将n个数放到n+1个位置上,如果是左侧的数多了,则会导致cnt[n]>mid,此时我们可以在左侧区间寻找

    image-20230724185558331

    温馨提示:对于所有的二分查找,边界值都是需要十分注意的,这个我在以前总结的二分查找中就已经进行了详细讲解,这里我也不在赘述了,直接给出结论,如果想要了解的,可以参考我以前写的一篇关于二分查找边界值问题的总结

    1. 对于向下取整mid = (right-left)/2 + left ,如果取等 while(left<=right),那么目标值在右right=mid-1,目标值在左left=mid+1

    2. 对于向下取整mid=(right-left)/2 + left,如果不取等while(left<right),那么目标值在右right=mid,目标值在左left=mid+1

      如果取等匹配right=mid会导致死循环,如果不取等匹配right=mid-1会出现遗漏导致结果错误

    /*** @author ghp* @title* @description*/
    class Solution {public int findDuplicate(int[] nums) {int left = 1, right = nums.length - 1;while (left < right) {int mid = (right - left) / 2 + left;// 计算当前小于等于mid的元素有多少个int count = 0;for (int i = 0; i < nums.length; i++) {if (nums[i] <= mid){count++;}}if (count > mid){// 比mid小的元素超过了mid个,根据抽屉原理可以知道mid左侧出现了重复元素right = mid;}else{// 比mid小的元素超过了mid个,根据抽屉原理可以知道mid右侧出现了重复元素left = mid + 1;}}return left;}
    }
    

    复杂度分析:

    • 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    其中n为数组中元素的个数

  • 解法三:位运算

    太强了,感兴趣的可以去看LeetCode官网,我先把前面两种解法消化吸收了

    class Solution {public int findDuplicate(int[] nums) {int n = nums.length, ans = 0;int bit_max = 31;while (((n - 1) >> bit_max) == 0) {bit_max -= 1;}for (int bit = 0; bit <= bit_max; ++bit) {int x = 0, y = 0;for (int i = 0; i < n; ++i) {if ((nums[i] & (1 << bit)) != 0) {x += 1;}if (i >= 1 && ((i & (1 << bit)) != 0)) {y += 1;}}if (x > y) {ans |= 1 << bit;}}return ans;}
    }作者:LeetCode-Solution
    链接:https://leetcode.cn/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/
    来源:力扣(LeetCode)
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    

    复杂度分析:

    • 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    其中n为数组中元素的个数

二叉树的序列化与反序列化

🔒题目

原题链接:297.二叉树的序列化与反序列化

image-20230724191312364

🔑题解

  • 解法一:BFS(层序遍历)

    不知道为什么我第一眼看着提感觉挺简单的,直接BFS不就好了吗,结果bug频出,一眨眼一小时就过去了,经过不断的debug最终成功完成了初步代码,并最终过了😄写这题的思路也比较简答, 直接使用BFS实现层序遍历即可

    如果不会层序遍历的话,可以参考这篇文章:【LeetCode热题100】打卡第29天:二叉树的层序遍历

    class Codec {public String serialize(TreeNode root) {if (root == null) {// 防止NPEreturn null;}// 存储每一层的节点的值StringBuilder ans = new StringBuilder(root.val + ",");// BFS层序遍历所有节点,将二叉树所有节点的值转存到ans中Deque<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode pre = queue.poll();TreeNode left = pre.left;if (left != null) {queue.offer(left);}ans.append(left == null ? "null" : left.val).append(",");TreeNode right = pre.right;if (right != null) {queue.offer(right);}ans.append(right == null ? "null" : right.val).append(",");}// 删除最后一个多余的逗号ans.deleteCharAt(ans.length() - 1);return ans.toString();}public TreeNode deserialize(String data) {if (data == null) {// 防止NPEreturn null;}// 将String转成List方便后续逻辑处理String[] dataStr = data.split(",");List<Integer> dataList = Arrays.stream(dataStr).map(str -> str.equals("null") ? null : Integer.valueOf(str)).collect(Collectors.toList());// BFS层序遍历所有节点,将层序遍历的字符串重新构建成一棵二叉树Deque<TreeNode> queue = new LinkedList<>();// 将根节点加入队列中TreeNode root = new TreeNode(dataList.get(0));queue.offer(root);dataList.remove(0);while (!dataList.isEmpty()) {TreeNode node = queue.poll();if (dataList.get(0) != null) {// 这里一定要判空,否则自动拆箱时会报NPE,下面那个判空也是一样的node.left = new TreeNode(dataList.get(0));queue.offer(node.left);}dataList.remove(0);if (dataList.isEmpty()) {// 防止NPEbreak;}if (dataList.get(0) != null) {node.right = new TreeNode(dataList.get(0));queue.offer(node.right);}dataList.remove(0);}return root;}
    }
    

    复杂度分析:

    序列化

    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( n ) O(n) O(n)

    反序列化

    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( n ) O(n) O(n)

    其中 n n n 为二叉树节点的个数

    代码优化

    对于serialize方法:

    1. 每个循环只需要处理一个节点,不需要额外的变量来保存父节点

    对于deserialize方法:

    1. 使用整型数组代替列表,因为在循环中频繁进行插入和删除操作会导致列表的性能下降
    2. 使用索引标记当前节点的位置,避免频繁调用 dataList.get() 方法
    /*** @author ghp* @title* @description*/
    class Codec {public String serialize(TreeNode root) {if (root == null) {return null;}StringBuilder ans = new StringBuilder();Deque<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();if (node != null) {ans.append(node.val).append(",");queue.offer(node.left);queue.offer(node.right);} else {ans.append("null,");}}ans.deleteCharAt(ans.length() - 1);return ans.toString();}public TreeNode deserialize(String data) {if (data == null) {return null;}String[] dataStr = data.split(",");List<Integer> dataList = Arrays.stream(dataStr).map(str -> str.equals("null") ? null : Integer.valueOf(str)).collect(Collectors.toList());Deque<TreeNode> queue = new LinkedList<>();TreeNode root = new TreeNode(dataList.get(0));queue.offer(root);int index = 1;for (; index < dataList.size(); index += 2) {TreeNode node = queue.poll();if (dataList.get(index) != null) {node.left = new TreeNode(dataList.get(index));queue.offer(node.left);}if (index + 1 < dataList.size() && dataList.get(index + 1) != null) {node.right = new TreeNode(dataList.get(index + 1));queue.offer(node.right);}}return root;}
    }
    
  • 解法二:DFS(前序遍历)

    这里主要是通过前序遍历实现

    image-20230724231231663

    1. 序列化实现比较简单,直接DFS搜索即可: [1,2,null,null,3,4,null,null,5,null,null]

    2. 反序列化的时候,第一个元素为根节点,接下来都是按照前序遍历的顺序,先走左边,直到遇到 null 结束,然后换另一边

    整个过程递归进行

    class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
    }/*** @author ghp* @title* @description*/
    class Codec {public String serialize(TreeNode root) {StringBuilder ans = new StringBuilder();dfs(root, ans);ans.deleteCharAt(ans.length() - 1);return ans.toString();}private void dfs(TreeNode root, StringBuilder ans) {if (root == null) {ans.append("null,");return;}ans.append(root.val).append(",");dfs(root.left, ans);dfs(root.right, ans);}public TreeNode deserialize(String data) {String[] dataStr = data.split(",");// 根据前序遍历的结果构建二叉树return buildTree(dataStr);}private int i = 0;private TreeNode buildTree(String[] dataStr) {String value = dataStr[i++];if (value.equals("null")) {// 防止自动拆箱导致NPE,同时也是递归结束条件return null;}TreeNode node = new TreeNode(Integer.valueOf(value));// 构建左子树node.left = buildTree(dataStr);// 构建右子树node.right = buildTree(dataStr);return node;}
    }
    

    复杂度分析:

    序列化

    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( n ) O(n) O(n)

    反序列化

    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( n ) O(n) O(n)

    其中 n n n 为二叉树节点的个数

最长递增子序列

🔒题目

原题链接:300.最长递增子序列

image-20230724231525418

🔑题解

  • 解法一:暴力DFS(超时 22 / 54

    image-20230725131751062

    PS:画的有点丑,但是能看明白就行(●ˇ∀ˇ●)

    /*** @author ghp* @title* @description*/
    public class Solution {public int lengthOfLIS(int[] nums) {// 最长递增子序列的长度int maxLength = 0;// DFS遍历每一个节点for (int i = 0; i < nums.length; i++) {int length = dfs(nums, i, Integer.MIN_VALUE);maxLength = Math.max(maxLength, length);}return maxLength;}private int dfs(int[] nums, int index, int preLen) {if (index == nums.length) {// 达到数组末尾,返回长度为0return 0;}int len1 = 0;if (nums[index] > preLen) {// 当前元素大于前一个元素,可以选择当前元素作为递增子序列的一部分len1 = 1 + dfs(nums, index + 1, nums[index]);}// 不选择当前元素,继续寻找下一个递增子序列int len2 = dfs(nums, index + 1, preLen);// 返回选择当前元素和不选择当前元素中的较长子序列的长度return Math.max(len1, len2);}
    }
    

    复杂度分析:

    • 时间复杂度: O ( 2 n ) O(2^n) O(2n),每一个节点都有选和不选两种情况,所以总的来说是 2 n 2^n 2n
    • 空间复杂度: O ( l o g n ) O(logn) O(logn),空间复杂度为递归的最大深度,最大深度是树的最大高度

    其中 n n n 为数组中元素的个数

    代码优化:时间优化

    我们可以通过记忆化搜索来大幅度提高搜索的速度,我们需要新增一个memo数组,memo[i][j]表示以第i个元素为结尾、且第j个元素为上一个结尾元素的最长递增子序列的长度。

    为了新增一个记忆搜索功能,我们需要对上面代码进行一个微型改造,我们在DFS搜索时,不能像前面一样传递上一个节点的长度,而是需要传递上一个节点的索引,这样我们才能够使用memo数组对当前状态进行标记,下面的示意图是添加了记忆数组之后的搜索

    image-20230725140526859

    通过Debug也可以看出来,每进行一次DFS,都可以直接将当前节点到其它任意节点的距离计算出来,这样就能大幅度进行剪枝了。比如上图,0到1这条路径,就可以计算出0到其它节点(1,0,3,2,3)的距离了,后面的路径0到0、0到3、0到2、0到3就不用再去重新遍历了,而是直接拿我们缓存在memo中的路径

    image-20230725140755759

    public class Solution {public int lengthOfLIS(int[] nums) {int maxLength = 1;// 记录节点的状态 memo[i][j]表示索引为j的节点到索引为i的节点的最长递增节点数int[][] memo = new int[nums.length][nums.length];// DFS搜索每一个节点for (int i = 0; i < nums.length; i++) {maxLength = Math.max(maxLength, dfs(nums, i, i, memo));}return maxLength;}private int dfs(int[] nums, int curIndex, int preIndex, int[][] memo) {if (curIndex >= nums.length) {// 后面已经没有节点了,结束搜索return 0;}if (memo[curIndex][preIndex] > 0) {// preIndex到curIndex这个状态已计算过,直接返回return memo[curIndex][preIndex];}int len1 = 0;if (preIndex == curIndex || nums[curIndex] > nums[preIndex]) {// 当前元素大于前一个元素,可以选择当前元素作为递增子序列的一部分len1 = 1 + dfs(nums, curIndex + 1, curIndex, memo);}// 不选择当前元素,继续寻找下一个递增子序列int len2 = dfs(nums, curIndex + 1, preIndex, memo);// 缓存preIndex到curIndex这个状态memo[curIndex][preIndex] = Math.max(len1, len2);// 返回选择当前元素和不选择当前元素中的较长子序列的长度return memo[curIndex][preIndex];}
    }
    

    记忆搜索是经典的拿时间换空间,时间复杂度虽然没有变,但是却大大缩减了搜索结果的时间,空间复杂度提高了

    复杂度分析:

    • 时间复杂度: O ( 2 n ) O(2^n) O(2n),每一个节点都有选和不选两种情况,所以总的来说是 2 n 2^n 2n
    • 空间复杂度: O ( n 2 ) O(n^2) O(n2),memo占用 n 2 n^2 n2的空间

    其中 n n n 为数组中元素的个数

    备注:将 memo[curIndex][preIndex] 转换为 memo[preIndex][curIndex] 是不可行的。这是因为 preIndex 的值是固定的,是遍历时的前一个索引,而 curIndex 是在不断递增变化的。

    如果我们将 memo[curIndex][preIndex] 转换为 memo[preIndex][curIndex],则无法正确存储和查找子问题的解决方案。由于 curIndex 不断增加,我们无法准确地映射到递归调用中的子问题。

    代码优化:空间优化

    我们可以发现memo每进行一次DFS都只用到了一列的数据,所以我们完全可以将二维的memo压缩为一维的memo

    public class Solution {public int lengthOfLIS(int[] nums) {int maxLength = 1;int[] memo = new int[nums.length];Arrays.fill(memo, 1);for (int i = 0; i < nums.length; i++) {maxLength = Math.max(maxLength, dfs(nums, i, memo));}return maxLength;}private int dfs(int[] nums, int curIndex, int[] memo) {if (curIndex >= nums.length) {return 0;}if (memo[curIndex] > 1) {return memo[curIndex];}int maxLen = 1;for (int i = curIndex + 1; i < nums.length; i++) {if (nums[i] > nums[curIndex]) {maxLen = Math.max(maxLen, 1 + dfs(nums, i, memo));}}memo[curIndex] = maxLen;return maxLen;}
    }
    

    复杂度分析:

    • 时间复杂度: O ( n 2 ) O(n^2) O(n2),每一个节点都有选和不选两种情况,所以总的来说是 2 n 2^n 2n
    • 空间复杂度: O ( n ) O(n) O(n),memo占用 n n n的空间

    其中 n n n 为数组中元素的个数

  • 解法二:动态规划

    我们需要构建一个dp[i]dp[i]表示以nums[i]结尾的最长递增子序列的长度,此时我们可以知道 当前第i个节点结尾的最长递增子序列,一定是由前面的节点转移而来的,至于是前面哪一个节点,我们无法直接确定,所以此时需要遍历 前面 i+1个节点,在遍历的同时,我们不断更新当前的 dp[i],遍历完毕,即可得到当前最大长度。

    不知道为什么感觉动态规划比前面的DFS要简单多了

    import java.util.Arrays;/*** @author ghp* @title* @description*/
    public class Solution {public int lengthOfLIS(int[] nums) {if (nums.length == 0) {return 0;}int maxLength = 1;int[] dp = new int[nums.length];// 每一个节点自身的初始长度都是1Arrays.fill(dp, 1);// 遍历每一个节点for (int i = 1; i < nums.length; i++) {// 遍历0~i之间的节点,计算出所有以当前nums[i]结尾的最长递增子序列的长度for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}maxLength = Math.max(maxLength, dp[i]);}return maxLength;}
    }
    

    复杂度分析:

    • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
    • 空间复杂度: O ( n ) O(n) O(n)

    其中 n n n 为数组中元素的个数

  • 解法三:动态规划+二分查找

    来自:300. 最长递增子序列(动态规划 + 二分查找,清晰图解) - 最长递增子序列 - 力扣(LeetCode)

    class Solution {public int lengthOfLIS(int[] nums) {int len = 1, n = nums.length;if (n == 0) {return 0;}int[] d = new int[n + 1];d[len] = nums[0];for (int i = 1; i < n; ++i) {if (nums[i] > d[len]) {d[++len] = nums[i];} else {int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大,此时要更新 d[1],所以这里将 pos 设为 0while (l <= r) {int mid = (l + r) >> 1;if (d[mid] < nums[i]) {pos = mid;l = mid + 1;} else {r = mid - 1;}}d[pos + 1] = nums[i];}}return len;}
    }作者:LeetCode-Solution
    链接:https://leetcode.cn/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
    来源:力扣(LeetCode)
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    

    复杂度分析:

    • 时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
    • 空间复杂度: O ( n ) O(n) O(n)

    其中 n n n 为数组中元素的个数

删除无效括号

先缓缓w(゚Д゚)w,明天在写把,不然今天任务完不成了

🔒题目

原题链接:301.删除无效括号

image-20230725144743877

🔑题解

  • 解法一:暴力

    
    

    复杂度分析:

    • 时间复杂度: O ( n 2 ) O(n^2) O(n2)
    • 空间复杂度: O ( 1 ) O(1) O(1)

    其中 n n n 为数组中元素的个数

  • 解法二:哈希表

    这个太强了,时间复杂度直接变成 O ( n ) O(n) O(n),它是利用Map的Key不能重复的特性,来判断元素是否符合要求。

    
    

    复杂度分析:

    • 时间复杂度: O ( n ) O(n) O(n)
    • 空间复杂度: O ( n ) O(n) O(n)

    其中 n n n 为数组中元素的个数

参考题解

  • 9种方法(可能是目前最全的),拓展大家思路 - 寻找重复数 - 力扣(LeetCode)
  • 使用「二分查找」搜索一个有范围的整数(结合「抽屉原理」) - 寻找重复数 - 力扣(LeetCode)
  • 【图解】dfs + bfs + 后序遍历 + 其他思路 - 二叉树的序列化与反序列化 - 力扣(LeetCode)# 【LeetCode热题100】打卡第44天:倒数第30~25题

相关文章:

【LeetCode热题100】打卡第44天:倒数第30~25题

文章目录 【LeetCode热题100】打卡第44天&#xff1a;倒数第30~25题⛅前言 移动零&#x1f512;题目&#x1f511;题解 寻找重复数&#x1f512;题目&#x1f511;题解 二叉树的序列化与反序列化&#x1f512;题目&#x1f511;题解 最长递增子序列&#x1f512;题目&#x1f5…...

C# 匿名方法和Lambda表达式

一.匿名方法 1.匿名方法的演变 匿名方法是为了简化委托的实现&#xff0c;方便调用委托方法而出现的&#xff0c;同时&#xff0c;匿名方法也是学好lambda表达式的基础。在委托调用的方法中&#xff0c;如果方法只被调用一次&#xff0c;这个时候我们就没有必要创建具名方法&…...

uniapp微信小程序scroll-view滚动scrollLeft不准确

今天在实现微信小程序的一个横向导航的时候出现了一个问题&#xff0c;就是每次滑到滚动条最右边的时候 scrollLeft的值都不准确 原因&#xff1a;因为每次滚动监听事件都会被调用比较耗费资源系统会默认节流&#xff0c;可以在scroll-view 加一个 throttle“{{false}}” 关闭…...

symfony/console

github地址&#xff1a;GitHub - symfony/console: Eases the creation of beautiful and testable command line interfaces 文档地址&#xff1a;The Console Component (Symfony 5.4 Docs) 默认命令list&#xff0c;可以用register注册一个command命令&#xff0c;之后可以…...

OSI模型简介及socket,tcp,http三者之间的区别和原理

1.OSI模型简介&#xff08;七层网络模型&#xff09; OSI 模型(Open System Interconnection model)&#xff1a;一个由国际标准化组织提出的概念模型&#xff0c;试图提供一个使各种不同的计算机和网络在世界范围内实现互联的标准框架。 它将计算机网络体系结构划分为七层,每…...

【leetcode】leetcode69 x的平方根

文章目录 给你一个非负整数 x &#xff0c;计算并返回 x 的 算术平方根 。原理牛顿法&#xff08;数值分析中使用到的&#xff09;:二分法 解决方案java 实现实例执行结果 python 实现实例 给你一个非负整数 x &#xff0c;计算并返回 x 的 算术平方根 。 由于返回类型是整数&…...

springboot与rabbitmq的整合【演示5种基本交换机】

前言&#xff1a; &#x1f44f;作者简介&#xff1a;我是笑霸final&#xff0c;一名热爱技术的在校学生。 &#x1f4dd;个人主页&#xff1a;个人主页1 || 笑霸final的主页2 &#x1f4d5;系列专栏&#xff1a;后端专栏 &#x1f4e7;如果文章知识点有错误的地方&#xff0c;…...

【设计模式】设计原则-单一职责原则

单一职责原则 类的设计原则之单一职责原则&#xff0c;是最常用的类的设计的原则之一。 百度百科&#xff1a;就一个类而言&#xff0c;应该仅有一个引起它变化的原因。应该只有一个职责。 通俗的讲就是&#xff1a;一个类只做一件事 这个解释更通俗易懂&#xff0c;也更符…...

【C++】-多态的底层原理

&#x1f496;作者&#xff1a;小树苗渴望变成参天大树&#x1f388; &#x1f389;作者宣言&#xff1a;认真写好每一篇博客&#x1f4a4; &#x1f38a;作者gitee:gitee✨ &#x1f49e;作者专栏&#xff1a;C语言,数据结构初阶,Linux,C 动态规划算法&#x1f384; 如 果 你 …...

【部署】让你的电脑多出一个磁盘来用!使用SSHFS将远程服务器目录挂载到Windows本地,挂载并共享服务器资源

让你的电脑多出一个磁盘来用&#xff01;---使用SSHFS将远程服务器目录挂载到Windows本地 1. 方法原理介绍2.SSHFS-Win使用教程—实现远程服务器磁盘挂载本地 由于日常主要用 Windows 系统&#xff0c;每次都得 ssh 到服务器上进行取资源&#xff08;本地磁盘不富裕&#xff09…...

/var/lock/subsys目录的作用

总的来说&#xff0c;系统关闭的过程&#xff08;发出关闭信号&#xff0c;调用服务自身的进程&#xff09;中会检查/var/lock/subsys下的文件&#xff0c;逐一关闭每个服务&#xff0c;如果某一运行的服务在/var/lock/subsys下没有相应的选项。在系统关闭的时候&#xff0c;会…...

DETR (DEtection TRansformer)基于自建数据集开发构建目标检测模型超详细教程

目标检测系列的算法模型可以说是五花八门&#xff0c;不同的系列有不同的理论依据&#xff0c;DETR的亮点在于它是完全端到端的第一个目标检测模型&#xff0c;DETR&#xff08;Detection Transformer&#xff09;是一种基于Transformer的目标检测模型&#xff0c;由Facebook A…...

C++初阶 - 5.C/C++内存管理

目录 1.C/C的内存分布 2.C语言中动态内存管理方式&#xff1a;malloc、calloc、realloc、free 3.C内存管理方式 3.1 new/delete操作内置类型 3.2 new 和 delete操作自定义类型 4.operator new 与 operator delete 函数&#xff08;重要点&#xff09; 4.1 operator new 与…...

数学建模学习(3):综合评价类问题整体解析及分析步骤

一、评价类算法的简介 对物体进行评价&#xff0c;用具体的分值评价它们的优劣 选这两人其中之一当男朋友&#xff0c;你会选谁&#xff1f; 不同维度的权重会产生不同的结果 所以找到每个维度的权重是最核心的问题 0.25 二、评价前的数据处理 供应商ID 可靠性 指标2 指…...

【后端面经】微服务构架 (1-5) | 限流:濒临奔溃?限流守护者拯救系统于水火之中!

文章目录 一、前置知识1、什么是限流?2、限流算法A) 静态算法a) 漏桶b) 令牌桶c) 固定窗口d) 滑动窗口B) 动态算法3、限流的模式4、 限流对象4、限流后应该怎么做?二、面试环节1、面试准备2、基本思路3、亮点展现A) 突发流量(针对请求个数而言)B) 请求大小(针对请求大小而言)…...

HDFS异构存储详解

异构存储 HDFS异构存储类型什么是异构存储异构存储类型如何让HDFS知道集群中的数据存储目录是那种类型存储介质 块存储选择策略选择策略说明选择策略的命令 案例&#xff1a;冷热温数据异构存储对应步骤 HDFS内存存储策略支持-- LAZY PERSIST介绍执行使用 HDFS异构存储类型 冷…...

《面试1v1》Kafka消息是采用Pull还是Push模式

&#x1f345; 作者简介&#xff1a;王哥&#xff0c;CSDN2022博客总榜Top100&#x1f3c6;、博客专家&#x1f4aa; &#x1f345; 技术交流&#xff1a;定期更新Java硬核干货&#xff0c;不定期送书活动 &#x1f345; 王哥多年工作总结&#xff1a;Java学习路线总结&#xf…...

Windows环境Docker安装

目录 安装Docker Desktop的步骤 Docker Desktop 更新WSL WSL 的手动安装步骤 Windows PowerShell 拉取&#xff08;Pull&#xff09;镜像 查看已下载的镜像 输出"Hello Docker!" Docker Desktop是Docker官方提供的用于Windows的图形化桌面应用程序&#xff0c…...

Spring 6.0官方文档示例(23): singleton类型的bean和prototype类型的bean协同工作的方法(二)

使用lookup-method: 一、实体类&#xff1a; package cn.edu.tju.domain2;import java.time.LocalDateTime; import java.util.Map;public class Command {private Map<String, Object> state;public Map<String, Object> getState() {return state;}public void …...

Docker Compose 容器编排

Docker compose Docker compose 实现单机容器集群编排管理&#xff08;使用一个模板文件定义多个应用容器的启动参数和依赖关系&#xff0c;并使用docker compose来根据这个模板文件的配置来启动容器&#xff09; 通俗来说就是把之前的多条docker run启动容器命令 转换为docker…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...