A control device has 4 buttons that can be used to move a character around a screen in 4 directions: Up (U), Down (D), Left (L), and Right (R). The movement needs to be optimized by deleting unnecessary instructions while maintaining the same destination. Given the original set of instructions, what is the maximum number of instructions that can be deleted and still have the character reach the destination? Note: The instructions that are deleted do not need to be contiguous.

Constraints

N/A

Example 1

Input:

s = "RRR"

Output:

0

Explanation: There is nothing that can be deleted from these instructions, so the answer is 0.

解法

每对相反指令 (U↔D, L↔R) 可以同时删除一个。删除数 = 2 · min(U, D) + min(L, R)。时间复杂度 O(n)。

def characterReprogramming(s: str) -> int:
    U = s.count('U'); D = s.count('D')
    L = s.count('L'); R = s.count('R')
    return 2 * (min(U, D) + min(L, R))

class Solution {
    int characterReprogramming(String s) {
        int U = 0, D = 0, L = 0, R = 0;
        for (char c : s.toCharArray()) {
            if (c == 'U') U++; else if (c == 'D') D++;
            else if (c == 'L') L++; else if (c == 'R') R++;
        }
        return 2 * (Math.min(U, D) + Math.min(L, R));
    }
}

class Solution {
public:
    int characterReprogramming(string s) {
        int U = 0, D = 0, L = 0, R = 0;
        for (char c : s) {
            if (c == 'U') U++; else if (c == 'D') D++;
            else if (c == 'L') L++; else if (c == 'R') R++;
        }
        return 2 * (min(U, D) + min(L, R));
    }
};

Students in a class are asked to stand in ascending order according to their heights for the annual class photograph. Determine the number of students not currently standing in their correct positions. Function Description Complete the function countStudents in the editor. countStudents has the following parameter(s):

• int height[n]: an array of heights in the order the students are standing Returns int: the number of students not standing in the correct positions.

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ height[i] ≤ 10⁹

Example 1

Input:

height = [1, 1, 3, 3, 4, 1]

Output:

3

Explanation: The 3 students indicated in red at indices 2, 4 and 5, are not in the right positions. The correct positions are [1, 1, 1, 3, 3, 4]. Return 3.

Example 2

Input:

height = [1, 1, 3, 4, 1]

Output:

3

Explanation: The 3 students not standing in the correct position are at indices [2, 3, 4]. So, return 3. The currect positions are [1, 1, 1, 3, 4] :)

解法

把 sorted 后与原数组对比，统计不一致位置数。时间复杂度 O(n log n)。

from typing import List

def countStudents(height: List[int]) -> int:
    s = sorted(height)
    return sum(1 for a, b in zip(height, s) if a != b)

class Solution {
    int countStudents(int[] height) {
        int[] s = height.clone();
        Arrays.sort(s);
        int cnt = 0;
        for (int i = 0; i < height.length; i++) if (height[i] != s[i]) cnt++;
        return cnt;
    }
}

class Solution {
public:
    int countStudents(vector<int>& height) {
        vector<int> s = height;
        sort(s.begin(), s.end());
        int cnt = 0;
        for (int i = 0; i < (int)height.size(); i++) if (height[i] != s[i]) cnt++;
        return cnt;
    }
};

A substring is a group of contiguous characters in a string. For instance, all substrings of abc are [a, b, c, ab, bc, abc]. Given a binary representation of a number, determine the total number of substrings present that match the following conditions: The 0s and 1s are grouped consecutively (e.g., 01, 10, 0011, 1100, 000111, etc.). The number of 0s in the substring is equal to the number of 1s in the substring. As an example, consider the string 001101. The 4 substrings matching the two conditions include [0011, 01, 10, 01]. Note that 01 appears twice, from indices 1-2 and 4-5. There are other substrings, e.g. 001 and 011 that match the first condition but not the second. Function Description Complete the function counting in the editor . Returns int: the number of substrings of s that satisfy the two conditions

Constraints

• 5 ≤ |s| ≤ 5 x 10⁵
• each s[i] is either '0' or '1'

Example 1

Input:

s = "00110"

Output:

3

Explanation: No explanation for now...

解法

LC 696 经典题。记录连续同字符段长度 group，对相邻段 (prev, cur) 贡献 min(prev, cur) 个合规子串。时间复杂度 O(n)。

def counting(s: str) -> int:
    groups = []
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]: j += 1
        groups.append(j - i)
        i = j
    return sum(min(groups[k], groups[k + 1]) for k in range(len(groups) - 1))

class Solution {
    int counting(String s) {
        List<Integer> groups = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
            groups.add(j - i);
            i = j;
        }
        int total = 0;
        for (int k = 0; k + 1 < groups.size(); k++) total += Math.min(groups.get(k), groups.get(k + 1));
        return total;
    }
}

class Solution {
public:
    int counting(string s) {
        vector<int> groups;
        int i = 0;
        while (i < (int)s.size()) {
            int j = i;
            while (j < (int)s.size() && s[j] == s[i]) j++;
            groups.push_back(j - i);
            i = j;
        }
        int total = 0;
        for (int k = 0; k + 1 < (int)groups.size(); k++) total += min(groups[k], groups[k + 1]);
        return total;
    }
};