摘要:例如,當為時,機器人能夠進入方格,因為。請問該機器人能夠達到多少個格子分析這題和上題劍指矩陣中的路徑屬于同一類型的題目。
題目
{% cq %} 地上有一個m行和n列的方格。一個機器人從坐標0,0的格子開始移動,每一次只能向左,右,上,下四個方向移動一格,但是不能進入行坐標和列坐標的數(shù)位之和大于k的格子。 例如,當k為18時,機器人能夠進入方格(35,37),因為3+5+3+7 = 18。但是,它不能進入方格(35,38),因為3+5+3+8 = 19。請問該機器人能夠達到多少個格子? {% endcq %}
分析這題和上題劍指Offer:矩陣中的路徑屬于同一類型的題目。所以大致思路相同,只需要將判斷條件變成判斷他是否能夠達到相應的格子(即判斷即將進入個格子行坐標和列坐標的數(shù)位之和是否大于k) 而且其實坐標已經(jīng)確定了,實現(xiàn)相對簡單
public class Solution { public int movingCount(int threshold, int rows, int cols) { if (threshold < 0 || rows <= 0 || cols <= 0) return 0; boolean[] visited = new boolean[rows*cols]; return moveCount(threshold, rows, cols, 0, 0, visited); } public int moveCount(int threshold, int rows, int cols, int row, int col, boolean[] visited) { int count = 0; if (isOK(threshold, row, col) && row >= 0 && col >= 0 && row < rows && col < cols && !visited[cols*row+col]) { visited[row*cols + col] = true; count = 1 + moveCount(threshold, rows, cols, row-1, col, visited) + moveCount(threshold, rows, cols, row, col-1, visited) + moveCount(threshold, rows, cols, row+1, col, visited) + moveCount(threshold, rows, cols, row, col+1, visited); } return count; } // 判斷即將進入個格子行坐標和列坐標的數(shù)位之和是否大于k public boolean isOK(int threshold, int row, int col){ int sum = 0; while (row != 0){ sum += (row%10); row /= 10; } while (col != 0){ sum += (col%10); col /= 10; } if (sum > threshold) return false; else return true; } }
文章版權歸作者所有,未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/69255.html
摘要:有效三角形的個數(shù)雙指針最暴力的方法應該是三重循環(huán)枚舉三個數(shù)字。總結本題和三數(shù)之和很像,都是三個數(shù)加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸,所以空間復雜度為 ...
摘要:附上和實現(xiàn)二維數(shù)組中的查找題目描述在一個二維數(shù)組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數(shù),輸入這樣的一個二維數(shù)組和一個整數(shù),判斷數(shù)組中是否含有該整數(shù)。 為了實習的準備,開始刷題來鞏固基礎算法和數(shù)據(jù)結構,大神輕噴。 1.數(shù)組中重復的數(shù)字 題目描述:在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復的,但不知道有...
摘要:題目在一個長度為的數(shù)組里面的所有數(shù)字都在的范圍內(nèi),所以數(shù)組中至少有一個數(shù)字是重復的。請找出數(shù)組中任意一個重復的數(shù)字,但不能修改輸入的數(shù)組。例如,如果輸入長度為的數(shù)組,那么對應的輸出是重復的數(shù)字或者。 題目 在一個長度為n+1的數(shù)組里面的所有數(shù)字都在1~n的范圍內(nèi),所以數(shù)組中至少有一個數(shù)字是重復的。請找出數(shù)組中任意一個重復的數(shù)字,但不能修改輸入的數(shù)組。例如,如果輸入長度為9的數(shù)組{2,3...
摘要:題目描述在一個長度為的數(shù)組里的所有數(shù)字都在到的范圍內(nèi)。請找出數(shù)組中任意一個重復的數(shù)字。例如,如果輸入長度為的數(shù)組,那么對應的輸出是第一個重復的數(shù)字。判斷數(shù)組是否為空參考劍指 題目描述 在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復的,但不知道有幾個數(shù)字是重復的。也不知道每個數(shù)字重復幾次。請找出數(shù)組中任意一個重復的數(shù)字。 例如,如果輸入長度為7的數(shù)組{2,...
摘要:假設反轉對象節(jié)點為,反轉指向的結點為,反轉后指向的結點為首結點。當然也可以根據(jù)棧先進后出的特點,使用棧反轉鏈表。 ??前面的話?? 大家好!博主開辟了一個新的專欄—...
閱讀 2571·2021-08-20 09:38
閱讀 1355·2019-08-30 15:43
閱讀 593·2019-08-29 17:13
閱讀 1601·2019-08-29 14:01
閱讀 1314·2019-08-29 13:29
閱讀 2322·2019-08-23 18:29
閱讀 2047·2019-08-23 17:51
閱讀 1915·2019-08-23 17:16