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).
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理