Day16 矩阵中的路径 + 求1+2+…+n + 把字符串转换

TODO:

1. 重做矩阵中的路径
2. 回顾一下，求1+2+…+n + 把字符串转换成整数 。 ♥(快速幂的方法这次没有看)♥

一、剑指 Offer 12. 矩阵中的路径(中等)

一道经典的dfs+剪枝的矩问题
写了好久好久，写的特别直白且丑陋，没有任何思维的闪光点。只是单纯的上下左右遍历...
题解直接将矩阵中已经搜寻过后的数据变为"*"，而没空vis数组节省了空间开销。

class Solution {
public:
    int n,m,pos;
    bool yes = false;

    bool exist(vector<vector<char>>& board, string word) {
        if(board.size() == 0 || board[0].size() == 0) return false;
        n = board.size(); 
        m = board[0].size();
        pos=0; 
        for(int i =0; i < n; i++){
            for(int j = 0; j < m; j++){   
                if(board[i][j] == word[0]){
                    vector<vector<bool>> vis(n+1,vector<bool>(m+1,false));
                    pos = 0;
                    dfs(board,word,vis,i,j);   
                }
                if(yes) return yes;
            }
        }
        return yes;
    }
    void dfs(vector<vector<char>>& board, string& word,vector<vector<bool>>&vis,int i,int j){ 
        if(yes||i> n || j>m || i<0 || j<0) return ;
        vis[i][j] = true;
        pos++;
        if(pos == word.size()) {yes = true; return ;}
        
        if(i+1 <n && board[i+1][j] == word[pos]&&!vis[i+1][j]){
            dfs(board,word,vis,i+1,j);
            vis[i+1][j] = false;
            
        }
        if(j+1<m && board[i][j+1] == word[pos]&&!vis[i][j+1]){
          
            dfs(board,word,vis,i,j+1);
            vis[i][j+1] = false;
        }
        if(i-1>=0 && board[i-1][j] == word[pos]&&!vis[i-1][j]){
            dfs(board,word,vis,i-1,j);
            vis[i-1][j] = false;
        }
        if(j-1>=0 && board[i][j-1] == word[pos]&&!vis[i][j-1]){
            dfs(board,word,vis,i,j-1);
            vis[i][j-1] = false;
        }
        pos--;
        return;
    }
};

题解
题解的答案虽然看着清爽但是时间开销似乎比我的还大。

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;
    }
};

image.png
这份题解似乎不错

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, 0, i ,j)) return true;
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& board, string word, int u, int x, int y)
    {
        if(board[x][y] != word[u]) return false;//查找失败
        if(u == word.size() - 1) return true;//查找成功
        int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};//四个方向
        char c = board[x][y];//存储当前点
        board[x][y] = '*';//当前点已经使用过
        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];//四个方向
            if(a >= 0 && a < board.size() && b >= 0 && b < board[0].size())//注意边界值
            {
                if(dfs(board, word, u + 1, a, b)) return true;
            }
        }
        board[x][y] = c;//恢复现场
        return false;
    }
};

二、剑指 Offer 64. 求1+2+…+n(中等)

没做出来但是题解都好有意思

方法一 利用构造函数：

class AddSum{
    public:
     AddSum(){N++;Sum+=N;}
    static int N;
    static int Sum;
    static int getSum(){return Sum;}
    static void Reset(){N=0;Sum=0;}
    
};
int AddSum::N =0;
int AddSum::Sum =0;
class Solution {
public:
    int sumNums(int n) {
        AddSum::Reset();
       AddSum *a = new AddSum[n];
       return AddSum::N;
    //    return 0;
    }
};

方法二 利用短路与的性质

class Solution {
public:
    int res = 0;
    int sumNums(int n) {
       n&&sumNums(n-1);
       res += n;
       return res;
    }
};

方法三 计算内存

class Solution {
public:
    int sumNums(int n) {
        bool a[n][n+1];
        return sizeof(a)>>1;
    }
};

快速乘还没有看

三、剑指 Offer 67. 把字符串转换成整数(中等)

看到这个题就害怕，感觉和Day7做的剑指 Offer 46. 把数字翻译成字符串（中等）有类似之处。

事实上比Day7的题简单太多，做出来啦。瞥了眼题解大差不差，就这样吧。

class Solution {
public:
    int strToInt(string str) {
        if(str.empty()) return 0;
        int flag = 1;
        int idx = 0;
        while(str[idx] == ' ') idx++;
        if(str[idx] == '-'||str[idx] == '+'){
            if(str[idx]=='-'){
                flag = -1;
            }
            idx++; }
        int limit = INT_MAX;
        int res = 0;
        while(str[idx] >= '0' && str[idx] <='9'){
            if(flag == 1){
                if((res > limit/10) || (res == limit/10 && str[idx]>='7')) return INT_MAX;
            } 
            else{
                if(res > limit/10 || (res == limit/10 && str[idx]>='8')){ 
                    return INT_MIN;
                }
            }
            res = res *10 +(str[idx]-'0');
            idx++;
        }
        return flag * res;

    }
};