头像

Liar_6




离线:1天前


最近来访(1)
用户头像
bhs


Liar_6
3天前


活动打卡代码 AcWing 278. First Bad Version

Liar_6
2019-11-30 05:51
//这里填你的代码^^
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        long long  l = 1, r = n, m;
        while (l < r) {
            m = (l+r)/2;
            if (isBadVersion(m)) r = m;
            else l = m+1;
        }
        return m;
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Liar_6
2019-11-26 15:56
//这里填你的代码^^
class Solution {
public:
    vector<string> res;
    string cur; // 自动初始化为null
    map<char, string> mp = {
        {'2', "abc"}, {'3', "edf"}, {'4', "ghi"},
        {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"},
        {'8', "tuv"}, {'9', "wxyz"}
    };
    vector<string> letterCombinations(string digits) {
        if (!digits.size()) return res;
        DFS(digits);
        return res;
    }
    void DFS(string digit) {    // 栈or队列
        if (!digit.size()) res.push_back(cur);
        else {
            char num = digit[0];
            string letter = mp[num];
            for (int i = 0; i < letter.size(); ++i) {
                cur.push_back(letter[i]);
                DFS(digit.substr(1));
                cur.pop_back();
            }
        }
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Liar_6
2019-11-25 05:25
//这里填你的代码^^
class Solution {
public:
    int findMin(vector<int>& nums) {
        int m, s = 0, e = nums.size()-1, min = nums[0];
        while (s <= e) {
            int m = (s+e+1)/2;
            if (nums[m] > min) s = m+1;
            else {
                e = m-1;
                min = nums[m];
            }
        }
        return min;
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 120. Triangle

Liar_6
2019-11-24 15:46
//这里填你的代码^^
class Solution {
public:
    int minimumTotal(vector<vector<int>>& nums) {
        int n = nums.size();
        vector<vector<long long>> f(2, vector<long long>(n));
        f[0][0] = nums[0][0];
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                f[i][j] = INT_MAX;
                if (j > 0) f[i][j] = min(f[i][j], f[i-1][j-1] + nums[i][j]);
                if (j < i) f[i][j] = min(f[i][j], f[i-1][j] + nums[i][j]);
            }
        }
        long long res = INT_MAX;
        for (int i = 0; i < n; i++) res = min(f[n-1][i], res);
        return res;
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 74. Search a 2D Matrix

Liar_6
2019-11-24 10:22
//这里填你的代码^^
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 注意数组为空时,matrix[0]越界
        int r = matrix.size(), c;
        if (r == 0) return false;
        else c = matrix[0].size();
        int s = 0, e = r*c-1;
        while (s <= e) {
            int m = (s+e)/2;
            int mc = m%c;
            int mr = (m-mc)/c;
            if (matrix[mr][mc] < target) s = m+1;
            else if (matrix[mr][mc] > target) e = m-1;
            else return true;
        }
        return false;
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 198. House Robber

Liar_6
2019-11-24 08:59
//这里填你的代码^^
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n);
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]);
        if (n == 3) return max(nums[0]+nums[2], nums[1]);
        f[0] = nums[0], f[1] = nums[1];
        f[2] = max(nums[0]+nums[2], nums[1]);
        int m = max(f[0], f[1]);
        m = max(f[2], m);
        for (int i = 3; i < n; i++) {
            if (i-3 >= 0) f[i] = max(f[i-2], f[i-3]) + nums[i];
            m = max(f[i], m);
        }
        return m;
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 63. Unique Paths II

Liar_6
2019-11-22 16:00
//这里填你的代码^^
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<long long>> dp(m+1, vector<long long>(n+1, 0));
        if (obstacleGrid[0][0] == 1) return 0;
        else dp[1][1] = 1;
        for (int i = 1; i < m+1; i++) {
            for (int j = 1; j < n+1; j++) {
                if (obstacleGrid[i-1][j-1] == 1) {
                    dp[i][j] = 0;
                    continue;
                }
                dp[i][j] = max(dp[i][j], dp[i-1][j] + dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~


活动打卡代码 AcWing 53. Maximum Subarray

Liar_6
2019-11-19 03:47
//这里填你的代码^^
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN, pre = 0;
        for (int i = nums.size()-1; i >= 0; i--) {  //向前处理f[i]=max(f[i+1],0)+nums[i];
            int now = max(pre, 0) + nums[i];
            res = max(res, now);
            pre = now;
        }
        return res;
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~



Liar_6
2019-11-18 01:14
//这里填你的代码^^
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res;
        if (nums.empty()) return {-1,-1};
        int i = 0, l = nums.size()-1;
        while (i < l) {
            int m = (i+l)/2;
            if (nums[m] < target) {
                i = m+1;
            } else {
                l = m;
            }
        }
        if (nums[l]==target) res.push_back(l);
        else res.push_back(-1);
        i = 0, l = nums.size()-1;
        while (i < l) {
            int m = (i+l+1)/2;
            if (nums[m] > target) {
                l = m-1;
            } else {
                i = m;
            }
        }
        if (nums[i]==target) res.push_back(i);
        else res.push_back(-1);
        return res;
    }
};
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~