1578. Minimum Time to Make Rope Colorful
Posted Updated LeetCode / Medium2 minutes read (About 291 words)

1578. Minimum Time to Make Rope Colorful

Problem

Alice has n balloons arranged on a rope. You are given a 0-indexed string colors where colors[i] is the color of the i<sup>th</sup> balloon.

Alice wants the rope to be colorful. She does not want two consecutive balloons to be of the same color, so she asks Bob for help. Bob can remove some balloons from the rope to make it colorful. You are given a 0-indexed integer array neededTime where neededTime[i] is the time (in seconds) that Bob needs to remove the i<sup>th</sup> balloon from the rope.

Return the minimum time Bob needs to make the rope colorful.

Solution

滑动窗口，遍历字符串。
common用来记录连续颜色相同的个数，初始化为1。
如果当前字符与下一个字符相同，则窗口向右侧扩展，common++。
遍历时记录替换气球需要的最大时间maxTime和替换掉所有同色气球的总时间deleteTime。

如果common大于1，则总时间加上需要删除的时间（刨除最大时间maxTime）。
更新i为i + common。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minCost(String colors, int[] neededTime) {
        int i = 0, totalTime = 0;
        char[] c = colors.toCharArray();
        while(i < neededTime.length){
            int common = 1, maxTime = neededTime[i], deleteTime = neededTime[i];
            while(i + common < neededTime.length && c[i] == c[i + common]){
                maxTime = Math.max(maxTime, neededTime[i + common]);
                deleteTime += neededTime[i + common];
                common++;
            }
            if(common > 1){
                deleteTime -= maxTime;
                totalTime += deleteTime;
            }
            i += common;
        }
        return totalTime;
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 235 words)

567. Permutation in String

问题
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.

将要查找的组合加入数组，数值为字符出现的次数。
滑动窗口，入窗口对应的元素数值-1，出窗口对应的元素数值+1。
每次移动窗口都检验一次数组的数值是否全部为0，如果是真，则返回真。
小技巧：直接用数组来记录字符出现的次数，用字符减去与’a’的差作为下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()){
            return false;
        }
        
        int[] dic = new int[26];
        for (int i = 0; i < s1.length(); i++){
            dic[s1.charAt(i)-'a']++;
            dic[s2.charAt(i)-'a']--;
        }
 
        int i = 0;
        int j = s1.length();
        
        while( j < s2.length() ){
            if ( allZero(dic) ){
                return true;
            }
            dic[s2.charAt(i)-'a']++;
            dic[s2.charAt(j)-'a']--;
            i++;
            j++;
        }
        return allZero(dic);
    }
    
    private boolean allZero(int[] dic){
        for (int num : dic){
            if ( num != 0 ){
                return false;
            }
        }
        return true;
    }
}
Follow

Recents

Archives

Links

×