LeetCode 143周赛
2019-10-07 本文已影响0人
crishawy
1. 题目列表
2. 分糖果 II
简单模拟。
代码：
class Solution {
public:
vector<int> distributeCandies(int candies, int num_people) {
int cnt = 0;
vector<int> res(num_people);
int i = 0;
while (true){
int next = i + 1 + num_people * cnt;
if (candies <= next){
res[i] += candies;
break;
}else{
res[i] += (i + 1 + num_people * cnt);
candies -= next;
i++;
if (i == num_people){
i = 0;
cnt++;
}
}
}
return res;
}
};
3. 二叉树寻路
对于按正常顺序排列的完全二叉树来说：
当某节点的编号k为偶数时，则该节点为编号k/2节点的右子节点，
当某节点的编号k为奇数时，则该节点为编号k/2节点的左子节点。
对于z型二叉树来说，当节点的层数layer为偶数层时，当前层的实际节点编号为逆序交换后的节点编号，具体来说：
根据节点的层数计算该层节点的左边界和右边界节点分别为l和r，那么
l = 2^{layer - 1}, r = 2^{layer} - 1
实际节点的编号 s = 3l - label。
自底向上遍历，记录每层实际节点编号，直到节点的层数为1。
注意：当初始节点为偶数节点时，进行预处理，统一成奇数层节点。
代码：
class Solution {
public:
vector<int> pathInZigZagTree(int label) {
vector<int> res;
int n = (int)(log(label) / log(2)) + 1; // label节点的层数
int l = (int)pow(2, n - 1), s;
if (n % 2 == 0){
// 偶数层节点先统一成奇数层节点
res.push_back(label);
label = 3 * l - label - 1;
label /= 2;
n--;
}
while (n){
if (n % 2 == 0){ // 当前为偶数层
l = (int)pow(2, n - 1);
s = 3 * l - label - 1;
res.push_back(s);
}else{
// 当前为奇数层
res.push_back(label);
}
label /= 2;
n--;
}
reverse(res.begin(), res.end());
return res;
}
};
4. 填充书架
思路：一维DP
定义dp[i]表示前i个物品放在书架上的所需要的最小高度。
则状态转移方程：
dp[i] = min(dp[i], dp[j] + maxh), j = i-1, i-2, ..., 0
其中maxh表示物品i, i - 1, ... , j + 1最大高度，上述方程的含义是
对于第i个物品，我们尝试让其与更多的物品放在同一层书架，枚举所有的i-1...1的物品，
计算第i个物品的所需要的最小书架高度。
代码：
class Solution {
public:
int minHeightShelves(vector<vector<int>>& books, int shelf_width) {
int MIN = 0x7fffffff;
int dp[1010];
memset(dp, 0, sizeof(dp));
dp[0] = books[0][1];
for (int i = 1; i < books.size(); i++){
dp[i] = dp[i - 1] + books[i][1]; // 初始化dp[i]为新一层书架的高度
int maxh = books[i][1];
int w = books[i][0];
for (int j = i - 1; j >= 0; j--){
if (w + books[j][0] <= shelf_width){
maxh = max(maxh, books[j][1]);
if (j == 0) dp[i] = min(dp[i], maxh);
else dp[i] = min(dp[i], dp[j - 1] + maxh);
w += books[j][0];
}else break;
}
}
return dp[books.size() - 1];
}
};
5. 至少有 1 位重复的数字
排列组合：
注意转换思路，当讨论重复位过于复杂时，转换问题为计算1~N的不重复位数有多少个。
具体步骤：
假设N的位数为p，先计算1~p-1位的不重复位的个数。如97783，p = 5，设位数为i
i = 1时， 共9种
i = 2时， 共9 * 9 = 81种
i = 3时， 共9 * 9 * 8种
i = 4时， 共9 * 9 * 8 * 7种
i = 5时， 需要逐位讨论，设讨论的当前位为j
j = 1时，计算第一位小于N[1]的个数，_ _ _ _ _ 共8 * 9 * 8 * 7 * 6种
j = 2时，计算第二位小于N[2]的个数，9_ _ _ _ _ 共 7 * 8 * 7 * 6种，
j = 3时，计算第三位小于N[3]的个数，97_ _ _ 共7 * 7 * 6种，
j = 4时，计算第四位小于N[4]的个数，977_ _ _，此时出现重复位，则不用计算剩下的位数。
res = N - sum
注意：特判N < 10，return 0
代码：
class Solution {
public:
int numDupDigitsAtMostN(int N) {
if (N < 10) return 0;
int a = N; // 拷贝N
int p = 0;
vector<int> digits;
while (N){
p++;
digits.push_back(N % 10);
N /= 10;
}
int sum = 0;
for (int i = 1; i < p; i++){
int cnt = 9;
for (int j = 1; j < i; j++)
cnt = cnt * (10 - j);
sum += cnt;
}
reverse(digits.begin(), digits.end());
int len = digits.size();
int hash[11];
memset(hash, 0, sizeof(hash));
for (int i = 0; i < len; i++){
int cnt = 0;
if (i == 0){
cnt = digits[i] - 1;
hash[digits[i]] = 1;
if (cnt <= 0) continue;
for (int j = 1; j <= len - 1; j++)
cnt *= (10 - j);
sum += cnt;
}else if(i == len - 1){
for (int j = 0; j <= digits[i]; j++){
if (!hash[j]) cnt++;
}
sum += cnt;
}else{
int cf = 0; // 定义当前位与前导位重复位的个数
for (int j = 0; j < digits[i]; j++){
if (hash[j]) cf++;
}
cnt = digits[i] - cf; // 当前位的可选个数 = 0 ~ (digits[i] - 1) - 重复位个数
for (int j = i + 1; j < len; j++){
cnt *= (10 - j); // 剩余位可选择的个数
}
sum += cnt;
if (hash[digits[i]] == 1){ // 如果当前位与前导位存在重复位，那么后续位不存在满足条件的数
break;
}
hash[digits[i]] = 1; // 记录当前位已存在
}
}
return a - sum;
}
};
