带网站的图片素材,广州邮局网站,dede网站被黑,高端网站设计企业网站建设目录
1401. 圆和矩形是否有重叠
1402. 做菜顺序
1406. 石子游戏 III
1414. 和为 K 的最少斐波那契数字数目
1419. 数青蛙
1420. 生成数组
1424. 对角线遍历 II
1426. 数元素
1427. 字符串的左右移
1428. 至少有一个 1 的最左端列
1430. 判断给定的序列是否是二叉树从…目录
1401. 圆和矩形是否有重叠
1402. 做菜顺序
1406. 石子游戏 III
1414. 和为 K 的最少斐波那契数字数目
1419. 数青蛙
1420. 生成数组
1424. 对角线遍历 II
1426. 数元素
1427. 字符串的左右移
1428. 至少有一个 1 的最左端列
1430. 判断给定的序列是否是二叉树从根到叶的路径
1441. 用栈操作构建数组
1442. 形成两个异或相等数组的三元组数目
1443. 收集树上所有苹果的最少时间
1447. 最简分数
1448. 统计二叉树中好节点的数目
1450. 在既定时间做作业的学生人数
1451. 重新排列句子中的单词
1452. 收藏清单
1455. 检查单词是否为句中其他单词的前缀
1456. 定长子串中元音的最大数目
1457. 二叉树中的伪回文路径
1458. 两个子序列的最大点积
1461. 检查一个字符串是否包含所有长度为 K 的二进制子串
1462. 课程表 IV
1464. 数组中两元素的最大乘积
1465. 切割后面积最大的蛋糕
1466. 重新规划路线
1467. 两个盒子中球的颜色数相同的概率
1469. 寻找所有的独生节点
1470. 重新排列数组
1471. 数组中的 k 个最强值
1472. 设计浏览器历史记录
1473. 给房子涂色 III
1474. 删除链表 M 个节点之后的 N 个节点
1480. 一维数组的动态和
1481. 不同整数的最少数目
1482. 制作 m 束花所需的最少天数
1483. 树节点的第 K 个祖先
1485. 克隆含随机指针的二叉树
1486. 数组异或操作
1487. 保证文件名唯一
1488. 避免洪水泛滥
1489. 找到最小生成树里的关键边和伪关键边
1490. 克隆 N 叉树
1492. n 的第 k 个因子
1494. 并行课程 II
1496. 判断路径是否相交
1500. 设计文件分享系统 1401. 圆和矩形是否有重叠
计算几何
1402. 做菜顺序
贪心3其他排序问题
1406. 石子游戏 III
公开游戏
1414. 和为 K 的最少斐波那契数字数目
斐波那契数列
1419. 数青蛙
给你一个字符串 croakOfFrogs它表示不同青蛙发出的蛙鸣声字符串 croak 的组合。由于同一时间可以有多只青蛙呱呱作响所以 croakOfFrogs 中会混合多个 “croak” 。请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。
注意要想发出蛙鸣 croak青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母那么它就不会发出声音。
如果字符串 croakOfFrogs 不是由若干有效的 croak 字符混合而成请返回 -1 。 示例 1
输入croakOfFrogs croakcroak 输出1 解释一只青蛙 “呱呱” 两次 示例 2
输入croakOfFrogs crcoakroak 输出2 解释最少需要两只青蛙“呱呱” 声用黑体标注 第一只青蛙 crcoakroak 第二只青蛙 crcoakroak 示例 3
输入croakOfFrogs croakcrook 输出-1 解释给出的字符串不是 croak 的有效组合。 示例 4
输入croakOfFrogs croakcroa 输出-1
提示
1 croakOfFrogs.length 10^5 字符串中的字符只有 c, r, o, a 或者 k
class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {mapchar,intm;int ans0;for(int i0;icroakOfFrogs.length();i){m[croakOfFrogs[i]];if(m[c]m[r] || m[r]m[o] || m[o]m[a] || m[a]m[k])return -1;ansmax(ans,m[c]-m[k]);}if(m[c]m[r] || m[r]m[o] || m[o]m[a] || m[a]m[k])return -1;return ans;}
};
1420. 生成数组 高维DP
1424. 对角线遍历 II
给你一个列表 nums 里面每一个元素都是一个整数列表。请你依照下面各图的规则按顺序返回 nums 中对角线上的整数。
示例 1 输入nums [[1,2,3],[4,5,6],[7,8,9]] 输出[1,4,2,7,5,3,8,6,9] 示例 2 输入nums [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]] 输出[1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16] 示例 3
输入nums [[1,2,3],[4],[5,6,7],[8],[9,10,11]] 输出[1,4,2,5,3,8,6,9,7,10,11] 示例 4
输入nums [[1,2,3,4,5,6]] 输出[1,2,3,4,5,6]
提示
1 nums.length 10^5 1 nums[i].length 10^5 1 nums[i][j] 10^9 nums 中最多有 10^5 个数字。 超时代码
void f(vectorvectorintans, vectorintv)
{vectorinttmp;ans.insert(ans.begin(), tmp);for (int i 0; i v.size(); i){if (i ans.size())ans.push_back(tmp);ans[i].push_back(v[i]);}
}
class Solution {
public:vectorint findDiagonalOrder(vectorvectorint nums) {vectorvectorintans;for (int i nums.size() - 1; i 0; i--)f(ans, nums[i]);vectorintres;for (int i 0; i ans.size(); i){for (int j 0; j ans[i].size(); j)res.push_back(ans[i][j]);}return res;}
}; 其中最致命的问题是有大量的在vector前面插入元素的操作
看了同事的js代码之后我照着她的思路重写了代码
class Solution {
public:vectorint findDiagonalOrder(vectorvectorint nums) {mapint,vectorintans;vectorintemp;int k-1;for(int i0;inums.size();i)for(int j0;jnums[i].size();j){if(kij)ans[k]emp;ans[ij].push_back(nums[i][j]);}vectorintres;for (int i 0; i ans.size(); i){for (int j ans[i].size()-1;j0;j--)res.push_back(ans[i][j]);}return res;}
};
1426. 数元素
给你一个整数数组 arr 对于元素 x 只有当 x 1 也在数组 arr 里时才能记为 1 个数。
如果数组 arr 里有重复的数每个重复的数单独计算。 示例 1
输入arr [1,2,3] 输出2 解释1 和 2 被计算次数因为 2 和 3 在数组 arr 里。 示例 2
输入arr [1,1,3,3,5,5,7,7] 输出0 解释所有的数都不算, 因为数组里没有 2、4、6、8。
提示
1 arr.length 1000 0 arr[i] 1000
class Solution {
public:int countElements(vectorint arr) {mapint, intm;for (auto ai : arr)m[ai];int ans 0;for (auto ai : arr)ans m[ai 1] ? 1 : 0;return ans;}
};
1427. 字符串的左右移
给定一个包含小写英文字母的字符串 s 以及一个矩阵 shift其中 shift[i] [direction, amount]
direction 可以为 0 表示左移或 1 表示右移。 amount 表示 s 左右移的位数。 左移 1 位表示移除 s 的第一个字符并将该字符插入到 s 的结尾。 类似地右移 1 位表示移除 s 的最后一个字符并将该字符插入到 s 的开头。 对这个字符串进行所有操作后返回最终结果。 示例 1
输入s abc, shift [[0,1],[1,2]] 输出cab 解释 [0,1] 表示左移 1 位。 abc - bca [1,2] 表示右移 2 位。 bca - cab 示例 2
输入s abcdefg, shift [[1,1],[1,1],[0,2],[1,3]] 输出efgabcd 解释 [1,1] 表示右移 1 位。 abcdefg - gabcdef [1,1] 表示右移 1 位。 gabcdef - fgabcde [0,2] 表示左移 2 位。 fgabcde - abcdefg [1,3] 表示右移 3 位。 abcdefg - efgabcd
提示
1 s.length 100 s 只包含小写英文字母 1 shift.length 100 shift[i].length 2 0 shift[i][0] 1 0 shift[i][1] 100
class Solution {
public:string stringShift(string s, vectorvectorint shift) {int n 0, len s.length();for (auto si : shift)n (si[0] * 2 - 1) * si[1];n (n % len len) % len;return s.substr(len - n, n) s.substr(0, len - n);}
};1428. 至少有一个 1 的最左端列
这是一个交互题
我们称只包含元素 0 或 1 的矩阵为二进制矩阵。矩阵中每个单独的行都按非递减顺序排序。
给定一个这样的二进制矩阵返回至少包含一个 1 的最左端列的索引从 0 开始。如果这样的列不存在返回 -1。
您不能直接访问该二进制矩阵。你只可以通过 BinaryMatrix 接口来访问。
BinaryMatrix.get(row, col) 返回位于索引 (row, col) 从 0 开始的元素。 BinaryMatrix.dimensions() 返回含有 2 个元素的列表 [rows, cols]表示这是一个 rows * cols的矩阵。 如果提交的答案调用 BinaryMatrix.get 超过 1000 次则该答案会被判定为错误答案。提交任何试图规避判定机制的答案将会被取消资格。
下列示例中 mat 为给定的二进制矩阵。您不能直接访问该矩阵。 示例 1: 输入: mat [[0,0],[1,1]] 输出: 0 示例 2: 输入: mat [[0,0],[0,1]] 输出: 1 示例 3: 输入: mat [[0,0],[0,0]] 输出: -1 示例 4: 输入: mat [[0,0,0,1],[0,0,1,1],[0,1,1,1]] 输出: 1
提示:
rows mat.length cols mat[i].length 1 rows, cols 100 mat[i][j] 只会是 0 或 1。 mat[i] 已按非递减顺序排序。
class Solution {
public:int leftMostColumnWithOne(BinaryMatrix bm) {int a 0, row -1, col bm.dimensions()[1] - 1;while (true) {if (a 0)row;else col--;if (row bm.dimensions()[0] || col 0)break;a bm.get(row, col);}return col bm.dimensions()[1] - 1 ? col 1 : -1;}
};
1430. 判断给定的序列是否是二叉树从根到叶的路径
二叉树
1441. 用栈操作构建数组
给你一个目标数组 target 和一个整数 n。每次迭代需要从 list {1,2,3..., n} 中依序读取一个数字。
请使用下述操作来构建目标数组 target
Push从 list 中读取一个新元素 并将其推入数组中。 Pop删除数组中的最后一个元素。 如果目标数组构建完成就停止读取更多元素。 题目数据保证目标数组严格递增并且只包含 1 到 n 之间的数字。
请返回构建目标数组所用的操作序列。
题目数据保证答案是唯一的。 示例 1
输入target [1,3], n 3 输出[Push,Push,Pop,Push] 解释 读取 1 并自动推入数组 - [1] 读取 2 并自动推入数组然后删除它 - [1] 读取 3 并自动推入数组 - [1,3] 示例 2
输入target [1,2,3], n 3 输出[Push,Push,Push] 示例 3
输入target [1,2], n 4 输出[Push,Push] 解释只需要读取前 2 个数字就可以停止。 示例 4
输入target [2,3,4], n 4 输出[Push,Pop,Push,Push,Push]
提示
1 target.length 100 1 target[i] 100 1 n 100 target 是严格递增的
class Solution {
public:vectorstring buildArray(vectorint target, int n) {vectorstringans;int key0;for(auto ittarget.begin();it!target.end();it){int k*it;key;while(keyk){key;ans.insert(ans.end(),Push);ans.insert(ans.end(),Pop);}ans.insert(ans.end(),Push);}return ans;}
};
1442. 形成两个异或相等数组的三元组数目
给你一个整数数组 arr 。
现需要从数组中取三个下标 i、j 和 k 其中 (0 i j k arr.length) 。
a 和 b 定义如下
a arr[i] ^ arr[i 1] ^ ... ^ arr[j - 1] b arr[j] ^ arr[j 1] ^ ... ^ arr[k] 注意^ 表示 按位异或 操作。
请返回能够令 a b 成立的三元组 (i, j , k) 的数目。 示例 1
输入arr [2,3,1,6,7] 输出4 解释满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4) 示例 2
输入arr [1,1,1,1,1] 输出10 示例 3
输入arr [2,3] 输出0 示例 4
输入arr [1,3,5,7,9] 输出3 示例 5
输入arr [7,11,12,9,5,2,7,17,22] 输出8
提示
1 arr.length 300 1 arr[i] 10^8
class Solution {
public:int countTriplets(vectorint arr) {int lenarr.size();int ans0;for(int i1;ilen;i){arr[i]^arr[i-1];if(arr[i]0)ansi;}for(int i0;ilen;i)for(int ki1;klen;k)if(arr[i]arr[k])ansk-i-1;return ans;}
};
1443. 收集树上所有苹果的最少时间
给你一棵有 n 个节点的无向树节点编号为 0 到 n-1 它们中有一些节点有苹果。通过树上的一条边需要花费 1 秒钟。你从 节点 0 出发请你返回最少需要多少秒可以收集到所有苹果并回到节点 0 。
无向树的边由 edges 给出其中 edges[i] [fromi, toi] 表示有一条边连接 from 和 toi 。除此以外还有一个布尔数组 hasApple 其中 hasApple[i] true 代表节点 i 有一个苹果否则节点 i 没有苹果。
示例 1 输入n 7, edges [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple [false,false,true,false,true,true,false] 输出8 解释上图展示了给定的树其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。 示例 2 输入n 7, edges [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple [false,false,true,false,false,true,false] 输出6 解释上图展示了给定的树其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。 示例 3
输入n 7, edges [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple [false,false,false,false,false,false,false] 输出0
提示
1 n 10^5 edges.length n-1 edges[i].length 2 0 fromi, toi n-1 fromi toi hasApple.length n
class Solution {
public:int minTime(int n, vectorvectorint edges, vectorbool hasApple) {int *fanew int[n];int *ansnew int[n];for(int i0;in;i)ans[i]0;ans[0]1;for(auto itedges.begin();it!edges.end();it)fa[(*it)[1]](*it)[0];fa[0]0;for(int i0;in;i)if(hasApple[i]){int ji;while(ans[j]0){ans[j]1,jfa[j];}}int res-1;for(int i0;in;i)if(ans[i])res;return res*2;}
};
1447. 最简分数
欧几里得
1448. 统计二叉树中好节点的数目
dfs
1450. 在既定时间做作业的学生人数
给你两个整数数组 startTime开始时间和 endTime结束时间并指定一个整数 queryTime 作为查询时间。
已知第 i 名学生在 startTime[i] 时开始写作业并于 endTime[i] 时完成作业。
请返回在查询时间 queryTime 时正在做作业的学生人数。形式上返回能够使 queryTime 处于区间 [startTime[i], endTime[i]]含的学生人数。 示例 1
输入startTime [1,2,3], endTime [3,2,7], queryTime 4 输出1 解释一共有 3 名学生。 第一名学生在时间 1 开始写作业并于时间 3 完成作业在时间 4 没有处于做作业的状态。 第二名学生在时间 2 开始写作业并于时间 2 完成作业在时间 4 没有处于做作业的状态。 第二名学生在时间 3 开始写作业预计于时间 7 完成作业这是是唯一一名在时间 4 时正在做作业的学生。 示例 2
输入startTime [4], endTime [4], queryTime 4 输出1 解释在查询时间只有一名学生在做作业。 示例 3
输入startTime [4], endTime [4], queryTime 5 输出0 示例 4
输入startTime [1,1,1,1], endTime [1,3,2,4], queryTime 7 输出0 示例 5
输入startTime [9,8,7,6,5,4,3,2,1], endTime [10,10,10,10,10,10,10,10,10], queryTime 5 输出5
提示
startTime.length endTime.length 1 startTime.length 100 1 startTime[i] endTime[i] 1000 1 queryTime 1000
class Solution {
public:int busyStudent(vectorint startTime, vectorint endTime, int queryTime) {int ans0;for(int i0;istartTime.size();i)if(startTime[i]queryTime queryTimeendTime[i])ans;return ans;}
};
1451. 重新排列句子中的单词
拓展排序
1452. 收藏清单
给你一个数组 favoriteCompanies 其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单下标从 0 开始。
请找出不是其他任何人收藏的公司清单的子集的收藏清单并返回该清单下标。下标需要按升序排列。 示例 1
输入favoriteCompanies [[leetcode,google,facebook],[google,microsoft],[google,facebook],[google],[amazon]] 输出[0,1,4] 解释 favoriteCompanies[2][google,facebook] 是 favoriteCompanies[0][leetcode,google,facebook] 的子集。 favoriteCompanies[3][google] 是 favoriteCompanies[0][leetcode,google,facebook] 和 favoriteCompanies[1][google,microsoft] 的子集。 其余的收藏清单均不是其他任何人收藏的公司清单的子集因此答案为 [0,1,4] 。 示例 2
输入favoriteCompanies [[leetcode,google,facebook],[leetcode,amazon],[facebook,google]] 输出[0,1] 解释favoriteCompanies[2][facebook,google] 是 favoriteCompanies[0][leetcode,google,facebook] 的子集因此答案为 [0,1] 。 示例 3
输入favoriteCompanies [[leetcode],[google],[facebook],[amazon]] 输出[0,1,2,3]
提示
1 favoriteCompanies.length 100 1 favoriteCompanies[i].length 500 1 favoriteCompanies[i][j].length 20 favoriteCompanies[i] 中的所有字符串 各不相同 。 用户收藏的公司清单也 各不相同 也就是说即便我们按字母顺序排序每个清单 favoriteCompanies[i] ! favoriteCompanies[j] 仍然成立。 所有字符串仅包含小写英文字母。 代码一
mapstring,intm[105];
class Solution {
public:vectorint peopleIndexes(vectorvectorstring favoriteCompanies) {vectorintans;for(int i0;ifavoriteCompanies.size();i){m[i].clear();for(int j0;jfavoriteCompanies[i].size();j)m[i][favoriteCompanies[i][j]]1;}for(int i0;ifavoriteCompanies.size();i){bool flagtrue;for(int j0;flag (jfavoriteCompanies.size());j){if(ji)continue;if(favoriteCompanies[i].size()favoriteCompanies[j].size())continue;bool flag2true;for(int ii0;flag2 (iifavoriteCompanies[i].size());ii)if(!m[j][favoriteCompanies[i][ii]])flag2false;if(flag2)flagfalse;}if(flag)ans.insert(ans.end(),i);}return ans;}
};
这是我比赛时候的代码已经做了一部分优化了比较列表长短但是还是超时超时的用例就是极限用例。
然后我考虑到把100个列表按照长度排序每个列表就只需要看比自己长的列表有没有覆盖自己的把没有被覆盖的列表的ID记下来这样每个列表就只需要看比自己长而且没有被任何列表覆盖的列表我花了20分钟去改最后没来得及完成。
代码二
struct node
{int num;int id;
};
bool cmp(node x,node y)
{return x.numy.num;
}
mapstring,intm[105];
class Solution {
public:vectorint peopleIndexes(vectorvectorstring favoriteCompanies) {vectornodevn;vectorintans;for(int i0;ifavoriteCompanies.size();i){m[i].clear();for(int j0;jfavoriteCompanies[i].size();j)m[i][favoriteCompanies[i][j]]1;node nn;nn.numfavoriteCompanies[i].size(),nn.idi;vn.insert(vn.end(),nn);}sort(vn.begin(),vn.end(),cmp);for(int i0;ivn.size();i){bool flagtrue;for(int j0;flag (ji);j){bool flag2true;for(int ii0;flag2 (iifavoriteCompanies[vn[i].num].size());ii)if(!m[vn[j].num][favoriteCompanies[vn[i].num][ii]])flag2false;if(flag2)flagfalse;}if(flag)ans.insert(ans.end(),vn[i].id);}sort(ans.begin(),ans.end());return ans;}
};
事后我的2个同事给了我思路一个是把map改为unordered_map
只把代码一的第1行改掉就AC了。
另外一个思路是不用map把每个列表的字符串排序然后用双指针的方法判断一个列表是不是覆盖另外一个列表他这个思路也AC了。
1455. 检查单词是否为句中其他单词的前缀
给你一个字符串 sentence 作为句子并指定检索词为 searchWord 其中句子由若干用 单个空格 分隔的单词组成。
请你检查检索词 searchWord 是否为句子 sentence 中任意单词的前缀。
如果 searchWord 是某一个单词的前缀则返回句子 sentence 中该单词所对应的下标下标从 1 开始。 如果 searchWord 是多个单词的前缀则返回匹配的第一个单词的下标最小下标。 如果 searchWord 不是任何单词的前缀则返回 -1 。 字符串 S 的 「前缀」是 S 的任何前导连续子字符串。 示例 1
输入sentence i love eating burger, searchWord burg 输出4 解释burg 是 burger 的前缀而 burger 是句子中第 4 个单词。 示例 2
输入sentence this problem is an easy problem, searchWord pro 输出2 解释pro 是 problem 的前缀而 problem 是句子中第 2 个也是第 6 个单词但是应该返回最小下标 2 。 示例 3
输入sentence i am tired, searchWord you 输出-1 解释you 不是句子中任何单词的前缀。 示例 4
输入sentence i use triple pillow, searchWord pill 输出4 示例 5
输入sentence hello from the other side, searchWord they 输出-1
提示
1 sentence.length 100 1 searchWord.length 10 sentence 由小写英文字母和空格组成。 searchWord 由小写英文字母组成。 前缀就是紧密附着于词根的语素中间不能插入其它成分并且它的位置是固定的——-位于词根之前。引用自 前缀_百度百科
class Solution {
public:int isPrefixOfWord(string sentence, string searchWord) {int key1;for(int i0,j0;isentence.length();){if(sentence[i] )i,key,j0;else if(sentence[i]searchWord[j]){i,j;if(jsearchWord.length())return key;}else{j0;while(isentence.length() sentence[i]! )i;i,key;}}return -1;}
};
1456. 定长子串中元音的最大数目
给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为a, e, i, o, u。 示例 1
输入s abciiidef, k 3 输出3 解释子字符串 iii 包含 3 个元音字母。 示例 2
输入s aeiou, k 2 输出2 解释任意长度为 2 的子字符串都包含 2 个元音字母。 示例 3
输入s leetcode, k 3 输出2 解释lee、eet 和 ode 都包含 2 个元音字母。 示例 4
输入s rhythms, k 4 输出0 解释字符串 s 中不含任何元音字母。 示例 5
输入s tryhard, k 4 输出1
提示
1 s.length 10^5 s 由小写英文字母组成 1 k s.length
int f(char c)
{if(ca||ce||ci||co||cu)return 1;return 0;
}class Solution {
public:int maxVowels(string s, int k) {int r0;for(int i0;ik;i)rf(s[i]);int ansr;for(int ik;is.length();i){rf(s[i])-f(s[i-k]);ansmax(ans,r);}return ans;}
};
1457. 二叉树中的伪回文路径
树形DP
1458. 两个子序列的最大点积 数列DP
1461. 检查一个字符串是否包含所有长度为 K 的二进制子串
给你一个二进制字符串 s 和一个整数 k 。
如果所有长度为 k 的二进制字符串都是 s 的子串请返回 True 否则请返回 False 。 示例 1
输入s 00110110, k 2 输出true 解释长度为 2 的二进制串包括 000110 和 11。它们分别是 s 中下标为 0132 开始的长度为 2 的子串。 示例 2
输入s 00110, k 2 输出true 示例 3
输入s 0110, k 1 输出true 解释长度为 1 的二进制串包括 0 和 1显然它们都是 s 的子串。 示例 4
输入s 0110, k 2 输出false 解释长度为 2 的二进制串 00 没有出现在 s 中。 示例 5
输入s 0000000001011100, k 4 输出false
提示
1 s.length 5 * 10^5 s 中只含 0 和 1 。 1 k 20
class Solution {
public:bool hasAllCodes(string s, int k) {unordered_setstringse;for(int i0;iks.length();i){se.insert(s.substr(i,k));if(se.size()s.length()-i-k(1k))return false;if(se.size()(1k))return true;}return false;}
};
1462. 课程表 IV
拓扑排序
1463. 摘樱桃 II
高维DP
1464. 数组中两元素的最大乘积
给你一个整数数组 nums请你选择数组的两个不同下标 i 和 j使 (nums[i]-1)*(nums[j]-1) 取得最大值。
请你计算并返回该式的最大值。 示例 1
输入nums [3,4,5,2] 输出12 解释如果选择下标 i1 和 j2下标从 0 开始则可以获得最大值(nums[1]-1)*(nums[2]-1) (4-1)*(5-1) 3*4 12 。 示例 2
输入nums [1,5,4,5] 输出16 解释选择下标 i1 和 j3下标从 0 开始则可以获得最大值 (5-1)*(5-1) 16 。 示例 3
输入nums [3,7] 输出12
提示
2 nums.length 500 1 nums[i] 10^3
class Solution {
public:int maxProduct(vectorint nums) {int a0,b0,c;for(int i0;inums.size();i){cnums[i]-1;if(bc)b^c^b^c;if(ac)a^c^a^c;}return a*b;}
};
1465. 切割后面积最大的蛋糕
矩形蛋糕的高度为 h 且宽度为 w给你两个整数数组 horizontalCuts 和 verticalCuts其中 horizontalCuts[i] 是从矩形蛋糕顶部到第 i 个水平切口的距离类似地 verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离。
请你按数组 horizontalCuts 和 verticalCuts 中提供的水平和竖直位置切割后请你找出 面积最大 的那份蛋糕并返回其 面积 。由于答案可能是一个很大的数字因此需要将结果对 10^9 7 取余后返回。 示例 1
输入h 5, w 4, horizontalCuts [1,2,4], verticalCuts [1,3] 输出4 解释上图所示的矩阵蛋糕中红色线表示水平和竖直方向上的切口。切割蛋糕后绿色的那份蛋糕面积最大。 示例 2
输入h 5, w 4, horizontalCuts [3,1], verticalCuts [1] 输出6 解释上图所示的矩阵蛋糕中红色线表示水平和竖直方向上的切口。切割蛋糕后绿色和黄色的两份蛋糕面积最大。 示例 3
输入h 5, w 4, horizontalCuts [3], verticalCuts [3] 输出9
提示
2 h, w 10^9 1 horizontalCuts.length min(h, 10^5) 1 verticalCuts.length min(w, 10^5) 1 horizontalCuts[i] h 1 verticalCuts[i] w 题目数据保证 horizontalCuts 中的所有元素各不相同 题目数据保证 verticalCuts 中的所有元素各不相同
class Solution {
public:int f(int len, vectorintv){sort(v.begin(),v.end());int ansmax(v[0],len-v[v.size()-1]);for(int i1;iv.size();i)ansmax(ans,v[i]-v[i-1]);return ans;}int maxArea(int h, int w, vectorint horizontalCuts, vectorint verticalCuts) {long long af(h,horizontalCuts),bf(w,verticalCuts);return a*b%1000000007;}
};
1466. 重新规划路线
BFS
1467. 两个盒子中球的颜色数相同的概率
桌面上有 2n 个颜色不完全相同的球球上的颜色共有 k 种。给你一个大小为 k 的整数数组 balls 其中 balls[i] 是颜色为 i 的球的数量。
所有的球都已经 随机打乱顺序 前 n 个球放入第一个盒子后 n 个球放入另一个盒子请认真阅读示例 2 的解释部分。
注意这两个盒子是不同的。例如两个球颜色分别为 a 和 b盒子分别为 [] 和 ()那么 [a] (b) 和 [b] (a) 这两种分配方式是不同的请认真阅读示例 1 的解释部分。
请计算「两个盒子中球的颜色数相同」的情况的概率。 示例 1
输入balls [1,1] 输出1.00000 解释球平均分配的方式只有两种 - 颜色为 1 的球放入第一个盒子颜色为 2 的球放入第二个盒子 - 颜色为 2 的球放入第一个盒子颜色为 1 的球放入第二个盒子 这两种分配两个盒子中球的颜色数都相同。所以概率为 2/2 1 。 示例 2
输入balls [2,1,1] 输出0.66667 解释球的列表为 [1, 1, 2, 3] 随机打乱得到 12 种等概率的不同打乱方案每种方案概率为 1/12 [1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1] 然后我们将前两个球放入第一个盒子后两个球放入第二个盒子。 这 12 种可能的随机打乱方式中的 8 种满足「两个盒子中球的颜色数相同」。 概率 8/12 0.66667 示例 3
输入balls [1,2,1,2] 输出0.60000 解释球的列表为 [1, 2, 2, 3, 4, 4]。要想显示所有 180 种随机打乱方案是很难的但只检查「两个盒子中球的颜色数相同」的 108 种情况是比较容易的。 概率 108 / 180 0.6 。 示例 4
输入balls [3,2,1] 输出0.30000 解释球的列表为 [1, 1, 1, 2, 2, 3]。要想显示所有 60 种随机打乱方案是很难的但只检查「两个盒子中球的颜色数相同」的 18 种情况是比较容易的。 概率 18 / 60 0.3 。 示例 5
输入balls [6,6,6,6,6,6] 输出0.90327
提示
1 balls.length 8 1 balls[i] 6 sum(balls) 是偶数 答案与真实值误差在 10^-5 以内则被视为正确答案 思路
k种颜色的球从k-1到0依次放球balls数组存了每种颜色的球的数目。
当放第i个球的时候i从0到k-1枚举在左边放球的数量jj从
左边还有nl个空位右边还有nr个空位那么一共有c[nlnr][balls[k]]这么多种情况其中c数组是组合数
这些情况中左边放j个右边放balls[k]-j个的情况数是c[nl][j] * c[nr][balls[k]-j]
所以这么放的概率是c[nl][j] * c[nr][balls[k]-j] / c[nlnr][balls[k]] 依次枚举每种颜色的球在左边放的数目每一种颜色的球的放置都是独立的不断更新两边的色差最后色差为0的那些情况的概率加起来就是最后答案。
代码
double eps0.00000001;
class Solution {
public:double c[51][51];double ans[25][25][9][20];vectorintb;double getc(int n,int i){if(n0||i0)return c[n][i]1;if(c[n][i]eps)return c[n][i];return c[n][i]getc(n-1,i-1)*n/i;}double dp(int nl,int nr,int k,int dif){if(k0)return (dif10)?1:0;if(ans[nl][nr][k][dif]eps)return ans[nl][nr][k][dif];int nkb[k];double res0;for(int i0;ink;i){if(nli || nrnk-i)continue;double pc[nl][i]*c[nr][nk-i]/c[nlnr][nk];int tmpdif(i?1:0)-((ink)?0:1);resp*dp(nl-i,nr-nki,k-1,dif-tmpdif);}return ans[nl][nr][k][dif]res;}double getProbability(vectorint balls) {bballs; for(int i0;i50;i)for(int j0;j50;j)getc(i,j);int n0;for(int i0;ib.size();i)nb[i];return dp(n/2,n/2,b.size()-1,10);}
};
1469. 寻找所有的独生节点
二叉树DFS
1470. 重新排列数组
给你一个数组 nums 数组中有 2n 个元素按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。
请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列返回重排后的数组。 示例 1
输入nums [2,5,1,3,4,7], n 3 输出[2,3,5,4,1,7] 解释由于 x12, x25, x31, y13, y24, y37 所以答案为 [2,3,5,4,1,7] 示例 2
输入nums [1,2,3,4,4,3,2,1], n 4 输出[1,4,2,3,3,2,4,1] 示例 3
输入nums [1,1,2,2], n 2 输出[1,2,1,2]
提示
1 n 500 nums.length 2n 1 nums[i] 10^3
class Solution {
public:vectorint shuffle(vectorint nums, int n) {vectorintans;for(int i0;in;i){ans.push_back(nums[i]);ans.push_back(nums[ni]);}return ans;}
};
1471. 数组中的 k 个最强值
给你一个整数数组 arr 和一个整数 k 。
设 m 为数组的中位数只要满足下述两个前提之一就可以判定 arr[i] 的值比 arr[j] 的值更强 |arr[i] - m| |arr[j] - m| |arr[i] - m| |arr[j] - m|且 arr[i] arr[j] 请返回由数组中最强的 k 个值组成的列表。答案可以以 任意顺序 返回。
中位数 是一个有序整数列表中处于中间位置的值。形式上如果列表的长度为 n 那么中位数就是该有序列表下标从 0 开始中位于 ((n - 1) / 2) 的元素。
例如 arr [6, -3, 7, 2, 11]n 5数组排序后得到 arr [-3, 2, 6, 7, 11] 数组的中间位置为 m ((5 - 1) / 2) 2 中位数 arr[m] 的值为 6 。 例如 arr [-7, 22, 17, 3]n 4数组排序后得到 arr [-7, 3, 17, 22] 数组的中间位置为 m ((4 - 1) / 2) 1 中位数 arr[m] 的值为 3 。
示例 1
输入arr [1,2,3,4,5], k 2 输出[5,1] 解释中位数为 3按从强到弱顺序排序后数组变为 [5,1,4,2,3]。最强的两个元素是 [5, 1]。[1, 5] 也是正确答案。 注意尽管 |5 - 3| |1 - 3| 但是 5 比 1 更强因为 5 1 。 示例 2
输入arr [1,1,3,5,5], k 2 输出[5,5] 解释中位数为 3, 按从强到弱顺序排序后数组变为 [5,5,1,1,3]。最强的两个元素是 [5, 5]。 示例 3
输入arr [6,7,11,7,6,8], k 5 输出[11,8,6,6,7] 解释中位数为 7, 按从强到弱顺序排序后数组变为 [11,8,6,6,7,7]。 [11,8,6,6,7] 的任何排列都是正确答案。 示例 4
输入arr [6,-3,7,2,11], k 3 输出[-3,11,2] 示例 5
输入arr [-7,22,17,3], k 2 输出[22,17]
提示
1 arr.length 10^5 -10^5 arr[i] 10^5 1 k arr.length
class Solution {
public:vectorint getStrongest(vectorint arr, int k) {sort(arr.begin(),arr.end());int midarr[(arr.size()-1)/2];int low0,higharr.size()-1;vectorintans;while(k--){if(abs(arr[low]-mid)abs(arr[high]-mid) || abs(arr[low]-mid)abs(arr[high]-mid) arr[low]arr[high])ans.push_back(arr[low]);else ans.push_back(arr[high--]);}return ans;}
};
1472. 设计浏览器历史记录
你有一个只支持单个标签页的 浏览器 最开始你浏览的网页是 homepage 你可以访问其他的网站 url 也可以在浏览历史中后退 steps 步或前进 steps 步。
请你实现 BrowserHistory 类
BrowserHistory(string homepage) 用 homepage 初始化浏览器类。 void visit(string url) 从当前页跳转访问 url 对应的页面 。执行此操作会把浏览历史前进的记录全部删除。 string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps x 那么你只后退 x 步。请返回后退 至多 steps 步以后的 url 。 string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps x 那么你只前进 x 步。请返回前进 至多 steps步以后的 url 。
示例
输入 [BrowserHistory,visit,visit,visit,back,back,forward,visit,forward,back,back] [[leetcode.com],[google.com],[facebook.com],[youtube.com],[1],[1],[1],[linkedin.com],[2],[2],[7]] 输出 [null,null,null,null,facebook.com,google.com,facebook.com,null,linkedin.com,google.com,leetcode.com]
解释 BrowserHistory browserHistory new BrowserHistory(leetcode.com); browserHistory.visit(google.com); // 你原本在浏览 leetcode.com 。访问 google.com browserHistory.visit(facebook.com); // 你原本在浏览 google.com 。访问 facebook.com browserHistory.visit(youtube.com); // 你原本在浏览 facebook.com 。访问 youtube.com browserHistory.back(1); // 你原本在浏览 youtube.com 后退到 facebook.com 并返回 facebook.com browserHistory.back(1); // 你原本在浏览 facebook.com 后退到 google.com 并返回 google.com browserHistory.forward(1); // 你原本在浏览 google.com 前进到 facebook.com 并返回 facebook.com browserHistory.visit(linkedin.com); // 你原本在浏览 facebook.com 。 访问 linkedin.com browserHistory.forward(2); // 你原本在浏览 linkedin.com 你无法前进任何步数。 browserHistory.back(2); // 你原本在浏览 linkedin.com 后退两步依次先到 facebook.com 然后到 google.com 并返回 google.com browserHistory.back(7); // 你原本在浏览 google.com 你只能后退一步到 leetcode.com 并返回 leetcode.com
提示
1 homepage.length 20 1 url.length 20 1 steps 100 homepage 和 url 都只包含 . 或者小写英文字母。 最多调用 5000 次 visit back 和 forward 函数。
class BrowserHistory {
public:vectorstringv;int k, len;BrowserHistory(string homepage) {v.push_back(homepage), k 0, len 1;}void visit(string url) {Finsert(v, k, url);len k 1;}string back(int steps) {return v[k - min(steps, k)];}string forward(int steps) {return v[k min(steps, len - k - 1)];}
};
1473. 给房子涂色 III 高维DP
1474. 删除链表 M 个节点之后的 N 个节点
单链表
1480. 一维数组的动态和
给你一个数组 nums 。数组「动态和」的计算公式为runningSum[i] sum(nums[0]…nums[i]) 。
请返回 nums 的动态和。 示例 1
输入nums [1,2,3,4] 输出[1,3,6,10] 解释动态和计算过程为 [1, 12, 123, 1234] 。 示例 2
输入nums [1,1,1,1,1] 输出[1,2,3,4,5] 解释动态和计算过程为 [1, 11, 111, 1111, 11111] 。 示例 3
输入nums [3,1,2,10,1] 输出[3,4,6,16,17]
提示
1 nums.length 1000 -10^6 nums[i] 10^6
class Solution {
public:vectorint runningSum(vectorint nums) {for(int i1;inums.size();i)nums[i]nums[i-1];return nums;}
};
1481. 不同整数的最少数目
给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素请找出移除后数组中不同整数的最少数目。 示例 1
输入arr [5,5,4], k 1 输出1 解释移除 1 个 4 数组中只剩下 5 一种整数。 示例 2
输入arr [4,3,1,1,3,3,2], k 3 输出2 解释先移除 4、2 然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个最后剩下 1 和 3 两种整数。
提示
1 arr.length 10^5 1 arr[i] 10^9 0 k arr.length 思路
先计数再排序再贪心就可以了。
class Solution {
public:int findLeastNumOfUniqueInts(vectorint arr, int k) {unordered_mapint,intm;for(int i0;iarr.size();i)m[arr[i]];vectorintans;for(auto im.begin();i!m.end();i)ans.push_back(i-second);sort(ans.begin(),ans.end());int i;for(i0;ians.size();i){if(kans[i])k-ans[i];else if(kans[i])return ans.size()-i-1;else return ans.size()-i;}return 0;}
};
1482. 制作 m 束花所需的最少天数 二分、三分 1483. 树节点的第 K 个祖先
给你一棵树树上有 n 个节点按从 0 到 n-1 编号。树以父节点数组的形式给出其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。
请你设计并实现 getKthAncestor(int node, int k) 函数函数返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点返回 -1 。
树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。 示例 输入 [TreeAncestor,getKthAncestor,getKthAncestor,getKthAncestor] [[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]
输出 [null,1,0,-1]
解释 TreeAncestor treeAncestor new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);
treeAncestor.getKthAncestor(3, 1); // 返回 1 它是 3 的父节点 treeAncestor.getKthAncestor(5, 2); // 返回 0 它是 5 的祖父节点 treeAncestor.getKthAncestor(6, 3); // 返回 -1 因为不存在满足要求的祖先节点
提示
1 k n 5*10^4 parent[0] -1 表示编号为 0 的节点是根节点。 对于所有的 0 i n 0 parent[i] n 总成立 0 node n 至多查询 5*10^4 次 这个题有极限用例5万个结点单链树深度为5万查询次数5万每次查询的k也是4-5万。
C暴力是过不了的但是js暴力能过。 分析
如果不使用任何数据结构和算法那么对于单次查询来说5万次计算是必不可少的
而对于多次查询来说既然暴力不能过那就只有两种情况
1通过数据结构采用信息转换的方式降低单次查询时间
PS哈希字典树状态压缩等都属于我理解的信息转换而这题的LCA解法BFSDFS二分就是属于这一种
2通过算法整改解空间去掉多次查询之间的重复计算
PS本题的倍增法本质就是动态规划但是可能动态规划的特征没那么明显 思路一
用f(node, k)表示答案在我们求出f(100,50)x之后如果再求f(100,51)直接用f(x,1)来求就行了。
可是如果先求f(100,51)再求(100,50)呢
如果我们在求f(100,51)的过程中把f(100,1) ......f(100,51)都存起来那么这个算法光空间复杂度就n^2了不行。
继续分析这个大小为n^2的解空间哪些信息是重复的
很明显是有的如果我们存了(100,1) ......f(100,10)y也存了f(y,1)......f(y,40)那么f(100,11)......f(51)还有必要存吗
没有必要只要跳转一次就行了
假设每个节点只存f(n,1)......f(n,m那么空间复杂度n*m时间复杂度n*mn*n/m也就是n^1.5大概等于1千万。
PS这个思路的前面一半是我比赛时的实际思路然后我想到带权并查集然后放弃了这个思路。
PPS和我 CSU 1515: Sequence 区间DP_csuzhucong的博客-CSDN博客 这个题的做法也比较像。
赛后代码
int ans[50005][201];class TreeAncestor {
public:vectorintp;int n;TreeAncestor(int n, vectorint parent) {pparent,this-nn;for(int i0;in;i)ans[i][0]i;for(int d1;d200;d)for(int i0;in;i)ans[i][d]ans[i][d-1]0?parent[ans[i][d-1]]:-1;}int getKthAncestor(int node, int k) {while(k200){nodeans[node][200],k-200;if(node-1)return -1;}return ans[node][k];}
};
思路二倍增法
参考树状数组用ans[i][j]表示第i个结点的第2^j个祖先
时间复杂度和空间复杂度都是O(nlogn)
比赛代码
int ans[50005][18];class TreeAncestor {
public:vectorintp;int n;TreeAncestor(int n, vectorint parent) {pparent,this-nn;for(int i0;in;i)ans[i][1]parent[i];for(int d2;d18;d)for(int i0;in;i)ans[i][d]ans[i][d-1]0?ans[ans[i][d-1]][d-1]:-1;}int getKthAncestor(int node, int k) {for(int i1;i18;i){if(k(1(i-1)))nodeans[node][i];if(node-1)return -1;}return node;}
};
思路三
力扣题解中的BFSDFS二分 PS
LCA最近公共祖先问题可以用BFSDFSRMQ区间极值来做也可以用倍增法来做。
这个题的倍增法和LCA的倍增法差不多。
这个题的BFSDFS二分解法和LCA的BFSDFSRMQ解法差不多。
1485. 克隆含随机指针的二叉树
二叉树
1486. 数组异或操作
给你两个整数n 和 start 。
数组 nums 定义为nums[i] start 2*i下标从 0 开始且 n nums.length 。
请返回 nums 中所有元素按位异或XOR后得到的结果。 示例 1
输入n 5, start 0 输出8 解释数组 nums 为 [0, 2, 4, 6, 8]其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) 8 。 ^ 为按位异或 XOR 运算符。
示例 2
输入n 4, start 3 输出8 解释数组 nums 为 [3, 5, 7, 9]其中 (3 ^ 5 ^ 7 ^ 9) 8.
示例 3
输入n 1, start 7 输出7
示例 4
输入n 10, start 5 输出2 提示
1 n 10000 start 1000n nums.length
class Solution {
public:int xorOperation(int n, int start) {if(n1)return start;return start^xorOperation(n-1,start2);}
};
1487. 保证文件名唯一
给你一个长度为 n 的字符串数组 names 。你将会在文件系统中创建 n 个文件夹在第 i 分钟新建名为 names[i] 的文件夹。
由于两个文件 不能 共享相同的文件名因此如果新建文件夹使用的文件名已经被占用系统会以 (k) 的形式为新文件夹的文件名添加后缀其中 k 是能保证文件名唯一的 最小正整数 。
返回长度为 n 的字符串数组其中 ans[i] 是创建第 i 个文件夹时系统分配给该文件夹的实际名称。 示例 1
输入names [pes,fifa,gta,pes(2019)]
输出[pes,fifa,gta,pes(2019)]
解释文件系统将会这样创建文件名
pes -- 之前未分配仍为 pes
fifa -- 之前未分配仍为 fifa
gta -- 之前未分配仍为 gta
pes(2019) -- 之前未分配仍为 pes(2019)示例 2
输入names [gta,gta(1),gta,avalon]
输出[gta,gta(1),gta(2),avalon]
解释文件系统将会这样创建文件名
gta -- 之前未分配仍为 gta
gta(1) -- 之前未分配仍为 gta(1)
gta -- 文件名被占用系统为该名称添加后缀 (k)由于 gta(1) 也被占用所以 k 2 。实际创建的文件名为 gta(2) 。
avalon -- 之前未分配仍为 avalon示例 3
输入names [onepiece,onepiece(1),onepiece(2),onepiece(3),onepiece]
输出[onepiece,onepiece(1),onepiece(2),onepiece(3),onepiece(4)]
解释当创建最后一个文件夹时最小的正有效 k 为 4 文件名变为 onepiece(4)。示例 4
输入names [wano,wano,wano,wano]
输出[wano,wano(1),wano(2),wano(3)]
解释每次创建文件夹 wano 时只需增加后缀中 k 的值即可。
示例 5
输入names [kaido,kaido(1),kaido,kaido(1)]
输出[kaido,kaido(1),kaido(2),kaido(1)(1)]
解释注意如果含后缀文件名被占用那么系统也会按规则在名称后添加新的后缀 (k) 。提示
1 names.length 5 * 10^41 names[i].length 20names[i] 由小写英文字母、数字和/或圆括号组成。
class Solution {
public:vectorstring getFolderNames(vectorstring names) {unordered_mapstring,intm;m.reserve(50005);vectorstringans;char cn[6];for(int i0;inames.size();i){string snames[i],s1;if(m[s]0){ans.push_back(s);m[s]1;continue;}for(int im[s];i50005;i){sprintf(cn,%d,i);s1s(cn);if(m[s1]0){ans.push_back(s1);m[s]i1;m[s1]1;break;}}}return ans;}
}; PS:
我WA的用例
[kaido,kaido(1),kaido,kaido(1),kaido(2)] [kaido,kaido(1),kaido(2),kaido(1)(1),kaido(2)(1)]
修改代码
s和s1都要存入map改完AC
1488. 避免洪水泛滥 线段树
1489. 找到最小生成树里的关键边和伪关键边
最小生成树
1490. 克隆 N 叉树
二叉树
1491. 去掉最低工资和最高工资后的工资平均值
水题
1492. n 的第 k 个因子
因式分解
1494. 并行课程 II
状态压缩DP
1496. 判断路径是否相交
给你一个字符串 path其中 path[i] 的值可以是 N、S、E 或者 W分别表示向北、向南、向东、向西移动一个单位。
机器人从二维平面上的原点 (0, 0) 处开始出发按 path 所指示的路径行走。
如果路径在任何位置上出现相交的情况也就是走到之前已经走过的位置请返回 True 否则返回 False 。 示例 1
输入path NES 输出false 解释该路径没有在任何位置相交。 示例 2
输入path NESWW 输出true 解释该路径经过原点两次。
提示
1 path.length 10^4 path 仅由 {N, S, E, W} 中的字符组成 C代码
class Solution {
public:bool isPathCrossing(string path) {int ns0,ew0;mappairint,int,intm;m[make_pair(ns,ew)]1;for(int i0;path[i];i){if(path[i]N)ns;if(path[i]S)ns--;if(path[i]E)ew;if(path[i]W)ew--;if(m[make_pair(ns,ew)])return true;m[make_pair(ns,ew)]1;}return false;}
};
C代码
typedef struct {int key;int value;UT_hash_handle hh;
} Hash;
Hash *hash NULL;// 增加
void add(int key, int value)
{Hash *s NULL;s (Hash *)malloc(sizeof(Hash));s-key key;s-value value;HASH_ADD_INT(hash, key, s);
}
// 查找
int find(int key)
{Hash *s NULL;HASH_FIND_INT(hash, key, s);if (s ! NULL) {// 查找到结果return 1;} else {return 0;}
}
// 删除
void delete (Hash *s)
{HASH_DEL(hash, s);free(s);s NULL;
}
//清空
void clearAll()
{Hash *s,*tmp;HASH_ITER(hh, hash, s, tmp){delete(s);}
}bool isPathCrossing(char * path){int ns0,ew0;add(0,1);for(int i0;path[i];i){if(path[i]N)ns;if(path[i]S)ns--;if(path[i]E)ew;if(path[i]W)ew--;if(find(ns*10000ew)){clearAll();return true;}add(ns*10000ew,1);}clearAll();return false;
}
1500. 设计文件分享系统
我们需要使用一套文件分享系统来分享一个非常大的文件该文件由 m 个从 1 到 m 编号的文件块组成。
当用户加入系统时系统应为其注册一个独有的 ID。这个独有的 ID 应当被相应的用户使用一次但是当用户离开系统时其 ID 应可以被后续新注册的用户再次使用。
用户可以请求文件中的某个指定的文件块系统应当返回拥有这个文件块的所有用户的 ID。如果用户收到 ID 的非空列表就表示成功接收到请求的文件块。 实现 FileSharing 类
FileSharing(int m) 初始化该对象文件有 m 个文件块。int join(int[] ownedChunks)一个新用户加入系统并拥有文件的一些文件块。系统应当为该用户注册一个 ID该 ID 应是未被其他用户占用的最小正整数。返回注册的 ID。void leave(int userID)ID 为 userID 的用户将离开系统你不能再从该用户提取文件块了。int[] request(int userID, int chunkID)ID 为 userID 的用户请求编号为 chunkID 的文件块。返回拥有这个文件块的所有用户的 ID 所构成的列表或数组按升序排列。 示例:
输入:
[FileSharing,join,join,join,request,request,leave,request,leave,join]
[[4],[[1,2]],[[2,3]],[[4]],[1,3],[2,2],[1],[2,1],[2],[[]]]
输出:
[null,1,2,3,[2],[1,2],null,[],null,1]
解释:
FileSharing fileSharing new FileSharing(4); // 我们用该系统分享由 4 个文件块组成的文件。fileSharing.join([1, 2]); // 一个拥有文件块 [1,2] 的用户加入系统为其注册 id 1 并返回 1。fileSharing.join([2, 3]); // 一个拥有文件块 [2,3] 的用户加入系统为其注册 id 2 并返回 2。fileSharing.join([4]); // 一个拥有文件块 [4] 的用户加入系统为其注册 id 3 并返回 3。fileSharing.request(1, 3); // id 1 的用户请求第 3 个文件块只有 id 2 的用户拥有文件块返回 [2] 。注意现在用户 1 现拥有文件块 [1,2,3]。fileSharing.request(2, 2); // id 2 的用户请求第 2 个文件块id 为 [1,2] 的用户拥有该文件块所以我们返回 [1,2] 。fileSharing.leave(1); // id 1 的用户离开系统其所拥有的所有文件块不再对其他用户可用。fileSharing.request(2, 1); // id 2 的用户请求第 1 个文件块系统中没有用户拥有该文件块所以我们返回空列表 [] 。fileSharing.leave(2); // id 2 的用户离开系统。fileSharing.join([]); // 一个不拥有任何文件块的用户加入系统为其注册 id 1 并返回 1 。注意id 1 和 2 空闲可以重新使用。提示:
1 m 1050 ownedChunks.length min(100, m)1 ownedChunks[i] mownedChunks 的值是互不相同的。1 chunkID m当你正确地注册用户 ID 时题目保证 userID 是系统中的一个已注册用户。join、 leave 和 request 最多被调用 104 次。每次对 leave 的调用都有对应的对 join 的调用。 进阶
当系统以用户的 IP 地址而不是独有 ID 来识别用户且用户断开连接后以相同 IP 重新连接系统时会发生什么当用户频繁加入并退出系统且该用户不请求任何文件块时你的解决方案仍然保持高效吗当所有用户同时加入系统请求所有文件并离开时你的解决方案仍然保持高效吗如果系统用于分享 n 个文件其中第 i 个文件由 m[i] 组成你需要如何修改
class FileSharing {
public:FileSharing(int m) {}int join(vectorint ownedChunks) {int id1;while(ids[id])id;ids[id]1;m[id]ownedChunks;for(auto x:ownedChunks)m2[x][id]1;return id;}void leave(int userID) {for(auto x:m[userID])m2[x][userID]0;m[userID].clear();ids[userID]0;}vectorint request(int userID, int chunkID) {auto m3m2[chunkID];vectorintans;for(auto p:m3)if(p.second)ans.push_back(p.first);if(!ans.empty() m2[chunkID][userID]0){m[userID].push_back(chunkID);m2[chunkID][userID]1;}return ans;}
private:mapint,intids;mapint,vectorintm;mapint,mapint,intm2;
};
