Given an integer n, your task is to calculate the alternating sum of its digits. In other words, add up all the digits, taking the first digit with a positive sign, the second digit with a negative sign, the third digit with a positive sign, etc.
n = 521314→5 - 2 + 1 - 3 + 1 - 4 = -2n = 12134→1n = 104956→-5
解法
转字符串，按下标奇偶给每位数字定符号(偶位 +，奇位 -)求和。复杂度 O(log n)。
def solution(n: int) -> int:
s = str(n)
return sum((1 if i % 2 == 0 else -1) * int(c) for i, c in enumerate(s))class Solution {
static int solution(int n) {
String s = String.valueOf(n);
int sum = 0;
for (int i = 0; i < s.length(); i++)
sum += (i % 2 == 0 ? 1 : -1) * (s.charAt(i) - '0');
return sum;
}
}#include <string>
using namespace std;
int solution(int n) {
string s = to_string(n);
int sum = 0;
for (int i = 0; i < (int)s.size(); i++)
sum += (i % 2 == 0 ? 1 : -1) * (s[i] - '0');
return sum;
}You have a deck of cards numbered from 1 to n. The cards are currently in some order; you want to sort them ascending. The only operation: take k cards from the top of the deck and move them to the bottom (k ∈ [0, n-1]). Return the minimum number of cards k to move, or -1 if impossible.
deck = [1, 4, 2, 3]→-1deck = [3, 4, 5, 1, 2]→3
解法
找到 1 的位置，验证从该位置起的剩余 n-1 张牌构成循环升序。答案为 1 的下标，否则返回 -1。复杂度 O(n)。
def solution(deck: list[int]) -> int:
n = len(deck)
if 1 not in deck: return -1
pos = deck.index(1)
for i in range(n):
if deck[(pos + i) % n] != i + 1:
return -1
return posclass Solution {
static int solution(int[] deck) {
int n = deck.length, pos = -1;
for (int i = 0; i < n; i++) if (deck[i] == 1) { pos = i; break; }
if (pos < 0) return -1;
for (int i = 0; i < n; i++)
if (deck[(pos + i) % n] != i + 1) return -1;
return pos;
}
}#include <vector>
using namespace std;
int solution(vector<int>& deck) {
int n = deck.size(), pos = -1;
for (int i = 0; i < n; i++) if (deck[i] == 1) { pos = i; break; }
if (pos < 0) return -1;
for (int i = 0; i < n; i++)
if (deck[(pos + i) % n] != i + 1) return -1;
return pos;
}You are exploring a labyrinth in the shape of a rectangular matrix, which contains obstacles and teleports. Starting from the upper-left cell (0, 0), you need to reach the lower-right cell (n-1, m-1) while moving through as many cells as possible. You are given n × m grid size, obstacles list of [r, c] cells that are blocked, and teleports list of [src_r, src_c, dest_r, dest_c] pairs.
Rules:
-
From a cell
(r, c), you can move to(r+1, c)or(r, c+1)if it's within bounds and not blocked. -
If the cell you just stepped onto is a teleport source, you are immediately teleported to its destination. Teleports may chain.
-
Loop detection: if teleports trap you in an infinite loop, return
-2. -
If you cannot reach the goal, return
-1. -
Otherwise return the maximum number of cells visited (counting starting cell, all walked cells, and all teleport endpoints).
-
n=3, m=3, obstacles=[[2,1]], teleports=[[0,1,2,0]]→-1 -
n=3, m=4, obstacles=[[1,1]], teleports=[[0,2,0,1],[0,3,2,0]]→-2 -
n=3, m=4, obstacles=[[2,0],[1,0]], teleports=[[0,1,1,1],[1,2,0,2],[0,3,2,1]]→9 -
n=3, m=4, obstacles=[[0,2]], teleports=[[1,3,0,3]]→6
解法
向下/向右 DFS；每到一格用本地 seen 集合解析传送链以检测环。每条路径分支独立记访问格；在所有到达终点的分支中取最大。最坏 O(paths)，受网格大小限制。
def solution(n, m, obstacles, teleports):
blocked = set(map(tuple, obstacles))
tele = {(s_r, s_c): (d_r, d_c) for s_r, s_c, d_r, d_c in teleports}
GOAL = (n - 1, m - 1)
has_loop = [False]
best = [-1]
def resolve(pos, visited):
cur = pos
local_seen = set()
while cur in tele:
if cur in local_seen:
has_loop[0] = True
return None, visited
local_seen.add(cur)
visited = visited | {cur}
cur = tele[cur]
visited = visited | {cur}
return cur, visited
def dfs(pos, visited):
if pos == GOAL:
best[0] = max(best[0], len(visited))
return
r, c = pos
for dr, dc in [(1, 0), (0, 1)]:
nr, nc = r + dr, c + dc
if not (0 <= nr < n and 0 <= nc < m): continue
if (nr, nc) in blocked: continue
new_pos, new_visited = resolve((nr, nc), visited)
if new_pos is None: continue
dfs(new_pos, new_visited)
start, init_visited = resolve((0, 0), set())
if start is not None:
dfs(start, init_visited)
if best[0] == -1:
return -2 if has_loop[0] else -1
return best[0]import java.util.*;
class Solution {
int n, m;
Set<Long> blocked;
Map<Long, Long> tele;
long goalKey;
boolean hasLoop;
int best;
long key(int r, int c) { return (long) r * m + c; }
Long resolve(long pos, Set<Long> visited) {
Set<Long> local = new HashSet<>();
long cur = pos;
while (tele.containsKey(cur)) {
if (!local.add(cur)) { hasLoop = true; return null; }
visited.add(cur);
cur = tele.get(cur);
}
visited.add(cur);
return cur;
}
void dfs(long pos, Set<Long> visited) {
if (pos == goalKey) {
best = Math.max(best, visited.size());
return;
}
int r = (int) (pos / m), c = (int) (pos % m);
int[][] dirs = {{1, 0}, {0, 1}};
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
long nk = key(nr, nc);
if (blocked.contains(nk)) continue;
Set<Long> nv = new HashSet<>(visited);
Long res = resolve(nk, nv);
if (res == null) continue;
dfs(res, nv);
}
}
int solution(int n, int m, int[][] obstacles, int[][] teleports) {
this.n = n; this.m = m;
blocked = new HashSet<>();
for (int[] o : obstacles) blocked.add(key(o[0], o[1]));
tele = new HashMap<>();
for (int[] t : teleports) tele.put(key(t[0], t[1]), key(t[2], t[3]));
goalKey = key(n - 1, m - 1);
hasLoop = false; best = -1;
Set<Long> init = new HashSet<>();
Long start = resolve(key(0, 0), init);
if (start != null) dfs(start, init);
if (best == -1) return hasLoop ? -2 : -1;
return best;
}
}#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
int n, m;
unordered_set<long long> blocked;
unordered_map<long long, long long> tele;
long long goalKey;
bool hasLoop;
int best;
long long key(int r, int c) { return (long long) r * m + c; }
bool resolve(long long pos, unordered_set<long long>& visited, long long& out) {
unordered_set<long long> local;
long long cur = pos;
while (tele.count(cur)) {
if (local.count(cur)) { hasLoop = true; return false; }
local.insert(cur);
visited.insert(cur);
cur = tele[cur];
}
visited.insert(cur);
out = cur;
return true;
}
void dfs(long long pos, unordered_set<long long> visited) {
if (pos == goalKey) {
best = max(best, (int) visited.size());
return;
}
int r = (int)(pos / m), c = (int)(pos % m);
int dirs[2][2] = {{1, 0}, {0, 1}};
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
long long nk = key(nr, nc);
if (blocked.count(nk)) continue;
auto nv = visited;
long long out;
if (!resolve(nk, nv, out)) continue;
dfs(out, nv);
}
}
int solution(int n_, int m_, vector<vector<int>>& obstacles, vector<vector<int>>& teleports) {
n = n_; m = m_;
for (auto& o : obstacles) blocked.insert(key(o[0], o[1]));
for (auto& t : teleports) tele[key(t[0], t[1])] = key(t[2], t[3]);
goalKey = key(n - 1, m - 1);
hasLoop = false; best = -1;
unordered_set<long long> init;
long long start;
if (resolve(key(0, 0), init, start)) dfs(start, init);
if (best == -1) return hasLoop ? -2 : -1;
return best;
}
};