Count four-digit codes (0000 through 9999, leading zeros allowed) whose decimal digit sum equals S. Returns the count.
Example
solution(35) = 4 (9998, 9989, 9899, 8999)
solution(4) = 35 (e.g. 0022, 1003, 1111, 2020, 4000, ...)
solution(2) = 10 (0002, 0011, 0020, 0101, 0110, 0200, 1001, 1010, 1100, 2000)Constraints
0 <= S <= 36.
解法
暴力枚举 0..9999，求数位和并计数匹配。S 在 [0, 36]、范围只有 10000，速度无压力。复杂度 O(10⁴)。
def solution(S: int) -> int:
if S < 0 or S > 36:
return 0
count = 0
for n in range(10000):
digit_sum = (n // 1000) + (n // 100 % 10) + (n // 10 % 10) + (n % 10)
if digit_sum == S:
count += 1
return countclass Solution {
public int solution(int S) {
if (S < 0 || S > 36) return 0;
int count = 0;
for (int n = 0; n < 10000; n++) {
int digitSum = (n / 1000) + (n / 100 % 10) + (n / 10 % 10) + (n % 10);
if (digitSum == S) count++;
}
return count;
}
}class Solution {
public:
int solution(int S) {
if (S < 0 || S > 36) return 0;
int count = 0;
for (int n = 0; n < 10000; n++) {
int digitSum = (n / 1000) + (n / 100 % 10) + (n / 10 % 10) + (n % 10);
if (digitSum == S) count++;
}
return count;
}
};There is a board with N cells (numbered 0 to N-1). Each cell holds a token (T) or is empty (E). Each cell with a token contributes points[i]; additionally, every adjacent T-T pair contributes 1 bonus point. Return the total score.
Example
solution([3, 4, 5, 2, 3], "TEETT") = 9
Token cells 0, 3, 4: 3 + 2 + 3 = 8. Adjacent pair (3,4): +1. Total 9.
solution([3, 2, 1, 2, 2], "ETTTE") = 7
Token cells 1, 2, 3: 2 + 1 + 2 = 5. Adjacent pairs (1,2), (2,3): +2. Total 7.
solution([2, 2, 2, 2], "TTTT") = 11
Token cells all: 8. Adjacent pairs (0,1),(1,2),(2,3): +3. Total 11.Constraints
1 <= N <= 1001 <= points[i] <= 1000tokensconsists of'E'and'T'only.
解法
第一遍累加 tokens[i] == 'T' 处的 points[i]，第二遍数相邻 T-T 对。复杂度 O(N)。
from typing import List
def solution(points: List[int], tokens: str) -> int:
n = len(points)
ans = 0
for i in range(n):
if tokens[i] == 'T':
ans += points[i]
for i in range(n - 1):
if tokens[i] == 'T' and tokens[i + 1] == 'T':
ans += 1
return ansclass Solution {
public int solution(int[] points, String tokens) {
int n = points.length;
int ans = 0;
for (int i = 0; i < n; i++) {
if (tokens.charAt(i) == 'T') ans += points[i];
}
for (int i = 0; i < n - 1; i++) {
if (tokens.charAt(i) == 'T' && tokens.charAt(i + 1) == 'T') ans++;
}
return ans;
}
}#include <string>
#include <vector>
class Solution {
public:
int solution(std::vector<int>& points, std::string& tokens) {
int n = (int) points.size();
int ans = 0;
for (int i = 0; i < n; i++) {
if (tokens[i] == 'T') ans += points[i];
}
for (int i = 0; i < n - 1; i++) {
if (tokens[i] == 'T' && tokens[i + 1] == 'T') ans++;
}
return ans;
}
};There is an array A of N integers. A triplet is a sequence of three consecutive elements whose sum is 0. Each element of A may belong to at most one triplet. Return the largest number of triplets that can be selected simultaneously.
Example
A = [-4, 1, 0, -1, 0, 0, 0, 0, 0]
Pick triplet at indices (1,2,3) = (1, 0, -1). Remaining zeros at indices 4..8.
From those 5 zeros, one triplet of three consecutive zeros (4,5,6). Answer: 2.
A = [-1, 3, -1, 2, -1, 0, -3] -> 1 (only (-1, 2, -1) at indices 2..4)
A = [-1, -2, 3, -1, 0, 1] -> 2Constraints
1 <= N <= 100-100 <= A[i] <= 100
解法
下标 DP：dp[i] = A[0..i-1] 中三元组最大个数。转移 dp[i] = dp[i-1]，若 i >= 3 且 A[i-3]+A[i-2]+A[i-1] == 0，则 dp[i] = max(dp[i], dp[i-3] + 1)。复杂度 O(N)。
def solution(A):
n = len(A)
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i - 1]
if i >= 3 and A[i - 3] + A[i - 2] + A[i - 1] == 0:
dp[i] = max(dp[i], dp[i - 3] + 1)
return dp[n]class Solution {
public static int solution(int[] A) {
int n = A.length;
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1];
if (i >= 3 && A[i - 3] + A[i - 2] + A[i - 1] == 0) {
dp[i] = Math.max(dp[i], dp[i - 3] + 1);
}
}
return dp[n];
}
}#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int>& A) {
int n = A.size();
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1];
if (i >= 3 && A[i - 3] + A[i - 2] + A[i - 1] == 0) {
dp[i] = max(dp[i], dp[i - 3] + 1);
}
}
return dp[n];
}