普通版剑指 Offer 浅刷浅刷( 三 ) _数组

>& board, int row, int col, string word, int idx) {//索引和长度相同表示查询完成了if (idx == word.size()) {return 1;}//查询超界直接返回0if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size()) {return 0;}//不匹配返回0if (word[idx] != board[row][col]) {return 0;}//该位置访问过了，做记号，因为上边的严格筛选条件，如果能走到这，那么一定就是该位置已经匹配上了，那么下次就不能用了board[row][col] = '*';//调用该函数继续向四个位置分别匹配查找下一个字符if (backSearchResult(board, row - 1, col, word, idx + 1) || backSearchResult(board, row + 1, col, word, idx + 1) || backSearchResult(board, row, col - 1, word, idx + 1) || backSearchResult(board, row, col + 1, word, idx + 1)) {return true;}//这个写法很妙，走到这，说明上面的这个条件没有成立，即四周没有匹配到下一个字符，那么就回溯，把这之前给该位置赋值的‘*’换回原来的字符board[row][col] = word[idx];return 0;}};
利用回溯的写法，对先查找二维数组中与word第一个字符匹配的位置，然后利用对上下左右四个方向对idx位字符进行匹配，能匹配上了再将这个位置传给下一个该函数再次进行下一个字符（idx + 1）的匹配，一直到匹配完成。
看看别的大哥的思路吧：
剑指 Offer 13. 机器人的运动范围
class Solution {public:int movingCount(int m, int n, int k) {vector> myVector(m, vector(n, 0));int num = 0;judgeMoving(m, n, k, 0, 0, myVector);for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (myVector[i][j]) {num++;}}}return num;}private:bool judgeMoving(int m, int n, int k, int row, int col, vector> &myVector) {if (row < 0 || row >= m || col < 0 || col >= n) {return 0;}//判断该位置是否可以int temp = 0;int tempRow = row, tempCol = col;while (tempRow || tempCol) {temp += tempRow % 10;tempRow /= 10;temp += tempCol % 10;tempCol /= 10;}if (temp > k || myVector[row][col]) {return 0;}//能过就给该位置赋1myVector[row][col] = 1;if (judgeMoving(m, n, k, row - 1, col, myVector) || judgeMoving(m, n, k, row + 1, col, myVector) || judgeMoving(m, n, k, row, col - 1, myVector) || judgeMoving(m, n, k, row, col + 1, myVector)) {return 1;}return 0;}};
递归+回溯，用一个二维的数组存放机器人是否能到达，初始化为0，若能到达就将该位置的值改为1，最后加以判断，等递归结束，再便利这个二维数组，统计有多少个1就行了。因为初始位置都是（0，0），所以不需要架循环，直接就从该位置开始，逐步便利其上下左右，当周围能走完的地方都走了之后，它就会返回，此时统计就行。
剑指 Offer 14- I. 剪绳子
【普通版剑指 Offer 浅刷浅刷】class Solution {public:int cuttingRope(int n) {return n <= 3 ? n - 1 : pow(3, n / 3) * 4 / (4 - n % 3);}};//或者class Solution {public:int cuttingRope(int n) {if (n <= 3) {return n - 1;}if (n % 3 == 1) {return 4 * pow(3, n / 3 - 1);} else if (n % 3 == 2) {return 2 * pow(3, n / 3);} else {return pow(3, n / 3);}}};
经大数据计算，3最多的时候值是最大的，最优3，次优2，最后才是1 。
剑指 Offer 14- II. 剪绳子 II
class Solution {public:int cuttingRope(int n) {if (n <= 3) {return n - 1;}long int res = 1;while (n > 4) {res *= 3;res = res % 1000000007;n -= 3;}return (res * n) % 1000000007;}};
这道题是剪绳子的升级版，它的n可以到1000，所以我们得考虑存不存的下的问题，就不能直接使用pow函数了，所以这里我们使用循环相乘，通过n的大小判断，最终再返回乘积与n再相乘的结果，注意要时刻取余，不然容易超界。
剑指 Offer 15. 二进制中1的个数

普通版 剑指 Offer 浅刷浅刷( 三 )

普通版剑指 Offer 浅刷浅刷( 三 )