首页 > 其他分享 >刷题分享12-2日

刷题分享12-2日

时间:2024-12-02 20:33:34浏览次数:11  
标签:12 return string int res startindex 分享 backtracking 刷题

刷题分享

1.(力扣131)这是一道分割子串的问题,其核心在于理解清除startindex即为当前切割线,而每一层对应的startindex-I这个区间,其实就是当前分割出来的子串

class Solution {
public:
    vector<vector<string>>res;
    vector<string>path;

    bool judge(string s,int l,int r){
        while(l<r){
            if(s[l]==s[r]){
                l++;
                r--;
            }else{
                return false;
            }
        }
        return true;
    }

    void backtracking(string s,int startindex){
        if(startindex>=s.size()){
           res.push_back(path);
           return ;
        }
        for(int i=startindex;i<s.size();i++){
            if(judge(s,startindex,i)){
                string tem;
                tem=s.substr(startindex,i-startindex+1);
   //substr的第二个参数是截取元素的个数,而非结束位置
                path.push_back(tem);
                backtracking(s,i+1);
            }else{
                continue;
            }
            path.pop_back();
        }
    }

    vector<vector<string>> partition(string s) {
        backtracking(s,0);
        return res;
    }
};

2.(力扣93)这道题的核心是掌握在递归调用里,引用的特殊性,每一层递归里的s在逻辑上可以看作是独立的个体,虽然名字相同,但它们有着各自独立的 “生命周期” 和状态管理,res里存储的是之前各层递归结束那一刻对应的s的状态,后续递归中对当前层s的改动不会传导过去

class Solution {
public:
    vector<string>res;
    bool judge(string s,int l,int r){
        if(l>r){
            return false;
        }
        if(s[l]=='0'&&l!=r){
            return false;
        }
        int num=0;
        for(int i=l;i<=r;i++){
            if(s[i]>'9'||s[i]<'0'){
                return false;
            }
            num=num*10+(s[i]-'0');
            if(num>255){
                return false;
            }

        }
        return true;
    }

    void backtracking(string &s,int startindex,int pointnum){
        if(pointnum==3){
            if(judge(s,startindex,s.size()-1)){
                res.push_back(s);
            }
            return ;
        }
        for(int i=startindex;i<s.size();i++){
            if(judge(s,startindex,i)){
                s.insert(s.begin()+i+1,'.');
                pointnum++;
                backtracking(s,i+2,pointnum);
            }else{
                break;
            }
            s.erase(s.begin()+i+1);
            pointnum--;
        }
    }

    vector<string> restoreIpAddresses(string s) {
        backtracking(s,0,0);
        return res;
    }
};

标签:12,return,string,int,res,startindex,分享,backtracking,刷题
From: https://blog.csdn.net/2401_86941858/article/details/144197007

相关文章

  • 2024-12-02:划分数组得到最小的值之和。用go语言,你有两个数组,nums 和 andValues,它们的
    2024-12-02:划分数组得到最小的值之和。用go语言,你有两个数组,nums和andValues,它们的长度分别为n和m。定义数组的“值”为其最后一个元素。你的任务是将nums划分为m个不重叠的连续子数组。对于第i个子数组[li,ri],该子数组的所有元素通过按位与运算后,结果必须等......
  • 力扣刷题TOP101:10.BM12 单链表的排序
    目录:目的思路复杂度记忆秘诀python代码目的{1,3,2,4,5}排序变成{1,2,3,4,5}思路这个任务是将无序单链表变成有序表。推荐使用归并算法。可以理解为汉武帝的推恩令政策(分治思想)。将大块封地分成小块封地(分割链表),对小封地进行整顿,确保符合中央标准(分到最小),将整治......
  • 2024.12.3(周二)
    #导入必要的库fromsklearnimportdatasetsfromsklearn.model_selectionimporttrain_test_split,cross_val_score,StratifiedKFoldfromsklearn.svmimportSVCfromsklearn.metricsimportaccuracy_score,precision_score,recall_score,f1_score,classification......
  • 2024.12.2(周一)
    importnumpyasnpfromsklearnimportdatasetsfromsklearn.model_selectionimporttrain_test_split,cross_val_scorefromsklearn.metricsimportaccuracy_score,precision_score,recall_score,f1_score,confusion_matrix,make_scorerfromsklearn.treeimpo......
  • 2024.12.6(周五)
    #导入相关库importnumpyasnpfromsklearn.datasetsimportload_irisfromsklearn.model_selectionimporttrain_test_split,cross_val_scorefromsklearn.clusterimportKMeansfromsklearn.metricsimportaccuracy_score,precision_score,recall_score,f1_scor......
  • 2024.12.5(周四)
    #导入必要的库importnumpyasnpfromsklearnimportdatasetsfromsklearn.model_selectionimporttrain_test_split,cross_val_score,StratifiedKFoldfromsklearn.naive_bayesimportGaussianNBfromsklearn.metricsimportaccuracy_score,precision_score,reca......
  • 2024.12.9(周一)
    importnumpyasnpimportpandasaspdfromsklearnimportdatasetsfromsklearn.model_selectionimporttrain_test_split,cross_val_score,StratifiedKFoldfromsklearn.ensembleimportRandomForestClassifierfromsklearn.metricsimportaccuracy_score,prec......
  • 12.2 CW 模拟赛 赛时记录
    前言\(12\)月的第一场,没有大样例这次带了耳塞,注意考试方法其实并不复杂,先看题吧带上耳塞,终于舒服了看题\(\rm{T1}\)结论题?\(\rm{T2}\)\(\rm{HS}\)似乎讲过???但是我忘了,一会看能不能推一下多半是找规律\(\rm{T3}\)性质题?\(\rm{T4}\)数据结构维护吧,......
  • 近期计划(2024/12/2 ~ 2024/12/8)
    本文和DailySchedule仓库同步进度。Plan今天是2024年12月2日(校历第十四周),给这周画个饼。月底差不多就要期末考了,这个月要准备各种大作业和水课的期末考,忙起来了(悲),下个月元旦过完差不多放假了(估计1月10日)。蓝桥杯:这周过完理论开始做东西。FJCPCTools:弄个初版,......
  • 基于Java的电子产品租借管理系统的设计与实现-毕业设计源码39512
    基于Java的电子产品租借管理系统的设计与实现摘 要信息化社会内需要与之针对性的信息获取途径,但是途径的扩展基本上为人们所努力的方向,由于站在的角度存在偏差,人们经常能够获得不同类型信息,这也是技术最为难以攻克的课题。针对电子产品租借管理系统的设计与实现等问题,对电......