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 的方式做暴力搜索。所以,回溯法本质就是一种暴力搜索。


很多问题的“更优解”,本质都是对“暴力搜索”的优化,比如剪枝,比如动态规划(搜索过程做记忆化。)。还有一些问题,利用问题本身的一些性质,但暴力搜索也是一个“底子”,比如二分搜索利用了解空间的单调性,但这也首先要求你能明确解空间,即如果暴力搜索的话,应该怎么做,然后看如何在这个解空间里是否可能“更聪明”的得到解。


从这个角度看,图论可以理解成是当解空间可以被组织成一个图以后,解决相关问题的方法的集合。图论只不过是一种方法而已,但从思维的角度,考虑问题的解空间到底是什么,在很多问题中是更重要的。(当然,也有另外一类问题,解空间是什么是很明显的,怎么在这个解空间更快地得到解是更难的。)


不管怎样,当对问题没有思路的时候,就先用暴力试试看。暴力不一定正确,但很有可能是一个正确的开始。


继续加油!:)

1
0

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7451 学习 · 1159 问题

查看课程