【Leetcode Sheet】Weekly Practice 13
Leetcode Test
1155 掷骰子等于目标和的方法数(10.24)
这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
给定三个整数 n , k 和 target ，返回可能的方式(从总共 kn 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。
答案可能很大，你需要对 109 + 7 取模 。
提示：
1 <= n, k <= 301 <= target <= 1000
【动态规划】
const int MOD = 1e9 + 7;int numRollsToTarget(int n, int k, int target) {int f[n + 1][target + 1];memset(f, 0, sizeof(f));f[0][0] = 1;for (int i = 1; i <= n; ++i) {for (int j = 0; j <= target; ++j) {for (int x = 1; x <= k; ++x) {if (j - x >= 0) {f[i][j] = (f[i][j] + f[i - 1][j - x]) % MOD;}}}}return f[n][target];
}
2698 求一个整数的惩罚数(10.25)
给你一个正整数 n ，请你返回 n 的 惩罚数 。
n 的 惩罚数 定义为所有满足以下条件 i 的数的平方和：
1 <= i <= ni * i的十进制表示的字符串可以分割成若干连续子字符串，且这些子字符串对应的整数值之和等于i。
提示：
1 <= n <= 1000
【回溯】
bool dfs(const char *s, int pos, int tot, int target) {//tot累计和，target目标和if (s[pos] == '\0') {return tot == target;} int sum = 0;for (int i = pos; s[i] != '\0'; i++) {sum = sum * 10 + s[i] - '0';//子串对应的整数值if (sum + tot > target) {break;}if (dfs(s, i + 1, sum + tot, target)) {return true;}}return false;
}int punishmentNumber(int n){int res = 0;char s[32];for (int i = 1; i <= n; i++) {sprintf(s, "%d", i * i);//将i*i转换为字符串sif (dfs(s, 0, 0, i)) {res += i * i;//回溯}}return res;
}
2520 统计能整除数字的位数(10.26)
给你一个整数 num ，返回 num 中能整除 num 的数位的数目。
如果满足 nums % val == 0 ，则认为整数 val 可以整除 nums 。
提示：
1 <= num <= 109num的数位中不含0
【模拟】
int countDigits(int num){int t=num,cnt=0;while(t>0){if(num%(t%10)==0){cnt++;}t/=10;}return cnt;
}
1465 切割后面积最大的蛋糕(10.27)
矩形蛋糕的高度为 h 且宽度为 w，给你两个整数数组 horizontalCuts 和 verticalCuts，其中：
horizontalCuts[i]是从矩形蛋糕顶部到第i个水平切口的距离verticalCuts[j]是从矩形蛋糕的左侧到第j个竖直切口的距离
请你按数组 horizontalCuts 和 verticalCuts 中提供的水平和竖直位置切割后，请你找出 面积最大 的那份蛋糕，并返回其 面积 。由于答案可能是一个很大的数字，因此需要将结果 对 109 + 7 取余 后返回。
提示：
2 <= h, w <= 1091 <= horizontalCuts.length <= min(h - 1, 105)1 <= verticalCuts.length <= min(w - 1, 105)1 <= horizontalCuts[i] < h1 <= verticalCuts[i] < w- 题目数据保证
horizontalCuts中的所有元素各不相同 - 题目数据保证
verticalCuts中的所有元素各不相同
【贪心】找到最宽和最高的位置间距
int cmp(void *a,void *b){return *(int*)a-*(int*)b;
}int maxArea(int h, int w, int* horizontalCuts, int horizontalCutsSize, int* verticalCuts, int verticalCutsSize){qsort(horizontalCuts,horizontalCutsSize,sizeof(int),cmp);qsort(verticalCuts,verticalCutsSize,sizeof(int),cmp);//search for the widest gap//必须longlong不然溢出long long hgap=horizontalCuts[0],vgap=verticalCuts[0];for(int i=1;i<horizontalCutsSize;i++){hgap=fmax(hgap,horizontalCuts[i]-horizontalCuts[i-1]);}hgap=fmax(hgap,h-horizontalCuts[horizontalCutsSize-1]);for(int i=1;i<verticalCutsSize;i++){vgap=fmax(vgap,verticalCuts[i]-verticalCuts[i-1]);}vgap=fmax(vgap,w-verticalCuts[verticalCutsSize-1]);int mod=1e9+7;long long ret=vgap*hgap%mod;return ret;
}
2558 从数量最多的堆取走礼物(10.28)
给你一个整数数组 gifts ，表示各堆礼物的数量。每一秒，你需要执行以下操作：
- 选择礼物数量最多的那一堆。
- 如果不止一堆都符合礼物数量最多，从中选择任一堆即可。
- 选中的那一堆留下平方根数量的礼物（向下取整），取走其他的礼物。
返回在 k 秒后剩下的礼物数量。
提示：
1 <= gifts.length <= 1031 <= gifts[i] <= 1091 <= k <= 103
【排序】
int cmp(void *a,void *b){return*(int*)a-*(int*)b;
}long long pickGifts(int* gifts, int giftsSize, int k){long long ret=0;for(int i=0;i<k;i++){qsort(gifts,giftsSize,sizeof(int),cmp);gifts[giftsSize-1]=sqrt(gifts[giftsSize-1]);}for(int i=0;i<giftsSize;i++){ret+=gifts[i];}return ret;
}
【原地堆化】灵神
class Solution {
public:long long pickGifts(vector<int> &gifts, int k) {make_heap(gifts.begin(), gifts.end()); // 原地堆化（最大堆）while (k-- && gifts[0] > 1) {pop_heap(gifts.begin(), gifts.end()); // 弹出堆顶并移到末尾gifts.back() = sqrt(gifts.back());push_heap(gifts.begin(), gifts.end()); // 把末尾元素入堆}return accumulate(gifts.begin(), gifts.end(), 0LL);}
};
274 H指数(10.29)
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，h 指数 是其中最大的那个。
提示：
n == citations.length1 <= n <= 50000 <= citations[i] <= 1000
【排序】
int cmp(void *a,void *b){return *(int*)a-*(int*)b;
}int hIndex(int* citations, int citationsSize){int n=citationsSize;qsort(citations,n,sizeof(int),cmp);int h=0,i=n-1;while(i>=0 && citations[i]>h){h++;i--;}return h;
}
【二分】对论文的数量进行二分，总有一个最大的h满足（宫水三叶）
class Solution {
public:int hIndex(vector<int>& cs) {int n = cs.size();int l = 0, r = n;while (l < r) {int mid = (l + r + 1) / 2;//如果满足引用mid次的论文大于mid篇，更新左侧if (check(cs, mid)) l = mid;//如果引用mid次的论文小于mid篇，更新右侧else r = mid - 1;}return r;}bool check(vector<int>& cs, int x) {int cnt = 0;for (int c : cs) {if (c >= x) cnt++;}return cnt >= x;}
};
275 H指数Ⅱ(10.30)
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。
h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。
请你设计并实现对数时间复杂度的算法解决此问题。
提示：
n == citations.length1 <= n <= 1050 <= citations[i] <= 1000citations按 升序排列
【二分】
int hIndex(int* citations, int citationsSize){int left=0,right=citationsSize-1;while(left<=right){int mid=left+(right-left)/2;if(citations[mid]>=citationsSize-mid){right=mid-1;}else{left=mid+1;}}return citationsSize-left;
}