题目描述:

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

蓄水的问题，我的想法是一个凹槽能蓄水，意味着它的两边比最低处高。考虑两边的话，最高的水面高度与较矮的一边相同。所以从左到右遍历每一个高度，对每一个高度向右寻找比它高的第一个高度，得到的就是蓄水的宽度。但是也有左边高右边低的情况，所以我先找到最高的高度，该高度左边的高度的右边都必然存在一个比它高的高度（最高的）。最高高度右边的高度则从右向左遍历。

class Solution {
public:
    int trap(vector<int>& height) {
        int i = 0, j = 0;
        int len = height.size(), ret = 0;
        int maxPos = 0, maxHeight = INT_MIN;
        for(int i = 0; i < len; i++){
            if(height[i] > maxHeight){
                maxHeight = height[i];
                maxPos = i;
            }
        }
        while(i < maxPos){
            for(j = i + 1; j < maxPos && height[j] < height[i]; j++) ret += (height[i] - height[j]);
            i = j;
        }
        i = len - 1;
        while(i > maxPos){
            for(j = i - 1; j > maxPos && height[j] < height[i]; j--) ret += (height[i] - height[j]);
            i = j;
        }
        return ret;
    }
};

题目描述:

Given an unsorted integer array, find the first missing positive integer.

For example,

Given [1,2,0] return 3,

and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

给定一个未排序数组, 要求找到其中缺失的最小正整数. 由于题目要求使用常数的空间, 因此只能利用输入数组中的空间. 我的思路是将正整数1...n与下标0...n-1对应起来, 假设数组大小为n, 将数值在[1, n]范围内的元素放到下标[0,n-1]的对应位置上, 然后再从头遍历一次数组, nums[i] != i + 1的位置就是缺失的第一个正整数. 对与<=0和>n的数不需要处理, 因为<=0的数与结果无关, 而如果出现了>n的数, 那么必然在[1,n]中有缺失的数, 也只需要处理[1,n]即可. 时间复杂度O(n).

由于交换nums中的两个元素后, 将nums[i]中的数放到了nums[nums[i] - 1]中, 因此nums[i]中此时仍然储存一个没有放到相应位置的数, 所以下一个循环还要处理i而不是i+1, 所以i要减1, 但是这在[1,1]这种输入数据中会导致死循环, 因此还要加一个判断, 即要交换的目标位置是不是已经有了对应的数, 如果有则不再需要处理.

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] <= nums.size() && nums[i] > 0 && nums[nums[i] - 1] != nums[i]){
                swap(nums[nums[i] - 1], nums[i]);
                i--;
            }
        }
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] != i + 1) return i + 1;
        }
        return nums.size() + 1;
    }
};

题目描述:

Given a collection of candidate numbers © and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,

A solution set is:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

解法参照上一题: LeetCode 39. Combination Sum, 区别在于两点

• 输入数组中可能存在重复数字
• 每个元素只能选择一次

解决第二个问题的办法很简单, 就是在每次进入下一级递归时从下一个元素开始. 解决第一个问题的办法是当一个值已经出现在结果中的某个位置时跳过接下来与这个值相等的所有元素.

代码如下:

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> re;
        for (int i = 0; i < candidates.size(); i++) {
            if(i > 0 && candidates[i] == candidates[i - 1]) continue; //防止重复而跳过元素
            vector<int> path;
            getWithFirst(candidates, target, i, re, path);
        }

        return re;
    }
    
    void getWithFirst(vector<int>& c, int target, int first, vector<vector<int>> &ret, vector<int> &path) {
        if (c[first] == target) {
            path.push_back(c[first]);
            ret.push_back(path);
            path.pop_back();
            return;
        }
        int newTarget = target - c[first];
        path.push_back(c[first]);
        for (int i = first + 1; i < c.size() && c[i] <= newTarget; i++) { //从first+1开始循环
            if(i > first + 1 && c[i] == c[i - 1]) continue; //防止重复而跳过元素
            getWithFirst(c, newTarget, i, ret, path);
        }
        path.pop_back();
    }
};

题目描述:

Given a set of candidate numbers © and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is:

[
  [7],
  [2, 2, 3]
]

在一个整数集合中取出元素(同一个元素可以选出多次)使它们的和等于target. 思路是先对数组排序, 然后以每个元素作为第一个元素, 从它后面的元素(包括它自己)中再继续选取元素. 使用递归来实现这个思路.

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> re;
        for (int i = 0; i < candidates.size() && candidates[i] <= target; i++) {
            vector<int> path;
            getWithFirst(candidates, target, i, re, path);
        }
        return re;
    }

    //函数参数和返回值都应该尽量不要直接使用对象, 虽然这样会损失函数封装性.
    void getWithFirst(vector<int>& c, int target, int first, vector<vector<int>> &ret, vector<int> &path) {
        if (c[first] == target) {
            //找到一组符合要求的元素
            path.push_back(c[first]);
            ret.push_back(path);
            path.pop_back();
            return;
        }
        int newTarget = target - c[first];
        path.push_back(c[first]);
        for (int i = first; i < c.size() && c[i] <= newTarget; i++) {
            //继续遍历first下标及之后的元素
            getWithFirst(c, newTarget, i, ret, path);
        }
        path.pop_back();
    }
};

题目描述:

The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ...

1 is read off as “one 1” or 11.

11 is read off as “two 1s” or 21.

21 is read off as “one 2, then one 1” or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

题目意思要求把数字"说出来", 其实含义就是给定一个包含数字的字符串, 把它用另一种方式表示出来, 即"数字连续出现的数量 + 该数字". 这个新字符串作为下一次处理的源字符串. 因此我的解法就是模拟这种做法.

class Solution {
public:
    string countAndSay(int n) {
        string s = "1";
        for (int i = 1; i < n; i++) {
            string re;
            char now = s[0];
            int num = 1;
            int len = s.size();
            for (int i = 1; i < len; i++) {
                if (s[i] == now) num++;
                else {
                    re = re + to_string(num);
                    re.push_back(now);
                    num = 1;
                    now = s[i];
                }
            }
            re = re + to_string(num);
            re.push_back(now);
            s = re;
        }
        return s;
    }
};

题目描述:

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character ‘.’.

You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

题目要求解数独, 首先想到的解法是通过递归来穷举每一种可能的解. 在getValidNum函数中根据数独中已经存在的数获得当前位置可能填入的数. 该解法运行时间356ms.

class Solution {
public:
    vector<char> getValidNum(vector<vector<char>>& board, int step) {
        int r = step / 9, c = step % 9;
        set<char> re = { '1', '2', '3', '4', '5', '6', '7', '8', '9' };
        for (int i = 0; i < 9; i++) {
            if (board[r][i] != '.')
                re.erase(board[r][i]);
            if (board[i][c] != '.')
                re.erase(board[i][c]);
        }
        int rr = (r / 3) * 3, cc = (c / 3) * 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[rr + i][cc + j] != '.')
                    re.erase(board[rr + i][cc + j]);
            }
        }
        vector<char> rev;
        for (auto i : re)
            rev.push_back(i);
        return rev;
    }
    bool solveStep(vector<vector<char>>& board, int step) {
        if (step >= 81)
            return true;
        int r = step / 9, c = step % 9;
        if (board[r][c] != '.') {
            return solveStep(board, step + 1);
        }
        vector<char> validNum = getValidNum(board, step);
        for (auto i : validNum) {
            board[r][c] = i;
            if (solveStep(board, step + 1))
                return true;
        }
        board[r][c] = '.';
        return false;
    }
    void solveSudoku(vector<vector<char>>& board) {
        bool re = solveStep(board, 0);
    }
};

使用位运算代替set和vector来记录合法数字, 运算时间可以降至20ms.

class Solution {
public:
    int getValidNum(vector<vector<char>>& board, int step) {
        int r = step / 9, c = step % 9;
        int re = 0;
        for (int i = 0; i < 9; i++) {
            if (board[r][i] != '.')
                re |= 1 << (board[r][i] - '1');
            if (board[i][c] != '.')
                re |= 1 << (board[i][c] - '1');
        }
        int rr = (r / 3) * 3, cc = (c / 3) * 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[rr + i][cc + j] != '.')
                    re |= 1 << (board[rr + i][cc + j] - '1');
            }
        }
        return re;
    }
    bool solveStep(vector<vector<char>>& board, int step) {
        if (step >= 81)
            return true;
        int r = step / 9, c = step % 9;
        if (board[r][c] != '.') {
            return solveStep(board, step + 1);
        }
        int validNum = getValidNum(board, step);
        for (int i = 0; i < 9; i++) {
            if(validNum & (1 << i)) continue;
            board[r][c] = i + '1';
            if (solveStep(board, step + 1))
                return true;
        }
        board[r][c] = '.';
        return false;
    }
    void solveSudoku(vector<vector<char>>& board) {
        bool re = solveStep(board, 0);
    }
};

题目描述:

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

A partially filled sudoku which is valid.

Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

要求判断一个数独题目是否合法, 但并不要求一定有解. 一个数独题目合法有以下三个条件:

1. 每一行都没有重复元素
2. 每一列都没有重复元素
3. 九个3x3方格中都没有重复元素

因此验证这三个条件即可.

class Solution {
public:
    void setNumFlag(vector<int>& v){
        for(int i = 0; i < v.size(); i++) v[i] = 0;
    }
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<int> numFlag(9);
        for(int i = 0; i < 9; i++){
            setNumFlag(numFlag);
            for(int j = 0; j < 9; j++){
                char t = board[i][j];
                if(t >= '1' && t <= '9'){
                    if(numFlag[t - '1'] == 1)
                        return false;
                    else
                        numFlag[t - '1'] = 1;
                }
            }
        }

        for(int i = 0; i < 9; i++){
            setNumFlag(numFlag);
            for(int j = 0; j < 9; j++){
                char t = board[j][i];
                if(t >= '1' && t <= '9'){
                    if(numFlag[t - '1'] == 1)
                        return false;
                    else
                        numFlag[t - '1'] = 1;
                }
            }
        }

        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                int x = i * 3, y = j * 3;
                setNumFlag(numFlag);
                for(int ii = 0; ii < 3; ii++){
                    for(int jj = 0; jj < 3; jj++){
                        char t = board[x + ii][y + jj];
                        if(t >= '1' && t <= '9'){
                            if(numFlag[t - '1'] == 1)
                                return false;
                            else
                                numFlag[t - '1'] = 1;
                        }
                    }
                }
            }
        }

        return true;
    }
};

题目描述:

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

二分查找先确定数组中存不存在target, 如果存在则返回它的下标, 如果不存在那么就看target是不是比nums中的所有元素都大, 如果是就返回最后一个元素的下标nums.size(), 接下来判断二分搜索的结束位置与target的关系, 如果比target大, 那么就返回结束位置, 如果比target小, 那么就返回结束位置 + 1.

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int low = 0, high = nums.size();
        while(low < high){
            if(nums[(low + high) / 2] == target) return (low + high) / 2;
            else if(nums[(low + high) / 2] < target){
                low = (low + high) / 2 + 1;
            }else{
                high = (low + high) / 2;
            }
        }
        if(low == nums.size() || nums[low] > target)return low;
        else return low + 1;
    }
};

题目描述:

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

先使用二分搜索查找到目标, 再向前后搜索到数值的起始位置.

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                vector<int> ret = {mid, mid};
                while(ret[0] >= 0 && nums[ret[0]] == target) ret[0]--;
                while(ret[1] < nums.size() && nums[ret[1]] == target) ret[1]++;
                ret[0]++;
                ret[1]--;
                return ret;
            }
            else if(nums[mid] > target){
                right = mid;
            }
            else{
                left = mid + 1;
            }
        }
        return vector<int>(2, -1);
    }
};

印象笔记前段时间调整了收费策略, 免费账户只能同时登录两个设备, 这个就有点不爽了. 而且我也不是重度用户, 觉得并不值得为高级账户付钱, 所以想起了被传的神乎其神的OneNote.

我在装Office的时候一起装了OneNote, 所以直接打开试试, 不得不说功能可以的, 但是同步实在太过于艰难了, 在移动设备上同步更改要等很久很久, 这还是在Wi-Fi下, 在网络不好的时候岂不是完全不能用了? 而且我从印象笔记使用微软官方提供的工具导入笔记, 但是同步的时候却告诉我格式错误. Exo me? 这不是你自己导入的吗? 因为OneNote是基于OndDrive来同步的, 所以OneNote的同步问题就是OneDrive的同步问题, 我在Win10中彻底禁用OneDrive就是因为这个同步功能过于坑爹.

难道我跟微软的东西都是相性不合? 微软做的东西我就没几个是用的舒心的(少数的几个有VS, OutLook邮箱不是客户端, Windows和VS Online的Git服务), 尤其是跟网络沾边的东西, 不过这大概也不全是巨硬的锅, 毕竟我现在还生活在一个不正常国家. 另外, 相比于OneNote的类Word的编辑体验, 我更喜欢纯文本的编辑(比如Markdown), 大概是因为这给了我更大的自主性吧, 而且一些其他的高级功能我也用不上. 我现在还是用Markdown+Git来写东西和同步(BTW, 我的私人Git服务是用的微软的, 不过这该算是Git好用还是难得我用巨硬的东西用的舒服呢), 我喜欢这种每一个环节都可以彻底掌控的感觉, 只不过手机和平板上就没办法了.

最后, 折腾了几个小时OneNote最后还是浪费时间. 暂时还是用着印象笔记吧.