leetcode轮回计划20181127

355 Design Twitter
题意：要求实现[发布、关注、取关、获得前十条记录]四个接口。
思路：自己不能关注自己（因为会在获取记录的时候重复获取），优先队列的使用
357 Count Numbers with Unique Digits
题意：n位置数中没有重复数字的数字个数
思路：比较别致的动态规划。
365 Water and Jug Problem
题意：用两个量具测量一个特定的容量
思路：最大公约数
368 Largest Divisible Subset
题意：返回数组中的divisible子集
思路：中等难度的动态规划。

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int size = nums.size();
        vector<int> subset(size, 0);
        vector<int> parent(size, 0);
        int m = 0;
        int mi = 0;
        for(int i = size - 1;i >= 0;-- i){
            for(int j = i;j < size;++ j){
                if(nums[j] % nums[i] == 0 && subset[i] < subset[j] + 1){
                    subset[i] = subset[j] + 1;
                    parent[i] = j;
                    if(subset[i] > m){
                        m = subset[i];
                        mi = i;
                    }
                }
            }
        }
        
        vector<int> ret;
        for(int i = 0;i < m;++ i){
            ret.push_back(nums[mi]);
            mi = parent[mi];
        }
        return ret;
    }
};

371 Sum of Two Integers
题意：不用加减法进行两个整数的加法运算
思路：a + b = a^b + (a & b) << 1其中第一部分是不考虑进位的加法运算，第二部分是只考虑进位的加法运算。
375 Guess Number Higher or Lower II
题意：猜数字，能确定猜中的最小积分。
思路：中等难度的动态规划。

class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> dp(n + 1, vector<int>(n + 1));
        for(int j = 2;j <= n;++ j){
            for(int i = j - 1;i > 0;-- i){
                int global = INT_MAX;
                for(int k = i + 1;k < j;++ k){
                    int local = k + max(dp[i][k-1], dp[k+1][j]);
                    global = min(global, local);
                }
                dp[i][j] = i + 1 == j ? i : global;
            }
        }
        return dp[1][n];
    }
};

376 Wiggle Subsequence
题意：最小波浪子序列
思路：flag的应用
377 Combination Sum IV
题意：目标数字的组合方式的种类数量
思路：动态规划，注意重复。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int size = nums.size();
        vector<int> dp(target + 1, 0);
        int mini = INT_MAX;
        for(auto a : nums) if(a <= target) dp[a] = 1;
        for(int i = 1;i <= target + 1;++ i) for(auto a : nums) dp[i] += i > a ? dp[i - a] : 0;
        return dp[target];
    }
};

378 Kth Smallest Element in a Sorted Matrix
题意：矩阵行有序、列有序。返回矩阵中第K大的数字
思路：优先队列
380 Insert Delete GetRandom O(1)
题意：数据结构设计题目，要求三个功能[insert, remove, getrandom]要求平均时间复杂度为O(1)
思路：题目有问题吧，没有办法做到O(1)啊。。。不过能想到的只有hash。。。

leetcode轮回计划20181127

推荐阅读更多精彩内容