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 ≤ 2000wordconsists only of lowercase English letters.
Example 1
Input:
word = "asdf"Output:
6Explanation: 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:
4Explanation: 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:
6Explanation: 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 cntclass 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 hammerint 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;
}
};