贪心

贪心算法顾名思义就是对当前问题的每一步采用最佳的方式来解决问题，只考虑当前步骤的一个子问题（动态规划是考虑每个步骤所有需要解决的子问题），判断能否使用贪心的方法就是找到一个反例，但是证明贪心一定正确有一定的难度。

剑指Offer14-1

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]k[1]...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

思路：对于剪绳子，我们需要思考两个问题，改切多少段，每一段该有多长。如果用数学思路来解决，很容易可以联想到算术几何均值不等式

$$ \frac{n1 + n2 + n3 + ... + na}{a} >= \sqrt[a]{n1*n2*n3*...*na} $$

这个公式相等的条件就是n1 = n2 = n3 = ...= na，当n = 4时，ans = 2x2 = 4 ，n= 5时，ans = 2x3 = 6, n =6时，ans = 3x3 =9

我们可以猜测每一段的最优长度应该是3，但是 n = 4时 ，3x1 < 2x2所以我们应该考虑到当n%3 = 1时，绳子最后一段应该被切为2x2

代码如下：

class Solution {
public:
    int cuttingRope(int n) {
        if ( n <= 3){
            return n - 1;
        }
        int b = n % 3;
        if (b == 1){
            return pow(3, n / 3 - 1) * 4;
        }
        if(b == 2){
            return pow(3, n / 3) * 2;
        }
        return pow(3, n / 3);
    }
};

剑指Offer14-2

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]k[1]...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

思路：此题的贪心思想和上题一样，唯一需要改变的就是求值的方式，这里不同于快速幂，我们只需要用循环来求余即可

class Solution {
public:
    int cuttingRope(int n) {
        if(n <= 3){
            return  n - 1;
        }
        int cont = n / 3 - 1;
        long ans = 1;
        for(int i = 0; i < cont; i++){
            ans = ans * 3 % 1000000007;
        }
        int b = n % 3;
        if(b == 1){
            return ans * 4 % 1000000007;    
        }
        if(b == 2){
            return  ans * 6 % 1000000007;
        }
        return ans * 3 % 1000000007;
    }
};

回溯

回溯法其实就是用一种试错的方法，分步骤解决问题的时候，尝试每一个步骤中的所有方法，当这个步骤得到的答案不对时，就会回退到上一个步骤，甚至上一个步骤也不对时，会回退到更加前面的步骤。这个方法就和我们经常使用到的深度优先遍历（DFS）密不可分。通常我们会利用DFS + 剪枝（不正确的步骤）来实现回溯

剑指Offer12

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

思路：按照一定顺序寻找有无指定字符串，是典型的回溯法的使用，我们只需要确定DFS的终止条件即可

索引越界，字符不匹配，当前元素已经被访问过则返回false

当字符串索引 = 字符串长度 - 1时则匹配完成返回true

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>>& board, string& word, int i, int j, int k){
        if(i >= board.size() || i < 0 || j >=board[0].size() || j < 0 || board[i][j] != word[k]){
            return false;
        }
        if(k == word.size() - 1){
            return true;
        }
        char temp = board[i][j];
        board[i][j] = '/';
        int x[4] = {-1, 0, 1, 0}, y[4] = {0, 1, 0, -1};
        for(int q = 0; q < 4; q++){
            int m = i + x[q], n = j + y[q];
            if(DFS(board, word, m, n, k + 1)){
                return true;
            }
        }
        board[i][j] = temp;
        return false;
    }
};

剑指Offer13

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

思路：这个问题同样是对回溯法的常规应用，只需要在符合条件的情况下结果+1，不断的从[0,0]开始尝试即可。

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> res(m, vector<bool>(n,0));
        return DFS(res, 0, 0, m, n, k);
    }
private:
    int numberSum(int x, int y){
        int s = 0;
        while(x != 0) {
            s += x % 10;
            x = x / 10;
        }
        while(y != 0){
            s += y % 10;
            y = y / 10;
        }
        return s;
    }

    int DFS(vector<vector<bool>>& res, int i, int j, int m, int n, int k){
        if(i >= m || j >= n || i < 0 || j < 0){
            return 0;
        }
        if(numberSum(i, j) <= k){
            if(res[i][j] == false){
                res[i][j] = true;
                return 1 + DFS(res, i + 1, j, m, n, k) + DFS(res, i, j + 1, m, n, k);
            }
        }
        return 0;
    }
};

剑指Offer38

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素

思路：对于字符的全排列，就可以用树的形式来表达，第一位字符，第二位字符，第三位字符，逐位的确定字符，从而得到全排列

class Solution {
public:
    vector<string> permutation(string s) {
        dfs(s, 0);
        return res;
    }
private:
    vector<string> res;
    void dfs(string s, int x){
        if(x == s.size() - 1){
            res.push_back(s);
            return;
        }
        set<int> st;
        for(int i = x; i < s.size(); i++){
            if(st.find(s[i]) != st.end()) continue; 
            st.insert(s[i]);
            swap(s[i], s[x]);                       
            dfs(s, x + 1);                          
            swap(s[i], s[x]);    
        }
    }
};