【Leetcode Sheet】Weekly Practice 5

Leetcode Test

823 带因子的二叉树(8.29)

给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。

用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。

满足条件的二叉树一共有多少个？答案可能很大，返回 对 109 + 7 取余 的结果。

提示：

• 1 <= arr.length <= 1000
• 2 <= arr[i] <= 109
• arr 中的所有值 互不相同

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 res=0,mod=1e9+7;//初始化result，定义modfor(int i=0;i<arrSize;i++){dp[i]=1;	//只有当前数字作为根节点，一定符合for(int left=0,right=i-1;left<=right;left++){//遍历当前数字之前的所有数字while(left<=right && (long long)arr[left]*arr[right]>arr[i]){//缩短right范围right--;}if(left<=right && (long long)arr[left]*arr[right]==arr[i]){//符合x*yif(left==right){//如果两个子节点相同dp[i]=(dp[i]+dp[left]*dp[right])%mod;}else{//如果两个子节点不同，left和right子节点可以交换，组成两个新的树，因此需要*2dp[i]=(dp[i]+dp[left]*dp[right]*2)%mod;}}}res+=dp[i];res=res%mod;}return res;
}

1654 到家的最少跳跃次数(8.30)

有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。

跳蚤跳跃的规则如下：

• 它可以 往前 跳恰好 a 个位置（即往右跳）。
• 它可以 往后 跳恰好 b 个位置（即往左跳）。
• 它不能 连续 往后跳 2 次。
• 它不能跳到任何 forbidden 数组中的位置。

跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。

给你一个整数数组 forbidden ，其中 forbidden[i] 是跳蚤不能跳到的位置，同时给你整数 a， b 和 x ，请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达 x 的可行方案，请你返回 -1 。

提示：

• 1 <= forbidden.length <= 1000
• 1 <= a, b, forbidden[i] <= 2000
• 0 <= x <= 2000
• forbidden 中所有位置互不相同。
• 位置 x 不在 forbidden 中。

class Solution {
public:int minimumJumps(vector<int>& forbidden, int a, int b, int x) {queue<tuple<int, int, int>> q;unordered_set<int> visited;q.emplace(0, 1, 0);visited.emplace(0);int lower = 0, upper = max(*max_element(forbidden.begin(), forbidden.end()) + a, x) + b;unordered_set<int> 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 <= 400
• edges[i].length == 2
• 1 <= edges.length <= n * (n-1) / 2
• 1 <= ui, vi <= n
• ui != 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 m=edgesSize;for(int i=0;i<m;i++){int x=edges[i][0]-1,y=edges[i][1]-1;//x和y是点的编号，从0开始g[x][y]=g[y][x]=1;//给x到y、y到x的边进行记录degree[x]++;//x度数++degree[y]++;//y度数++}int ans=INT_MAX;//初始化max-answerfor(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(g[i][j]==1){ //如果i到j有边for(int k=j+1;k<n;k++){if(g[i][k]==1 && g[j][k]==1){   //i到k有边 且 j到k有边ans=fmin(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(cost1<cost2) return waysToBuyPensPencils(total,cost2,cost1);//always let lower cost in the first placelong long res=0,cnt=0;//initializewhile(cnt*cost1<=total){    //cnt is for cost1res+=(total-cnt*cost1)/cost2+1;//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 n=fortsSize;int result=0,last=-1;for(int i=0;i<n;i++){if(forts[i]!=0){    //if forts[i] == 1 or -1if(last>=0 && forts[i]!=forts[last]){   //if last doesn't equal to iresult=fmax(result,i-last-1);   //update result}last=i; //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.length
• 1 <= n <= 105
• 1 <= 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 n=distSize;int arr[n];for(int i=0;i<n;i++){arr[i]=(dist[i]-1)/speed[i]+1;//dist[i]/speed[i] 可能是小数，但是需要取整}qsort(arr,n,sizeof(int),cmp);//排序到达时间for(int i=0;i<n;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;
}