域名注册网站排行,wordpress部分密码,专业官网建设,长春seo快速排名Leetcode Test
1155 掷骰子等于目标和的方法数(10.24)
这里有 n 个一样的骰子#xff0c;每个骰子上都有 k 个面#xff0c;分别标号为 1 到 k 。
给定三个整数 n , k 和 target #xff0c;返回可能的方式(从总共 kn 种方式中)滚动骰子的数量#xff0c;使正面朝上的数…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 tnum,cnt0;while(t0){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 hgaphorizontalCuts[0],vgapverticalCuts[0];for(int i1;ihorizontalCutsSize;i){hgapfmax(hgap,horizontalCuts[i]-horizontalCuts[i-1]);}hgapfmax(hgap,h-horizontalCuts[horizontalCutsSize-1]);for(int i1;iverticalCutsSize;i){vgapfmax(vgap,verticalCuts[i]-verticalCuts[i-1]);}vgapfmax(vgap,w-verticalCuts[verticalCutsSize-1]);int mod1e97;long long retvgap*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 ret0;for(int i0;ik;i){qsort(gifts,giftsSize,sizeof(int),cmp);gifts[giftsSize-1]sqrt(gifts[giftsSize-1]);}for(int i0;igiftsSize;i){retgifts[i];}return ret;
}【原地堆化】灵神
class Solution {
public:long long pickGifts(vectorint 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 ncitationsSize;qsort(citations,n,sizeof(int),cmp);int h0,in-1;while(i0 citations[i]h){h;i--;}return h;
}【二分】对论文的数量进行二分总有一个最大的h满足宫水三叶
class Solution {
public:int hIndex(vectorint 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(vectorint 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 left0,rightcitationsSize-1;while(leftright){int midleft(right-left)/2;if(citations[mid]citationsSize-mid){rightmid-1;}else{leftmid1;}}return citationsSize-left;
}
