美团笔试第一题求大佬理思路

第一题可以这么想，默认路径为一条，然后遍历比较每一列的两个值，如果有一列都为x则一条路径都没有，如果有一列都为.则路径条数乘2，其他则路径条数不变。

第一题用动态规划做AC了，其他都没有AC。。。     public static void search(int n,int row,int col) {         if(row == 0 && col == 0){             count++;             return;         }         if(array[row][col].equals("X")){             return;         }         if (array[row][col].equals(".") && row == 0 && col != 0){             search(n,row,col-1);             search(n,row+1, col-1);         }         if (array[row][col].equals(".") && row == 1 && col != 0){             search(n,row-1, col-1);             search(n,row, col-1);         }     }

同45无解，而且后面还不会做mmp

递归45:第二题众数我就不明白了，才9%，不是全部异或一遍就可以了吗

我暴力也是只过了45

我dp做出来36%

我也使用dp，也只过了45，表示没发现哪里出问题了

使用DFS，不知道会不会超时 res = 0 def search(row, rows, col, cols, borad):     global res     if row == rows-1 and col == cols-1:         res+=1         return      if row < 0&nbs***bsp;row >=rows&nbs***bsp;col < 0&nbs***bsp;col >= cols:         return     if borad[row][col] == 1:         return      search(row, rows, col+1, cols, borad)     search(row+1, rows, col+1, cols, borad)     search(row-1, rows, col+1, cols, borad) a =[     [0,0,1,0,1],     [1,1,0,0,0] ] search(0,2,0,5,a) print(res)

深度优先遍历： def dfs(pb, i, j, n, res):     if j == n-1:         if i == 1:             res[0] += 1         return     for ne in get_neigh(i, j, n):         if pb[ne[0]][ne[1]]:             pb[ne[0]][ne[1]] == False             dfs(pb, ne[0], ne[1], n, res)             pb[ne[0]][ne[1]] == True def get_neigh(i, j, x):     neigh = []     if j+1 < x:         neigh.append([i, j+1])     if j+1 < x and i == 0:         neigh.append([i+1, j+1])     if j+1 < x and i == 1:         neigh.append([i-1, j+1])     return neigh if __name__ == '__main__':     n = int(input())     p = []     p.append(list(input()))     p.append(list(input()))     pb = [[True for i in range(n)] for i in range(2)]     for i in range(2):         for j in range(n):             if p[i][j] != '.':                 pb[i][j] = False     pb[0][0] = False     res = [0]     dfs(pb, 0, 0, n, res)     res = res[0] if res[0] > 0 else -1     print(res)

动态规划: if __name__ == '__main__':     n = int(input())     p = []     p.append(list(input()))     p.append(list(input()))     dp = [[0 for i in range(n)] for i in range(2)]     pb = [[True for i in range(n)] for i in range(2)]     for i in range(2):         for j in range(n):             if p[i][j] != '.':                 pb[i][j] = False     dp[-1][-2] = 1 if pb[-1][-2] else 0     dp[-2][-2] = 1 if pb[-2][-2] else 0           for j in range(-3, -n-1, -1):         for i in range(-1, -3, -1):             if pb[i][j]:                 if i == -1:                     dp[i][j] = dp[i-1][j+1] + dp[i][j+1]                 if i == -2:                     dp[i][j] = dp[i][j+1] + dp[i+1][j+1]     res = dp[0][0] if dp[0][0] > 0 else -1     print(res)

第一题就dp想的太难了吧。。

while True:     try:         n=int(input())         line1=input()         line2=input()         res=1                      if line2[-1]=='X':             print(-1)             break         if n==1:             print(1)             break         for i in range(1,n):             temp=0             if line1[i]=='.':                 temp+=1             if line2[i]=='.':                 temp+=1             if temp==0:                 print(-1)                 break             res*=temp         print(res)         except:         break

递归做的也是45

同45，不知道错哪儿了     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         String nn = sc.nextLine();         int n = Integer.valueOf(nn);         String a1 = sc.nextLine();         String a2 = sc.nextLine();         char[][] arr = new char[3][n+1];         for (int i = 1; i <= n; i++) {             arr[1][i] = a1.charAt(i - 1);         }         for (int i = 1; i <= n; i++) {             arr[2][i] = a2.charAt(i - 1);         }         int[][] dp = new int[3][n + 1];         dp[1][1] = 1;         dp[2][1] = 0;         for (int i = 2; i <= n; i++) {             if (arr[1][i] == 'X') {                 dp[1][i] = 0;             } else {                 dp[1][i] = dp[1][i - 1] + dp[2][i - 1];             }             if (arr[2][i] == 'X') {                 dp[2][i] = 0;             } else {                 dp[2][i] = dp[2][i - 1] + dp[1][i - 1];             }         }         System.out.println(dp[2][n] == 0 ? -1 : dp[2][n]);     }

害，我第一题用dp ac了45%,第二题暴力36%，明明感觉很简单，我死活找不到错误。一气之下直接交卷了。 又没有大佬帮我看看我的第一题代码到底啥问题 def calWagsNums(n, row1, row2):     grids = [row1, row2]     if grids[0][0] == "X":         return -1     dp = [[0 for _ in range(n)] for _ in range(2)]     dp[0][0], dp[1][0] = 1, 0     grids[0][0] = 1     for j in range(1, n):         for i in range(2):             if grids[i][j] == "X":                 continue             dp[i][j] = 0             if j - 1 >= 0:                 dp[i][j] += dp[i][j - 1]                 if i - 1 >= 0:                     dp[i][j] += dp[i - 1][j - 1]                 if i + 1 < 2:                     dp[i][j] += dp[i + 1][j - 1]     return dp[-1][-1] if dp[-1][-1] != 0 else -1

遍历数组45%（我感觉这种是最快的）：设置一个数组，[0][0]初始为1，[0][1]初始为0，然后每一列每一列去考虑，每一列如果是X则直接设置为0，否则就加上左边一列的两个数字，比如第二列第一行[0][1]如果是x就直接设置为0，否则[1][1]=[0][0]+[1][0]；第二列第二行[1][1]如果是x就直接设置为0，否则[1][1]=[0][0]+[1][0]，最后直接输出最后一行最后一列就行了

醉了，我也是45%，想了半天也不知道错在哪了。

同dp，45分。。没想出来自己哪有问题。。。。

同45% 总个数a，直接从第2到N-1列，每一列有俩X，直接-1，如果一个X，a不变，如果没有X，a=a*2

第一题我也45.。。。。第三题大佬们不超时怎么做的？