周赛360 T1与T2

算法周赛

Leetcode

发布日期: 2023-08-27

更新日期: 2023-10-15

文章字数: 1.2k

阅读时长: 5 分

阅读次数:

周赛360：T1与T2

要说的话：隔了好多天又开始比赛了，还是2题选手，这回的前两题感觉还是比较容易想到的；后续的2题不太熟，所以等掌握了之后再回来补题解。

T1 .距离原点最远的点

1.1 题目说明

给你一个长度为 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" 。

1.2 解答分析

分析：对于距离原点的距离，_是可以随意替换的（可左可右），此时决定最大的距离的是L与R的个数问题，是否可以抵消？接着加上_的个数即可。下面是具体的代码方法
- 对于字符串的每一位，可以利用charAt(),也可以将字符串转化为字符串数组，利用toCharArray的方法。
- L和R的个数的抵消，想到的是利用减法进行，但是需要绝对值Math.abs()

1.3 具体代码

代码：

class Solution {
    public int furthestDistanceFromOrigin(String moves) {
    int distance=0;
    int r=0,l=0;

    for(char m:moves.toCharArray()){
        if(m=='_'){
            distance++;
        }
        if(m=='L'){
            l++;
        }
        if(m=='R'){
            r++;
        }
    }
    distance=distance+Math.abs(r-l);
    return distance;        
    }
}

时间复杂度： $O(n)$ ，其中 $n$ 为$ moves$的长度。
空间复杂度： $O(1)$ 。仅用到若干额外变量

T2 找出美丽数组的最小和

2.1 题目说明

给你两个正整数：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.2 解答分析

分析1:
- 这道题目需要用到贪心算法。一个简单的思路，假设我们期望加入1，那么 k - 1 就不再符合要求。但是1和k - 1之间，我们肯定选择1，因为很直观的1更小。因为提示给的范围很小1 <= n, k <= 50。暴力计数，只要n能满足。
- 具体这里用到的是HashSet，利用对数据元素（Object）的储存功能进行配对。HashSet的用法中不存在键值对的说法，本题要用到的contains()也仅代表的是值功能
分析2：
- 数学方法，对元素进行模拟（找规律），将target记作k,对于全体元素而言，比如1和k-1两个只能选一个，因此可以直到 $k//2$ (表示向下取整,数学上直接 $k/2$ )，此时可以假设 $m=(min(k//2,n))$ ,元素和为 $(1+m)m/2$
- 同时，剩余的 $n-m$ 个数，只能从 $k$ 后面开始选，那么第二段就是从 $k$ 到 $k+n-m-1$ ，元素和这里与上面雷同
- 将上述的两段之和相加即可

2.3 具体代码

代码1：贪心算法

class Solution {
    public long minimumPossibleSum(int n, int target) {
    long res = 0;
    int i = 1;
    Set<Integer> set=new HashSet<>();
    while(n>0){
        if(!(set.contains(i))){
            set.add(target-i);
            res+=i;
            n--;
        }
        i++;
        }
        return res;
    }
}

时间复杂度： $O(nlog(n))$

其中的 $log(n)$ 是 $set.contains()$ 的时间复杂度
空间复杂度： $O(n)$

HashSet额外开辟的存储空间n

代码2：数学模拟

class Solution {
    public long minimumPossibleSum(int n, int k) {
        long m = Math.min(k / 2, n);
        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) / 2;
    }
}