首页 > 其他分享 > 回溯 切割问题

回溯 切割问题

时间:2022-10-13 10:44:18浏览次数:79  
标签:pointNum return 切割 int 问题 start startIndex result 回溯

leetcode 131

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

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

示例 1:

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

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

思路

由于也是将字符串中的a拿出来,然后再与字符串当中的字母进行组合,所以其实也相当于组合问题,只不过,还多了一个判断是否为回文子串的问题。
所以可以考虑用回溯三部曲来分析做题。

返回值与参数

全局变量 result与path分别存储全部的结果与每次的结果,另外还可以添加一个参数startIndex,记录遍历的位置,也就是初始的位置,方便往下递归时候调用。

vector<vector<string>> result;//存储全部的结果
vector<string> path;
void backtracking(const string& s,int starIndex )

递归函数与终止条件

如果选取的位置大于或者等于s字符串的大小,那么就可以判断为取到合适的回文字符串;

if(startIndex >= s.size()){
result.push_back(path);
return;
}

遍历

for依然适用于横向遍历,递归适合往下遍历;这道题当中,还有一个问题就是判断所取得的字符串是否为回文。

for(int i = starIndex;i < s.size();i++)
        {
            if(isPalindrome(s,starIndex,i)){
                //判断是否是回文子串,获取[startIndex]在s中的子串
                string str = s.substr(starIndex,i - starIndex + 1);
                path.push_back(str);
            }
            else{
                continue;
            }
            backtracking(s,i+1); //寻找i+1的起始位置的子串
            path.pop_back(); //回溯过程,弹出本次已经处理的子串
        }

判断回文的函数:

bool isPalindrome(const string& s,int start,int end)
    {
        for(int i = start, j = end;i < j;i++,j--)
        {
            if(s[i] != s[j])
            {
                return false;
            }
        }
        return true;
    }

所有代码

class Solution {
private:
    vector<vector<string>> result;//存储全部的结果
    vector<string> path;
    void backtracking(const string& s,int starIndex ){
        if(starIndex >= s.size())
        { 
            //递归终止条件,是否大于该大小,如果大于就说明获得了一个数组
            result.push_back(path);
            return;
        }
        for(int i = starIndex;i < s.size();i++)
        {
            if(isPalindrome(s,starIndex,i)){
                //判断是否是回文子串
                string str = s.substr(starIndex,i - starIndex + 1);
                path.push_back(str);
            }
            else{
                continue;
            }
            backtracking(s,i+1);
            path.pop_back();
        }

    }
    bool isPalindrome(const string& s,int start,int end)
    {
        for(int i = start, j = end;i < j;i++,j--)
        {
            if(s[i] != s[j])
            {
                return false;
            }
        }
        return true;
    }
public:
    vector<vector<string>> partition(string s) {
      result.clear();
      path.clear();
      backtracking(s,0);
      return result;
    }
};

小结

本题难点:

  • 判断这个为回溯问题:将分割问题抽象为回溯
  • 判断的依据:题目字眼中有分割,重新组合,需要for循环多次遍历的
  • 本题当中,还需要考虑的一个问题就是判断字符串回文

leetcode 93

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

例如:"0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址,但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 无效 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"]

思路

切割问题,可以直接套用回溯三部曲进行分析

参数与返回值

本题主要就是分割数字段,除了记录下一层递归分割的起始位置的参数startIndex,还需要一个记录分段点数值pointNum;

vector<string> result;
//startIndex记录起始值,pointNum记录点的数量
void backtracking(string& s,int startIndex,int pointNum)

终止条件与递归函数

因为要分4段,所有就需要切三次,所以点数值保证在3就可以终止了,其次就是保证该字段的有效性。

if(pointNum == 3)
        {
           if(isValid(s, startIndex, s.size()-1))//需要添加判断字段有效性的函数
           {
               result.push_back(s);
           }
           return;
        }

遍历

for 横向遍历,递归函数向下遍历;

for (int i = startIndex; i < s.size();i++)
        {
            if(isValid(s,startIndex,i))
            {
                s.insert(s.begin()+i+1,'.');
                pointNum++;
                backtracking(s,i+2,pointNum);
                pointNum--;
                s.erase(s.begin() + i + 1);
            }else break;
        }

判断网络段的有效性,有三点:

  • 段位不能以0开头
  • 段位里有非正整数字符不合法
  • 不能大于255

所以函数为:

bool isValid(const string& s,int start,int end)
    {
        if(start > end)
        {
            return false;
        }
        if(s[start]=='0' && start != end)
        {
            return false;
        }
        int num = 0;
        for(int i = start;i <= end;i++){
            if (s[i] > '9' || s[i] < '0')
            {
                return false;
            }
            num = num*10 + (s[i] - '0');
            if(num > 255)
            {
                return false;
            }
        }
        return true;
    }

全部代码

class Solution {
private:
    vector<string> result;
    //startIndex记录起始值,pointNum记录点的数量
    void backtracking(string& s,int startIndex,int pointNum)
    {
        if(pointNum == 3)
        {
           if(isValid(s, startIndex, s.size()-1))
           {
               result.push_back(s);
           }
           return;
        }
        for (int i = startIndex; i < s.size();i++)
        {
            if(isValid(s,startIndex,i))
            {
                s.insert(s.begin()+i+1,'.');
                pointNum++;
                backtracking(s,i+2,pointNum);
                pointNum--;
                s.erase(s.begin() + i + 1);
            }else break;
        }
    }
    bool isValid(const string& s,int start,int end)
    {
        if(start > end)
        {
            return false;
        }
        if(s[start]=='0' && start != end)
        {
            return false;
        }
        int num = 0;
        for(int i = start;i <= end;i++){
            if (s[i] > '9' || s[i] < '0')
            {
                return false;
            }
            num = num*10 + (s[i] - '0');
            if(num > 255)
            {
                return false;
            }
        }
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        if (s.size() > 12) return result;
        backtracking(s,0,0);
        return result;

    }
};

本题小结

难点:

  • 切割问题转化为回溯算法思考
  • 对于题设当中的关键参数,能不能转化为代码
  • 本题的判断段位值的有效性

标签:pointNum,return,切割,int,问题,start,startIndex,result,回溯
From: https://www.cnblogs.com/7xiaomao/p/16787332.html

相关文章

  • element-ui的el-input设置number类型后的相关问题
    element-ui的el-input,设置type="number"后,后边会多一个上下箭头,并且在中文输入法输入数据的时候,光标上移!! 前端的强迫症啊(凭啥你这输入框和别人的不一样,凭啥你光标就......
  • 网页乱码问题
    字符编码是指对于一个具体的“文字”(字符),其内部设定的编号是多少(是一个数字)。任何一个国家的文字的字符,都会在操作系统内部预先定义好一个编码值——这就是字符编码。在htm......
  • 库存超发问题
    1.库存超发的原因是什么?在执行商品购买操作时,有一个基本流程:例如初始库存有3个。第一个购买请求来了,想买2个,从数据库中读取到库存有3个,数量够,可以买,减库存后,更新库存为1个......
  • 开发过程冷门问题汇总
    1.如何让gif动图每一次都重新加载,达到显示动画效果的目的?问题产生原因:浏览器的缓存机制,为了更快的渲染,浏览第一次加载后会对图片进行缓存解决办法:加时间戳,加随机......
  • Python相对路径导入问题
    如果某个项目的文件结构如上,想要在f1.py中导入pkg包的时候,可能会这样写:from....importpkg但是很遗憾,这样会引发ImportError异常。直接运行f1.py时,异常信息是Import......
  • 企业大数据发展面临问题之存算分离技术思考
    @目录概述背景为何要存算分离优势应用场景存算分离产品技术流派华为JuiceFSHashDataXSKY概述背景Hadoop一出生就是奔存算一体设计,当时设计思想就是存储不动而计算(code......
  • JMeter响应数据中文乱码问题
    解决方法1.打开JMeter安装目录->bin文件夹->jmeter.properties文件2.编辑文件搜索关键字sampleresult.default.encoding删掉注释符#编码替换为UTF-8......
  • ORA-01440: 要减小精度或标度, 则要修改的列必须为空问题修复
    环境准备:使用oracle数据库:createtabletable01(idnumber(16)notnull,namevarchar2(50)defaultnull,moneynumber(12,6)defaultnull,primarykey......
  • 【万能的圈友】SQL Server 磁盘空间不足问题分析
    JZGKCHINA工控技术分享平台技术交流与分享 是剑指工控全部的意义所在不论你在哪里,不论你遇到怎样的技术问题,剑指工控群里总有那么一群带有工控情结的技术人与你一起面对,一......
  • cesium教程9-加载倾斜摄影并解决高度问题
    无人机航拍的倾斜摄影,用照片和视频处理生成三维模型,一般照片都带有坐标信息,所以一般都能定位的比较准确,但是经常会出现高度偏差,这个时候就需要特殊处理了。今天航拍建模的......