Given an array of integers numbers, construct a new array following this rule:
- 1st element of new = 1st of
numbers - 2nd of new = last of
numbers - 3rd of new = 2nd of
numbers - 4th of new = 2nd-to-last of
numbers - ... alternating front/back.
Example: numbers = [1, 6, 9, 4, 3, 7, 8] → [1, 8, 6, 7, 9, 3, 4].
Constraints
5 ≤ n ≤ 1000.
解法
双指针 l = 0、r = n - 1，交替 append(numbers[l++]) 和 append(numbers[r--])，直到 l > r。复杂度 O(N)。
def zigzag(numbers):
l, r = 0, len(numbers) - 1
out = []
while l <= r:
out.append(numbers[l]); l += 1
if l <= r:
out.append(numbers[r]); r -= 1
return outclass Solution {
static int[] zigzag(int[] numbers) {
int n = numbers.length, l = 0, r = n - 1, i = 0;
int[] out = new int[n];
while (l <= r) {
out[i++] = numbers[l++];
if (l <= r) out[i++] = numbers[r--];
}
return out;
}
}#include <vector>
using namespace std;
vector<int> zigzag(vector<int>& numbers) {
int n = numbers.size(), l = 0, r = n - 1;
vector<int> out;
while (l <= r) {
out.push_back(numbers[l++]);
if (l <= r) out.push_back(numbers[r--]);
}
return out;
}Given a string message and integer n, replace every n-th consonant in the message with the next consonant in the alphabet (case-preserving; wraps z -> b, Z -> B). Vowels and non-letters are skipped when counting consonants. The "next consonant" also skips over vowels.
Note: code uses {/[ (ASCII 123 / 91) as the natural step past z / Z; the wrap rule then rolls them back to b / B (skipping a / A because a is a vowel).
解法
遍历字符串维护辅音计数；每第 n 个辅音字符向后位移一位，跳过元音，z 回绕到 b。复杂度 O(N)。
def shift_consonant(message, n):
vowels = set("aeiouAEIOU")
res = list(message)
cnt = 0
for i, c in enumerate(res):
if c.isalpha() and c not in vowels:
cnt += 1
if cnt % n == 0:
nx = c
while True:
nx = chr(ord(nx) + 1)
if nx == '{':
nx = 'b'
elif nx == '[':
nx = 'B'
if nx not in vowels:
break
res[i] = nx
return ''.join(res)class Solution {
static String shiftConsonant(String message, int n) {
StringBuilder sb = new StringBuilder(message);
int cnt = 0;
String vowels = "aeiouAEIOU";
for (int i = 0; i < sb.length(); i++) {
char c = sb.charAt(i);
if (Character.isLetter(c) && vowels.indexOf(c) < 0) {
cnt++;
if (cnt % n == 0) {
char nx = c;
do {
nx = (char) (nx + 1);
if (nx == 'z' + 1) nx = 'b';
else if (nx == 'Z' + 1) nx = 'B';
} while (vowels.indexOf(nx) >= 0);
sb.setCharAt(i, nx);
}
}
}
return sb.toString();
}
}#include <string>
using namespace std;
string shiftConsonant(string message, int n) {
string vowels = "aeiouAEIOU";
int cnt = 0;
for (char& c : message) {
if (isalpha(c) && vowels.find(c) == string::npos) {
cnt++;
if (cnt % n == 0) {
char nx = c;
do {
nx++;
if (nx == 'z' + 1) nx = 'b';
else if (nx == 'Z' + 1) nx = 'B';
} while (vowels.find(nx) != string::npos);
c = nx;
}
}
}
return message;
}Given a 2D matrix image[h][w] (0..255 pixel intensities) and integer radius. For each pixel (i, j) whose radius-neighborhood is fully inside the image (i.e., |i - i'| <= radius and |j - j'| <= radius), replace image[i][j] with the integer mean of its neighborhood (floor). Pixels near the boundary stay unchanged.
解法
二维前缀和让任意 (2r+1) × (2r+1) 窗口和 O(1) 查询，再除以面积 (2r+1)²。复杂度 O(h · w)。
def image_blur(image, radius):
h, w = len(image), len(image[0])
pref = [[0] * (w + 1) for _ in range(h + 1)]
for i in range(h):
for j in range(w):
pref[i+1][j+1] = pref[i][j+1] + pref[i+1][j] - pref[i][j] + image[i][j]
out = [row[:] for row in image]
d = 2 * radius + 1
for i in range(radius, h - radius):
for j in range(radius, w - radius):
s = pref[i+radius+1][j+radius+1] - pref[i-radius][j+radius+1] \
- pref[i+radius+1][j-radius] + pref[i-radius][j-radius]
out[i][j] = s // (d * d)
return outclass Solution {
static int[][] imageBlur(int[][] image, int radius) {
int h = image.length, w = image[0].length;
long[][] pref = new long[h + 1][w + 1];
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
pref[i + 1][j + 1] = pref[i][j + 1] + pref[i + 1][j] - pref[i][j] + image[i][j];
int[][] out = new int[h][w];
for (int i = 0; i < h; i++) out[i] = image[i].clone();
int d = 2 * radius + 1;
for (int i = radius; i < h - radius; i++)
for (int j = radius; j < w - radius; j++) {
long s = pref[i + radius + 1][j + radius + 1] - pref[i - radius][j + radius + 1]
- pref[i + radius + 1][j - radius] + pref[i - radius][j - radius];
out[i][j] = (int) (s / ((long) d * d));
}
return out;
}
}#include <vector>
using namespace std;
vector<vector<int>> imageBlur(vector<vector<int>>& image, int radius) {
int h = image.size(), w = image[0].size();
vector<vector<long long>> pref(h + 1, vector<long long>(w + 1, 0));
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
pref[i + 1][j + 1] = pref[i][j + 1] + pref[i + 1][j] - pref[i][j] + image[i][j];
vector<vector<int>> out = image;
int d = 2 * radius + 1;
for (int i = radius; i < h - radius; i++)
for (int j = radius; j < w - radius; j++) {
long long s = pref[i + radius + 1][j + radius + 1] - pref[i - radius][j + radius + 1]
- pref[i + radius + 1][j - radius] + pref[i - radius][j - radius];
out[i][j] = (int) (s / ((long long) d * d));
}
return out;
}