A DFS probl

Example 1

Input:

s = "abc"

Output:

["a", "ab", "abc", "ac", "b", "bc", "c"]

Explanation: The function should return all possible subsequences of the input string "abc" sorted alphabetically, which are: ["a", "ab", "abc", "ac", "b", "bc", "c"].

解法

DFS 枚举所有非空子序列。对每个位置选 / 不选，最后按字典序排序。时间复杂度 O(2^n · n)。

from typing import List

def dfsSubsequences(s: str) -> List[str]:
    res = []
    def dfs(i, cur):
        if i == len(s):
            if cur: res.append(cur)
            return
        dfs(i + 1, cur + s[i])
        dfs(i + 1, cur)
    dfs(0, "")
    return sorted(res)

class Solution {
    String[] dfsSubsequences(String s) {
        List<String> res = new ArrayList<>();
        dfs(s, 0, new StringBuilder(), res);
        Collections.sort(res);
        return res.toArray(new String[0]);
    }

    private void dfs(String s, int i, StringBuilder cur, List<String> res) {
        if (i == s.length()) {
            if (cur.length() > 0) res.add(cur.toString());
            return;
        }
        cur.append(s.charAt(i));
        dfs(s, i + 1, cur, res);
        cur.deleteCharAt(cur.length() - 1);
        dfs(s, i + 1, cur, res);
    }
}

class Solution {
public:
    vector<string> dfsSubsequences(string s) {
        vector<string> res;
        string cur;
        dfs(s, 0, cur, res);
        sort(res.begin(), res.end());
        return res;
    }

private:
    void dfs(string& s, int i, string& cur, vector<string>& res) {
        if (i == (int)s.size()) {
            if (!cur.empty()) res.push_back(cur);
            return;
        }
        cur += s[i];
        dfs(s, i + 1, cur, res);
        cur.pop_back();
        dfs(s, i + 1, cur, res);
    }
};

Each character of the English alphabet has been mapped to a digit as shown below. A string is divisible if the sum of the mapped values of its characters is divisible by its length. Given a string s, return the number of divisible substrings of s. A substring is a contiguous non-empty sequence of characters within a string.

Constraints

• 1 ≤ word.length ≤ 2000
• word consists only of lowercase English letters.

Example 1

Input:

word = "asdf"

Output:

6

Explanation: The table above contains the details about every substring of word, and we can see that 6 of them are divisible.

Example 2

Input:

word = "bdh"

Output:

4

Explanation: The 4 divisible substrings are: "b", "d", "h", "bdh". It can be shown that there are no other substrings of word that are divisible.

Example 3

Input:

word = "abcd"

Output:

6

Explanation: The 6 divisible substrings are: "a", "b", "c", "d", "ab", "cd". It can be shown that there are no other substrings of word that are divisible.

解法

每个字母对应一个数字(如 a=1, b=2, c=3, d=4 等，看题目映射表，常见为 phone keypad)。子串 (i..j) 可除 = 和能被长度整除。暴力 O(n²) 枚举所有子串，累计和判断。

def numberOfDivisibleSubstrings(word: str) -> int:
    # mapping (a,b,c)->1, (d,e,f)->2, ... phone keypad style
    mp = {}
    for i, group in enumerate(["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"], start=1):
        for c in group:
            mp[c] = i
    n = len(word)
    cnt = 0
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += mp[word[j]]
            if s % (j - i + 1) == 0:
                cnt += 1
    return cnt

class Solution {
    int numberOfDivisibleSubstrings(String word) {
        int[] mp = new int[26];
        String[] groups = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        for (int g = 0; g < groups.length; g++) for (char c : groups[g].toCharArray()) mp[c - 'a'] = g + 1;
        int n = word.length(), cnt = 0;
        for (int i = 0; i < n; i++) {
            long s = 0;
            for (int j = i; j < n; j++) {
                s += mp[word.charAt(j) - 'a'];
                if (s % (j - i + 1) == 0) cnt++;
            }
        }
        return cnt;
    }
}

class Solution {
public:
    int numberOfDivisibleSubstrings(string word) {
        int mp[26] = {0};
        string groups[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        for (int g = 0; g < 8; g++) for (char c : groups[g]) mp[c - 'a'] = g + 1;
        int n = word.size(), cnt = 0;
        for (int i = 0; i < n; i++) {
            long long s = 0;
            for (int j = i; j < n; j++) {
                s += mp[word[j] - 'a'];
                if (s % (j - i + 1) == 0) cnt++;
            }
        }
        return cnt;
    }
};

There are n bricks arranged in a row at positions numbered from 1 through n, inclusive. There is an array, newtons[n], that contains an integer indicating the number of newtons required to smash a brick. (A newton is a unit of force.) There are two hammers, one big and one small. The big hammer can smash any brick with one blow. The small hammer reduces the newtons required by 1 for each blow to a brick. For example, a brick requires 3 newtons of force. It will take 1 blow with the big hammer, or 3 blows with the small hammer to smash it. There is a limit to how many times the big hammer can be used. Determine 3 values: the minimum number of blows to smash all the bricks the 1-based indices of the bricks smashed by the big hammer sorted ascending the 1-based indices of the bricks smashed by the small hammer sorted ascending Return the values as a 2-dimensional integer array, [[total hits], [big hammer hits], [small hammer hits]]. If a hammer is not used, its index array should be [-1]. Function Description Complete the function smashTheBricks in the editor below. smashTheBricks has the following parameters:

• int bigHits: the maximum blows with the big hammer
• int newtons[n]: the newtons required to smash each brick Returns long [][], [p][q]: in the form [[ total hits], [sorted indices for big hammer hits], [sorted indices for small hammer hits]]

Constraints

• 1 ≤ n ≤ 2 x 10⁵
• 0 ≤ bigHits ≤ 2 x 10⁵
• 1 ≤ newtons[i] ≤ 10⁹
• Elements in newtons[] are distinct.

Example 1

Input:

bigHits = 0
newtons = [2]

Output:

[[2], [-1], [1]]

Explanation: The big hammer cannot be used. The small hammer takes 2 blows to smash the single brick at index 1. The return array is [[2], [-1], [1]].

Example 2

Input:

bigHits = 4
newtons = [3, 2, 5, 4, 6, 7, 9]

Output:

[[13], [3, 5, 6, 7], [1, 2, 4]]

Explanation: In this case, it is best to use the big hammer on bricks at sorted indices [3, 5, 7], using 4 hits to smash them all. The small hammer is used on sorted indices [1, 2, 4], which have newtons of 3, 2, and 4. It takes a total of 3 + 2 + 4 = 9 hits with the small hammer. The total blows required = 4 + 9 = 13. The return array is [[13], [3, 5, 6, 7], [1, 2, 4]].

Example 3

Input:

bigHits = 9
newtons = [7, 9, 3, 2, 5, 8, 4, 6]

Output:

[[8], [1, 2, 3, 4, 5, 6, 7, 8], [-1]]

Explanation: There are enough bigHits available to smash all of the bricks with the large hammer. The returned arr is [[8], [1, 2, 3, 4, 5, 6, 7, 8], [-1]]:)

Example 4

Input:

bigHits = 0
newtons = [10000000, 100000000, 1000000000]

Output:

[[1110000000], [-1], [1, 2, 3]]

Explanation: Since bigHits =0, the big hammer cannot be used. The toal hits required is the sum of the newtons arr, one hit with a small hammer for each newton. The returned arr is [[1110000000], [-1], [1, 2, 3]] :P

解法

贪心：把 bigHits 用在 newtons 最大的若干砖上。先按 newtons 降序排，取前 bigHits 个用大锤(其余用小锤)。结果按原 1-based 索引升序输出。时间复杂度 O(n log n)。

from typing import List

def smashTheBricks(bigHits: int, newtons: List[int]) -> List[List[int]]:
    n = len(newtons)
    indexed = sorted(range(n), key=lambda i: -newtons[i])
    big = sorted(i + 1 for i in indexed[:bigHits])
    small = sorted(i + 1 for i in indexed[bigHits:])
    small_hits = sum(newtons[i - 1] for i in small)
    total = len(big) + small_hits
    if not big: big = [-1]
    if not small: small = [-1]
    return [[total], big, small]

class Solution {
    long[][] smashTheBricks(int bigHits, int[] newtons) {
        int n = newtons.length;
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> newtons[b] - newtons[a]);
        int take = Math.min(bigHits, n);
        List<Long> big = new ArrayList<>(), small = new ArrayList<>();
        for (int i = 0; i < take; i++) big.add((long) idx[i] + 1);
        for (int i = take; i < n; i++) small.add((long) idx[i] + 1);
        Collections.sort(big); Collections.sort(small);
        long smallHits = 0;
        for (long i : small) smallHits += newtons[(int) i - 1];
        long total = big.size() + smallHits;
        long[][] res = new long[3][];
        res[0] = new long[]{total};
        res[1] = big.isEmpty() ? new long[]{-1} : big.stream().mapToLong(Long::longValue).toArray();
        res[2] = small.isEmpty() ? new long[]{-1} : small.stream().mapToLong(Long::longValue).toArray();
        return res;
    }
}

class Solution {
public:
    vector<vector<long long>> smashTheBricks(int bigHits, vector<int>& newtons) {
        int n = newtons.size();
        vector<int> idx(n);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int a, int b) { return newtons[a] > newtons[b]; });
        int take = min(bigHits, n);
        vector<long long> big, small;
        for (int i = 0; i < take; i++) big.push_back(idx[i] + 1);
        for (int i = take; i < n; i++) small.push_back(idx[i] + 1);
        sort(big.begin(), big.end()); sort(small.begin(), small.end());
        long long smallHits = 0;
        for (auto i : small) smallHits += newtons[i - 1];
        long long total = big.size() + smallHits;
        vector<vector<long long>> res(3);
        res[0] = {total};
        res[1] = big.empty() ? vector<long long>{-1} : big;
        res[2] = small.empty() ? vector<long long>{-1} : small;
        return res;
    }
};

We consider a binary string (i.e., a string consisting of 0s and 1s) to be magical if it satisfies the following constraints: It starts with the character 1. The string contains at least two 0s. The string contains an even number of 0s. For example, 1010001 is magical, but 01000 and 1000 are not. Complete the code in the editor below by replacing the blank (i.e., “________”) with a regular expression that matches magical strings according to the criteria above. Locked code in the editor prints True for each correct match and False for each incorrect match. Function Description Replace the blank in the editor below with a regex expression. If your expression matches, the code will print True. Otherwise it will print False.

Constraints

• 1 ≤ query ≤ 10³
• 1 ≤ string length ≤ 10³

Example 1

Input:

s = "1001"

Output:

"True"

Explanation: 1001 starts with a 1 and contains an even number of 0s, so it's magical.

Example 2

Input:

s = "11000"

Output:

"False"

Explanation: 11000 starts with a 1 but contains an odd number of 0s, so it's not magical.

Example 3

Input:

s = "0101"

Output:

"False"

Explanation: 0101 starts with a 0, so it's not magical.

Example 4

Input:

s = "1010"

Output:

"True"

Explanation: 1010 starts with a 1 and contains an even number of 0s, so it's magical.

Example 5

Input:

s = "1111"

Output:

"False"

Explanation: 1111 starts with a 1 but doesn't contain at least two 0s, so it's not magical.