电商网站 建社区,网页布局网站,家具在线设计网站,宁波网站关键词推广Leetcode Test
1462 课程表Ⅳ(9.12)
你总共需要上 numCourses 门课#xff0c;课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite #xff0c;其中 prerequisites[i] [ai, bi] 表示如果你想选 bi 课程#xff0c;你 必须 先选 ai 课程。
有的课会有直接…Leetcode Test
1462 课程表Ⅳ(9.12)
你总共需要上 numCourses 门课课程编号依次为 0 到 numCourses-1 。你会得到一个数组 prerequisite 其中 prerequisites[i] [ai, bi] 表示如果你想选 bi 课程你 必须 先选 ai 课程。
有的课会有直接的先修课程比如如果想上课程 1 你必须先上课程 0 那么会以 [0,1] 数对的形式给出先修课程数对。
先决条件也可以是 间接 的。如果课程 a 是课程 b 的先决条件课程 b 是课程 c 的先决条件那么课程 a 就是课程 c 的先决条件。
你也得到一个数组 queries 其中 queries[j] [uj, vj]。对于第 j 个查询您应该回答课程 uj 是否是课程 vj 的先决条件。
返回一个布尔数组 answer 其中 answer[j] 是第 j 个查询的答案。
提示
2 numCourses 1000 prerequisites.length (numCourses * (numCourses - 1) / 2)prerequisites[i].length 20 ai, bi n - 1ai ! bi每一对 [ai, bi] 都 不同先修课程图中没有环。1 queries.length 1040 ui, vi n - 1ui ! vi
【广度优先 拓扑】官解
/*** Note: The returned array must be malloced, assume caller calls free().*/
bool* checkIfPrerequisite(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize){int g[numCourses][numCourses];int gColSize[numCourses], indgree[numCourses];bool isPre[numCourses][numCourses];memset(gColSize, 0, sizeof(gColSize));memset(indgree, 0, sizeof(indgree));memset(isPre, 0, sizeof(isPre));for (int i 0; i prerequisitesSize; i) {int *p prerequisites[i];indgree[p[1]];g[p[0]][gColSize[p[0]]] p[1];}int queue[numCourses];int head 0, tail 0;for (int i 0; i numCourses; i) {if (indgree[i] 0) {queue[tail] i;}}while (head ! tail) {int cur queue[head];head;for (int j 0; j gColSize[cur]; j) {int ne g[cur][j];isPre[cur][ne] true;for (int i 0; i numCourses; i) {isPre[i][ne] isPre[i][ne] | isPre[i][cur];}--indgree[ne];if (indgree[ne] 0) {queue[tail] ne;}}}bool *res (bool *)malloc(sizeof(char) * queriesSize);for (int i 0; i queriesSize; i) {int *query queries[i];res[i] isPre[query[0]][query[1]];}*returnSize queriesSize;return res;
}2596 检查骑士巡视方案(9.13)
骑士在一张 n x n 的棋盘上巡视。在有效的巡视方案中骑士会从棋盘的 左上角 出发并且访问棋盘上的每个格子 恰好一次 。
给你一个 n x n 的整数矩阵 grid 由范围 [0, n * n - 1] 内的不同整数组成其中 grid[row][col] 表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。
如果 grid 表示了骑士的有效巡视方案返回 true否则返回 false。
注意骑士行动时可以垂直移动两个格子且水平移动一个格子或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。
提示
n grid.length grid[i].length3 n 70 grid[row][col] n * ngrid 中的所有整数 互不相同
【哈希表】
bool checkValidGrid(int** grid, int gridSize, int* gridColSize){//初始化hash-tableint ngridSize;int *xmalloc(sizeof(int)*(n*n));int *ymalloc(sizeof(int)*(n*n));for(int i0;in*n;i){x[i]0;y[i]0;}//遍历矩阵赋值hash-tablefor(int i0;in;i){for(int j0;jn;j){int posgrid[i][j]; //grid中的数字x[pos]i; //hash-xy[pos]j; //hash-y}}//定义初始值int xxx[0],yyy[0];bool flag1;if(xx!0 || yy!0) return 0; //骑士的行动是从下标 0 开始的。//遍历hash-tablefor(int i1;in*n;i){if( (abs(x[i]-xx)1 abs(y[i]-yy)2) || (abs(x[i]-xx)2 abs(y[i]-yy)1) ){xxx[i];yyy[i];//更新上一个值}else{flag0;break;}}return flag;
}1222 可以攻击国王的皇后(9.14)
在一个 8x8 的棋盘上放置着若干「黑皇后」和一个「白国王」。
给定一个由整数坐标组成的数组 queens 表示黑皇后的位置以及一对坐标 king 表示白国王的位置返回所有可以攻击国王的皇后的坐标(任意顺序)。
提示
1 queens.length 63queens[i].length 20 queens[i][j] 8king.length 20 king[0], king[1] 8一个棋盘格上最多只能放置一枚棋子。
【模拟】从king开始向8个方向寻找queen
/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
int** queensAttacktheKing(int** queens, int queensSize, int* queensColSize, int* king, int kingSize, int* returnSize, int** returnColumnSizes){//many blank, one white, 8x8//queens -- blanks, king -- whiteint nqueensSize;int pos[8][8]{0};for(int i0;in;i){pos[queens[i][0]][queens[i][1]]1;}//queen matrixint **res(int**)malloc(sizeof(int)*(2*n));*returnColumnSizes(int*)malloc(sizeof(int)*(2*n));*returnSize0;int xking[0],yking[1];int dir[8][2]{{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};//direction for attackfor(int i0;i8;i){int txxdir[i][0];int tyydir[i][1];while(tx0 tx8 ty0 ty8 pos[tx][ty]!1){txdir[i][0];tydir[i][1];}//move to the first bool flag1;if(tx0 || tx7 || ty0 || ty7){flag0;}if(!flag){continue;}//judge if pos out of rangeif(pos[tx][ty]1){res[*returnSize](int*)malloc(sizeof(int)*2);(*returnColumnSizes)[(*returnSize)]2; //每一个小数组包含2维res[(*returnSize)][0]tx;res[(*returnSize)][1]ty;(*returnSize);}}return res;
}LCP 50 宝石补给(9.15)
欢迎各位勇者来到力扣新手村在开始试炼之前请各位勇者先进行「宝石补给」。
每位勇者初始都拥有一些能量宝石 gem[i] 表示第 i 位勇者的宝石数量。现在这些勇者们进行了一系列的赠送operations[j] [x, y] 表示在第 j 次的赠送中 第 x 位勇者将自己一半的宝石需向下取整赠送给第 y 位勇者。
在完成所有的赠送后请找到拥有最多宝石的勇者和拥有最少宝石的勇者并返回他们二者的宝石数量之差。
注意
赠送将按顺序逐步进行。
提示
2 gem.length 10^30 gem[i] 10^30 operations.length 10^4operations[i].length 20 operations[i][0], operations[i][1] gem.length
【模拟】temp的那步很抽象必须单独设置一个中间变量。
int cmp(void *a,void *b){return *(int*)a-*(int*)b;
}int giveGem(int* gem, int gemSize, int** operations, int operationsSize, int* operationsColSize){int noperationsSize;for(int i0;in;i){int leftoperations[i][0],rightoperations[i][1];int tempgem[left]/2;gem[left]-temp;gem[right]temp;}qsort(gem,gemSize,sizeof(int),cmp);return gem[gemSize-1]-gem[0];
}198 打家劫舍(9.16)
你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。
提示
1 nums.length 1000 nums[i] 400
【动态规划】 d p [ 0 ] n u m s [ 0 ] dp[0]nums[0] dp[0]nums[0] d p [ 1 ] m a x ( n u m s [ 0 ] , n u m s [ 1 ] ) dp[1]max(nums[0],nums[1]) dp[1]max(nums[0],nums[1]) d p [ n ] m a x ( d p [ n − 1 ] , d p [ n − 2 ] n u m s [ i ] ) , 其中 n 1 dp[n]max(dp[n-1],dp[n-2]nums[i]) ,其中n1 dp[n]max(dp[n−1],dp[n−2]nums[i]),其中n1
其中Ⅲ式的含义如下 d p [ n − 1 ] 打劫过上一家不能打劫当前家 dp[n-1]打劫过上一家不能打劫当前家 dp[n−1]打劫过上一家不能打劫当前家 d p [ n − 2 ] n u m s [ i ] 打劫当前家不能打劫上一家 dp[n-2]nums[i]打劫当前家不能打劫上一家 dp[n−2]nums[i]打劫当前家不能打劫上一家
int rob(int* nums, int numsSize){//dynamic programmingif(numsSize0) return 0;else if(numsSize1) return nums[0];else if(numsSize2) return fmax(nums[0],nums[1]);int *dpmalloc(sizeof(int)*numsSize);dp[0]nums[0];dp[1]fmax(nums[0],nums[1]);for(int i2;inumsSize;i){dp[i]fmax(dp[i-2]nums[i],dp[i-1]);}return dp[numsSize-1];
}213 打家劫舍Ⅱ(9.17)
你是一个专业的小偷计划偷窃沿街的房屋每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 这意味着第一个房屋和最后一个房屋是紧挨着的。同时相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组计算你 在不触动警报装置的情况下 今晚能够偷窃到的最高金额。
提示
1 nums.length 1000 nums[i] 1000
【动态规划】参考灵神的思路
int originrob(int *nums,int start,int end){int f00,f10;for(int istart;iend;i){int newffmax(f1,f0nums[i]);f0f1;f1newf;}return f1;
}int rob(int* nums, int numsSize){//环形 考虑是否偷取num[0]//偷dp为num[2],num[n-2]//不偷dp为num[1],num[n-1]int nnumsSize;return fmax(nums[0]originrob(nums,2,n-1),originrob(nums,1,n));
}337 打家劫舍Ⅲ(9.18)
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口我们称之为 root 。
除了 root 之外每栋房子有且只有一个“父“房子与之相连。一番侦察之后聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 房屋将自动报警。
给定二叉树的 root 。返回 *在不触动警报的情况下 小偷能够盗取的最高金额* 。
提示
树的节点数在 [1, 104] 范围内0 Node.val 104
【哈希表 动态规划】
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*///f代表选择当前节点g代表不选择
//当前节点选择子节点不能选f(cur)g(left)g(right)
//当前节点不选择子节点可选可不选g(cur)max{f(left),g(left)} max{f(right),g(right)}class Solution {
public:unordered_mapTreeNode*,int f,g;void dfs(TreeNode* node){if(nodeNULL) return;dfs(node-left);dfs(node-right);f[node]node-valg[node-left]g[node-right];g[node]max(f[node-left],g[node-left])max(f[node-right],g[node-right]);}int rob(TreeNode* root) {dfs(root);return max(f[root],g[root]);}
};
