力扣回溯篇

文章目录

      • 46.全排列
      • 78.子集
      • 17.电话号码的字母组合
      • 39.组数总和
      • 79.单词搜索
      • 131.分割回文子串

46.全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以按任意顺序返回答案。

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

输入：nums = [0,1]
输出：[[0,1],[1,0]]

输入：nums = [1]
输出：[[1]]

class Solution {
    List<List<Integer>> res = new ArrayList<>(); // 存储结果的列表

    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length]; // 记录每个元素是否已经使用过
        List<Integer> track = new ArrayList<>(); // 存储当前排列的元素
        backtrack(track, nums, used); // 回溯算法求解全排列
        return res; // 返回结果列表
    }
    
    private void backtrack(List<Integer> track, int[] nums, boolean[] used){
        if(track.size() == nums.length){ // 如果当前排列的长度等于数组长度，说明已经找到一个全排列
            res.add(new ArrayList(track)); // 将当前排列添加到结果列表中
            return;
        }
        for(int i=0 ; i<nums.length ; i++){ // 遍历数组中的每个元素
            if(used[i]){ // 如果当前元素已经使用过，跳过
                continue;
            }
            used[i] = true; // 标记当前元素为已使用
            track.add(nums[i]); // 将当前元素添加到当前排列中
            backtrack(track, nums, used); // 继续寻找下一个元素
            used[i] = false; // 回溯，将当前元素标记为未使用
            track.removeLast(); // 回溯，移除当前排列中的最后一个元素
        }
    }
}

78.子集

给你一个整数数组 nums ，数组中的元素互不相同 。返回该数组所有可能的
子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

输入：nums = [0]
输出：[[],[0]]

class Solution {

    List<Integer> t = new ArrayList<Integer>(); // 用于存储当前子集的元素
    List<List<Integer>> ans = new ArrayList<>(); // 用于存储所有子集的结果

    public List<List<Integer>> subsets(int[] nums) {
        dfs(0, nums); // 从第0个元素开始进行深度优先搜索
        return ans; // 返回所有子集的结果
    }

    public void dfs(int cur, int[] nums) {
        if (cur == nums.length) { // 如果已经遍历完所有元素，将当前子集添加到结果中
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        t.add(nums[cur]); // 将当前元素添加到子集中
        dfs(cur + 1, nums); // 继续向下搜索
        t.remove(t.size() - 1); // 回溯，移除刚刚添加的元素
        dfs(cur + 1, nums); // 不包含当前元素的子集继续向下搜索
    }
}

还有一种题解很有意思

  1. 例如[1,2,3]，一开始解集为[[]]，表示只有一个空集。
  2. 遍历到1时，依次拷贝解集中所有子集，只有[]，把1加入拷贝的子集中得到[1]，然后加回解集中。此时解集为[[], [1]]。
  3. 遍历到2时，依次拷贝解集中所有子集，有[], [1]，把2加入拷贝的子集得到[2], [1, 2]，然后加回解集中。此时解集为[[], [1], [2], [1, 2]]。
  4. 遍历到3时，依次拷贝解集中所有子集，有[], [1], [2], [1, 2]，把3加入拷贝的子集得到[3], [1, 3], [2, 3], [1, 2, 3]，然后加回解集中。此时解集为[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]。
class Solution {

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>(); // 解集
        lists.add(new ArrayList<Integer>()); // 首先将空集加入解集中
        for(int i = 0; i < nums.length; i++){
            int size = lists.size(); // 当前子集数
            for(int j = 0; j < size; j++){ 
                List<Integer> newList = new ArrayList<>(lists.get(j));// 拷贝所有子集
                newList.add(nums[i]); // 向拷贝的子集中加入当前数形成新的子集
                lists.add(newList); // 向lists中加入新子集
            }
        }
        return lists;
    }
}

17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
在这里插入图片描述

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

输入：digits = ""
输出：[]

输入：digits = "2"
输出：["a","b","c"]

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>(); // 存储所有可能的组合结果
        if(digits.length() == 0){ // 如果输入为空，直接返回空列表
            return combinations;
        }
        Map<Character,String> phoneMap = new HashMap<Character,String>(){{ // 创建一个映射表，将数字映射到对应的字母
            put('2',"abc");
            put('3',"def");
            put('4',"ghi");
            put('5',"jkl");
            put('6',"mno");
            put('7',"pqrs");
            put('8',"tuv");
            put('9',"wxyz");
        }};

        backtracking(combinations,phoneMap,digits,0,new StringBuffer()); // 调用回溯函数进行搜索
        return combinations; // 返回所有可能的组合结果
    }

    public void backtracking(List<String> combinations,Map<Character,String> phoneMap,String digits,int index,StringBuffer combination){
        if(index == digits.length()){ // 如果已经遍历完所有的数字，将当前组合添加到结果列表中
            combinations.add(combination.toString());
        }else{
            char digit = digits.charAt(index); // 获取当前数字
            String letters = phoneMap.get(digit); // 获取当前数字对应的字母
            int lettersCount = letters.length(); // 获取当前数字对应的字母数量

            for(int i=0;i<lettersCount;i++){ // 遍历当前数字对应的所有字母
                combination.append(letters.charAt(i)); // 将当前字母添加到组合中
                backtracking(combinations,phoneMap,digits,index+1,combination); // 继续搜索下一个数字
                combination.deleteCharAt(index); // 回溯，移除刚刚添加的字母
            }
        }
    }
}

39.组数总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按任意顺序返回这些组合。candidates 中的同一个数字可以无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。


输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

输入: candidates = [2], target = 1
输出: []

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>(); // 存储结果的列表
        List<Integer> combine = new ArrayList<Integer>(); // 存储当前组合的列表

        dfs(candidates, target, ans, combine, 0); // 调用深度优先搜索函数
        return ans; // 返回结果列表

    }

    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if (idx == candidates.length) { // 如果已经遍历完所有候选数，直接返回
            return;
        }
        if (target == 0) { // 如果目标值减为0，说明找到了一个有效的组合，将其添加到结果列表中
            ans.add(new ArrayList<Integer>(combine));
            return;
        }

        dfs(candidates, target, ans, combine, idx + 1); // 不选择当前候选数，继续搜索下一个候选数
        if (target - candidates[idx] >= 0) { // 如果选择当前候选数后，目标值仍然大于等于0，继续搜索
            combine.add(candidates[idx]); // 将当前候选数添加到当前组合中
            dfs(candidates, target - candidates[idx], ans, combine, idx); // 继续搜索剩余的目标值
            combine.remove(combine.size() - 1); // 回溯，移除刚刚添加的候选数
        }
    }
}

79.单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
在这里插入图片描述

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

在这里插入图片描述

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

class Solution {
    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        boolean[][] visited = new boolean[h][w];

        // 遍历二维数组的每个元素
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                // 检查当前位置是否能够匹配单词的前缀
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }

        return false;
    }

    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        // 如果当前位置的字符与单词的第k个字符不匹配，返回false
        if (board[i][j] != s.charAt(k)) {
            return false;
        } else if (k == s.length() - 1) {
            // 如果已经匹配到单词的最后一个字符，返回true
            return true;
        }
        // 标记当前位置已访问
        visited[i][j] = true;
        // 定义四个方向的偏移量
        int[][] directions = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
        boolean result = false;

        // 遍历四个方向
        for (int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];
            // 判断新的位置是否在二维数组范围内
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                if (!visited[newi][newj]) {
                    // 递归调用check函数，继续匹配下一个字符
                    boolean flag = check(board, visited, newi, newj, s, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }

        // 回溯，将当前位置标记为未访问
        visited[i][j] = false;
        return result;
    }
}
  1. 将输入的字符串word转换为字符数组words。
  2. 遍历二维数组board的每一个元素，对于每一个元素，调用dfs函数进行深度优先搜索。
  3. 在dfs函数中，首先判断当前位置是否越界或者当前位置的字符与word中的对应字符不相等，如果满足这些条件，则返回false。
  4. 如果已经匹配到word的最后一个字符，说明找到了一个有效的路径，返回true。
  5. 将当前位置的字符暂时替换为’\0’，避免重复访问。
  6. 递归地对当前位置的上下左右四个方向进行深度优先搜索，如果有一个方向返回true，说明找到了一个有效的路径，返回true。
  7. 恢复当前位置的字符，继续搜索其他可能的路径。
  8. 如果所有方向都没有找到有效的路径，返回false。
  9. 如果遍历完二维数组board的所有元素都没有找到有效的路径，返回false。
class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if (dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if (k == word.length - 1) return true;
        board[i][j] = '\0';
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || 
                      dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
}

131.分割回文子串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

输入：s = "a"
输出：[["a"]]

class Solution {
    List<String> path = new ArrayList<>(); // 存储回文子串的路径
    List<List<String>> result = new ArrayList<>(); // 存储所有可能的回文子串组合

    public List<List<String>> partition(String s) {
        backtracking(s, 0); // 从字符串的第一个字符开始进行回溯
        return result; // 返回所有可能的回文子串组合
    }

    void backtracking(String s, int startIndex) {
        if (startIndex == s.length()) { // 如果已经遍历到字符串的末尾
            result.add(new ArrayList<>(path)); // 将当前路径添加到结果中
            return;
        }

        for (int i = startIndex + 1; i <= s.length(); i++) { // 遍历字符串，找到所有可能的回文子串
            String substring = s.substring(startIndex, i); // 获取当前子串
            if (!isPalindrome(substring)) { // 如果当前子串不是回文，跳过
                continue;
            }

            path.add(substring); // 将当前回文子串添加到路径中
            backtracking(s, i); // 继续向后遍历
            path.remove(path.size() - 1); // 回溯，移除当前回文子串
        }
    }

    boolean isPalindrome(String s) { // 判断一个字符串是否是回文
        int left = 0;
        int right = s.length() - 1;
        while (left < right) { // 从两端向中间遍历
            if (s.charAt(left) != s.charAt(right)) { // 如果两端的字符不相等，说明不是回文
                return false;
            }
            left++;
            right--;
        }
        return true; // 如果遍历完没有发现不相等的字符，说明是回文
    }
}

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

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

相关文章

C++利用键值对计算某一个数对应的最值及其索引位置

C++利用键值对计算某一个数对应的最值及其索引位置

目录 一、算法概述二、代码实现1、计算最值2、计算最值及其索引 三、结果展示 本文由CSDN点云侠原创&#xff0c;原文链接。如果你不是在点云侠的博客中看到该文章&#xff0c;那么此处便是不要脸的爬虫与GPT。 一、算法概述 类似下图所示&#xff0c;计算第一列中1或2对应的最…
阅读更多...
剑指Offer题目笔记26（动态规划的基础知识）

剑指Offer题目笔记26（动态规划的基础知识）

面试题88&#xff1a; 问题&#xff1a; ​ 一个数组cost的所有数字都是正数&#xff0c;它的第i个数字表示在一个楼梯的第i级台阶往上爬的成本&#xff0c;在支付了成本cost[i]之后可以从第i级台阶往上爬1级或2级。请计算爬上该楼梯的最少成本。 解决方案一&#xff1a;&…
阅读更多...
C++学习笔记（16）——vector的使用与模拟实现

C++学习笔记（16）——vector的使用与模拟实现

文章目录 比喻与理解一、定义二 、在使用层面三、在实现层面四、vector的成员变量五、vector的迭代器六、vector的容器函数七、vector的其他函数1. reserve更新容器空间大小&#xff1a;vector_name.reserve(size_type);2. resize大小&#xff1a;vector_name.resize(size_type…
阅读更多...
AcWing---公约数---最大公约数

AcWing---公约数---最大公约数

4199. 公约数 - AcWing题库 思路&#xff1a; 最大整数x一定是最大公约数的因数&#xff0c;所以先用__gcd(a,b)求出a和b的最大公因数&#xff0c;再用O(log(n))的算法求出最大公因数的因数&#xff0c;放到vector中&#xff0c;并将vector排序。利用STL中的upper_bound(res.…
阅读更多...
模组网络通用丨蜂窝网络基础知识介绍

模组网络通用丨蜂窝网络基础知识介绍

在物联网的时代&#xff0c;蜂窝网络成为了连接各种智能设备的重要基础。而在蜂窝网络中&#xff0c;蜂窝模组则是实现物联网连接的关键组件。作为物联网开发人员&#xff0c;了解蜂窝网络的基础知识是非常重要的。本文详细解答了6个在开发过程的常见问题&#xff0c;帮助客户更…
阅读更多...
自然语言处理NLP概述

自然语言处理NLP概述

大家好&#xff0c;自然语言处理(NLP)是计算机科学领域与人工智能领域中的一个重要方向&#xff0c;其研究能实现人与计算机之间用自然语言进行有效通信的各种理论和方法。本文将从自然语言处理的本质、原理和应用三个方面&#xff0c;对其进行概述。 一、NLP的本质 NLP是一种…
阅读更多...
linux常用目录结构（目录命令）--6986字详谈

linux常用目录结构（目录命令）--6986字详谈

前面与大家讨论了linux的发展与由来&#xff08;这一块挺多的&#xff0c;小编还没有编写完成&#xff0c;希望大家理解&#xff09;&#xff0c;紧接着谈到了vmware安装及运行所存在的故障&#xff08;鉴定错误&#xff0c;虚拟机没有网&#xff0c;蓝屏等常见现象的总结及处理…
阅读更多...
Mysql5.7 yum 简单/快速安装

Mysql5.7 yum 简单/快速安装

Centos7下MySql安装及配置过程&#xff0c;简单直装版 目录 操作步骤 一、检查linux是否已安装MySql二、清除MySQL&#xff08;适用重新安装&#xff09; 1、删除MySQL及其依赖包2、查询遗留的目录3、删除遗留的目录三、开始安装MySQL 1、下载并添加库2、安装MySQL包3、设置My…
阅读更多...
Qt环形颜色选择控件, 圆环颜色选择器

Qt环形颜色选择控件, 圆环颜色选择器

参考文章Qt编写自定义控件&#xff1a;环形颜色选择控件_qconicalgradient圆环渐变-CSDN博客 感谢作责提供的方法&#xff0c;下面程序的基础思路同参考文章。 为了更方便使用&#xff0c;这个选择器是基于64色表的&#xff0c;会显示选中的索引和色值。颜色选择时计算方式也…
阅读更多...
深入理解 Pandas 中的 groupby 函数

深入理解 Pandas 中的 groupby 函数

groupby 函数是 pandas 库中 DataFrame 和 Series 对象的一个方法&#xff0c;它允许你对这些对象中的数据进行分组和聚合。下面是 groupby 函数的一些常用语法和用法。 对于 DataFrame 对象&#xff0c;groupby 函数的语法如下&#xff1a; DataFrame.groupby(byNone, axis0…
阅读更多...
面试（03）————多线程和线程池

面试（03）————多线程和线程池

一、多线程 1、什么是线程?线程和进程的区别? 2、创建线程有几种方式 &#xff1f; 3、Runnable 和 Callable 的区别&#xff1f; 4、如何启动一个新线程、调用 start 和 run 方法的区别&#xff1f; 5、线程有哪几种状态以及各种状态之间的转换&#xff1f; 6、线程…
阅读更多...
内网穿透的应用-如何在Android Termux上部署MySQL数据库并实现无公网IP远程访问

内网穿透的应用-如何在Android Termux上部署MySQL数据库并实现无公网IP远程访问

文章目录 前言1.安装MariaDB2.安装cpolar内网穿透工具3. 创建安全隧道映射mysql4. 公网远程连接5. 固定远程连接地址 前言 Android作为移动设备&#xff0c;尽管最初并非设计为服务器&#xff0c;但是随着技术的进步我们可以将Android配置为生产力工具&#xff0c;变成一个随身…
阅读更多...
（十一）RabbitMQ及SpringAMQP

（十一）RabbitMQ及SpringAMQP

1.初识MQ 1.1.同步和异步通讯 微服务间通讯有同步和异步两种方式&#xff1a; 同步通讯&#xff1a;就像打电话&#xff0c;需要实时响应。 异步通讯&#xff1a;就像发邮件&#xff0c;不需要马上回复。 两种方式各有优劣&#xff0c;打电话可以立即得到响应&#xff0c;…
阅读更多...
YOLOV9 + 双目测距

YOLOV9 + 双目测距

YOLOV9 双目测距 1. 环境配置2. 测距流程和原理2.1 测距流程2.2 测距原理 3. 代码部分解析3.1 相机参数stereoconfig.py3.2 测距部分3.3 主代码yolov9-stereo.py 4. 实验结果4.1 测距4.2 视频展示 相关文章 1. YOLOV5 双目测距&#xff08;python&#xff09; 2. YOLOv7双目…
阅读更多...
第十四届蓝桥杯C/C++大学B组题解（一）

第十四届蓝桥杯C/C++大学B组题解（一）

1、日期统计 #include <bits/stdc.h> using namespace std; int main() {int array[100] {5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7,5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9,2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6,…
阅读更多...
【第十九篇】使用BurpSuite实现XXE+点击劫持（实战案例）

【第十九篇】使用BurpSuite实现XXE+点击劫持（实战案例）

XXE XXE漏洞的原理：攻击者通过注入特殊的XML实体来引用外部资源，比如本地文件系统中的文件。从而读取服务器上的敏感文件。 【1】Burp主动扫描 将条目发送至主动扫描： 仪表盘扫描出XML注入漏洞： 【2】手动测试 原请求包如下： 添加Payload并将 XML 中的数据值替换为我们…
阅读更多...
多功能调解室sip可视对讲方案

多功能调解室sip可视对讲方案

多功能调解室sip可视对讲方案 人民调解委员会是依法设立的调解民间纠纷的群众性组织。 我国基层解决人民内部纠纷的群众性自治组织.人民调解委员会在城市以居民委员会为单位,农村以村民委员会为单位建立.其任务是: 及时发现纠纷,迅速解决争端.防止矛盾激化,预防,减少犯罪的发生…
阅读更多...
EChart简单入门

EChart简单入门

echart的安装就细不讲了&#xff0c;直接去官网下&#xff0c;实在不会的直接用cdn,省的一番口舌。 cdn.staticfile.net/echarts/4.3.0/echarts.min.js 正入话题哈 什么是EChart&#xff1f; EChart 是一个使用 JavaScript 实现的开源可视化库&#xff0c;Echart支持多种常…
阅读更多...
postgresql数据库|数据整合的好工具--Oracle-fdw的部署和使用

postgresql数据库|数据整合的好工具--Oracle-fdw的部署和使用

概述 Oracle_fdw 是一种postgresql外部表插件&#xff0c;可以读取到Oracle上面的数据。是一种非常方便且常见的pg与Oracle的同步数据的方法 Oracle_fdw 适用场景&#xff1a; Oracle_fdw 是一个开源的 Foreign Data Wrapper (FDW)&#xff0c;主要用于在 PostgreSQL 数据库中…
阅读更多...
【2024】Rancher的安装与介绍

【2024】Rancher的安装与介绍

———————————————————————————— 记录一下rancher的学习与使用过程 本部分内容包括rancher的介绍、特点、与k8s关系和部署等内容 ———————————————————————————— Rancher是什么&#xff1f; 简单来说&#xff0c;Ranc…
阅读更多...
最新文章

Copyright @ 2022~2023