代码随想录-回溯算法

在这里插入图片描述

  1. 组合
//未剪枝
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return ans;
    }

    public void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n; i++) {
            path.add(i);
            backtracking(n, k, i + 1);
            path.removeLast();
        }
    }
}

//剪枝
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return ans;
    }

    public void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            backtracking(n, k, i + 1);
            path.removeLast();
        }
    }
}
  1. 组合总和 III
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k, n, 0, 1);
        return ans;
    }

    public void backtracking(int k, int targetSum, int sum, int startIndex) {
        if (path.size() == k) {
            if (sum == targetSum) {
                ans.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = startIndex; i <= 9; i++) {
            sum += i;
            path.add(i);
            backtracking(k, targetSum, sum, i + 1);
            sum -= i;
            path.removeLast();
        }
    }
}
  1. 电话号码的字母组合
class Solution {
    List<String> ans = new ArrayList<>();

    StringBuilder temp = new StringBuilder();

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return ans;
        }
        String[] numString = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        backTracking(digits, numString, 0);
        return ans;
    }

    public void backTracking(String digits, String[] numString, int len) {
        if (len == digits.length()) {
            ans.add(temp.toString());
            return;
        }
        String str = numString[digits.charAt(len) - '0'];
        for (int i = 0; i < str.length(); i++) {
            temp.append(str.charAt(i));
            backTracking(digits, numString, len + 1);
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}
  1. 组合总和
//未剪枝
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        bacaktracking(candidates, target, 0, 0);
        return ans;
    }

    public void bacaktracking(int[] candidates, int target, int sum, int startIndex) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            sum += candidates[i];
            path.add(candidates[i]);
            bacaktracking(candidates, target, sum, i);
            sum -= candidates[i];
            path.removeLast();
        }
    }
}

在求和问题中，排序之后加剪枝是常见的套路！

//剪枝
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        bacaktracking(candidates, target, 0, 0);
        return ans;
    }

    public void bacaktracking(int[] candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            sum += candidates[i];
            if (sum > target) {
                break;
            }
            path.add(candidates[i]);
            bacaktracking(candidates, target, sum, i);
            sum -= candidates[i];
            path.removeLast();
        }
    }
}
  1. 组合总和 II
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtracking(candidates, target, 0, 0);
        return ans;
    }

    public void backtracking(int[] candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            if (i > startIndex && candidates[i] == candidates[i - 1]) {
                continue;
            }
            sum += candidates[i];
            if (sum > target) {
                break;
            }
            path.add(candidates[i]);
            backtracking(candidates, target, sum, i + 1);
            sum -= candidates[i];
            path.removeLast();
        }
    }
}
  1. 分割回文串
class Solution {
    List<List<String>> ans = new ArrayList<>();
    Deque<String> path = new LinkedList<>();

    public List<List<String>> partition(String s) {
        backtracking(s, 0);
        return ans;
    }

    public void backtracking(String s, int startIndex) {
        if (startIndex >= s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindrome(s, startIndex, i)) {
                String str = s.substring(startIndex, i + 1);
                path.add(str);
            } else {
                continue;
            }
            backtracking(s, i + 1);
            path.removeLast();
        }
    }

    public boolean isPalindrome(String s, int start, int end) {
        for (int i = startIndex, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}
  1. 复原 IP 地址
class Solution {
    List<String> ans = new ArrayList<>();
    StringBuilder currentIP = new StringBuilder();

    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12)
            return ans;
        backtracking(s, 0, 0);
        return ans;
    }

    private void backtracking(String s, int startIndex, int pointNum) {
        if (pointNum == 3) {
            if (isValid(s, startIndex, s.length() - 1)) {
                currentIP.append(s.substring(startIndex));
                ans.add(currentIP.toString());

            }
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isValid(s, startIndex, i)) {
                int len = currentIP.length();
                currentIP.append(s.substring(startIndex, i + 1));
                if (pointNum < 3) {
                    currentIP.append(".");
                }
                backtracking(s, i + 1, pointNum + 1);
                currentIP.setLength(len);
            } else {
                break;
            }
        }
    }

    private Boolean isValid(String s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到非数字字符不合法
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果大于255了不合法
                return false;
            }
        }
        return true;
    }
}

class Solution {
    List<String> ans = new ArrayList<>();
    StringBuilder currentIP = new StringBuilder();

    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12)
            return ans;
        backtracking(s, 0, 0);
        return ans;
    }

    private void backtracking(String s, int startIndex, int pointNum) {
        if (pointNum == 3) {
            if (isValid(s, startIndex, s.length() - 1)) {
                currentIP.append(s.substring(startIndex));
                ans.add(currentIP.toString());

            }
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isValid(s, startIndex, i)) {
                int len = currentIP.length();
                currentIP.append(s.substring(startIndex, i + 1));
                if (pointNum < 3) {
                    currentIP.append(".");
                }
                backtracking(s, i + 1, pointNum + 1);
                currentIP.setLength(len);
            } else {
                break;
            }
        }
    }

    private Boolean isValid(String s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s.charAt(start) == '0' && start != end) {
            return false;
        }
        if (Integer.parseInt(s.substring(start, end + 1)) < 0 || Integer.parseInt(s.substring(start, end + 1)) > 255) {
            return false;
        }
        return true;
    }
}
  1. 子集
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums, 0);
        return ans;
    }

    public void backtracking(int[] nums, int startIndex) {
        ans.add(new ArrayList<>(path));
        if (startIndex >= nums.length) {
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.removeLast();
        }
    }

}
  1. 子集 II
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backtracking(nums, 0);
        return ans;
    }

    public void backtracking(int[] nums, int startIndex) {
        ans.add(new ArrayList<>(path));

        for (int i = startIndex; i < nums.length; i++) {
            if (i > startIndex && nums[i - 1] == nums[i]) {
                continue;
            }
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.removeLast();
        }
    }
}
  1. 非递减子序列
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        backtacking(nums, 0);
        return ans;
    }

    public void backtacking(int[] nums, int startIndex) {
        if (path.size() >= 2) {
            ans.add(new ArrayList<>(path));
        }
        Set<Integer> set = new HashSet<>();
        for (int i = startIndex; i < nums.length; i++) {
            if (!path.isEmpty() && path.peekLast() > nums[i] || set.contains(nums[i])) {
                continue;
            }
            set.add(nums[i]);
            path.add(nums[i]);
            backtacking(nums, i + 1);
            path.removeLast();
        }
    }
}
  1. 全排列
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0) {
            return ans;
        }
        backtracking(nums, path);
        return ans;
    }

    public void backtracking(int[] nums, Deque<Integer> path) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (path.contains(nums[i])) {
                continue;
            }
            path.add(nums[i]);
            backtracking(nums, path);
            path.removeLast();
        }
    }
}

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

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

相关文章

Python：关于数据服务中的Web API的设计

Python：关于数据服务中的Web API的设计

搭建类似joinquant、tushare类似的私有数据服务应用&#xff0c;有以下一些点需要注意&#xff1a; 需要说明的是&#xff0c;这里讨论的是web api前后端&#xff0c;当然还有其它方案&#xff0c;thrift&#xff0c;grpc等。因为要考虑到一鱼两吃&#xff0c;本文只探讨web ap…
阅读更多...
Android之UI Automator框架源码分析（第九篇：UiDevice获取UiAutomation对象的过程分析）

Android之UI Automator框架源码分析（第九篇：UiDevice获取UiAutomation对象的过程分析）

前言 学习UiDevice对象&#xff0c;就需要看它的构造方法&#xff0c;构造方法中有UiDevice对象持有一些对象&#xff0c;每个对象都是我们分析程序的重点&#xff0c;毕竟UiDevice对象的功能&#xff0c;依赖这些组合的对象 备注&#xff1a;当前对象持有的对象&#xff0c;初…
阅读更多...
Linux调试器-gdb使用与冯诺依曼体系结构

Linux调试器-gdb使用与冯诺依曼体系结构

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言 Linux调试器-gdb使用 1. 背景 2. 开始使用 冯诺依曼体系结构 总结 前言 世上有两种耀眼的光芒&#xff0c;一种是正在升起的太阳&#xff0c;一种是正在努力学…
阅读更多...
k8s部署mysql

k8s部署mysql

&#xff08;作者&#xff1a;陈玓玏&#xff09; 一、前置条件 已部署k8s&#xff0c;服务端版本为1.21.14 二、部署mysql 拉取镜像&#xff1b; docker pull mysql将账号密码等信息写到configmap&#xff0c;创建configmap&#xff1b; apiVersion: v1 kind: ConfigMap m…
阅读更多...
视觉AIGC识别——人脸伪造检测、误差特征 + 不可见水印

视觉AIGC识别——人脸伪造检测、误差特征 + 不可见水印

视觉AIGC识别——人脸伪造检测、误差特征 不可见水印 前言视觉AIGC识别【误差特征】DIRE for Diffusion-Generated Image Detection方法扩散模型的角色DIRE作为检测指标 实验结果泛化能力和抗扰动 人脸伪造监测&#xff08;Face Forgery Detection&#xff09;人脸伪造图生成 …
阅读更多...
android TextView 实现富文本显示

android TextView 实现富文本显示

android TextView 实现富文本显示&#xff0c;实现抖音直播间公屏消息案例 使用&#xff1a; val tvContent: TextView helper.getView(R.id.tvContent)//自己根据UI业务要求&#xff0c;可以控制 图标显示 大小val levelLabel MyImgLabel( bitmap 自己业务上的bitmap )va…
阅读更多...
卷积神经网络基本概念补充

卷积神经网络基本概念补充

卷积&#xff08;convolution&#xff09;、通道&#xff08;channel&#xff09; 卷积核大小一般为奇数&#xff0c;有中心像素点&#xff0c;便于定位卷积核。 步长&#xff08;stride&#xff09;、填充&#xff08;padding&#xff09; 卷积核移动的步长&#xff08;stride…
阅读更多...
FPGA之带有进位逻辑的加法运算

FPGA之带有进位逻辑的加法运算

module ADDER&#xff08; input [5&#xff1a;0]A&#xff0c; input [5&#xff1a;0]B&#xff0c;output[6&#xff1a;0]Q &#xff09;&#xff1b; assign Q AB&#xff1b; endmodule 综合结果如下图所示&#xff1a; 使用了6个Lut&#xff0c;&#xff0c;6个LUT分布…
阅读更多...
定制红酒：一次满足需求的个性化服务体验

定制红酒：一次满足需求的个性化服务体验

云仓酒庄洒派提供一次满足需求的个性化服务体验&#xff0c;让您的红酒定制之旅成为一段美好的记忆。 首先&#xff0c;云仓酒庄洒派深入了解每位消费者的需求。无论是对于红酒品种、年份、外包装还是其他个性化要求&#xff0c;云仓酒庄洒派都认真倾听并记录下来。这种细致入微…
阅读更多...
Solo 开发者周刊 （第6期）：

Solo 开发者周刊 （第6期）：

这里会整合 Solo 社区每周推广内容、产品模块或活动投稿&#xff0c;每周五发布。在这期周刊中&#xff0c;我们将深入探讨开源软件产品的开发旅程&#xff0c;分享来自一线独立开发者的经验和见解。本杂志开源&#xff0c;欢迎投稿。 产品推荐 1. 助眠类播客《静夜斋》上线 一…
阅读更多...
echarts鼠标向右/向左绘制实现放大/还原

echarts鼠标向右/向左绘制实现放大/还原

echarts toolbox 的datazoom提供了绘制放大的功能&#xff0c;但通过鼠标绘制只能进行放大 应需求放大与还原都通过鼠标行为实现&#xff0c;增加从右往左绘制时还原放大结果 demo 结果 重写datazoom的原型方法实现绘制事件的拦截 const comp myChart._model.getComponent(to…
阅读更多...
typora激活破解——仅需修改js即可

typora激活破解——仅需修改js即可

先打开官网下载typora&#xff0c;typora官网地址&#xff1a;https://typoraio.cn/安装完成后先启动一次Typora&#xff0c;看到激活提示&#xff0c;不需要点试用&#xff0c;直接关闭软件即可。找到安装路径&#xff0c;一般在 C:\Program Files接着找到安装路径&#xff0c…
阅读更多...
CC攻击与DDoS攻击有什么区别？如何进行有效防护？

CC攻击与DDoS攻击有什么区别？如何进行有效防护？

CC攻击的前身是一个名为Fatboy攻击程序&#xff0c;而之所以后来人们会成为CC&#xff0c;是因为DDoS攻击发展的初期阶段&#xff0c;绝大部分DDoS攻击都能被业界熟知的“黑洞”&#xff08;collapsar&#xff0c;一种安全防护产品&#xff09;所抵挡&#xff0c;CC攻击的诞生就…
阅读更多...
配置artifactory的反向代理和域名访问

配置artifactory的反向代理和域名访问

一、概述 在许多情况下&#xff0c;组织会通过反向代理来提供对 Artifactory 的访问。在某些情况下&#xff0c;例如使用 Artifactory 作为 Docker 注册表&#xff0c;这种设置甚至是强制性的。为了简化反向代理的配置&#xff0c;Artifactory 提供了生成反向代理的功能&#x…
阅读更多...
android开发需要哪些基础，已拿到offer

android开发需要哪些基础，已拿到offer

在线绘图神器 很多小伙伴咨询说博客文章里的技术图怎么画出来的&#xff0c;这里透个底&#xff0c;大部分都是通过processon画出来的&#xff0c;在线画图十分方便&#xff0c;几乎可以画出你想要的任何技术图&#xff0c;包括&#xff1a;流程图、思维导图、原型图、UML图、…
阅读更多...
WEB漏洞 逻辑越权之支付数据篡改安全

WEB漏洞 逻辑越权之支付数据篡改安全

水平越权 概述&#xff1a;攻击者尝试访问与他拥有相同权限的用户的资源 测试方法&#xff1a;能否通过A用户操作影响到B用户 案例&#xff1a;pikachu-本地水平垂直越权演示-漏洞成因 1&#xff09;可以看到kobe很多的敏感信息 2&#xff09;burp抓包&#xff0c;更改user…
阅读更多...
Unity中URP实现水体（整理优化）

Unity中URP实现水体（整理优化）

文章目录 前言一、优化水的深度1、我们把 水流动的方向 和 水深浅过渡值&#xff0c;整合到一个四维变量中2、修改 水体流动方向3、在片元着色器中&#xff0c;修改使用过渡变量 二、优化泡沫三、优化水下的扭曲1、修复原本扰动UV的计算 四、优化水面高光1、把高光强度、光滑度…
阅读更多...
基于java+springboot景区行李寄存管理系统设计和实现

基于java+springboot景区行李寄存管理系统设计和实现

基于javaspringboot景区行李寄存管理系统设计和实现 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言 文末获取…
阅读更多...
今年国内石油需求稳中有升，巡检机器人助力石油行业可持续发展

今年国内石油需求稳中有升，巡检机器人助力石油行业可持续发展

前言&#xff1a;全球能源市场出现普遍回落趋势&#xff0c;其中石油价格下降近20%&#xff0c;而天然气和煤炭价格更是下跌超过50%。此外&#xff0c;碳酸锂和光伏组件价格也纷纷下降超过50%。这种价格下滑对于全球经济的持续增长&#xff0c;尤其是控制通货膨胀方面&#xff…
阅读更多...
OpenLayers线性渐变和中心渐变（径向渐变）

OpenLayers线性渐变和中心渐变（径向渐变）

目录 1.前言2.添加一个面要素3.线性渐变3.1 第一个注意点3.2 第二个注意点 4.中心渐变&#xff08;径向渐变&#xff09;5.总结 1.前言 OpenLayers官网有整个图层的渐变示例&#xff0c;但是没有单个要素的渐变示例&#xff0c;我们这里来补充一下。OpenLayers中的渐变是通过fi…
阅读更多...
最新文章

Copyright @ 2022~2023