珠海网站建设报价,山西网站建设公司,淘宝联盟微信里做网站,网站怎么做图片栏目回溯法又叫回溯搜索法#xff0c;是搜索的一种方式。回溯法本质是穷举所有可能。如果想让回溯法高效一些#xff0c;可以加一些剪枝操作。回溯算法解决的经典问题#xff1a;组合问题切割问题子集问题排列问题棋盘问题如何去理解回溯法#xff1f;回溯法解决的问题都可以抽…回溯法又叫回溯搜索法是搜索的一种方式。回溯法本质是穷举所有可能。如果想让回溯法高效一些可以加一些剪枝操作。回溯算法解决的经典问题组合问题切割问题子集问题排列问题棋盘问题如何去理解回溯法回溯法解决的问题都可以抽象为树形结构回溯法解决的是在集合中递归查找子集集合的大小构成树的宽度递归的深度构成树的深度。递归就要有终止条件所以必然是一颗高度有限的树N叉树回溯法模板回溯三部曲回溯函数模板返回值以及参数一般返回值都为void回溯函数终止条件if(终止条件){存放结果;return;
}回溯搜索的遍历过程for(选择本层集合中的元素树中节点孩子的数量就是集合的大小){处理节点;backtracking(路径选择列表);//递归回溯撤销处理结果
}组合问题组合在for循环中i的结束条件可以优化即列表剩余元素个数n-i1所需元素个数k-path.size()in-kpath.size()1。组合总和无重复数可重复取组合总和II有重复数不可重复取组合总和III无重复数不可重复取组合总和IV无重复数可重复取且有排列动规问题组合总和III电话号码的字组合数字与字母的映射问题可以用map也可以用一个二维数组将char型转为int型用char-‘0’的方式。组合总和可以重复使用元素所以startIndex直接等于i就行了不能直接每次都从0开始这是排列的情况会有重复出现组合总和II集合中出现了重复元素如果用之前的常规做法会出现下面重复的情况因此需要去重工作。组合总和IV用回溯超时了是动态规划问题。切割问题分割回文串如何切割的问题--确定分割点例如abcdef切割一个a后在bvdef中再去切割第二段如何判断为回文串--写一个bool型函数专门用来判断注意截取子字符串substr(n,m)表示从下标n开始取m个元素。复原IP地址如何切割的问题确定切割点插入.号用已经插入.号的数量来判断是否结束如何判断是否为有效IP地址注意一些细节问题string中插入 insert 擦除erase因为已经插入.号因此下一层递归开始应该在i2处除了只有一个0以外以0开头的数字不合法大于255不合法 bool isValid(string s,int left,int right){if(leftright) return false;if(s[left]0left!right) return false;int xstoi(s.substr(left,right-left1));if(x255) return true;else return false;}子集问题子集 (不含重复元素)子集问题是找树的所有节点而组合和分割问题都是收集树的叶子节点。每个节点都需要保存所以先存再判断终止条件。子集II 含有重复元素在同一层中不可选取相同元素属于树层去重。其实树层去重可以不用used数组直接排序后判断相邻的数是否相同就可以完成树层去重。注意去重都需要排序递增子序列需要解决的问题去重问题仍然是树层的去重但是不能对数组进行排序了于是用哈希表进行去重选取的是符合条件的每个节点其实可以与之前的联系起来相当于可以不用写终止条件排列问题全排列没有重复元素排列问题就不需要startIndex了需要使用used数组来确定该数字在path中已经被取过了。全排列II有重复元素使用used数组哈希表进行树枝去重和数层去重。棋盘问题重新安排行程一个起飞机场对应多个降落机场、并且降落机场是有序的。所以映射后的降落机场用map去存。map中所有元素都是pairpair中第一个元素为key值键值第二个元素为value实值。所有元素都会根据元素的键值自动排序。unordered_mapstring,mapstring,int targets
