To reduce the size of messages transmitted over the internet, a compression algorithm encodes consecutive repeating characters in a string. Your task is to compress the given string using this rule:
- Scan the string from left to right and group consecutive identical characters.
- If a character appears once, add just the character to the output.
- If a character appears more than once in a row, add the character followed by the number of consecutive occurrences.
Example: message = "aabbccca" → "a2b2c3a".
Constraints
all chars in [a-z], length ≤ 10⁵.
解法
双指针扫描：合并连续相同字符；输出字符，仅当个数 > 1 时再输出个数。复杂度 O(n)。
def compressedString(message: str) -> str:
out = []
i, n = 0, len(message)
while i < n:
j = i
while j < n and message[j] == message[i]:
j += 1
cnt = j - i
out.append(message[i] + (str(cnt) if cnt > 1 else ''))
i = j
return ''.join(out)class Solution {
static String compressedString(String message) {
StringBuilder sb = new StringBuilder();
int n = message.length(), i = 0;
while (i < n) {
int j = i;
while (j < n && message.charAt(j) == message.charAt(i)) j++;
sb.append(message.charAt(i));
if (j - i > 1) sb.append(j - i);
i = j;
}
return sb.toString();
}
}#include <string>
using namespace std;
string compressedString(string message) {
string out;
int n = message.size(), i = 0;
while (i < n) {
int j = i;
while (j < n && message[j] == message[i]) j++;
out += message[i];
if (j - i > 1) out += to_string(j - i);
i = j;
}
return out;
}Given a permutation p[] of length n, a subarray p[l..r] of length k = r - l + 1 is balanced if {p[l], p[l+1], ..., p[r]} == {1, 2, ..., k} (i.e., it's a permutation of the first k positive integers).
Return a binary string out of length n where out[k-1] = '1' if there exists at least one balanced subarray of length k, else '0'.
Examples:
p = [4, 1, 3, 2]→"1011"(k=1: any single element trivially balanced; k=2:[1,3]has values{1,3}≠{1,2}, so look further — actuallyout[1]='0'because no length-2 window equals{1,2}; k=3:[1,3,2]={1,2,3}; k=4: whole array ={1,2,3,4}).p = [2, 3, 1]→"101".
解法
对每个窗口长度 k，单调队列维护 max 和 min。窗口平衡当且仅当 max == k 且 min == 1。外层枚举 k、内层滑窗，最坏 O(n²)。
from collections import deque
def countBalancedNumbers(p):
n = len(p)
out = ['0'] * n
for k in range(1, n + 1):
mxq, mnq = deque(), deque()
for i in range(n):
while mxq and p[mxq[-1]] <= p[i]: mxq.pop()
mxq.append(i)
while mnq and p[mnq[-1]] >= p[i]: mnq.pop()
mnq.append(i)
if mxq[0] <= i - k: mxq.popleft()
if mnq[0] <= i - k: mnq.popleft()
if i >= k - 1 and p[mxq[0]] == k and p[mnq[0]] == 1:
out[k - 1] = '1'
break
return ''.join(out)import java.util.*;
class Solution {
static String countBalancedNumbers(int[] p) {
int n = p.length;
char[] out = new char[n];
Arrays.fill(out, '0');
for (int k = 1; k <= n; k++) {
Deque<Integer> mxq = new ArrayDeque<>(), mnq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!mxq.isEmpty() && p[mxq.peekLast()] <= p[i]) mxq.pollLast();
mxq.offerLast(i);
while (!mnq.isEmpty() && p[mnq.peekLast()] >= p[i]) mnq.pollLast();
mnq.offerLast(i);
if (mxq.peekFirst() <= i - k) mxq.pollFirst();
if (mnq.peekFirst() <= i - k) mnq.pollFirst();
if (i >= k - 1 && p[mxq.peekFirst()] == k && p[mnq.peekFirst()] == 1) {
out[k - 1] = '1';
break;
}
}
}
return new String(out);
}
}#include <bits/stdc++.h>
using namespace std;
string countBalancedNumbers(vector<int>& p) {
int n = p.size();
string out(n, '0');
for (int k = 1; k <= n; k++) {
deque<int> mxq, mnq;
for (int i = 0; i < n; i++) {
while (!mxq.empty() && p[mxq.back()] <= p[i]) mxq.pop_back();
mxq.push_back(i);
while (!mnq.empty() && p[mnq.back()] >= p[i]) mnq.pop_back();
mnq.push_back(i);
if (mxq.front() <= i - k) mxq.pop_front();
if (mnq.front() <= i - k) mnq.pop_front();
if (i >= k - 1 && p[mxq.front()] == k && p[mnq.front()] == 1) {
out[k - 1] = '1';
break;
}
}
}
return out;
}Objects are moving along a table of length tableLength. The position of the i-th object is given by position[i], when 0 <= position[i] < tableLength. The left end of the line is at coordinate 0, and the right end is at coordinate tableLength. A positive velocity means moving towards the right end, and a negative velocity means moving towards the left end.
When two objects collide, their velocities are exchanged. Objects are removed if they move left of coordinate 0 or right of coordinate tableLength. All objects keep moving simultaneously at time 0.
Your task is to find the time in seconds when the last object exits the line. The answer should be rounded to the nearest integer (ceiling).
解法
一维弹性碰撞 = 交换标签 = 每个粒子独立处理。最后出局时间 = ceil(max_i (distance-to-nearest-exit / |v|))。复杂度 O(N)。
import math
def calculateLastExitTime(position, velocity, tableLength):
times = []
for p, v in zip(position, velocity):
if v > 0:
times.append((tableLength - p) / v)
elif v < 0:
times.append(p / (-v))
else:
times.append(float('inf'))
return math.ceil(max(times))class Solution {
static long calculateLastExitTime(int[] position, int[] velocity, int tableLength) {
double best = 0;
for (int i = 0; i < position.length; i++) {
double t;
if (velocity[i] > 0) t = (tableLength - position[i]) / (double) velocity[i];
else if (velocity[i] < 0) t = position[i] / (double) -velocity[i];
else continue;
if (t > best) best = t;
}
return (long) Math.ceil(best);
}
}#include <vector>
#include <cmath>
using namespace std;
long long calculateLastExitTime(vector<int>& position, vector<int>& velocity, int tableLength) {
double best = 0;
for (size_t i = 0; i < position.size(); i++) {
double t;
if (velocity[i] > 0) t = (tableLength - position[i]) / (double) velocity[i];
else if (velocity[i] < 0) t = position[i] / (double) -velocity[i];
else continue;
if (t > best) best = t;
}
return (long long) ceil(best);
}