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;
    }
};

Stacey is coordinating a beach clean-up event with her university's Women in STEM charity branch. The beach is covered with tin cans of varying weights arranged in a single line, indexed from 0 to n-1. Stacey uses a scooper that can pick up three adjacent cans at a time. For each selection: She identifies the lightest remaining can with weight w She uses the scooper to pick up that can along with its two adjacent cans (or fewer if at the edge) She continues this process until there are no cans left on the beach If multiple cans have the lightest weight, Stacey selects the one with the smallest index. If a can has fewer than two adjacent cans, she removes the available adjacent cans. Determine the sum of the weights of the lightest cans she picks in each selection. Function Description Complete the function findTotalWeight in the editor with the following parameters:

• int cans[]: the weights of the cans on the beach Returns int: the sum of the minimum-weight cans at each selection Constraints
• 3 ≤ length of cans ≤ 2000
• 1 ≤ cans[i] ≤ 10⁵

A software development firm is hiring engineers and used the following challenge in its online test. Given an array arr that contains n integers, the following operation can be performed on it any number of times (possibly zero):

• Choose any index i (0 ≤ i and swap arr[i] and arr[i + 1]
• Each element of the array can be swapped at most once during the whole process. The strength of an index i is defined as arr[i] * (i + 1) using 0-based indexing. Find the maximum possible sum of the strengths of all indices after optimal swaps. Mathematically, maximize the following: Function Description Complete the function getMaximumSumOfStrengths in the editor below. getMaximumSumOfStrengths has the following parameter:
• int arr[n]: the initial array Returns long integer: the maximum possible sum of strengths of all indices after the operations are applied optimally

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ arr[i]</cod

Example 1

Input:

arr = [2, 1, 4, 3]

Output:

30

Explanation: It is optimal to swap (arr[2], arr[3]) and (arr[0], arr[1]). The final array is [1, 2, 3, 4], and the sum of strengths = (1 * 1 + 2 * 2 + 3 * 3 + 4 * 4) = 30, which is maximum possible. Thus, the answer is 30.