Leetcode 1625 图的建模
来源:1-5 大厂面试为什么总考算法?
甲骨文_0001
2023-03-19
老师,1625题我看了您的解法,是图的BFS: 我的理解如下
初始出发顶点是初始字符串,然后针对两种操作(累加, 轮转)分别得到一个相邻节点,最终会形成一幅图。然后在此基础上作bfs遍历来求解字典序最小的字符串。我的理解是对的吗?
这道题我一拿到没思路,图论的知识我有,看了您的解法,又体会到了图的建模的妙用了。
今天早上我按图的bfs思路写一把,通过了 :)
/**
* @param {string} s
* @param {number} a
* @param {number} b
* @return {string}
*/
var findLexSmallestString = function(s, a, b) {
let visited = {}; // 访问历史表
let queue = []; // bfs队列
queue.push(s);
visited[s] = true;
let res = s; // 结果字典序最小
while( queue.length > 0 ){
let nowStr = queue.shift();
let s1 = op1(nowStr, a); // op1 累加 得到相邻顶点
if( !visited[s1] ){
visited[s1] = true;
queue.push(s1);
if( res > s1 ){
res = s1; // ** 记录当前最小字典序
}
}
let s2 = op2(nowStr, b) // op2 轮转 得到相邻顶点
if( !visited[s2] ){
visited[s2] = true;
queue.push(s2);
if( res > s2 ){
res = s2; // ** 记录当前最小字典序
}
}
} // while queue.length
return res;
};
function op1( s, num ){
let res = '';
for( let i = 0; i < s.length; i ++ ){
if( i % 2 == 0 ){
res += s[i];
}else{
res += (parseInt(s[i]) + num)%10;
}
} // for i
return res;
}
function op2( s, num ){
return s.slice( s.length - num ) + s.slice(0, s.length - num);
}
1回答
-
liuyubobobo
2023-03-20
大赞!理解的完全正确。
==========
随便聊两句。
在我看来,这个思路的重点不是 bfs,而是本质是我们在做“暴力搜索”。只不过对于这个搜索空间,使用 bfs 更方便而已。(但其实 dfs 也可以,感兴趣试试看?)
计算机处理问题的一个最重要的思路就是“暴力搜索。很多同学对暴力搜索的理解比较浅,总认为要几层循环才是暴力搜索。但是对于很多问题,问题的解空间不是线性的,所以需要使用类似 bfs 或者 dfs 的方式做暴力搜索。所以,回溯法本质就是一种暴力搜索。
很多问题的“更优解”,本质都是对“暴力搜索”的优化,比如剪枝,比如动态规划(搜索过程做记忆化。)。还有一些问题,利用问题本身的一些性质,但暴力搜索也是一个“底子”,比如二分搜索利用了解空间的单调性,但这也首先要求你能明确解空间,即如果暴力搜索的话,应该怎么做,然后看如何在这个解空间里是否可能“更聪明”的得到解。
从这个角度看,图论可以理解成是当解空间可以被组织成一个图以后,解决相关问题的方法的集合。图论只不过是一种方法而已,但从思维的角度,考虑问题的解空间到底是什么,在很多问题中是更重要的。(当然,也有另外一类问题,解空间是什么是很明显的,怎么在这个解空间更快地得到解是更难的。)
不管怎样,当对问题没有思路的时候,就先用暴力试试看。暴力不一定正确,但很有可能是一个正确的开始。
继续加油!:)
10
相似问题