北京企业建立网站,高校网站群建设方案,美食网站建设毕业设计,姐妹直播输入#xff1a;deadends 是指针终止状态列表#xff0c;target 是希望到达的指针状态#xff0c;初始化指针状态是0000。 输出#xff1a;如果指针能够到达target状态#xff0c;则变化的最少步骤是多少。如果不能到达target状态#xff0c;返回-1。 分析#xff1a;指…输入deadends 是指针终止状态列表target 是希望到达的指针状态初始化指针状态是0000。 输出如果指针能够到达target状态则变化的最少步骤是多少。如果不能到达target状态返回-1。 分析指针的状态有00000001… 9999 1万种状态。可以看做是1万个节点。 每个状态之间如果只有一个位置上的值有变化则这两个状态之间有连线。例如节点0000和100001000010000190000900…等这些节点有联系。 每个节点上的每一个位置有三种操作减1不变加1。 解决思路就是按照BFS的标准思路。先处理0000节点接着处理与其相邻的节点再依次扩散出去。 本题目很影响效率的地方是节点一个位置坐加1建1的操作变化。 直接操作字符串没有问题只是会慢。
//变换for(int j0;j4;j){int val node.charAt(j)-48;int newVal (val9?0:val1);int newVal1 (val0?9:val-1);String newNode node.substring(0,j)newValnode.substring(j1);if(!set.contains(newNode)){queue.offer(newNode);set.add(newNode);}String newNode1 node.substring(0,j)newVal1node.substring(j1);if(!set.contains(newNode1)){queue.offer(newNode1);set.add(newNode1);}}还有一种思路是用二进制来做。链接。 对于节点node“1234”先转为int。这个int有效位数是16位。这个int是这样的 0001 0010 0011 0100 依次表示1234。 如果需要将2变为3则可以进行如下操作 int mask (1 4) - 1;int[] num new int[]{(nodeInt 12) mask,(nodeInt 8) mask,(nodeInt 4) mask,nodeInt mask};num[1] 1;int res 0;for (int i 0; i 4 ; i) {res 4;res | num[i];}先使用掩码mask把nodeInt的值分成4个值放到数组中。接着修改某一位置的值。最后再通过移位做异或操作成为新的状态。这样速度就快很多。 代码
