day1
3.数组中重复的数字
思路1:先将数组排序，再从中找出重复的数字
排序o(nlogn)
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size()-1;i++){
if(nums[i]==nums[i+1]){
return nums[I];
}
}
return 0;
}
};
思路2:哈希表:从头到位按顺序扫描数组，每扫描一个就判断哈希表里是否已包含此数 [用o(1)的时间]，若无，则加入哈希表。否则，找出重复数字。
时间复杂度o(n) 但是空间复杂度o(n)
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
unordered_map<int,int> hashmap;
for(int i=0;i<nums.size();i++){
hashmap[nums[i]]++;
if(hashmap[nums[i]]>1){
return nums[I];
}
}
return 0;
}
};
思路3:
有没有空间复杂度为o(1)的方法？
书本p39-p40页
一句话概括：因为出现的元素值 < nums.size(); 所以我们可以让 位置i 的地方放元素i。如果位置i的元素不是i的话，那么我们就把i元素的位置放到它应该在的位置，即 nums[i] 和nums[nums[i]]的元素交换，这样就把原来在nums[i]的元素正确归位了。如果发现 要把 nums[i]正确归位的时候，发现nums[i]（这个nums[i]是下标）那个位置上的元素和要归位的元素已经一样了，说明就重复了，重复了就return
for(int i=0;i<nums.size();i++){
while(nums[i]!=i){
if(nums[nums[i]] == nums[i]) return nums[I];
int tmp = nums[I];
nums[i] = nums[tmp];
nums[tmp] = tmp;
}
}
return -1;
4.二维数组中的查找
思路1：暴力搜索，但在搜索前判断是否需要搜索该行的每一列
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if(matrix.empty()|| matrix[0].empty()) return false;
int row=matrix.size(),col=matrix[0].size();
for(int i=0;i<row;i++){
if(target>=matrix[i][0]&&target<=matrix[i][col-1]){
for(int j=0;j<col;j++){
if(target==matrix[i][j]){
return true;
}
}
}
}
return false;
}
};
特殊的输入：
[]
0
--
[[]]
1
思路2：
书本p45-47
总结：
步骤.png
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if(matrix.empty()|| matrix[0].empty()) return false;
int rows=matrix.size(),cols=matrix[0].size();
int row=0,col=cols-1;//右上角
while(row<rows&&col>=0){
if(target==matrix[row][col]){
return true;
}
else if(target<matrix[row][col]){
col--;
}
else{
row++;
}
}
return false;//越界了仍未找到返回false
}
};
5.替换空格
思路1:
暴力解法，遍历
使用string的erase和insert方法[o(n)]。
时间复杂度o(n^2)
class Solution {
public:
string replaceSpace(string s) {
for(int i=0;i<s.size();){
if(s[i]==' '){
s.erase(i,1);
s.insert(i,"%20");
i+=3;
}
else{
I++;
}
}
return s;
}
};
若不使用erase和insert方法，但额外使用空间:
class Solution {
public:
string replaceSpace(string s) {
string ans;
for(int i=0;i<s.size();i++){
if(s[i]==' '){
ans+="%20";
}
else{
ans+=s[i];
}
}
return ans;
}
};
思路2:
如何降低时间复杂度？（如何减少移动次数？）且不额外使用空间？
书本p51-53
将原长度修改为新字符串长度 = 原长+ 2 * 空格个数
ps:其实有resize()函数
其他人的代码:为什么运行时间更快？因为使用了for auto
class Solution {
public:
string replaceSpace(string s) {
if(s.length()==0) return s;
int originallen = s.size() - 1;
int numblank = 0;
for(auto c:s){
if(c == ' ') ++numblank;
}
int newlen = originallen + numblank * 2;
s += string(numblank * 2,' ');
while(originallen>=0 && newlen > originallen){
if(s[originallen] == ' '){
s[newlen--] = '0';
s[newlen--] = '2';
s[newlen--] = '%';
}
else{
s[newlen--] = s[originallen];
}
originallen--;
}
return s;
}
};
6.从头到尾打印链表
思路1:边遍历链表边存储值，最后再反向。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
vector<int> ans;
while(head){
ans.push_back(head->val);
head=head->next;
}
reverse(ans.begin(),ans.end());
return ans;
}
};
如果是反向打印，可以采用栈的数据结构，stack。
既然使用了栈，也意味着可以使用递归。
(课本)
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
if(!head)
return {};
vector<int> a=reversePrint(head->next);
a.push_back(head->val);
return a;
}
};
思路2:
扫描两遍链表
第一遍：获得链表的结点总数，建立定长的数组
第二遍：将结点从尾部存入数组
7.重建二叉树
(或许没有从大局上理解递归的意义。我个人的思维是不断利用前or后序遍历以及中序 确定根节点以及左右子树，那么这个思维就是一个可以使用递归的过程。加强掌握如何把自己的思维用代码写出来。)
知识点：
- 前序遍历列表：第一个元素永远是 【根节点 (root)】
- 中序遍历列表：根节点 (root)【左边】的所有元素都在根节点的【左分支】，【右边】的所有元素都在根节点的【右分支】
算法思路： - 通过【前序遍历列表】确定【根节点 (root)】
将【中序遍历列表】的节点分割成【左分支节点】和【右分支节点】 - 递归寻找【左分支节点】中的【根节点 (left child)】和 【右分支节点】中的【根节点 (right child)】
难道c++没有类似java的函数吗？
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
if (n == 0)
return null;
int rootVal = preorder[0], rootIndex = 0;
for (int i = 0; i < n; i++) {
if (inorder[i] == rootVal) {
rootIndex = I;
break;
}
}
TreeNode root = new TreeNode(rootVal);
root.left = buildTree(Arrays.copyOfRange(preorder, 1, 1 + rootIndex), Arrays.copyOfRange(inorder, 0, rootIndex));
root.right = buildTree(Arrays.copyOfRange(preorder, 1 + rootIndex, n), Arrays.copyOfRange(inorder, rootIndex + 1, n));
return root;
}
}
或许可以这样？没试过
TreeNode* buildTree(vector<int> preorder, vector<int> inorder) {
if(inorder.empty()||preorder.empty()) return NULL;
int i=-1;
while(preorder[0]!=inorder[++I]);
TreeNode* root = new TreeNode(preorder[0]);
root->left = buildTree( vector<int>(preorder.begin()+1,preorder.begin()+i+1),
vector<int>(inorder.begin(),inorder.begin()+i) );
root->right= buildTree( vector<int>(preorder.begin()+i+1,preorder.end()),
vector<int>(inorder.begin()+i+1,inorder.end()) );
return root;
}
其他答案思路
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return build(preorder, inorder, 0, 0, inorder.size() - 1);
}
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int root, int start, int end){// 中序的start和end
if(start > end) return NULL;
TreeNode *tree = new TreeNode(preorder[root]);
int i = start;
while(i < end && preorder[root] != inorder[i]) I++;
tree->left = build(preorder, inorder, root + 1, start, i - 1);
tree->right = build(preorder, inorder, root + 1 + i - start, i + 1, end);
return tree;
}
};
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
this->preorder = preorder;
for(int i = 0; i < inorder.size(); I++)
dic[inorder[i]] = i;
return recur(0, 0, inorder.size() - 1);
}
private:
vector<int> preorder;
unordered_map<int, int> dic;
TreeNode* recur(int root, int left, int right) {
if(left > right) return nullptr; // 递归终止
TreeNode* node = new TreeNode(preorder[root]); // 建立根节点
int i = dic[preorder[root]]; // 划分根节点、左子树、右子树
node->left = recur(root + 1, left, i - 1); // 开启左子树递归
node->right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
return node; // 回溯返回根节点
}
};
但是没细想为什么只记录root(preorder start)和inorder的start&end就可以了
答案或许在上述链接
没时间看这么多了
下次按照算法笔记的方法以及迭代(运用栈)的方法写一下。
可参考下面的链接：
9.用两个栈实现队列
题意：
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
这一行表示每一行代码的操作
[[],[3],[],[]]
这个表示每一行代码操作所需要的参数
举例：
CQueue 表示新建一个CQueue对象，对应的所需参数为[]，即此操作不需要参数。
appendTail 表示执行一个appendTail()操作，对应要被操作的元素为3。
deleteHead 表示执行一个deleteHead操作，对应的所需参数为[]，即此操作不需要参数。
deleteHead 表示执行一个deleteHead操作，对应的所需参数为[]，即此操作不需要参数。
思路：直接写就完事了.构造函数处记得清空栈
class CQueue {
public:
stack<int> s1,s2;
CQueue() {
while(!s1.empty()){
s1.pop();
}
while(!s2.empty()){
s2.pop();
}
}
void appendTail(int value) {
s1.push(value);
}
int deleteHead() {
if(!s2.empty()){
int val=s2.top();
s2.pop();
return val;
}
else if(!s1.empty()){
while(!s1.empty()){
int val=s1.top();
s1.pop();
s2.push(val);
}
int val=s2.top();
s2.pop();
return val;
}
else{
return -1;
}
}
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/
别人的代码更清晰，具体在于deletehead部分
class CQueue {
stack<int> stack1,stack2;
public:
CQueue() {
while (!stack1.empty()) {
stack1.pop();
}
while (!stack2.empty()) {
stack2.pop();
}
}
void appendTail(int value) {
stack1.push(value);
}
int deleteHead() {
// 如果第二个栈为空
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
}
if (stack2.empty()) {
return -1;
} else {
int deleteItem = stack2.top();
stack2.pop();
return deleteItem;
}
}
};
复杂度分析:
时间复杂度：对于插入和删除操作，时间复杂度均为 O(1)。插入不多说，对于删除操作，虽然看起来是 O(n) 的时间复杂度，但是仔细考虑下每个元素只会「至多被插入和弹出 stack2 一次」，因此均摊下来每个元素被删除的时间复杂度仍为O(1)。
空间复杂度：O(n)。需要使用两个栈存储已有的元素。
思考：如何用两个队列实现一个栈？
课本p71
10.斐波那契数列
注意题目要求：答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
思路1:TLE
class Solution {
public:
int fib(int n) {
if(n==0||n==1){
return n;
}
else{
return fib(n-1)+fib(n-2);
}
}
};
思路2:
思路1在于过多的重复计算，可以尝试把计算结果保存，避免重复计算，但是缺点在于要额外的空间。
class Solution {
public:
unordered_map<int,int> hashmap;
int fib(int n) {
if(n>1){
if(hashmap[n-1]==0){
hashmap[n-1]=fib(n-1);
}
if(hashmap[n-2]==0){
hashmap[n-2]=fib(n-2);
}
return (hashmap[n-1]+hashmap[n-2])%1000000007;
}
else{
hashmap[0]=0;
hashmap[1]=1;
return n;
}
}
};
思路3:从下往上计算，根据f(0) f(1)计算出f(2)，再根据f(1) f(2)计算出 f(3)...以此类推可以算出第n项，时间复杂度为o(n)
注意
计算过程中会溢出，不能用int,甚至long long型的数组都不足够存储：res[i]=res[i-1]+res[i-2]
数组的长度是101(0<=n<=100)，写100不对，有测试例会越界。
class Solution {
public:
int fib(int n) {
int res[101]={0,1};
if(n>1){
for(int i=2;i<=n;i++){
res[i]=(res[i-1]+res[i-2])%1000000007;
}
}
return res[n];
}
};
优化思路3，不额外建立数组保存结果。
class Solution {
public:
int fib(int n) {
if(n>1){
int f0=0,f1=1,f;
for(int i=2;i<=n;i++){
f=(f0+f1)%1000000007;
f0=f1;
f1=f;
}
return f;
}
else{
return n;
}
}
};
思路4:
课本p76
10.青蛙跳台阶
思路：
此类求 多少种可能性 的题目一般都有 递推性质 ，即f(n) 和
f(n−1)…f(1) 之间是有联系的。
f(0)=1;(题目要求)
f(1)=1;跳一级台阶只有一种跳法
f(2)=2;跳上两级台阶有两种跳法：分两次跳，一次跳一级；一次跳两级。
又f(n)=f(n-1)+f(n-2)
class Solution {
public:
int numWays(int n) {
if(n>2){
int f0=1,f1=2,f;
for(int i=3;i<=n;i++){
f=(f0+f1)%1000000007;
f0=f1;
f1=f;
}
return f;
}
else if(n==2){
return 2;
}
else{
return 1;
}
}
};
代码小改进：
class Solution {
public:
int numWays(int n) {
if(n>1){
int f0=1,f1=1,f;
for(int i=2;i<=n;i++){
f=(f0+f1)%1000000007;
f0=f1;
f1=f;
}
return f;
}
else{
return 1;
}
}
};
循环求余.png
同样有：(a∗b)%c=((a%c)∗(b%c))%c
11.旋转数组的最小数字
思路1：按照题意：输入一个递增排序的数组的一个旋转。所以该旋转数组是两个有序数列的拼接，直接遍历一遍，找到拼接处即可。
更粗暴的解法：从头到尾遍历，* 直接找最小值 *，不管旋转不旋转。
class Solution {
public:
int minArray(vector<int>& numbers) {
for(int i=0;i<numbers.size()-1;i++){
if(numbers[i]>numbers[i+1]){
return numbers[i+1];
}
}
return numbers[0];
}
};
时间复杂度O(n)
思路2:二分查找
课本p83-87
public int minArray(int[] numbers) {
int l = 0, r = numbers.length - 1;
while (l < r) {
int mid = ((r - l) >> 1) + l;
//只要右边比中间大，那右边一定是有序数组
if (numbers[r] > numbers[mid]) {
r = mid;
} else if (numbers[r] < numbers[mid]) {
l = mid + 1;
//去重
} else r--;
}
return numbers[l];
}
next：评论区、题解区、主站的区域。
12.矩阵中的路径 (重点)
注意题目要求：如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。
(所以，为了防止重复遍历相同的位置，需要额外维护一个与 board 等大的 visited 数组，用于标识每个位置是否被访问过。每次遍历相邻位置时，需要跳过已经被访问的位置。)
思路1:
运用回溯法，应尽量减少不必要的枚举。
回溯法使用递归实现。当我们到达某一个节点时，* 尝试所有可能的选项 ， 并在满足条件的前提下 *，递归地抵达下一个节点。
解题思路1.1.png
解题思路1.2
额外维护visited数组版本,注意人家是如何传参数的,当时纠结了很久。
88 ms 16.5 MB
函数中的形参 vector<vector<int>>& visited；
传参:visited
二维vector数组指定长度写法:vector<vector<int>> visited(h, vector<int>(w));
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int h = board.size(), w = board[0].size();
vector<vector<int>> visited(h, vector<int>(w));
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
bool flag = check(board, visited, i, j, word, 0);
if (flag) {
return true;
}
}
}
return false;
}
bool check(vector<vector<char>>& board, vector<vector<int>>& visited, int i, int j, string& s, int k) {
if (board[i][j] != s[k]) {
return false;
} else if (k == s.length() - 1) {
return true;
}
visited[i][j] = true;
vector<pair<int, int>> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool result = false;
for (const auto& dir: directions) {
int newi = i + dir.first, newj = j + dir.second;
if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size()) {
if (!visited[newi][newj]) {
bool flag = check(board, visited, newi, newj, s, k + 1);
if (flag) {
result = true;
break;
}
}
}
}
visited[i][j] = false;
return result;
}
};
优化：无vistied数组版本
332 ms 173.3 MB
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
rows = board.size();
cols = board[0].size();
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if(dfs(board, word, i, j, 0)) return true;
}
}
return false;
}
private:
int rows, cols;
bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {
if(i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false;
if(k == word.size() - 1) return true;
board[i][j] = '\0';
bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
board[i][j] = word[k];
return res;
}
};
代码优化，将四个dfs用循环写出。
24 ms 7.6 MB
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for (int i = 0; i < board.size(); i++) {
for (int j = 0; j < board[0].size(); j++) {
if (dfs(board, word, i, j, 0))
return true;
}
}
return false;
}
private:
bool dfs(vector<vector<char>>& b, string& w, int i, int j, int k) {
if (i >= b.size() || i < 0 || j >= b[0].size() || j < 0 || b[i][j] != w[k])
return false;
if (k == w.length() - 1)
return true;
char temp = b[i][j];
b[i][j] = '/';
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
for (int q = 0; q < 4; q ++ ) {
int m = i + dx[q], n = j + dy[q];
if (dfs(b, w, m, n, k + 1)) return true;
}
b[i][j] = temp;
return false;
}
};
复杂度分析
自己改了好几遍才过的复杂代码
140 ms 54.9 MB
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size()));
for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
if(board[i][j]==word[0]){ //其实可以移到下面，第一个字符也在searchpath判断！就不用先标记啊啥啥啥的
visited[i][j]=true;//不要忘记第一个也要标记visited
if(SearchPath(board,word,1,i,j,visited)){
return true;
}
visited[i][j]=false;
}
}
}
return false;
}
bool SearchPath(vector<vector<char>>& board,string word,int level,int x,int y,vector<vector<bool>>& visited){
if(level==word.size()){
return true;
}
for(int i=0;i<4;i++){
if(i==0 && y>0 && (word[level]==board[x][y-1])&& !visited[x][y-1]){
visited[x][y-1]=true;
//如果没有越界且成功匹配
if(SearchPath(board,word,level+1,x,y-1,visited)){
return true;
}
else{
visited[x][y-1]=false;
}
}
else if(i==1 && y<board[0].size()-1 && (word[level]==board[x][y+1])&&!visited[x][y+1]){
visited[x][y+1]=true;
if(SearchPath(board,word,level+1,x,y+1,visited)){
return true;
}
else{
visited[x][y+1]=false;
}
}
else if(i==2 && x>0 && (word[level]==board[x-1][y])&&!visited[x-1][y]){
visited[x-1][y]=true;
if(SearchPath(board,word,level+1,x-1,y,visited)){
return true;
}
else{
visited[x-1][y]=false;
}
}
else if(i==3 && x<board.size()-1 && (word[level]==board[x+1][y])&&!visited[x+1][y]){
visited[x+1][y]=true;
if(SearchPath(board,word,level+1,x+1,y,visited)){
return true;
}
else{
visited[x+1][y]=false;
}
}
}
return false;
}
};
尝试修改自己的代码，变简洁了，但是时间和空间还是很大，尤其是时间，因为我不管是否越界，我都调用searchpath，进去了才判断，而不是像第一个解法，先if判断是否越界才调用。
392 ms 175.2 MB
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size()));
for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
if(SearchPath(board,word,0,i,j,visited)){
return true;
}
}
}
return false;
}
bool SearchPath(vector<vector<char>>& board,string word,int level,int x,int y,vector<vector<bool>>& visited){
if(level==word.size()){ //别人都不用进入到这步！
return true;
}
if(x>=0 && x<board.size() && y>=0 && y<board[0].size() && word[level]==board[x][y] && !visited[x][y]){
visited[x][y]=true;
if(SearchPath(board,word,level+1,x,y-1,visited)||(SearchPath(board,word,level+1,x,y+1,visited))||(SearchPath(board,word,level+1,x-1,y,visited))||(SearchPath(board,word,level+1,x+1,y,visited))){
return true;
}
visited[x][y]=false;
}
return false;
}
};
再次修改，删掉了visited但是时间和空间居然没下降。不纠结了
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for(int i=0;i<board.size();i++){
for(int j=0;j<board[0].size();j++){
if(SearchPath(board,word,0,i,j)){
return true;
}
}
}
return false;
}
bool SearchPath(vector<vector<char>>& board,string word,int level,int x,int y){
if(level==word.size()){ //别人都不用进入到这步！
return true;
}
if(x>=0 && x<board.size() && y>=0 && y<board[0].size() && word[level]==board[x][y]){
char temp = board[x][y];
board[x][y] = '/';
if(SearchPath(board,word,level+1,x,y-1)||(SearchPath(board,word,level+1,x,y+1))||(SearchPath(board,word,level+1,x-1,y))||(SearchPath(board,word,level+1,x+1,y))){
return true;
}
board[x][y]=temp;
}
return false;
}
};
我靠！string改成引用传参就变成16 ms 7.5 MB！！
看来问题的关键在这里！！！不是之前以为的多次调用了searchpath
ps:
C++在做递归回溯算法相关题目时，递归函数形参传值和传引用运行速度有很大的差异。这是我这道题dfs函数的声明，主要区别是visited和word，一个是传值，一个是传引用。前者执行超时，后者在本题是32ms.
个人理解为传值时每次递归调用都要在内存中新建立一个vector 来保存visit传入的值，但是传引用直接在visited原始位置操作，不需要进行新建变量与赋值，节省了代码运行的空间与时间开销。
void dfs(vector<vector<char>>& board,vector<vector<int>>visited,int x,int y,int n,string word,bool& flag)
void dfs(vector<vector<char>>& board,vector<vector<int>>& visited,int x,int y,int n,string& word,bool& flag)
13.机器人的运动范围
思路1：回溯法
与上一题类似
class Solution {
public:
int movingCount(int m, int n, int k) {
int count=0;
vector<vector<bool>> vistied(m, vector<bool>(n));
searchPath(0,0,m,n,k,count,vistied);
return count;
}
void searchPath(int x,int y,const int &m,const int &n,const int &k,int &count,vector<vector<bool>>& vistied){
//if中的顺序很重要，不然会影响时间
if(x<0 || y<0 || x>m-1 || y>n-1 || vistied[x][y] || (x/100+(x%100)/10+(x%100)%10+y/100+(y%100)/10+(y%100)%10)>k){
return;
}
count++;
vistied[x][y]=true;
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
for (int q = 0; q < 4; q ++ ) {
int newX = x + dx[q], newY = y + dy[q];
searchPath(newX,newY,m,n,k,count,vistied);
}
return ;
}
};
可以看看人家是如何求余数的。
如何计算一个数的数位之和呢？我们只需要对数 x 每次对 10 取余，就能知道数 x 的个位数是多少，然后再将 x 除 10，这个操作等价于将 x 的十进制数向右移一位，删除个位数（类似于二进制中的 >> 右移运算符），不断重复直到 x 为 0 时结束。
class Solution {
public:
int vis[101][101]={0};
int movingCount(int m, int n, int k) {
return dfs(0,0,m,n,k);
}
int dfs(int x,int y,int m,int n,int k){
if(x<0||y<0||x>=m||y>=n||vis[x][y]||sum(x,y)>k) return 0;
vis[x][y]=1;
return dfs(x-1,y,m,n,k)+dfs(x,y-1,m,n,k)+dfs(x+1,y,m,n,k)+dfs(x,y+1,m,n,k)+1;
}
int sum(int x,int y){
int res=0;
while(x){
res+=x%10;
x/=10;
}
while(y){
res+=y%10;
y/=10;
}
return res;
}
};
