Let's consider the following infinite sequence:
0, 1, 1, 2, 3, 5, 8, 13, 12, 7, 10, 8, 9, ...The 0th element is 0 and the 1st element is 1. The successive elements are defined recursively: each of them is the sum of the separate digits of the two previous elements.
Write int solution(int N) returning the N-th element.
Example: N = 2 → 1.
解法
从 2 迭代到 N，每步把前两项各自的数位和相加。复杂度 O(N · log V)。
def solution(N: int) -> int:
if N == 0:
return 0
if N == 1:
return 1
a, b = 0, 1
for _ in range(2, N + 1):
s = sum(int(c) for c in str(a)) + sum(int(c) for c in str(b))
a, b = b, s
return bclass Solution {
public int solution(int N) {
if (N == 0) return 0;
if (N == 1) return 1;
int a = 0, b = 1;
for (int i = 2; i <= N; i++) {
int s = digitSum(a) + digitSum(b);
a = b; b = s;
}
return b;
}
private int digitSum(int x) {
int s = 0;
while (x > 0) { s += x % 10; x /= 10; }
return s;
}
}int digitSum(int x) {
int s = 0;
while (x > 0) { s += x % 10; x /= 10; }
return s;
}
int solution(int N) {
if (N == 0) return 0;
if (N == 1) return 1;
int a = 0, b = 1;
for (int i = 2; i <= N; i++) {
int s = digitSum(a) + digitSum(b);
a = b; b = s;
}
return b;
}There is a board with N cells (numbered from 0 to N−1) arranged in a row. The board is described by an array points and a string tokens, both of length N. The K-th letter of tokens is either 'T' or 'E', indicating whether the K-th cell contains a token or is empty.
If the K-th cell contains a token, we score the number of points in points[K]. Additionally, we score another point for every pair of adjacent cells with tokens. What is the total number of points scored?
Examples:
points = [3,2,1,2,2], tokens = "ETTTE"→ 7points = [2,2,2,2], tokens = "TTTT"→ 11
Constraints
1 ≤ N ≤ 100, 1 ≤ points[i] ≤ 1000, tokens[i] ∈ {E, T}.
解法
单次遍历：遇到 T 累加 points[i]；若 tokens[i-1] == tokens[i] == 'T' 再额外加 1。复杂度 O(N)。
def solution(points, tokens):
n = len(points)
score = 0
for i in range(n):
if tokens[i] == 'T':
score += points[i]
if i > 0 and tokens[i-1] == 'T':
score += 1
return scoreclass Solution {
public int solution(int[] points, String tokens) {
int n = points.length, score = 0;
for (int i = 0; i < n; i++) {
if (tokens.charAt(i) == 'T') {
score += points[i];
if (i > 0 && tokens.charAt(i - 1) == 'T') score += 1;
}
}
return score;
}
}int solution(vector<int>& points, string& tokens) {
int n = points.size(), score = 0;
for (int i = 0; i < n; i++) {
if (tokens[i] == 'T') {
score += points[i];
if (i > 0 && tokens[i - 1] == 'T') score += 1;
}
}
return score;
}