代码随想录刷题笔记-Day25

1. 分割回文串

131. 分割回文串icon-default.png?t=N7T8https://leetcode.cn/problems/palindrome-partitioning/

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

回文串 是正着读和反着读都一样的字符串。

示例 1:

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

示例 2:

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

解题思路

要做的流程就是以每一个字符为启示,每一个字符为终止,判断是否为回文数,所以使用回溯。

代码

class Solution {
    List<List<String>> res = new ArrayList<>();
    Deque<String> list = new LinkedList<>();

    public List<List<String>> partition(String s) {
        helper(s, 0);
        return res;
    }

    public void helper(String s, int i) {
        if (i >= s.length()) {
            res.add(new ArrayList(list));
            return;
        }
        for (int j = i; j < s.length(); j++) {
            if (isPalindrome(s, i, j )) {
                String str = s.substring(i, j + 1);
                list.addLast(str);
            } else {
                continue;
            }

            helper(s, j + 1);
            list.removeLast();

        }
    }

    public boolean isPalindrome(String str, int left, int right) {
        while (left < right) {
            if (str.charAt(left++) != str.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

2. 复原IP地址

93. 复原 IP 地址icon-default.png?t=N7T8https://leetcode.cn/problems/restore-ip-addresses/

有效 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 '.' 分隔。

  • 例如:"0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址,但是 "0.011.255.245""192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ,用以表示一个 IP 地址,返回所有可能的有效 IP 地址,这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1:

输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]

示例 2:

输入:s = "0000"
输出:["0.0.0.0"]

示例 3:

输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

解题思路

需要找到一个字符串的组合方式,这是一个回溯问题。

  • 终止条件:当开始位置大于字符串长度的时候,加入返回值。
  • 参数:一个字符串,一个起始索引
  • 回溯逻辑:循环遍历起始索引开始的位置,对每一个切分出来的数字判断,如果不满足就break掉(剪枝),满足就进入下一层递归。

代码

 

class Solution {
    List<String> res = new ArrayList<>();

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

    public void backtracking(String s, int startIndex, int pointCount) {
        if (pointCount == 3) {
            if (isIpParam(s, startIndex, s.length() - 1))
                res.add(s);
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            if (isIpParam(s, startIndex, i)) {
                s = s.substring(0, i + 1) + "." + s.substring(i + 1, s.length());
                backtracking(s, i + 2, pointCount + 1);
                s = s.substring(0, i + 1) + s.substring(i + 2, s.length());
            } else {
                break;
            }
        }
    }

    public boolean isIpParam(String s, int startIndex, int endIndex) {
        if (startIndex > endIndex)
            return false;
        if (s.charAt(startIndex) == '0' && startIndex != endIndex)
            return false;
        int num = 0;
        while (startIndex <= endIndex) {
            num = num * 10 + (s.charAt(startIndex) - '0');
            if (num > 255)
                return false;
            startIndex++;
        }
        return true;
    }
}

3. 子集

78. 子集icon-default.png?t=N7T8https://leetcode.cn/problems/subsets/

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1:

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

示例 2:

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

解题思路

要在不重复的集合内,找到所有的子集,所有的子集也就是要记录所有的回溯算法的路径。回溯算法本身就是不重复路径的。所以在回溯算法一开始就要进行result的add操作。每执行一次函数就add一次。本身回溯算法的第一次递归中,就会以每个节点为起点进行操作,在以每个节点为起点的操作的下个迭代中,又是以每一个节点为起点的迭代。

代码

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> list = new LinkedList<>();

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

    public void backTrack(int[] nums, int index) {
        res.add(new ArrayList(list));
        if (index == nums.length)
            return;

        for (int i = index; i < nums.length; i++) {
            list.add(nums[i]);
            backTrack(nums, i + 1);
            list.removeLast();
        }
    }

}

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

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

相关文章

端智能:面向手机计算环境的端云协同AI技术创新

近年来&#xff0c;随着移动端设备软硬件能力的进步&#xff0c;移动端的算力有了很大提升&#xff0c;同时面向移动端的机器学习框架和模型轻量化技术越来越成熟&#xff0c;端上的AI能力逐渐进入大众视野&#xff0c;端智能在电商领域也开始逐步走向规模化应用。通过持续探索…

动态规划之解码方法【LeetCode】

动态规划之解码方法 91. 解码方法解法1解法2 91. 解码方法 91. 解码方法 解法1 状态表示&#xff08;这是最重要的&#xff09;&#xff1a;dp[i]表示以第i个字符为结尾&#xff0c;解码方法的总数。 状态转移方程&#xff08;最难的&#xff09;&#xff1a;根据最近的一步来…

故障诊断 | 一文解决,PSO-BP粒子群算法优化BP神经网络模型的故障诊断(Matlab)

文章目录 效果一览文章概述模型描述源码设计参考资料效果一览 文章概述 故障诊断 | 一文解决,PSO-BP粒子群算法优化BP神经网络模型的故障诊断(Matlab) 粒子群优化算法(Particle Swarm Optimization, PSO)是一种群体智能优化算法,用于求解优化问题。BP神经网络是一种用于模…

【机器学习】线性回归模型(Linear Regression)

&#x1f338;博主主页&#xff1a;釉色清风&#x1f338;文章专栏&#xff1a;机器学习&#x1f338;今日语录:温柔的一半是知识&#xff0c;没有知识的涵养撑不起你想要的风骨。 ☘️0文章预览 本系列文章主要是根据吴恩达老师的机器学习课程以及自己的理解整合而成&#xf…

【MySQL】基本查询(表的增删改查)-- 详解

CRUD&#xff1a;Create&#xff08;创建&#xff09;&#xff0c;Retrieve&#xff08;读取&#xff09;&#xff0c;Update&#xff08;更新&#xff09;&#xff0c;Delete&#xff08;删除&#xff09;。 一、Create insert [into] table_name [(column [, column] ...)] v…

2月28日做题总结(C/C++真题)

今天是2月28日&#xff0c;做题第三天。道阻且长&#xff0c;行则将至&#xff1b;行而不辍&#xff0c;则未来可期&#xff01; 第一题 static char a[2]{1,2,3};说法是否正确&#xff1f; A---正确 B---错误 正确答案&#xff1a;B 解析&#xff1a;数组定义时&#xf…

Linux系统——Nginx拓展

目录 一、重写功能——rewrite 1.if 1.1 if 2. return 2.1状态码301和302的区别 301 302 3. set 4. break 5. rewrite 5.1 rewrite flag使用 5.2 flag说明 5.3举例 5.3.1访问 bj 跳转 beijing 5.3.2举例——break 5.3.3 http 转 https 5.3.4 break 与 last …

JavaScript 进阶03

编程思想 面向过程 面向过程就是分析出解决问题所需要的步骤&#xff0c;然后用函数把这些步骤一步一步实现&#xff0c;使用的时候再一个一个的依次调用 面向对象 面向对象是把事务分解成为一个个对象&#xff0c;然后由对象之间分工与合作。 在面向对象程序开发思想中&a…

kali安装ARL灯塔(docker)

1、root身份进入容器 ┌──(root㉿Kali)-[~/桌面] └─# su root ┌──(root㉿Kali)-[~/桌面] └─# docker 2、先更新再克隆 ┌──(root㉿Kali)-[~/桌面] └─# apt-get update …

如何在windows系统部署Lychee网站,并结合内网穿透打造个人云图床

文章目录 1.前言2. Lychee网站搭建2.1. Lychee下载和安装2.2 Lychee网页测试2.3 cpolar的安装和注册 3.本地网页发布3.1 Cpolar云端设置3.2 Cpolar本地设置 4.公网访问测试5.结语 1.前言 图床作为图片集中存放的服务网站&#xff0c;可以看做是云存储的一部分&#xff0c;既可…

蓝桥杯-常用STL(三)

常用STL &#x1f388;1.映射&#x1f388;2.map的基础使用&#x1f52d;2.1引入库&#x1f52d;2.2构造一个映射&#x1f52d;2.3插入一对映射&#x1f52d;2.4判断关键字是否存在&#x1f52d;2.5遍历映射&#x1f52d;2.6清空 &#x1f388;1.映射 &#x1f50e;映射是指两个…

xss.haozi.me靶场练习

靶场地址alert(1) 1、第一关 输入在文本框里面&#xff0c;我们闭合前面的标签&#xff0c;中间的内容我们就可以随意写了 2、第二关 逃逸value的属性即可&#xff0c;这里使用点击事件触发xss 3、第三关 看代码&#xff0c;使用了正则表达式&#xff0c;去掉了所有的括号字…

Apache POl

介绍 Apache POl是一个处理Miscrosoft Ofice各种文件格式的开源项目。简单来说就是&#xff0c;我们可以使用 POI 在 Java 程序中对Miscrosoft Office各种文件进行读写操作,一般情况下&#xff0c;POI都是用于操作 Excel 文件。 Apache POl 的应用场景 1.银行网银系统导出交易…

如何正确清除电脑的缓存垃圾?终于明白了!

前言 新的电脑总是好的&#xff0c;各种干净整洁无垃圾。 使用了一段时间之后&#xff0c;小伙伴们就会发现电脑C盘飙红了。然后就各种论坛查找清除电脑垃圾的方法。 电脑正常使用下&#xff0c;是会产生很多缓存的&#xff0c;所以C盘红了也很正常。除非电脑组装之后不开机&a…

如何做代币分析:以 TRX 币为例

作者&#xff1a;lesleyfootprint.network 编译&#xff1a;cicifootprint.network 数据源&#xff1a;TRX 代币仪表板 &#xff08;仅包括以太坊数据&#xff09; 在加密货币和数字资产领域&#xff0c;代币分析起着至关重要的作用。代币分析指的是深入研究与代币相关的数据…

量子算法入门—4.量子比特与量子门(1)

1.量子比特 经典比特和量子比特 经典比特只有0、1两种取值&#xff0c;非黑即白&#xff0c;有n位即 2 n 2^n 2n种可能量子比特使用0、1的量子态描述量子比特的状态&#xff0c;可以通过线性组合形成新的量子态&#xff0c;就像光谱可以调节成分 引入线代记法&#xff0c;0、…

java程序设计案例教程王希军,渣本二面阿里受挫

1 JVM的内存区域布局 java代码的执行步骤有三点 java源码文件->编译器->字节码文件字节码文件->JVM->机器码机器码->系统CPU执行 JVM执行的字节码需要用类加载来载入&#xff1b;字节码文件可以来自本地文件&#xff0c;可以在网络上获取&#xff0c;也可以实时…

【Go语言】Go语言中的切片

Go语言中的切片 1.切片的定义 Go语言中&#xff0c;切片是一个新的数据类型数据类型&#xff0c;与数组最大的区别在于&#xff0c;切片的类型中只有数据元素的类型&#xff0c;而没有长度&#xff1a; var slice []string []string{"a", "b", "c…

android应用开发基础知识,安卓面试2020

第一章&#xff1a;设计思想与代码质量优化 1、设计思想六大原则 2、三大设计模式 3、数据结构 4、算法 第二章&#xff1a;程序性能优化 1、启动速度和执行效率优化 2、布局检测与优化 3、内存优化 4、耗电优化 5、网络传输与数据存储优化 6、APK大小优化 7、屏幕适配 8、…

Sora - 真正单兵作战时代来临了

一、 OpenAI Sora 视频生成模型技术报告总结 不管是在视频的保真度、长度、稳定性、一致性、分辨率、文字理解等方面&#xff0c;Sora都做到了SOTA&#xff08;当前最优&#xff09;。 技术细节写得比较泛&#xff08;防止别人模仿&#xff09;大概就是用视觉块编码&#xff08…