Trackback: 经典书目系列
前言
对于回溯算法,一开始接触感觉还是挺难的,随着刷到的题目的数量增多,慢慢也可以总结出来相应的套路出来。大家一起来看看下面的伪代码
public 返回值 backtrace(起始条件){
if(满足条件){
返回值;
}
for(所有可以的选择){
做出选择a;
backtrace(更新条件);
撤销选择a;
}
}
当我们翻看我们所做过的所有回溯算法的相关题目时,其实可以发现使用的套路,都离不开上面的模板。
其实我们换一个思路来理解回溯算法,回溯说到底也就是一种穷举算法,尝试每一种可能,如果当前这种尝试计算到头都不符合最后的结果,那么我们就依次向后退步,再次尝试新的方案,并没有什么特别神秘的地方。
可是发现这个套路的同学应该也有很多,但是每次遇到回溯算法,依旧很难实现相关代码。其实主要原因在于我们有时候难以选取结束条件,还有就是不清楚我们到底有多少种选择。这才是大多数回溯算法困扰我们的地方。
下面我们一起来看3道比较经典的回溯算法题目,来找找感觉吧~
一、解数独
★LeetCode37 --- 解数独【困难】 ”
题目描述
如图所示:数独要求我们行、列以及九宫格内都不允许出现相同的数字,这样就可以构成一个数独了!
1.1 解题思路
题目会首先给我们一个不完整的9x9
的数独,然后我们需要根据已有的信息,向里面添加数据,构成一个完整的数独。那么我们现在就按照上面的模板来完善这道题。
- 可以做出的选择:每个格子只能选择字符
1--9
,而且只能对未填充的空格进行填写,所以我们首先可以确定自己的选择空间。 - 结束条件:在填写数独的每一个方格时,我们选择从左上角开始,从左到右,一行一行进行填写,直到最后一个方格,所以当我们填写到最后一个方格时,就可以代表之前填写的方格都是成功的,至此也就结束了我们整个解数独的过程。
- 每次更新的条件:通过结束条件我们可以看出,结束条件是依赖于填写的方格的位置的。由此我们可以推断出,每次的更新条件,也就是我们每次进行填写的方格的位置。
下面我们来实现一下我们的思路。
1.2 代码实现
public void solveSudoku(char[][] board) {
if(board == null || board.length != 9 || board[0].length != 9 ) return;//非法数独判断
back(board , 0 , 0);//进入回溯
}
private boolean back(char[][] board , int row , int col){
if(col == 9) return back(board , row+1 , 0);//处理边界情况,此时已经到达了最右边一列,进入下一行的迭代
if(row == 9) return true;//此时已经遍历完了board[8][8],即已经全部遍历完了
if(board[row][col] != '.') return back(board , row , col+1);//当前字符不是空字符
for(char ch = '1' ; ch <= '9' ; ch++){
if(isValid(board , row , col , ch)){//查看当前字符如果放在此处是否合法
board[row][col] = ch;//如果合法,则此字符放置在此处
if(back(board,row,col+1)) return true;//进入递归,查看当前解是否为最终解
board[row][col] = '.';//如果不为最终解,则进行回溯
}
}
return false;
}
private boolean isValid(char[][] board , int row , int col , char ch){
for(int i = 0 ; i < 9 ; i++){
if(board[row][i] == ch) return false;//对当前行进行遍历,查看是否有重复元素
if(board[i][col] == ch) return false;//对当前列进行遍历,查看是否有重复元素
if(board[(row/3)*3 + i/3][(col/3)*3 + i%3] == ch) return false;//对当前方格进行遍历,查看是否有重复元素
}
return true;
}
二、N皇后
★leetcode51---N皇后【困难】 ”
题目描述
2.1 解题思路
首先拿到这道题目,小白是有点懵逼的,不清楚什么是“皇后”之间的攻击,经过一番查阅之后,可以将皇后之间的攻击类比为下面这种情况:
N皇后攻击示意图
也就是说,一个“皇后”会以她自己为中心,进行散射性攻击,所有处于“皇后”对角线,行和列的位置都会被“攻击”,并且这种攻击是一直延续的,并不会受距离的限制。
说到这里,是不是也很类似于上面的解数独的题目。
我们依旧可以按照上面的套路来完成这道题,不过这道题和上一个有一个区别在于,每一个空格只有两种状态,选择或者不选择放置“皇后”。
此处我们按照行来进行遍历,对于“N皇后”问题,每一行都会放置一个“皇后”。所以我们在查询的时候,只需要判断当前位置的上半部分即可,下半部分为空,当前行也是只有一个“皇后”的。在每次的更新条件时,可以仅仅更新下一次回溯时“皇后”所在的行数即可。
2.2 代码实现
List<List<String>> res = new LinkedList<>();
public List<List<String>> solveNQueens(int n) {
if(n <= 0) return res;
char[][] board = new char[n][n];
for(int i = 0 ; i < n ; i++){
Arrays.fill(board[i],'.');
}
back(board , n , 0 );
return res;
}
private void back(char[][] board , int n , int row ){
if(row == n){//完成了一种解法,皇后的数量等于n
LinkedList<String> path = new LinkedList<>();
for(int i = 0 ; i < n ; i++){
StringBuilder sb = new StringBuilder();
for(int j = 0 ; j < n ; j++){
sb.append(board[i][j]);
}
path.add(sb.toString());
}
res.add(path);
return ;
}
for(int j = 0 ; j < n ; j++){
if(isValid(board , n , row , j)){//当前位置可以放置皇后
board[row][j] = 'Q';//做出选择
back(board , n , row+1);
board[row][j] = '.';//撤销选择
}
}
}
private boolean isValid(char[][] board , int n , int row , int col ){
for(int i = 0 ; i < row ; i++){//判断当前列是否已经有皇后
if(board[i][col] == 'Q') return false;
}
for(int left = col-1 , up = row-1 ; left >= 0 && up >= 0 ;left-- , up-- ){//判断左上
if(board[up][left] == 'Q') return false;
}
for(int right = col + 1 , up = row - 1 ; right < n && up >= 0 ; right++ , up--){//判断右上
if(board[up][right] == 'Q') return false;
}
return true;
}
三、组合
★leetcode77----组合【中等】 ”
题目描述
3.1 解题思路
对于此题,我们依旧使用回溯算法来进行实现。我们需要从1---n
中,选取k
个数字,来完成组合,我们按照顺序来依次选择不同的数字进行组合。
- 每次的选择:我们每次选择的时候,应该将已经使用过的数据排除在外,每次的选择都是在剩余的数字中挑选。
- 结束条件:我们使用一个链表
path
来保存每一次的选择数字,当链表的长度为k
的时候,我们就完成了一次选择,所以结束条件应该以path
的长度来判断。 - 每次的更新条件:为了避免重复选择,我们在每次更新条件时,应该限制可选数字的范围,避免重复选择,由于我们是按照顺序来选择每一次的数据,所以,在每次更新条件的时候,应该将下一次可选的第一个数字传输进去。
由此我们再次结束回溯的三个步骤,开始代码实现。
3.2 代码实现
List<List<Integer>> output = new LinkedList<>();//最后的结果
List<Integer> path = new LinkedList<>();//保存每一次的组合
public List<List<Integer>> combine(int n, int k) {
if(n < k || n <= 0 || k <= 0) return output;
backtrace(n , k , 1);
return output;
}
private void backtrace(int n , int k , int start){
if(path.size() == k){//当前组合是满足条件的
output.add(new LinkedList(path));
return;
}
for(int i = start ; i <= n ; i++){
path.add(i);//做出选择
backtrace(n , k , i+1);
path.remove(path.size() - 1);//撤销选择
}
}
推荐阅读
-
玩转轨迹预测!解析系列中的经典网络方法
-
经典 F1 系列游戏《F1 2018》限时免费发售!F1 2018》的简单介绍--有任何问题请在评论区留言,打开官网,将页面向下滚动一点,即可看到《F1 2018》板块,然后点击进入领取,下面是《F1 2018》游戏的简单介绍!
-
[三十六计系列】远交近攻(附经典商业案例)
-
经典考题 8 - 巴林回声系列 - 234.回声链列表(简单)
-
Trackback: 经典书目系列
-
DenseNet、MobileNet、DPN......你都掌握了吗?一篇总结图像分类基本经典模型的文章(二)--MobileNet(MobileNet 系列)
-
经典游戏系列介绍 (1) - 《文明》系列
-
aps是什么意思_不同的富士APS-C画幅微单区别在哪里,档次是怎么划分的?-X-A系列原本指的是富士的入门级微单,最大的特点是没有使用富士X-Trans™CMOS 传感器,目前在售的有两款,分别是XA5和XA7。 富士(FUJIFILM)X-A5/XA5 15-45套机 富士(FUJIFILM)X-A7/XA7 15-45套机 目前这两款相机都处于历史最低价附近,XA5套机2699元,XA7套机3999元。XA5就是一个标准的入门级相机,定位就是时尚小巧自拍,在2699这个价位不要对它的性能有太多的奢求。 XA7价格来到了3999元,这就很有意思了,富士把入门型的相机价格推到了4000元,并且提供了自拍翻转屏和4K30P视频录制,这样一款相机就很有性价比了。 XE3是老款的中端相机,价格和入门级的XA7是一样的,都是3999元,这两款相机如何做选择呢?XE3有着更多的按键意味着更好的操控,但屏幕不是自拍翻转屏所以这点不如XA7好用。 要注意的是XE3用的是富士独有的X-Trans™CMOS III传感器,XA7是普通的2400万像素传感器,你可以理解为X-Trans才是富士的精髓。 富士(FUJIFILM)X-E3 15-45套机 当然,买新不买旧,XA7的新功能和自拍翻转屏可能会更适合你。 XT200是富士专门针对vlog市场推出的相机,其实之前的XA7也可以拍摄vlog,但XT200是富士官方宣传中的第一款vlog相机。数码防抖+3.5mm 麦克风口+自拍翻转屏+无裁切4K30P,这些都是XT200的优势,但这款相机也是普通的2400万像素传感器,没有用富士独有的X-Trans,可能是从价格角度考虑做了阉割吧。 富士(FUJIFILM)X-T200/XT200 微单相机 Vlog相机 富士XT30是我认为富士性价比最高的微单照相机,注意我说的是照相机。理由很简单,因为从拍照角度来看XT30和XTXT3几乎没有明显差距,主要是操控差了一些、视频性能大幅削弱,但好歹也是个有着双波轮+曝光补偿波轮+快门速度波轮的相机,操控方面不会太差的。视频方面也有着超采4K 30P的规格,支持F-log输出。 可以这么说,如果你只拍照,那么XT30是富士微单中性价比最高的,视频方面XT30也不差,只不过没有专业的10bit和4K60P而已。 富士(FUJIFILM)X-T30/XT30 15-45套机 XT3和XT4得放在一起说,这两款相机其实都挺好,420 10bit 4K60P的专业视频模式基本代表了APS-C画幅的上限水平。XT4还提升了电池续航增加了五轴防抖,配上富士独特的胶片滤镜,不管是拍照还是拍视频都非常优秀。 不要觉得这两款相机贵,同价位里能做到4K60P的微单也就是M43画幅的GGHGH5S,最便宜的G9机身也要7000多,这APS-C画幅的XT3机身接近8000也算合理价格范围内。除此之外的4K60P机身只有13998的松下S5和15999的佳能R6了。 富士(FUJIFILM)X-T3/XT3 1855套机 富士(FUJIFILM)X-T4/XT4 微单相机 套机(18-55mm) B站更新4K视频投稿后有很多人想拍摄4K升格,在很长一段时间里富士XT3和XT4是最优选,毕竟兼顾视频和拍照,对焦也还算能用。 X-Pro3和X-Pro2这两款微单可以算是旁轴相机,是富士官方意义上的旗舰级相机。从用料做工操控按键角度来说的确是旗舰级别,但视频性能方面只有4K30P,价格却比XT3还贵,可能这就是旁轴情怀带来的溢价吧。 富士(FUJIFILM)X-Pro3 微单相机 机身 黑色 我在之前的文章里提过很多次,有一些相机属于如果你想买你压根不会看测评,如果你犹豫那么这款相机不适合你,为什么这么说,因为有一些比较小众的相机可能在性能上并不好,但独特的外形、操控、体积、传承赋予了它独特的定位。譬如富士X-Pro系列微单就是旁轴的电子化,理光GR传承大师的扫街理念,尼康DF的外形源自胶片时代的相机,这些相机就不是针对大多数消费者的,定位就是小众。所以我说喜欢就买,不要考虑什么性能规格。 X100系列相机是一款不可换镜头的等效35mm旁轴数码相机,从外形看就是经典的复古造型。这两款相机和X-Pro3一样,如果你喜欢那就买,别犹豫, 你在市场上找不到同类型的其他数码相机,徕卡Q是28mm,索尼RX1R系列是35mm但外形不够复古,X100系列就是独特的你没有其他选择。 那么X100F和X100V该如何选择呢?X100F的镜头很一般甚至算不上好,如果我没记错的话和初代的X100是同款镜头,X100V的镜头是全新制作的很棒,X100V的机身性能也和XTX-Pro3差不多。 富士(FUJIFILM)X100F 数码相机 旁轴 2430万像素 富士(FUJIFILM)X100V 数码相机 旁轴 2610万像素 还是那句话,这两款相机也是那种如果你喜欢那就毫不犹豫下单的类型,而且这两款相机也没有竞品。 以前不推荐富士的原因是原厂镜头太贵,现在唯卓仕给富士出了四款可以自动对焦的大光圈镜头,覆盖35到130mm的焦段,可以基本满足人像摄影爱好者的需求。拍风景的话国产很多镜头厂商都有富士卡口的手动镜头可以选择,从这个角度来说富士微单就非常值得入手了。 和友商竞品相比:
-
语义分割 | 评估指标和经典网络(FCN、DeepLab 系列、UNet、LR-ASPP) - 2. 评估指标
-
雷达无线电系列(III)经典 CFAR 算法阈值因子阿尔法计算(matlab)