当前位置: 首页 > news >正文

郑州专业网站制作服务报价二手车网站开发多少钱

郑州专业网站制作服务报价,二手车网站开发多少钱,自己免费网站建设,wordpress dante93.复原IP地址 思路#xff1a; 与分割回文串相似#xff0c;复原ip地址是将给定字符串分割成点分十进制的四段#xff0c;切割问题就可以使用回溯搜索法把所有可能性搜出来。回溯三部曲#xff1a; 递归参数#xff1a;除了传入的需要分割的字符串#xff0c;仍然需要…93.复原IP地址  思路 与分割回文串相似复原ip地址是将给定字符串分割成点分十进制的四段切割问题就可以使用回溯搜索法把所有可能性搜出来。回溯三部曲 递归参数除了传入的需要分割的字符串仍然需要startIndex保证不会重复分割还需要一个变量pointNum来记录已添加的逗点数量。终止条件当分割出四段也就是逗点数量记录为3时说明分割结束。再验证最后一段的合法性若合法就可以加入结果集中。前三段的合法性在添加逗点之前判断因为最后一段之后没有逗点了所以要单独判断。单层逻辑在for循环中判断截取的左闭右闭区间子串 [startIndex, i] 合法后在后面一位加上‘ . ’表示已经分割记录分隔符的变量pointNum加一再从‘ . ’的下一位开始继续递归回溯时将‘ . ’再删除pointNum减一。如果不合法结束本层循环。判断子串是否合法 以0开头但不只有0一个字符的子串不合法含有非0-9字符的子串不合法大于255的不合法剪枝输入长度不合法的字符串时(主函数中)子串不合法时剪枝(isValid)。时间复杂度: O(3^4)IP地址最多包含4个数字每个数字最多有3种可能的分割方式则搜索树的最大深度为4每个节点最多有3个子节点。空间复杂度: O(n) class Solution { private:vectorstring res;//startIndex记录起始位置(切割线)pointNum记录已添加的逗点数量void backtracking(string s, int startIndex, int pointNum) {if(pointNum 3) {//如果已添加三个逗点说明已经切割成四段切割完毕//判断切割的最后一段的合法性合法就收集结果if(isValid(s, startIndex, s.size() - 1)) {res.push_back(s);return;}}for(int i startIndex; i s.size(); i) {if(isValid(s, startIndex, i)) {//判断[startIndex, i]这一段的合法性合法才继续向下执行递归逻辑否则直接结束本层循环s.insert(s.begin() i 1, .);//在这一字段后面添加逗点pointNum;//逗点计数加一backtracking(s, i 2, pointNum);//递归从逗点后一位作为新的起始位置所以是i2pointNum--;//回溯s.erase(s.begin() i 1);//回溯} else break;}}//判断左闭右闭区间[start, end]字符串的合法性bool isValid(const string s, int start, int end) {if(start end) return false;//以0开头但不只有0一个字符的区间不合法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;//大于255则不合法}return true;}public:vectorstring restoreIpAddresses(string s) {res.clear();if(s.size() 4 || s.size() 12) return res;//传入字符串的长度不合法backtracking(s, 0, 0);return res;} }; 78.子集 思路 子集问题是找树的所有节点。集合是无序的子集{1,2} 和 子集{2,1}是一样的取过的元素不会重复取写回溯算法的时候for就要从startIndex开始。求排列问题的时候就要从0开始因为集合是有序的{1, 2} 和{2, 1}是两个集合。回溯三部曲 函数参数除了输入的数组还需要startIndex。终止条件剩余集合为空的时候就是叶子节点此时startIndex已经大于数组的长度了终止递归。其实可以不需要加终止条件因为startIndex nums.size()本层for循环本来也结束了也不会导致无限递归。单层逻辑求取子集问题不需要任何剪枝因为子集就是要遍历整棵树。何时收集结果 我自己实现时的思路是每次path收集完一个元素就收集一个结果在主函数中单独收集空集。后面学习到把收集子集放在终止条件之前就可以不用单独处理空集也不会漏掉集合本身这个子集。时间复杂度: O(n * 2^n)空间复杂度: O(n) class Solution { private:vectorint path;vectorvectorint res;void backtracking(vectorint nums, int startIndex) {res.push_back(path);//收集子集要放在终止添加的上面否则会漏掉自己本身这个子集//if(startIndex nums.size()) return;//终止条件可以不加for(int i startIndex; i nums.size(); i) {path.push_back(nums[i]);backtracking(nums, i 1);path.pop_back();}}public:vectorvectorint subsets(vectorint nums) {path.clear();res.clear();backtracking(nums, 0);return res;} }; 90.子集II 思路 本题与78.子集的区别在于输入集合有重复元素而要求输出的子集要去重在40.组合总和II中已经学习了如何处理这样的情况首先要排序为了让值相等的元素相邻在横向遍历(for循环)时判断当前元素是否与前一个元素值相等若相等则跳过搜索。 class Solution { private:vectorint path;vectorvectorint res;void backtracking(vectorint nums, int startIndex) {res.push_back(path);//if(startIndex nums.size()) return;for(int i startIndex; i nums.size(); i) {//横向遍历时值相同的两个元素不重复选取实现去重if(i startIndex nums[i] nums[i - 1]) continue;path.push_back(nums[i]);backtracking(nums, i 1);path.pop_back();}}public:vectorvectorint subsetsWithDup(vectorint nums) {path.clear();res.clear();sort(nums.begin(), nums.end());//排序方便去重backtracking(nums, 0);return res;} }; 总结 组合问题和分割问题都是收集树的叶子节点而子集问题是找树的所有节点 参考链接 代码随想录复原IP地址   子集   子集II
http://www.sadfv.cn/news/229031/

相关文章:

  • 网站运营公司哪家效果好网站降权怎么救
  • 专注网站建设微信开发北京大学两学一做网站
  • 网站做分站北京城建亚泰建设集团有限公司网站
  • 网络营销的定义及其内容是什么百度爱采购关键词优化
  • 网站建设企业建站哪家好?来这里看看免费的素材库视频无水印
  • 慈溪网站优化创建网站首页
  • 关于进一步加强网站建设和做h5免费软件有哪些
  • apache 搭建多个网站食品包装设计的相关介绍
  • 北京当地网站 点广州网站制作(信科网络)
  • 服务器网站建设流程wordpress ajax 提交表单
  • 海南旅游网站的建设理念wordpress托管服务器
  • 大庆市建设网站wordpress仿微信音乐插件
  • 北京网站seo收费标准竞价推广外包托管
  • 国家级门户网站有哪些seo如何提高排名
  • 深圳网站建设注册长沙的企业网站建设
  • 做网站推广优化哪家好地矿局网站建设方案
  • 如何用源代码做网站搭建网站工具
  • 普法网站建设进入网络管理的网站
  • 制作网站的花多少钱怎么免费下wordpress
  • 宁波网站设计公司排名百度竞价排名魏则西事件分析
  • 网站设计报价表市场营销推广方案模板
  • 网站建设备案是什么意思怎样做网站建设
  • 汉口北做网站用手机做诱导网站
  • 营销型网站建站教程拓者吧室内设计网站
  • 喀什住房和城乡建设局网站口碑好的网站建设价格
  • 小清新网站源码互联网服务商
  • 单页销售网站模板广告公司做网站
  • 网站推广注意事项wordpress 绑定二级域名
  • 电子商务网站的建设流程是怎样的推广信息哪个平台好
  • 网站查询功能是用什么程序做的电子商务公司开发网站