leetcode解题思路分析（六）37-42题-蒲公英云

解数独
编写一个程序，通过已填充的空格来解决数独问题。

本题主要是采取回溯法解决，选择最少空位的行、列、块，然后进行填入，如果出现问题则回溯

class Solution { 
public:
    // line, column, block 分别存储每行、每列、每宫中可用的数字
    vector<set<int>> line, column, block;
    //哈希更新每行/列/宫中可以使用的数字
    void update( vector<vector<char>>& board){ 
        set<int> compare = { 1,2,3,4,5,6,7,8,9};
        //a 行；b 列；c 宫
        for( int i = 0; i < 9; i++)
            line.push_back( compare), column.push_back( compare), block.push_back( compare); 
        for( int i = 0; i < 9; i++)
            for( int j = 0; j < 9; j++)
                if( board[i][j] != '.'){ 
                    int t = board[i][j] - '0';
                    line[i].erase( t),  column[j].erase(t), block[i / 3 + j / 3 * 3].erase(t); 
                }
        return ;
    }
    //检查该位置处字符是否可以放到该处
    bool check( vector<vector<char>>& board, const int& i, const int& j, int num){ 
        if( line[i].find( num) != line[i].end()
         && column[j].find( num) != column[j].end()
         && block[i/3 + j/3*3].find( num) != block[i/3 + j/3*3].end())
            return true;
        return false;
    }
    //标记
    int flag = 0;
    //dfs + 回溯
    void dfs( vector<vector<char>>& board, int count){ 
        if( count == 81){ 
            flag = 1;
            return ;
        }
        int i = count / 9, j = count % 9;
        if( board[i][j] == '.'){ 
            //检查 1 ～ 9 中数字哪一个可以放入该位置
            for( int k = 1; k < 10; k++)
                if( check( board, i, j, k)){ 
                    line[i].erase( k), column[j].erase( k), block[ i /3 + j/3*3].erase( k);
                    board[i][j] = k + '0';
                    dfs( board, count + 1);
                    if( !flag){ 
                        line[i].insert( k), column[j].insert( k), block[ i /3 + j/3*3].insert( k);
                        board[i][j] = '.';
                    }
                    else
                        return ;
                }
        }
        else
            dfs( board, count + 1);
        return ;
    }
    void solveSudoku(vector<vector<char>>& board) { 
        update( board);
        //show( line, column, block);
        dfs(board, 0);
    }
};

外观数列
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

本题采用递归可解：每次的答案均是上次的cnt + val

class Solution { 
public:
    string countAndSay(int n) { 
        if (n == 1)
            return "1";
        string s = countAndSay(n - 1);
        string ret;
        int size = s.size();
        for (int i = 0; i < size;)
        { 
            int cnt = 1;
            char val = s[i];
            i++;
            while (i < size && s[i] == val)
            { 
                i++;
                cnt++;
            }
            char count = cnt + '0';
            ret = ret + count + val;                           
        }
        return ret;
    }
};

组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。

本题可采用动态规划的方法解决：对target可以分解为数组中的某些元素，从第一个元素开始遍历，即dp[target] = dp[candidates[0]] + dp[target - candidates[0]]，由此可解

class Solution { 
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) { 
        unordered_map<int, set<vector<int>>>dict;
        for (int i = 1; i <= target; i++)
        { 
            for (int it : candidates) 
            {         
                if (i == it) dict[i].insert(vector<int>{ it});
                else if (i > it)
                { 
                    for (auto ivec : dict[i - it]) 
                    { 
                        ivec.push_back(it);
                        sort(ivec.begin(), ivec.end());
                        if(dict[i].count(ivec)==0)
                            dict[i].insert(ivec);
                    }
                }
            }
        }
        vector<vector<int>>ans;
        for (auto it : dict[target]) ans.push_back(it);
        return ans;
    }
};

增加剪枝操作之后的代码如下

class Solution { 
private:
    vector<int> candidates;
    vector<vector<int>> res;
    vector<int> path;
public:
    void DFS(int start, int target) { 
        if (target == 0) { 
            res.push_back(path);
            return;
        }
        for (int i = start;
             i < candidates.size() && target - candidates[i] >= 0; i++) { 
            path.push_back(candidates[i]);
            DFS(i, target - candidates[i]);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int> &candidates, int target) { 
        std::sort(candidates.begin(), candidates.end());
        this->candidates = candidates;
        DFS(0, target);
        return res;
    }
};

组合总和2
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。

此题本质上和上题是一样的东西，只不过是稍微修改一点条件而已。一样的回溯+剪纸可解

class Solution { 
public:
    vector<int> input;
    int target;
    vector<vector<int>> result;
    vector<int> vc;
    void dfs(int index, int sum) { 
        // index >= input.size() ，写成 index == input.size() 即可
        // 因为每次都 + 1，在 index == input.size() 剪枝就可以了
        if (sum >= target || index == input.size()) { 
            if (sum == target) { 
                result.push_back(vc);
            }
            return;
        }
        for (int i = index; i < input.size(); i++) { 
            if (input[i] > target) { 
                continue;
            }
            // 【我添加的代码在这里】：
            // 1、i > index 表明剪枝的分支一定不是当前层的第 1 个分支
            // 2、input[i - 1] == input[i] 表明当前选出来的数等于当前层前一个分支选出来的数
            // 因为前一个分支的候选集合一定大于后一个分支的候选集合
            // 故后面出现的分支中一定包含了前面分支出现的结果，因此剪枝
            // “剪枝”的前提是排序，升序或者降序均可
            if (i > index && input[i - 1] == input[i]) { 
                continue;
            }
            vc.push_back(input[i]);
            sum += input[i];
            dfs(i + 1, sum);
            vc.pop_back();
            sum -= input[i];
        }
    }
    vector<vector<int>> combinationSum2(vector<int> &candidates, int target) { 
        // “剪枝”的前提是排序，升序或者降序均可
        sort(candidates.begin(), candidates.end());
        this->input = candidates;
        this->target = target;
        dfs(0, 0);
        return result;
    }
};

缺失的第一个正数
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

本题有一个隐藏的结论：数组长度为N，则最小正整数一定小于等于N+1，介于此，我们可以用数组当哈希表用来存储状态，然后据此遍历一遍即可

class Solution { 
public:
    int firstMissingPositive(vector<int>& nums) { 
        int ret = 1;        
        int size = nums.size();
        int mapNums[size + 2] = { 0};
        for (int i = 0; i < nums.size(); i++)
        { 
            int tmp = nums[i];
            if (tmp < size + 2 && tmp > 0)
                mapNums[tmp] = 1;
        }
        while (1)
        { 
            if (mapNums[ret] == 1)
                ret++;
            else
                return ret;
        }
    }
};

接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

遇到这种一般最优解都是双指针首尾滑动，主要难点在于设计怎么计算。这题的核心思想在于：左边比右边高则从右边开始算格子，右边比左边高则从左边开始算格子

class Solution { 
public:
    int trap(vector<int>& height) { 
        int begin = 0, end = height.size() - 1, ret = 0;
        int leftMax = 0, rightMax = 0;
        while (begin < end)
        { 
            if (height[begin] < height[end])
            { 
                if (height[begin] < leftMax)
                    ret += leftMax - height[begin];
                else
                    leftMax = height[begin];
                begin++;
            }
            else
            { 
                if (height[end] < rightMax)
                    ret += rightMax - height[end];
                else
                    rightMax = height[end];
                end--;
            }
        }
        return ret;
    }
};