一般来讲这类问题 dp 比较多,因为很多时候只要返回数量的话,并不一定需要穷举所有情况,有很多利用 subproblem 重复还有对称性的 trick 可以用。
这题作为 google 近期热点题,挺有意思的,有趣在里面的细节和考点很多。
这个更多算是误会,实际上的连线没有那么复杂,走一个马步形状是不算 go through 的,因此最简单的办法,反正键盘数量有限,真正需要考虑的线路总共就 8 条,开个数组写出来就好了。
如果 passThrough 是 0 ,说明 i,j 的连线不过其他点;
其他情况说明 passThrough 的值就是路过需要检查的点。
这里的 dfs 结构更接近于 Tree 的形式,传进去的参数是当前在考虑的元素(但是已经确认是 valid input),还没有做任何 visited 的标记和计数。因此有别于大多数其他 backtracking 的问题在循环里 backtrack,这个是在 dfs 函数自身的开始 / 结束处做 backtracking.
另外一点是,我们有一个长度区间,而不仅仅是像大多数搜索问题那样,找到叶节点 / 找到解直接返回。这题当我们找到一个合理解的时候,需要继续往下探索,同时把以当前节点为起点,下面所有在合理深度范围的路径个数融合返回。
处理这个问题的一个简单,稍显暴力的做法,也是下面代码的做法,就是每次搜索时候固定深度,搜到目标深度就不搜了,返回 1 就行。优点是这样代码很好写;缺点是效率不高,因为同一个路径其实探了好几次。尤其在 “返回所有路径” 的搜索模式中,这种做法显然是不占优势的。
Copy public class Solution {
public int numberOfPatterns ( int m , int n) {
int [][] passThrough = new int [ 10 ][ 10 ];
boolean [] visited = new boolean [ 10 ];
// Rows
passThrough[ 1 ][ 3 ] = passThrough[ 3 ][ 1 ] = 2 ;
passThrough[ 4 ][ 6 ] = passThrough[ 6 ][ 4 ] = 5 ;
passThrough[ 7 ][ 9 ] = passThrough[ 9 ][ 7 ] = 8 ;
// Cols
passThrough[ 1 ][ 7 ] = passThrough[ 7 ][ 1 ] = 4 ;
passThrough[ 2 ][ 8 ] = passThrough[ 8 ][ 2 ] = 5 ;
passThrough[ 3 ][ 9 ] = passThrough[ 9 ][ 3 ] = 6 ;
// Diagnals
passThrough[ 1 ][ 9 ] = passThrough[ 9 ][ 1 ] = 5 ;
passThrough[ 3 ][ 7 ] = passThrough[ 7 ][ 3 ] = 5 ;
int count = 0 ;
for ( int i = m; i <= n; i ++ ){
count += 4 * dfs(visited , passThrough , 1 , i - 1 ) +
4 * dfs(visited , passThrough , 2 , i - 1 ) +
dfs(visited , passThrough , 5 , i - 1 ) ;
}
return count;
}
// take currently considering element
private int dfs ( boolean [] visited , int [][] passThrough , int curNum , int lenRemain){
if (lenRemain < 0 ) return 0 ;
if (lenRemain == 0 ) return 1 ;
int count = 0 ;
visited[curNum] = true ;
for ( int i = 1 ; i <= 9 ; i ++ ){
if ( ! visited[i] && (passThrough[curNum][i] == 0 || visited[passThrough[curNum][i]])){
count += dfs(visited , passThrough , i , lenRemain - 1 ) ;
}
}
visited[curNum] = false ;
return count;
}
}
另一种沿途计数的代码实现是这样,具体细节处理我还是得学习一个。。这个写法就很适合输出所有路径了,改一下执行条件即可。
因为能作为参数传进去的 num ,都是valid move,当前的有效长度其实已经是 len + 1 了。
我们做的是一个 Tree 类 DFS,带着一个一定合理但又没加进去的元素进 DFS,长度 +1, 只在函数最开始和末尾做 backtracking.
Copy public class Solution {
public int numberOfPatterns ( int m , int n) {
int [][] passThrough = new int [ 10 ][ 10 ];
boolean [] visited = new boolean [ 10 ];
// Rows
passThrough[ 1 ][ 3 ] = passThrough[ 3 ][ 1 ] = 2 ;
passThrough[ 4 ][ 6 ] = passThrough[ 6 ][ 4 ] = 5 ;
passThrough[ 7 ][ 9 ] = passThrough[ 9 ][ 7 ] = 8 ;
// Cols
passThrough[ 1 ][ 7 ] = passThrough[ 7 ][ 1 ] = 4 ;
passThrough[ 2 ][ 8 ] = passThrough[ 8 ][ 2 ] = 5 ;
passThrough[ 3 ][ 9 ] = passThrough[ 9 ][ 3 ] = 6 ;
// Diagnals
passThrough[ 1 ][ 9 ] = passThrough[ 9 ][ 1 ] = 5 ;
passThrough[ 3 ][ 7 ] = passThrough[ 7 ][ 3 ] = 5 ;
return 4 * dfs(visited , passThrough , 1 , 1 , m , n) +
4 * dfs(visited , passThrough , 2 , 1 , m , n) +
dfs(visited , passThrough , 5 , 1 , m , n) ;
}
//
private int dfs ( boolean [] visited , int [][] passThrough , int curNum , int curLen , int m , int n){
int cumuCount = 0 ;
if (curLen >= m) cumuCount ++ ;
if (curLen >= n) return cumuCount;
visited[curNum] = true ;
curLen ++ ;
for ( int i = 1 ; i <= 9 ; i ++ ){
if ( ! visited[i] && (passThrough[curNum][i] == 0 || visited[passThrough[curNum][i]])){
cumuCount += dfs(visited , passThrough , i , curLen , m , n) ;
}
}
visited[curNum] = false ;
return cumuCount;
}
}
题目换成这样了之后依然是一个搜索问题,但是有了新的有趣特性。
主要在于这题和之前的 combination sum 还不太一样,它把 [1,3] 和 [3,1] 这种重复搜索算成两个解。于是强行制造了 overlap subproblems.
于是这题用搜索解会 TLE,加个 hashmap 做记忆化搜索,立刻就过了。
24ms ,时间复杂度较高,不如下面那个迭代的写法速度快。
O(n^d),d代表得到 >= target 的搜索深度。
Copy public class Solution {
public int combinationSum4 ( int [] nums , int target) {
return dfs(nums , 0 , target , new HashMap < Integer , Integer >()) ;
}
private int dfs ( int [] nums , int curSum , int target , HashMap < Integer , Integer > map){
if (curSum > target) return 0 ;
if (curSum == target) return 1 ;
if ( map . containsKey (curSum)) return map . get (curSum);
int count = 0 ;
for ( int i = 0 ; i < nums . length ; i ++ ){
count += dfs(nums , curSum + nums[i] , target , map) ;
}
map . put (curSum , count);
return count;
}
}
考虑到可能的有效解路径一定是 [0,target] 之间,我们可以开一个定长的 array 做 hash,在 LC 上速度就快很多,1ms.
Copy public class Solution {
public int combinationSum4 ( int [] nums , int target) {
int [] count = new int [target + 1 ];
Arrays . fill (count , - 1 );
return combinationSumHelper(nums , target , count) ;
}
private int combinationSumHelper ( int [] candidates , int target , int [] count){
if (target == 0 ) return 1 ;
if (target < 0 ) return 0 ;
if (count[target] != - 1 ) return count[target];
int sum = 0 ;
for ( int i = 0 ; i < candidates . length ; i ++ ){
sum += combinationSumHelper(candidates , target - candidates[i] , count) ;
}
count[target] = sum;
return count[target];
}
}
另外一种继承了背包类问题思想(Backpack III,单个元素无限取) 的 bottom-up 循环解法,非常的简洁:
时间复杂度 O(n * target)
注意这里内外循环的顺序不能错,要先按 sum 从小到大的顺序看,然后才是遍历每个元素。因为所谓 bottom-up,是相对于 sum 而言的,不是相对于已有元素的 index 而言的。
Copy public class Solution {
public int combinationSum4 ( int [] nums , int target) {
// dp[sum] = number of ways to get sum
int [] dp = new int [target + 1 ];
// initialize, one way to get 0 sum with 0 coins
dp[ 0 ] = 1 ;
for ( int j = 1 ; j <= target; j ++ ){
for ( int i = 0 ; i < nums . length ; i ++ ){
if (j - nums[i] >= 0 ) dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}
}
第一遍写的,改了好多次,如果是面试第一次遇到的话,遇到这类题切记 “细心”。
特殊 case : 11,101,110, 501..
如果遇到有歧义的情况,原理和 climbing stairs 类似,当前位置的合理解个数要考虑到前面两个子问题的合理解个数,即 dp[i] 要看 dp[i - 1] 和 dp[i - 2];
前一位不是 0 ,并且能和当前 digit 组成合理字母,就 dp[i] = dp[i - 1] + dp[i - 2];
前一位组不了,就不产生新路线,dp[i] = dp[i - 1];
重点在于 "0" 的处理。
前一位数不能和当前 0 组成字母,无解,返回 0;
前一位数能和当前的 0 组成字母,dp[i] = dp[i - 2];
Copy public int numDecodings( String s) {
if (s == null || s . length () == 0 ) return 0 ;
if ( s . charAt ( 0 ) == '0' ) return 0 ; // Can't start with 0
int [] dp = new int [ s . length () + 1 ];
dp[ 0 ] = 1 ;
dp[ 1 ] = 1 ;
for ( int i = 1 ; i < s . length (); i ++ ){
int cur = s . charAt (i) - '0' ;
int prev = s . charAt (i - 1 ) - '0' ;
int num = prev * 10 + cur;
if (cur == 0 ){
if (prev == 0 ) return 0 ; // Error - 00
else if (num <= 26 ) dp[i + 1 ] = dp[i - 1 ]; // we can't discard current 0
else return 0 ; // 40, 50, etc.
} else {
if (prev != 0 && num <= 26 ) dp[i + 1 ] = dp[i] + dp[i - 1 ]; // "101" = 1 way
else dp[i + 1 ] = dp[i];
}
}
return dp[ s . length ()];
}
LC 论坛里关于这题还有好多种其他解法,比较简洁的有如下两个:
从左向右:
Copy public int numDecodings( String s) {
if (s == null || s . length () == 0 ) return 0 ;
if ( s . charAt ( 0 ) == '0' ) return 0 ;
int n = s . length ();
int [] dp = new int [n + 1 ];
dp[ 0 ] = 1 ;
dp[ 1 ] = 1 ;
for ( int i = 2 ; i <= n; i ++ ) {
int oneDigit = Integer . valueOf ( s . substring (i - 1 , i));
int twoDigits = Integer . valueOf ( s . substring (i - 2 , i));
if (oneDigit >= 1 && oneDigit <= 9 ) {
dp[i] += dp[i - 1 ];
}
if (twoDigits >= 10 && twoDigits <= 26 ) {
dp[i] += dp[i - 2 ];
}
}
return dp[n];
}
从右向左:
Copy public int numDecodings( String s) {
int n = s . length ();
if (n == 0 ) return 0 ;
int [] memo = new int [n + 1 ];
memo[n] = 1 ;
memo[n - 1 ] = s . charAt (n - 1 ) != '0' ? 1 : 0 ;
for ( int i = n - 2 ; i >= 0 ; i -- )
if ( s . charAt (i) == '0' ) continue ;
else memo[i] = ( Integer . parseInt ( s . substring (i , i + 2 )) <= 26 )
? memo[i + 1 ] + memo[i + 2 ]
: memo[i + 1 ];
return memo[ 0 ];
}