郑州 网站建设有限公司,建设手机网站经验分享,四川建设网是国企吗,杭州做网站公司文章目录1. 比赛结果2. 题目LeetCode 5311. 将数字变成 0 的操作次数 easyLeetCode 5312. 大小为 K 且平均值大于等于阈值的子数组数目 mediumLeetCode 5313. 时钟指针的夹角 mediumLeetCode 5314. 跳跃游戏 IV hard1. 比赛结果
做出来了1, 3, 4题#xff0c;第2题结束后12分…
文章目录1. 比赛结果2. 题目LeetCode 5311. 将数字变成 0 的操作次数 easyLeetCode 5312. 大小为 K 且平均值大于等于阈值的子数组数目 mediumLeetCode 5313. 时钟指针的夹角 mediumLeetCode 5314. 跳跃游戏 IV hard1. 比赛结果
做出来了1, 3, 4题第2题结束后12分钟做出来了。 全国排名231/112020.6%全球排名772/374520.6%
2. 题目
LeetCode 5311. 将数字变成 0 的操作次数 easy
题目链接 给你一个非负整数 num 请你返回将它变成 0 所需要的步数。 如果当前数字是偶数你需要把它除以 2 否则减去 1 。
示例 1
输入num 14
输出6
解释
步骤 1) 14 是偶数除以 2 得到 7 。
步骤 2 7 是奇数减 1 得到 6 。
步骤 3 6 是偶数除以 2 得到 3 。
步骤 4 3 是奇数减 1 得到 2 。
步骤 5 2 是偶数除以 2 得到 1 。
步骤 6 1 是奇数减 1 得到 0 。示例 2
输入num 8
输出4
解释
步骤 1 8 是偶数除以 2 得到 4 。
步骤 2 4 是偶数除以 2 得到 2 。
步骤 3 2 是偶数除以 2 得到 1 。
步骤 4 1 是奇数减 1 得到 0 。示例 3
输入num 123
输出12提示
0 num 10^6来源力扣LeetCode 链接https://leetcode-cn.com/problems/number-of-steps-to-reduce-a-number-to-zero 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 解答
class Solution {
public:int numberOfSteps (int num) {int count 0;while(num){ if(num%2 0)num / 2;elsenum - 1;count;}return count;}
};LeetCode 5312. 大小为 K 且平均值大于等于阈值的子数组数目 medium
题目链接 给你一个整数数组 arr 和两个整数 k 和 threshold 。
请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。
示例 1
输入arr [2,2,2,2,5,5,5,8], k 3, threshold 4
输出3
解释子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 45 和 6 。其他长度为 3 的子数组的平均值都小于 4 threshold 的值)。示例 2
输入arr [1,1,1,1,1], k 1, threshold 0
输出5示例 3
输入arr [11,13,17,23,29,31,7,5,2,3], k 3, threshold 5
输出6
解释前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。示例 4
输入arr [7,7,7,7,7,7,7], k 7, threshold 7
输出1示例 5
输入arr [4,4,4,4], k 4, threshold 1
输出1提示
1 arr.length 10^5
1 arr[i] 10^4
1 k arr.length
0 threshold 10^4来源力扣LeetCode 链接https://leetcode-cn.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 解题
一开始看错题子数组我看成可以随意组合。。。 双指针解题即可。
class Solution {
public:int numOfSubarrays(vectorint arr, int k, int threshold) {int i 0, j k-1, n arr.size(), sum0, target k*threshold;int count 0;for(i 0; i k; i) sum arr[i];if(sum target)count;i1,j;while(j n){sum arr[j]-arr[i-1];if(sum target)count;i,j;}return count;}
};LeetCode 5313. 时钟指针的夹角 medium
题目链接
给你两个数 hour 和 minutes 。请你返回在时钟上由给定时间的时针和分针组成的较小角的角度60 单位制。
提示
1 hour 12
0 minutes 59
与标准答案误差在 10^-5 以内的结果都被视为正确结果。解题
class Solution {
public:double angleClock(int hour, int minutes) {double d1 0, d2 0;d2 minutes*6;d1 (hour%12)*30 double(d2)/360*30;return min(abs(d1-d2),360-abs(d1-d2));}
};LeetCode 5314. 跳跃游戏 IV hard
题目链接
给你一个整数数组 arr 你一开始在数组的第一个元素处下标为 0。
每一步你可以从下标 i 跳到下标
i 1 满足i 1 arr.lengthi - 1 满足i - 1 0j 满足arr[i] arr[j] 且 i ! j
请你返回到达数组最后一个元素的下标处所需的 最少操作次数 。
注意任何时候你都不能跳到数组外面。
示例 1
输入arr [100,-23,-23,404,100,23,23,23,3,404]
输出3
解释那你需要跳跃 3 次下标依次为 0 -- 4 -- 3 -- 9 。
下标 9 为数组的最后一个元素的下标。示例 2
输入arr [7]
输出0
解释一开始就在最后一个元素处所以你不需要跳跃。示例 3
输入arr [7,6,9,6,9,6,9,7]
输出1
解释你可以直接从下标 0 处跳到下标 7 处也就是数组的最后一个元素处。示例 4
输入arr [6,1,9]
输出2示例 5
输入arr [11,22,7,7,7,7,7,7,7,22,13]
输出3提示
1 arr.length 5 * 10^4
-10^8 arr[i] 10^8解题
BFS, 广度优先搜索
开始想着用动态规划后来知道不是是最短路径问题。 先超时一次连续一样的数可以只插入最后一个即可 超时代码
class Solution {
public:int minJumps(vectorint arr) {if(arr.size() 1)return 0;int i, tp;const int n arr.size();vectorint dp(n, INT_MAX);queueint q;vectorbool visited(n,false);q.push(0);visited[0] true;dp[0] 0;multimapint, int m;for(i 1; i n; i)m.insert(make_pair(arr[i], i));while(!q.empty() (dp[n-1] INT_MAX)){tp q.front();q.pop();if(tp1 n !visited[tp1]){dp[tp1] min(dp[tp1], 1dp[tp]);q.push(tp1);visited[tp1] true;}if(tp-10 !visited[tp-1]){dp[tp-1] min(dp[tp-1], 1dp[tp]);q.push(tp-1);visited[tp-1] true;}if(dp[n-1] ! INT_MAX)return dp[n-1];auto start m.equal_range(arr[tp]).first, end m.equal_range(arr[tp]).second;for(auto it start; it ! end; it){if(!visited[it-second]){visited[it-second] true;dp[it-second] min(dp[it-second], 1dp[tp]);q.push(it-second);}if(dp[n-1] ! INT_MAX)return dp[n-1];}}return dp[n-1];}
};通过代码172ms
class Solution {
public:int minJumps(vectorint arr) {if(arr.size() 1)return 0;int i, tp, prev arr[0];const int n arr.size();vectorint dp(n, INT_MAX);queueint q;vectorbool visited(n,false);q.push(0);visited[0] true;dp[0] 0;multimapint, int m;for(i 0; i n; i){if(arr[i] prev)continue;else{m.insert(make_pair(prev, i-1));prev arr[i];}}m.insert(make_pair(arr[n-1],n-1));while(!q.empty() (dp[n-1] INT_MAX)){tp q.front();q.pop();if(tp1 n !visited[tp1]){dp[tp1] min(dp[tp1], 1dp[tp]);q.push(tp1);visited[tp1] true;}if(tp-10 !visited[tp-1]){dp[tp-1] min(dp[tp-1], 1dp[tp]);q.push(tp-1);visited[tp-1] true;}if(dp[n-1] ! INT_MAX)return dp[n-1];auto start m.equal_range(arr[tp]).first, end m.equal_range(arr[tp]).second;for(auto it start; it ! end; it){if(!visited[it-second]){visited[it-second] true;dp[it-second] min(dp[it-second], 1dp[tp]);q.push(it-second);}if(dp[n-1] ! INT_MAX)return dp[n-1];}}return dp[n-1];}
};赛后优化代码如下
class Solution {
public:int minJumps(vectorint arr) {if(arr.size() 1)return 0;int i, tp, prev INT_MIN, step 0, size;const int n arr.size();queueint q;vectorbool visited(n,false);q.push(0);visited[0] true;multimapint, int m;for(i 0; i n; i){if(arr[i] prev)continue;//跳过一样的else//只插入连续相同的一段的首尾中间跳肯定不是最短距离{ if(i-10)m.insert(make_pair(arr[i-1],i-1));m.insert(make_pair(arr[i], i));prev arr[i];}if(i n-1)//插入最后一个位置可能重复插入了但是不影响m.insert(make_pair(arr[i],i));}while(!q.empty()){size q.size();while(size--){tp q.front();q.pop();if(tp n-1)return step;// 跳往i1位置if(tp1 n !visited[tp1]){q.push(tp1);visited[tp1] true;}// 跳往i-1位置if(tp-10 !visited[tp-1]){q.push(tp-1);visited[tp-1] true;}// 跳往值相同的位置auto start m.equal_range(arr[tp]).first, end m.equal_range(arr[tp]).second;for(auto it start; it ! end; it){if(!visited[it-second]){visited[it-second] true;q.push(it-second);}}}step;}return step;}
};
