- 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。。。
