【Leetcode Sheet】Weekly Practice 13

Leetcode Test

1155 掷骰子等于目标和的方法数(10.24)

这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。

给定三个整数 n , k 和 target ，返回可能的方式(从总共 kn 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。

答案可能很大，你需要对 109 + 7 取模 。

提示：

• 1 <= n, k <= 30
• 1 <= 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 <= n
• i * 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 <= 109
• num 的数位中不含 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 <= 109
• 1 <= horizontalCuts.length <= min(h - 1, 105)
• 1 <= verticalCuts.length <= min(w - 1, 105)
• 1 <= horizontalCuts[i] < h
• 1 <= 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 <= 103
• 1 <= gifts[i] <= 109
• 1 <= 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.length
• 1 <= n <= 5000
• 0 <= 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.length
• 1 <= n <= 105
• 0 <= citations[i] <= 1000
• citations 按 升序排列

【二分】

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;
}