临沂培训学校网站建设,网站网站制作需要多少钱,吃什么补肾快,怎么做市场推广【力扣周赛】第360场周赛 8015.距离原点最远的点题目描述解题思路 8022. 找出美丽数组的最小和题目描述解题思路 8015.距离原点最远的点
题目描述
描述#xff1a;给你一个长度为 n 的字符串 moves #xff0c;该字符串仅由字符 ‘L’、‘R’ 和 ‘_’ 组成。字符串表示你在… 【力扣周赛】第360场周赛 8015.距离原点最远的点题目描述解题思路 8022. 找出美丽数组的最小和题目描述解题思路 8015.距离原点最远的点
题目描述
描述给你一个长度为 n 的字符串 moves 该字符串仅由字符 ‘L’、‘R’ 和 ‘_’ 组成。字符串表示你在一条原点为 0 的数轴上的若干次移动。
你的初始位置就在原点0第 i 次移动过程中你可以根据对应字符选择移动方向
如果 moves[i] ‘L’ 或 moves[i] ‘’ 可以选择向左移动一个单位距离 如果 moves[i] ‘R’ 或 moves[i] ’ 可以选择向右移动一个单位距离 移动 n 次之后请你找出可以到达的距离原点 最远 的点并返回 从原点到这一点的距离 。
示例 1
输入moves L_RL__R
输出3
解释可以到达的距离原点 0 最远的点是 -3 移动的序列为 LLRLLLR 。示例 2
输入moves _R__LL_
输出5
解释可以到达的距离原点 0 最远的点是 -5 移动的序列为 LRLLLLL 。示例 3
输入moves _______
输出7
解释可以到达的距离原点 0 最远的点是 7 移动的序列为 RRRRRRR 。提示
1 moves.length n 50 moves 仅由字符 ‘L’、‘R’ 和 ‘_’ 组成
解题思路
思路脑筋急转弯将直观模拟转换为求解L和R数量因为L和R可以抵消故可以将_转换为L和R较多的那个再进行求解。
class Solution {
public:int furthestDistanceFromOrigin(string moves) {int nmoves.size();// l表示L数量 r表示R数量int l0,r0;// 转化为l与r抵消剩余多少则往哪个方向移动for(auto move:moves){if(moveR)r;if(moveL)l;}return lr?n-2*r:n-2*l;}
};总结首先是理解题意然后是直观模拟当直观模拟较为复杂则考虑在不改变结果的情况下如何转换求解以便优化时空复杂度。
8022. 找出美丽数组的最小和
题目描述
描述给你两个正整数n 和 target 。
如果数组 nums 满足下述条件则称其为 美丽数组 。
nums.length n. nums 由两两互不相同的正整数组成。 在范围 [0, n-1] 内不存在 两个 不同 下标 i 和 j 使得 nums[i] nums[j] target 。 返回符合条件的美丽数组所可能具备的 最小 和。
示例 1
输入n 2, target 3
输出4
解释nums [1,3] 是美丽数组。
- nums 的长度为 n 2 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j 使得 nums[i] nums[j] 3 。
可以证明 4 是符合条件的美丽数组所可能具备的最小和。示例 2
输入n 3, target 3
输出8
解释
nums [1,3,4] 是美丽数组。
- nums 的长度为 n 3 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j 使得 nums[i] nums[j] 3 。
可以证明 8 是符合条件的美丽数组所可能具备的最小和。示例 3
输入n 1, target 1
输出1
解释nums [1] 是美丽数组。提示
1 n 105 1 target 105
解题思路
思路最开始是一种很神奇的感觉没有说那种脑海中浮现出很直观的清晰的逻辑思路但是写着写着就写出来了。贪心想法必定是按照1、2、3…n的顺序得到的数组和最小而且1必定在结果中所以使用uset存储已经加入结果集合初始为1使用num表示当前加入元素初始为2使用res表示当前数组和初始为1当在uset中找不到与num相加和为target的元素时则将num加入uset并更新数组和res。
class Solution {
public:long long minimumPossibleSum(int n, int target) {// 长度为1的数组最小为1if(n1)return 1;// 记录元素和 1肯定在long long res1;// 记录加入元素unordered_setint uset;uset.emplace(1);// 记录当前加入元素int num2;// 1 2 3 4依次加入最小 按照target排除不能加入元素 使用uset记录已经加入元素while(uset.size()n){if(uset.find(target-num)uset.end()){uset.emplace(num);resnum;}num;}return res;}
};优化当时在模拟示例数据时想到对于元素和target在和为target的两两配对中必定选取较小的那个数而对于大于等于target的数选择部分数使得总数据数量为n。
class Solution {
public:long long minimumPossibleSum(int n, int target) {// 第一部分两两配对中取较小者 1、2、3...k/2 使得nmlong long mmin(target/2,n);// 第二部分剩余n-m个数 k...kn-m-1 如果最小m为n 那么后者为0return (m*(m1)(target*2n-m-1)*(n-m))/2;}
};PS后两题不会hhh有时候想想刷题真神奇因为无论如何都不会到达天花板总是会在某些题中找到无力感和挫败感但是又有什么办法呢感觉还是多总结多思考不断积累思路然后形成知识体系总有一天会blingblingbling的吧~~
