专业设计网站排名,wordpress做门户网,罗湖网站的建设,制作钓鱼网站教程Leetcode Test
823 带因子的二叉树(8.29)
给出一个含有不重复整数元素的数组 arr #xff0c;每个整数 arr[i] 均大于 1。
用这些整数来构建二叉树#xff0c;每个整数可以使用任意次数。其中#xff1a;每个非叶结点的值应等于它的两个子结点的值的乘积。
满足条件的二…Leetcode Test
823 带因子的二叉树(8.29)
给出一个含有不重复整数元素的数组 arr 每个整数 arr[i] 均大于 1。
用这些整数来构建二叉树每个整数可以使用任意次数。其中每个非叶结点的值应等于它的两个子结点的值的乘积。
满足条件的二叉树一共有多少个答案可能很大返回 对 109 7 取余 的结果。
提示
1 arr.length 10002 arr[i] 109arr 中的所有值 互不相同
int cmp(void *a,void *b){return *(int*)a-*(int*)b;
}
int numFactoredBinaryTrees(int* arr, int arrSize){//每个非叶结点的值应等于它的两个子结点的值的乘积。qsort(arr,arrSize,sizeof(int),cmp);//对arr进行排序long long *dp(long long*)malloc(sizeof(long long)*arrSize);//开辟dp数组long long res0,mod1e97;//初始化result定义modfor(int i0;iarrSize;i){dp[i]1; //只有当前数字作为根节点一定符合for(int left0,righti-1;leftright;left){//遍历当前数字之前的所有数字while(leftright (long long)arr[left]*arr[right]arr[i]){//缩短right范围right--;}if(leftright (long long)arr[left]*arr[right]arr[i]){//符合x*yif(leftright){//如果两个子节点相同dp[i](dp[i]dp[left]*dp[right])%mod;}else{//如果两个子节点不同left和right子节点可以交换组成两个新的树因此需要*2dp[i](dp[i]dp[left]*dp[right]*2)%mod;}}}resdp[i];resres%mod;}return res;
}1654 到家的最少跳跃次数(8.30)
有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发到达它的家。
跳蚤跳跃的规则如下
它可以 往前 跳恰好 a 个位置即往右跳。它可以 往后 跳恰好 b 个位置即往左跳。它不能 连续 往后跳 2 次。它不能跳到任何 forbidden 数组中的位置。
跳蚤可以往前跳 超过 它的家的位置但是它 不能跳到负整数 的位置。
给你一个整数数组 forbidden 其中 forbidden[i] 是跳蚤不能跳到的位置同时给你整数 a b 和 x 请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达 x 的可行方案请你返回 -1 。
提示
1 forbidden.length 10001 a, b, forbidden[i] 20000 x 2000forbidden 中所有位置互不相同。位置 x 不在 forbidden 中。
class Solution {
public:int minimumJumps(vectorint forbidden, int a, int b, int x) {queuetupleint, int, int q;unordered_setint visited;q.emplace(0, 1, 0);visited.emplace(0);int lower 0, upper max(*max_element(forbidden.begin(), forbidden.end()) a, x) b;unordered_setint forbiddenSet(forbidden.begin(), forbidden.end());while (!q.empty()) {auto [position, direction, step] q.front();q.pop();if (position x) {return step;}int nextPosition position a;int nextDirection 1;if (lower nextPosition nextPosition upper !visited.count(nextPosition * nextDirection) !forbiddenSet.count(nextPosition)) {visited.emplace(nextPosition * nextDirection);q.emplace(nextPosition, nextDirection, step 1);}if (direction 1) {nextPosition position - b;nextDirection -1;if (lower nextPosition nextPosition upper !visited.count(nextPosition * nextDirection) !forbiddenSet.count(nextPosition)) {visited.emplace(nextPosition * nextDirection);q.emplace(nextPosition, nextDirection, step 1);}}}return -1;}
};1761 一个图中连通三元组的最小度数(8.31)
给你一个无向图整数 n 表示图中节点的数目edges 数组表示图中的边其中 edges[i] [ui, vi] 表示 ui 和 vi 之间有一条无向边。
一个 连通三元组 指的是 三个 节点组成的集合且这三个点之间 两两 有边。
连通三元组的度数 是所有满足此条件的边的数目一个顶点在这个三元组内而另一个顶点不在这个三元组内。
请你返回所有连通三元组中度数的 最小值 如果图中没有连通三元组那么返回 -1 。
提示
2 n 400edges[i].length 21 edges.length n * (n-1) / 21 ui, vi nui ! vi图中没有重复的边。
【枚举法】
int minTrioDegree(int n, int** edges, int edgesSize, int* edgesColSize){//枚举法int g[n][n],degree[n];//邻接矩阵g存储所有边//三元组i、j、k对应的三个g都是1//degree处理每个点的度数memset(g,0,sizeof(g));memset(degree,0,sizeof(degree));//初始化int medgesSize;for(int i0;im;i){int xedges[i][0]-1,yedges[i][1]-1;//x和y是点的编号从0开始g[x][y]g[y][x]1;//给x到y、y到x的边进行记录degree[x];//x度数degree[y];//y度数}int ansINT_MAX;//初始化max-answerfor(int i0;in;i){for(int ji1;jn;j){if(g[i][j]1){ //如果i到j有边for(int kj1;kn;k){if(g[i][k]1 g[j][k]1){ //i到k有边 且 j到k有边ansfmin(ans,degree[i]degree[j]degree[k]-6); //取最小值}}}}}return ans INT_MAX ? -1 : ans;
}2240 买钢笔和铅笔的方案数(9.1)
给你一个整数 total 表示你拥有的总钱数。同时给你两个整数 cost1 和 cost2 分别表示一支钢笔和一支铅笔的价格。你可以花费你部分或者全部的钱去买任意数目的两种笔。
请你返回购买钢笔和铅笔的 不同方案数目 。
提示
1 total, cost1, cost2 106
【枚举法】
long long waysToBuyPensPencils(int total, int cost1, int cost2){if(cost1cost2) return waysToBuyPensPencils(total,cost2,cost1);//always let lower cost in the first placelong long res0,cnt0;//initializewhile(cnt*cost1total){ //cnt is for cost1res(total-cnt*cost1)/cost21;//total - cost1*cnt : remain $//remain / cost2 : most object2 itemscnt;}return res;
}2511 最多可以摧毁的敌人城堡数目(9.2)
给你一个长度为 n 下标从 0 开始的整数数组 forts 表示一些城堡。forts[i] 可以是 -1 0 或者 1 其中
-1 表示第 i 个位置 没有 城堡。0 表示第 i 个位置有一个 敌人 的城堡。1 表示第 i 个位置有一个你控制的城堡。
现在你需要决定将你的军队从某个你控制的城堡位置 i 移动到一个空的位置 j 满足
0 i, j n - 1军队经过的位置 只有 敌人的城堡。正式的对于所有 min(i,j) k max(i,j) 的 k 都满足 forts[k] 0 。
当军队移动时所有途中经过的敌人城堡都会被 摧毁 。
请你返回 最多 可以摧毁的敌人城堡数目。如果 无法 移动你的军队或者没有你控制的城堡请返回 0 。
提示
1 forts.length 1000-1 forts[i] 1
【对last使用dp】
int captureForts(int* forts, int fortsSize){//move from [i] to [j]//forts[i]1 forts[j]-1int nfortsSize;int result0,last-1;for(int i0;in;i){if(forts[i]!0){ //if forts[i] 1 or -1if(last0 forts[i]!forts[last]){ //if last doesnt equal to iresultfmax(result,i-last-1); //update result}lasti; //update last}}return result;
}1921 消灭怪物的最大数量(9.3)
你正在玩一款电子游戏在游戏中你需要保护城市免受怪物侵袭。给你一个 下标从 0 开始 且长度为 n 的整数数组 dist 其中 dist[i] 是第 i 个怪物与城市的 初始距离单位米。
怪物以 恒定 的速度走向城市。给你一个长度为 n 的整数数组 speed 表示每个怪物的速度其中 speed[i] 是第 i 个怪物的速度单位米/分。
怪物从 第 0 分钟 时开始移动。你有一把武器并可以 选择 在每一分钟的开始时使用包括第 0 分钟。但是你无法在一分钟的中间使用武器。这种武器威力惊人一次可以消灭任一还活着的怪物。
一旦任一怪物到达城市你就输掉了这场游戏。如果某个怪物 恰 在某一分钟开始时到达城市这会被视为 输掉 游戏在你可以使用武器之前游戏就会结束。
返回在你输掉游戏前可以消灭的怪物的 最大 数量。如果你可以在所有怪物到达城市前将它们全部消灭返回 n 。
提示
n dist.length speed.length1 n 1051 dist[i], speed[i] 105
【贪心】
int cmp(void *a,void *b){return *(int*)a-*(int*)b;
}//贪心法消灭来的最快的
int eliminateMaximum(int* dist, int distSize, int* speed, int speedSize){int ndistSize;int arr[n];for(int i0;in;i){arr[i](dist[i]-1)/speed[i]1;//dist[i]/speed[i] 可能是小数但是需要取整}qsort(arr,n,sizeof(int),cmp);//排序到达时间for(int i0;in;i){if(arr[i]i){return i;}}return n;
}449 序列化和反序列化二叉搜索树(9.4)
序列化是将数据结构或对象转换为一系列位的过程以便它可以存储在文件或内存缓冲区中或通过网络连接链路传输以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
提示
树中节点数范围是 [0, 104]0 Node.val 104题目数据 保证 输入的树是一棵二叉搜索树。
#define MAX_NODE_SIZE 10000void postOrder(struct TreeNode *root, int *arr, int *pos) {if (root NULL) {return;}postOrder(root-left, arr, pos);postOrder(root-right, arr, pos);arr[(*pos)] root-val;
}struct TreeNode * construct(int lower, int upper, int *stack, int *top) {if (*top 0 || stack[*top - 1] lower || stack[*top - 1] upper) {return NULL;}int val stack[*top - 1];(*top)--;struct TreeNode *root (struct TreeNode *)malloc(sizeof(struct TreeNode));root-val val;root-right construct(val, upper, stack, top);root-left construct(lower, val, stack, top);return root;
}char* serialize(struct TreeNode* root) {char *res NULL;int *arr (int *)malloc(sizeof(int) * MAX_NODE_SIZE);int pos 0;postOrder(root, arr, pos);if (pos 0) {return ;}res (char *)malloc(sizeof(char) * pos * 6);int len 0;for (int i 0; i pos - 1; i) {len sprintf(res len, %d,, arr[i]);}sprintf(res len, %d, arr[pos - 1]);free(arr);return res;
}struct TreeNode* deserialize(char* data) {int len strlen(data);if (len 0) {return NULL;}int *stack (int *)malloc(sizeof(int) * MAX_NODE_SIZE);int pos 0;int top 0;while (pos len) {while (pos len data[pos] ,) {pos;}int val 0;int start pos;while (pos len data[pos] ! ,) {val val * 10 data[pos] - 0;pos;}if (start pos) {stack[top] val;}}struct TreeNode *root construct(INT_MIN, INT_MAX, stack, top);free(stack);return root;
}
