Loading...
墨滴

jrh

2021/12/19  阅读:47  主题:WeChat-Format

LeetCode 第 272 场周赛题解

往期回顾

第一题

题目链接🔗:https://leetcode-cn.com/problems/find-first-palindromic-string-in-the-array/

题目要求我们返回给定数组中的第一个回文字符串,如果不存在回文字符串则返回一个空字符串。

为了竞赛时码字的速度,我这里面直接使用 StringBuilderreverse 方法反转字符串,将反转字符串与原字符串进行比较来判断该字符串是否是一个回文字符串,如果是则返回;如果遍历完数组还没有任何一个回文字符串则返回空字符串。

Java 代码:

class Solution {
    public String firstPalindrome(String[] words) {
        for (String word : words)
            if (isPalindrome(word)) return word;

        return "";
    }

    public boolean isPalindrome(String word) {
        StringBuilder reverse = new StringBuilder(word).reverse();
        if (reverse.toString().equals(word)) return true;
        return false;
    }
}

第二题

题目链接🔗:https://leetcode-cn.com/problems/adding-spaces-to-a-string/

题目给定了一个字符串 ,以及一个整数数组

给定了我们需要在原字符串中添加空格的下标。

譬如给定字符串 为:

s = "LeetcodeHelpsMeLearn"

数组 为:

spaces = [8,13,15]

在相应的索引下标添加空格后,返回后的字符串为:

res = "Leetcode Helps Me Learn"

解题思路:

  1. 题目中并未说明 是按照从小到大进行排序的,所以我们首先要对 数组进行排序
  2. 初始化一个 StringBuilder,以及索引 指向字符串 指向数组
  3. 从头遍历字符串 。如果遍历到的索引 中,即:i == spaces[j],我们就向 StringBuilder 中先添加空格,然后再添加 s.charAt(i) 字符,同时我们让索引 向后移动一个单位
  4. 如果遍历到的索引 并未在 数组中,则向 StringBuilder 中添加 s.charAt(i) 字符,同时让索引 向后移动一个单位

Java 代码如下:

class Solution {
    public String addSpaces(String s, int[] spaces) {
        Arrays.sort(spaces);
        StringBuilder sb = new StringBuilder();
        for (int i = 0, j = 0; i < s.length(); i++) {
            if (j < spaces.length && spaces[j] == i) {
                sb.append(" ");
                sb.append(s.charAt(i));
                j++;
            } else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}

第三题

题目链接🔗:https://leetcode-cn.com/problems/number-of-smooth-descent-periods-of-a-stock/

题目给定了一个整数数组 prices[i] 表示一支股票在第 天的价格,要求我们返回平滑下降阶段的数目。

平滑下降阶段的定义为:对于连续一天或多天,每日的股价都比前一日股价恰好少

譬如:

数组为:

prices = [3,2,1,4]

平滑下降阶段的数目为

[3]
[2]
[1]
[4] 
[3,2]
[2,1]
[3,2,1]

解题思路:

使用两个指针, 指向 prices 数组, 则用来维护一个平滑阶段。

如果一个平滑阶段由 个元素组成,那么这个平滑阶段的数目为

举个 🌰:

...,5,4,3,2,...

在数组 prices 中,5,4,3,2 为一个平滑阶段。这个平滑阶段由 个元素组成,那么这个平滑阶段的数目为:1+2+3+4 = 10

Java 代码如下:

class Solution {
    public long getDescentPeriods(int[] prices) {
        long res = 0;
        int j = 0;
        for (int i = 0; i < prices.length; i = j + 1) {
            j = i;
            while (j < prices.length - 1 && prices[j] - prices[j + 1] == 1) {
                j++;
            }
            res += count1ToN(j - i + 1);
        }
        return res;
    }

    public long count1ToN(long n) {
        return ((1 + n) * n) / 2;
    }
}

第四题

题目链接🔗:https://leetcode-cn.com/problems/minimum-operations-to-make-the-array-k-increasing/

题目给定了一个正整数数组 以及一个正整数

对于满足 的下标 ,都有 ,我们就称 递增的。

题目要求我们返回使数组变为 递增的最少操作次数。

譬如,给定输入:

arr = [4,1,5,2,6,2]
k = 3

如果要想将数组 变为 递增,那么最少的改动次数为 ,对应的修改位置为

举个 🌰,我们可以将数组修改为:

arr = [4,1,5,4,6,5]

修改后的数组满足 递增。

解题思路:

  1. 将数组 分为 个组

    譬如对于 arr = [4,1,5,5,6,2,1], k = 3,我们可以将 分为三个组,分别为:

    • arr[0] arr[3] arr[6]
    • arr[1] arr[4]
    • arr[2] arr[5]
  2. 找到每个组的最长非递减数组长度,用该组的元素总量 - 该组的最长非递减数组长度,得到的结果便是使该组变为 递增的最少的改动次数

  3. 统计 个组的最少的改动次数,将结果相加并返回

在步骤 中,我们可以使用二分法来优化算法的复杂度。该题所使用的是一种 分治 的算法思想,将题目拆解成相应的子问题,分而治之。

Java 代码如下:

class Solution {
    List<List<Integer>> list = new ArrayList<>();

    public int kIncreasing(int[] arr, int k) {
        // arr = [4,1,5,5,6,2,1] , k = 3
        // arr[0] arr[3] arr[6]  ===> 4 5 1 ---- 3 - 2
        // arr[1] arr[4]  ===> 1 6 ---- 2 - 2
        // arr[2] arr[5]  ===> 5 2 ---- 2 - 0
        // res = 1 + 0 + 2 = 3

        int res = 0;

        for (int i = 0; i < k; i++) {
            List<Integer> tmpList = new ArrayList<>();
            int j = i;
            while (j < arr.length) {
                tmpList.add(arr[j]);
                j += k;
            }
            list.add(tmpList);
        }

        for (int i = 0; i < list.size(); i++) {
            res += list.get(i).size() - getNumberOfLongestSubsequencesInList(list.get(i));
        }
        return res;
    }

    public int getNumberOfLongestSubsequencesInList(List<Integer> list) {
        // 存储递增子序列的元素
        List<Integer> tmp = new ArrayList<>();
        tmp.add(list.get(0));

        for (int i = 1; i < list.size(); i++) {
            int l = 0;
            int r = tmp.size() - 1;
            if (list.get(i) >= tmp.get(r)) {
                tmp.add(list.get(i));
            } else {
                // 二分
                while (l < r) {
                    int mid = l + (r - l) / 2;
                    if (tmp.get(mid) <= list.get(i)) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
                tmp.set(l, list.get(i));
            }
        }
        return tmp.size();
    }
}

PS:这场周赛应该有很多人 AC 吧,祝大家越来越猛!

jrh

2021/12/19  阅读:47  主题:WeChat-Format

作者介绍

jrh