剑指offer 46与47


剑指offer 46与47

1.面试题46. 把数字翻译成字符串

method1:递归法

class Solution {
public:
    int translateNum(int num) {
        // to_string
        string nums = to_string(num);
        int right = nums.size();
        // recursion;
        return recursion(nums,0,right);
    }

    int recursion(string nums,int left,int right) {
        if(left==right) {
            return 1;
        }
        // 若只有一个数字或者这个数字为0(不能跟后面合并),或者合并不满足0~25,就一步走
        if (left == right-1 || nums[left] == '0' || nums.substr(left, 2) > "25")

            return recursion(nums,left+1,right);

        int sum = 0;

        // 总和 = 一步走+二步走
        sum += recursion(nums,left+1,right) + recursion(nums,left+2,right);

        return sum;
    }
};

method2:动态规化

类似跳台阶,分为下面几类:

  • 当前元素可合并前面元素,且前面元素不为0(为0就没法合并了)。
    • 那么可合并就是两种可能:
      • 第一:由前面的前面决定,dp[i] = dp[i-2]
      • 第二:由前面决定,dp[i] = dp[i-1]
  • 当前元素单独翻译,直接由前面决定
    • dp[i] = dp[i-1]
class Solution {
public:
    int translateNum(int num) {
        // to_string
        string nums = to_string(num);
        int n = nums.size();
        vector<int> dp(n+1,1);

        for(int i=2;i<=n;i++) {
            // 翻译当前
            if(nums[i-2]!='0' && nums.substr(i-2,2) <= "25") {
                dp[i] = dp[i-1]+dp[i-2];
            }
            // 不翻译当前
            else {
                dp[i] = dp[i-1];
            }
        }
        return dp[n];
    }
};

2.面试题47. 礼物的最大价值

method1:动态规化法

class Solution {
private:
    vector<vector<int>> dp;
    int m,n;
public:
    int maxValue(vector<vector<int>>& grid) {
        m = grid.size();
        assert(m>0);
        n = grid[0].size();
        dp = vector<vector<int>>(m,vector<int>(n,0));
        dp[0][0] = grid[0][0];
        // 处理第一行
        for(int i=1;i<n;i++) {
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        // 处理第一列
        for(int i=1;i<m;i++) {
            dp[i][0] =  dp[i-1][0] + grid[i][0];
        }
        // 处理矩形
        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

更多内容,订阅公众号

文章作者: light-city
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 light-city !
评论
  目录