hot100（6）

51.22.括号生成

字符串回溯的典型问题

char[] path;
    List<String> res;
    int n;
    public List<String> generateParenthesis(int n) {
        this.n = n;
        path = new char[2*n];
        res = new ArrayList<>();
        dfs(0,0,0);
        return res;
    }
    public void dfs(int index,int left, int right){
        if(index == 2*n){
            res.add(new String(path));
            return ;
        }
        if(left < n){
            path[index] = '(';
            dfs(index + 1,left + 1 , right);
        }
        if(right < left){
            path[index] = ')';
            dfs(index + 1, left, right + 1);
        }
        
    }

52.49. 字母异位词分组 - 力扣（LeetCode）

本题考查哈希思想和字符串的处理

I排序

使用排序后的字符数组作为key，异位词的key相同，使用hashTable将词分组。

注意这里需要用String作为key ，而不能用char数组作为key，原因在于String的equals方法已经实现了基于内容的比较，而char数组的equals方法仍然是基于引用的比较。

public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(str);
            map.put(key,list);
        }
        return new ArrayList<List<String>>(map.values());
    }

时间复杂度O(n*mlogm)

空间复杂度O(n*m)

II统计各个字符串字母个数作为key，进行分组

public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for (String str : strs) {
            int[] cnt = new int[26];
            for(int i = 0 ; i < str.length() ; i++){
                cnt[str.charAt(i) - 'a']++;
            }
            StringBuilder key = new StringBuilder();
            for(int i = 0 ; i < 26 ; i++){
                if(cnt[i] != 0){
                    key.append(i + 'a');
                    key.append(cnt[i]);
                }
            }
            List<String> list = map.getOrDefault(key.toString(),new ArrayList<>());
            list.add(str);
            map.put(key.toString(),list);
        }
        return new ArrayList<List<String>>(map.values());
    }

53.48. 旋转图像 - 力扣（LeetCode）

I 使用辅助数组

原来图像中第i行第j个的像素，在旋转后，它出现在倒数第 i 列的第 j 个位置。

空间复杂度O(n^2)

时间复杂度O(n^2)

public void rotate(int[][] matrix) {
        int[][] newMatrix = new int[matrix.length][matrix[0].length];
        for(int i = 0 ; i < matrix.length ; i++){
            for(int j = 0 ; j < matrix[0].length ; j++){
                newMatrix[j][matrix[0].length - i - 1] = matrix[i][j];
            }
        }
        for(int i = 0 ; i < matrix.length ; i++){
            for(int j = 0 ; j < matrix[0].length ; j++){
                matrix[i][j] = newMatrix[i][j];
            }
        }
    }

II原地旋转

题目中要求我们尝试在不使用额外内存空间的情况下进行矩阵的旋转，也就是说，我们需要「原地旋转」这个矩阵。那么我们如何在方法一的基础上完成原地旋转呢？

public void rotate(int[][] matrix) {
        int row = 0 ,col = 0;
        int length = matrix.length;
        if(matrix.length % 2 == 0){
            row = matrix.length/2;
            col = matrix.length/2;
        }else{
            row = (matrix.length + 1)/2;
            col = (matrix.length - 1)/2;
        }
        for(int i = 0 ; i < row ; i++){
            for(int j = 0 ; j < col ; j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[length - 1 - j][i];
                matrix[length - 1 - j][i] = matrix[length - 1 - i][length - 1 - j];
                matrix[length - 1 - i][length - 1 - j] = matrix[j][length - 1 - i];
                matrix[j][length - 1 - i] = temp;
            }
        }
    }

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(matrix[i][j], matrix[n - i - 1][j]);
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

54.46. 全排列 - 力扣（LeetCode）

关于数组的回溯问题

List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    boolean[] visited;
    public List<List<Integer>> permute(int[] nums) {
        visited = new boolean[nums.length];
        dfs(nums);
        return res;
    }
    public void dfs(int[] nums){
        boolean isAns = true;
        for(int i = 0 ; i < nums.length ; i++){
            if(!visited[i]){
                isAns = false;
                break;
            }
        }
        if(isAns){
            res.add(new ArrayList<>(list));
            return ;
        }
        for(int i = 0 ; i < nums.length ; i++){
            if(visited[i] == false){
                visited[i] = true;
                list.add(nums[i]);
                dfs(nums);
                visited[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }

这里用到visited数组进行剪枝和去重，也可以用set：

List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] nums;
    Set<Integer> set = new HashSet<>();
    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        dfs();
        return res;
    }
    
    public void dfs(){
        if(path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return ; 
        }
        for(int i = 0 ; i < nums.length ; i++){
            if(!set.contains(nums[i])){
                set.add(nums[i]);
                path.add(nums[i]);
                dfs();
                path.remove(path.size()-1);
                set.remove(nums[i]);
            }else{
                continue;
            }
        }
    }

55.42. 接雨水 - 力扣（LeetCode）

I前后缀

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

public int trap(int[] height) {
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        int res = 0;
        for(int i = 1 ; i < height.length ; i++){
            leftMax[i] = Math.max(height[i-1],leftMax[i-1]);
        }
        for(int i = height.length - 2 ; i >= 0 ; i--){
            rightMax[i] = Math.max(height[i+1],rightMax[i+1]);
        }
        for(int i = 0 ; i < height.length ; i++){
            int water = Math.min(leftMax[i],rightMax[i]) - height[i];
            if(water > 0){
                res += water;
            }
        }
        return  res;
    }

II单调栈

public int trap(int[] height) {
        int res = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        for(int i = 1 ; i < height.length ; i++){
            if(height[stack.peek()] == height[i]){
                stack.pop();
            }else if(height[stack.peek()] < height[i]){
                while(!stack.isEmpty() && height[stack.peek()] < height[i]){
                    int mid = stack.pop();
                    if(!stack.isEmpty()){
                        int left = stack.peek();
                        int right =i;
                        int w = right - left - 1;
                        int h = Math.min(height[right],height[left]) - height[mid];
                        res += w*h;
                    }
                }
            }
            stack.push(i);
        }
        return res;
    }

56.39. 组合总和 - 力扣（LeetCode）

回溯问题 dfs

其中为了避免因为顺序导致的List不同，先将candidates进行排序，按排序后的进行计算。

并且由于判断递归进入的逻辑sum + candidates[i] <= target 一项，Arrays.sort(candidates)也是必须的。

List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] candidates;
    int target;
    int sum = 0;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        this.candidates = candidates;
        this.target = target;
        dfs(0);
        return res;
    }
    public void dfs(int startIndex){
        if(sum == target){
            res.add(new ArrayList<>(path));
        }
        for(int i = startIndex ; i < candidates.length && sum + candidates[i] <= target ; i++){
            sum += candidates[i];
            path.add(candidates[i]);
            dfs(i);
            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }

57.543. 二叉树的直径 - 力扣（LeetCode）

回溯问题

int res;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res;
    }
    public int dfs(TreeNode root){
        if(root.left == null && root.right == null){
            return 1;
        }
        int leftHeight = 0;
        if(root.left != null){
            leftHeight = dfs(root.left);
        }
        int rightHeight = 0;
        if(root.right != null){
            rightHeight = dfs(root.right);
        }
        res = Math.max(res,leftHeight + rightHeight);
        return Math.max(leftHeight,rightHeight) + 1;
    }

58.34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

二分法

public int[] searchRange(int[] nums, int target) {
        int left = lowerBound(nums,target);
        int right = lowerBound(nums,target + 1) - 1;
        if(left == nums.length || nums[left] != target){
            return new int[]{-1,-1};
        }
        return new int[]{left,right};
    }
    public int lowerBound(int[] nums,int target){
        int left = 0 , right = nums.length - 1;
        int mid = left + (right - left)/2;
        while(left <= right){
            mid = left + (right - left)/2;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }

59.33. 搜索旋转排序数组 - 力扣（LeetCode）

仍然是二分法，需要掌握二分法的思想，具体分析

public int search(int[] nums, int target) {
        int n = nums.length;
        if(n == 1){
            return nums[0] == target ? 0 : -1;
        }
        int left = 0 ,right = n - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(target == nums[mid]){
                return target;
            }
            if(nums[0] <= nums[mid]){
                //左侧有序
                if(nums[0] <= target && target <= nums[mid]){
                    //在左侧，到左侧找
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else{
                //右侧有序
                if(nums[mid] <= target && target <= nums[n - 1]){
                    //在右侧，到右侧找
                    left = mid + 1; 
                }else{
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

60.32. 最长有效括号 - 力扣（LeetCode）

I栈

大多数人对于这题的第一直觉是找到每个可能的子串后判断它的有效性，但这样的时间复杂度会达到 O(n^3)，无法通过所有测试用例。但是通过栈，我们可以在遍历给定字符串的过程中去判断到目前为止扫描的子串的有效性，同时能得到最长有效括号的长度。

这里栈底的“最后一个没有被匹配的右括号下标”即左侧边界。

public int longestValidParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);
        int res = 0 ;
        for(int i = 0 ; i < s.length() ; i++){
            if(s.charAt(i) == '('){
                stack.push(i);
            }else{
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }else{
                    res = Math.max(res,i - stack.peek());
                }
                
            }
        }
        return res;
    }

II动态规划

1.dp数组及下标含义

dp[i] : 以s.charAt(i)为结尾的最长有效字符串长度为dp[i]

2.递推方程

(1)考虑累加

s.charAt(i) == ')' && s.charAt(i) == '('

那么 dp[i] = dp[i-2] + 2;

(2)考虑嵌套

s.charAt(i) == ')'  && s.charAt(i-1) == ')' 

如果是有效字符串，那么在i-1位置的‘)'匹配的'('之前，必然有一个'(' 与i位置的')'相匹配

即 s.charAt(i - dp[i-1] - 2) == '('

那么 dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2];

3.初始化

初始化为0

4.遍历顺序

从前向后

5.举例推导dp数组

public int longestValidParentheses(String s) {
        int[] dp = new int[s.length()];
        int res = 0;
        for(int i = 1 ; i < s.length() ; i++){
            if(s.charAt(i) == ')'){
                if(s.charAt(i-1) == '('){
                    dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
                }else if(i - dp[i-1] > 0 && s.charAt(i - dp[i-1] - 1) == '('){
                    dp[i] = dp[i-1] + 2 + ((i - dp[i-1] )>= 2 ? dp[i-dp[i-1]-2] : 0 ) ;
                }
                res = Math.max(res,dp[i]);
            }
        }
        return res;
    }

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/964201.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【游戏设计原理】98 - 时间膨胀

【游戏设计原理】98 - 时间膨胀

从上文中&#xff0c;我们可以得到以下几个启示&#xff1a; 游戏设计的核心目标是让玩家感到“时间飞逝” 游戏的成功与否&#xff0c;往往取决于玩家的沉浸感。如果玩家能够完全投入游戏并感受到时间飞逝&#xff0c;说明游戏设计在玩法、挑战、叙事等方面达到了吸引人的平衡…
阅读更多...
RocketMQ面试题：进阶部分

RocketMQ面试题：进阶部分

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;精通Java编…
阅读更多...
Deepseek-R1 和 OpenAI o1 这样的推理模型普遍存在“思考不足”的问题

Deepseek-R1 和 OpenAI o1 这样的推理模型普遍存在“思考不足”的问题

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…
阅读更多...
结构性多余到结构性消失的现象和案例

结构性多余到结构性消失的现象和案例

在碎片化的现象和案例中提取关联性的信息。 也就是废墟之上如何重生的问题。 碎片化无处不在&#xff0c;普通人无人可以幸免。 当AI能力越来越强大&#xff0c;如下这些都在变为现实。 生产力 98%的人是过剩劳动力 人在大规模地被废弃 当人是生产力主体的时候&#xff0c;如…
阅读更多...
(脚本学习)BUU18 [CISCN2019 华北赛区 Day2 Web1]Hack World1

(脚本学习)BUU18 [CISCN2019 华北赛区 Day2 Web1]Hack World1

自用 题目 考虑是不是布尔盲注&#xff0c;如何测试&#xff1a;用"1^1^11 1^0^10&#xff0c;就像是真真真等于真&#xff0c;真假真等于假"这个测试 SQL布尔盲注脚本1 import requestsurl "http://8e4a9bf2-c055-4680-91fd-5b969ebc209e.node5.buuoj.cn…
阅读更多...
【C++】P1957 口算练习题

【C++】P1957 口算练习题

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 &#x1f4af;前言&#x1f4af;题目描述输入格式&#xff1a;输出格式&#xff1a; &#x1f4af;我的做法代码实现&#xff1a; &#x1f4af;老师的做法代码实现&#xff1a; &#x1f4af;对比分析&am…
阅读更多...
【Linux系统】信号：再谈OS与内核区、信号捕捉、重入函数与 volatile

【Linux系统】信号：再谈OS与内核区、信号捕捉、重入函数与 volatile

再谈操作系统与内核区 1、浅谈虚拟机和操作系统映射于地址空间的作用 我们调用任何函数&#xff08;无论是库函数还是系统调用&#xff09;&#xff0c;都是在各自进程的地址空间中执行的。无论操作系统如何切换进程&#xff0c;它都能确保访问同一个操作系统实例。换句话说&am…
阅读更多...
LabVIEW双光子成像系统：自主创新，精准成像，赋能科研

LabVIEW双光子成像系统：自主创新，精准成像，赋能科研

双光子成像系统&#xff1a;自主创新&#xff0c;精准成像&#xff0c;赋能科研 第一部分&#xff1a;概述 双光子成像利用两个低能量光子同时激发荧光分子&#xff0c;具有深层穿透、高分辨率、低光损伤等优势。它能实现活体深层组织的成像&#xff0c;支持实时动态观察&…
阅读更多...
「全网最细 + 实战源码案例」设计模式——策略模式

「全网最细 + 实战源码案例」设计模式——策略模式

核心思想 享元模式&#xff08;Flyweight Pattern&#xff09;是一种行为型设计模式&#xff0c;用于定义一系列算法或策略&#xff0c;将它们封装成独立的类&#xff0c;并使它们可以相互替换&#xff0c;而不影响客户端的代码&#xff0c;提高代码的可维护性和扩展性。 结构…
阅读更多...
安全策略实验

安全策略实验

安全策略实验 1.拓扑图 2.需求分析 需求&#xff1a; 1.VLAN 2属于办公区&#xff0c;VLAN 3属于生产区 2.办公区PC在工作日时间&#xff08;周一至周五&#xff0c;早8到晚6&#xff09;可以正常访问OA server其他时间不允许 3.办公区PC可以在任意时刻访问Web Server 4.生产…
阅读更多...
一文了解边缘计算

一文了解边缘计算

什么是边缘计算&#xff1f; 我们可以通过一个最简单的例子来理解它&#xff0c;它就像一个司令员&#xff0c;身在离炮火最近的前线&#xff0c;汇集现场所有的实时信息&#xff0c;经过分析并做出决策&#xff0c;及时果断而不拖延。 1.什么是边缘计算&#xff1f; 边缘计算…
阅读更多...
对象的实例化、内存布局与访问定位

对象的实例化、内存布局与访问定位

一、创建对象的方式 二、创建对象的步骤: 一、判断对象对应的类是否加载、链接、初始化: 虚拟机遇到一条new指令&#xff0c;首先去检查这个指令的参数能否在Metaspace的常量池中定位到一个类的符号引用&#xff0c;并且检查这个符号引用代表的类是否已经被加载、解析和初始化…
阅读更多...
Altium Designer绘制原理图时画斜线的方法

Altium Designer绘制原理图时画斜线的方法

第一步&#xff1a;检查设置是否正确 打开preferences->PCB Editor ->Interactive Routing->Interactive Routing Options->Restrict TO 90/45去掉勾选项&#xff0c;点击OK即可。如下图所示&#xff1a; 然后在划线时&#xff0c;按下shift空格就能够切换划线…
阅读更多...
【R语言】环境空间

【R语言】环境空间

一、环境空间的特点 环境空间是一种特殊类型的变量&#xff0c;它可以像其它变量一样被分配和操作&#xff0c;还可以以参数的形式传递给函数。 R语言中环境空间具有如下3个特点&#xff1a; 1、对象名称唯一性 此特点指的是在不同的环境空间中可以有同名的变量出现&#x…
阅读更多...
NeuralCF 模型：神经网络协同过滤模型

NeuralCF 模型：神经网络协同过滤模型

实验和完整代码 完整代码实现和jupyter运行&#xff1a;https://github.com/Myolive-Lin/RecSys--deep-learning-recommendation-system/tree/main 引言 NeuralCF 模型由新加坡国立大学研究人员于 2017 年提出&#xff0c;其核心思想在于将传统协同过滤方法与深度学习技术相结…
阅读更多...
【ChatGPT：开启人工智能新纪元】

【ChatGPT：开启人工智能新纪元】

一、ChatGPT 是什么 最近，ChatGPT 可是火得一塌糊涂，不管是在科技圈、媒体界，还是咱们普通人的日常聊天里，都能听到它的大名。好多人都在讨论，这 ChatGPT 到底是个啥 “神器”，能让大家这么着迷？今天咱就好好唠唠。 ChatGPT，全称是 Chat Generative Pre-trained Trans…
阅读更多...
c++ 定点 new 及其汇编解释

c++ 定点 new 及其汇编解释

&#xff08;1&#xff09; 代码距离&#xff1a; #include <new> // 需要包含这个头文件 #include <iostream>int main() {char buffer[sizeof(int)]; // 分配一个足够大的字符数组作为内存池int* p new(&buffer) int(42); // 使用 placement new…
阅读更多...
Linux系统之whereis命令的基本使用

Linux系统之whereis命令的基本使用

Linux系统之whereis命令的基本使用 一、whereis命令介绍二、whereis命令的使用帮助2.1 whereis命令的帮助信息2.2 whereis命令帮助解释 三、whereis命令的基本使用3.1 查找命令的位置3.2 仅查找二进制文件3.3 仅查找手册页3.4 输出实际使用的查找路径3.5 指定自定义搜索路径 四…
阅读更多...
CH340G上传程序到ESP8266-01(S)模块

CH340G上传程序到ESP8266-01(S)模块

文章目录 概要ESP8266模块外形尺寸模块原理图模块引脚功能 CH340G模块外形及其引脚模块引脚功能USB TO TTL引脚 程序上传接线Arduino IDE 安装ESP8266开发板Arduino IDE 开发板上传失败上传成功 正常工作 概要 使用USB TO TTL&#xff08;CH340G&#xff09;将Arduino将程序上传…
阅读更多...
整形的存储形式和浮点型在计算机中的存储形式

整形的存储形式和浮点型在计算机中的存储形式

在计算机科学的底层世界里&#xff0c;数据存储是基石般的存在。不同数据类型&#xff0c;如整形与浮点型&#xff0c;其存储方式犹如独特的密码&#xff0c;隐藏着计算机高效运行的秘密。理解它们&#xff0c;是深入掌握编程与计算机原理的关键。 一、整形的存储形式 原码、反…
阅读更多...
最新文章

Copyright @ 2022~2023