There is a small, one-way bridge that can carry a maximum weight of U units at a time. A line of N cars is waiting with weights weight[0..N-1] (entering in that order).
At most two cars can be on the bridge at once. To begin, the first two cars enter. After that, car k enters as soon as car k - 2 leaves (i.e., the bridge always holds two consecutive cars from the kept sequence). Cars leave in entry order.
If at any moment the total weight on the bridge would exceed U, some drivers have to turn back. A driver who turns back is removed from the line and never tries again. Return the minimum number of drivers that must turn back so the bridge is never overloaded.
Constraints
1 ≤ N ≤ 100000, 1 ≤ weight[i] ≤ 10⁹, 1 ≤ U ≤ 10⁹.
Examples:
U = 9, weight = [5, 3, 8, 1, 8, 7, 7, 6]→4. Remaining[5, 3, 1, 6]crosses safely.U = 7, weight = [7, 6, 5, 2, 7, 4, 5, 4]→5. Remaining[5, 2, 4].U = 7, weight = [3, 4, 3, 1]→0.U = 2, weight = [3, 7, 5, 5, 6, 3, 9, 10, 8, 4]→10(every weight> U).
解法
保留一个保持原顺序的子序列，要求：(1) 每个保留的重量 ≤ U；(2) 任意相邻两个保留之和 ≤ U。求最少去除数。贪心从左到右扫描，维护 prev = 上一辆保留车的重量；prev + w > U 时退掉更重的那辆，让保留邻居尽量轻。单车 w > U 一定退。复杂度 O(N)。
def min_turn_back(U, weight):
turnbacks = 0
prev = None
for w in weight:
if w > U:
turnbacks += 1
continue
if prev is None:
prev = w
elif prev + w <= U:
prev = w
else:
turnbacks += 1
if w < prev:
prev = w
return turnbacksclass Solution {
public int solution(int U, int[] weight) {
int turnbacks = 0;
long prev = -1;
for (int w : weight) {
if (w > U) { turnbacks++; continue; }
if (prev < 0) { prev = w; }
else if (prev + w <= U) { prev = w; }
else {
turnbacks++;
if (w < prev) prev = w;
}
}
return turnbacks;
}
}int solution(int U, vector<int>& weight) {
int turnbacks = 0;
long long prev = -1;
for (int w : weight) {
if (w > U) { turnbacks++; continue; }
if (prev < 0) prev = w;
else if (prev + w <= U) prev = w;
else {
turnbacks++;
if (w < prev) prev = w;
}
}
return turnbacks;
}Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.
Implement an LRU (Least Recently Used) cache that supports:
LRUCache(capacity): initialize the cache with the given positive capacity.
get(key): return the value if the key exists and mark it as most recently used; otherwise return -1.
put(key, value): insert or update the key with the value and mark it as most recently used; if the cache exceeds capacity, evict the least recently used entry.
Requirements:
Target time complexity: O(1) per get/put.
Constraints
Number of operations: 1 ≤ N ≤ 2 * 10⁵
key, value are 32-bit integers
Input:
capacity=2
put(1,1)
put(2,2)
get(1)
put(3,3)
get(2)
put(4,4)
get(1)
get(3)
get(4)
Output:
1
-1
3
4
Input:
capacity=1
put(1,1)
put(2,2)
get(1)
get(2)
Output:
-1
2
Input:
capacity=2
put(1,1)
put(1,10)
get(1)
Output:
10
Input:
capacity=3
get(42)
Output:
-1
Input:
capacity=2
put(1,1)
put(2,2)
put(3,3)
get(1)
get(2)
get(3)
Output:
-1
2
3
Example
Input
capacity=2
put(1,1)
put(2,2)
get(1)
put(3,3)
get(2)
put(4,4)
get(1)
get(3)
get(4)
Output
1
-1
3
4
Function Description
Complete solveLRUCacheOperations. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.
Constraints
Use the limits and requirements stated in the prompt.
Example 1
Input:
input = "capacity=2\nput(1,1)\nput(2,2)\nget(1)\nput(3,3)\nget(2)\nput(4,4)\nget(1)\nget(3)\nget(4)"Output:
["1", "-1", "-1", "3", "4"]Explanation: The returned string array must match the expected standard output lines for the sample input.
解法
经典 LRU：用「哈希表 + 双向链表」实现 O(1) 的 get/put。get 命中把节点移到队头，put 时若已存在则更新并移到队头，否则插入队头，超出容量从队尾淘汰。每次操作 O(1)，空间 O(capacity)。
from collections import OrderedDict
from typing import List
class LRUCache:
def __init__(self, capacity: int) -> None:
self.cap = capacity
self.data: "OrderedDict[int, int]" = OrderedDict()
def get(self, key: int) -> int:
if key not in self.data:
return -1
self.data.move_to_end(key)
return self.data[key]
def put(self, key: int, value: int) -> None:
if key in self.data:
self.data.move_to_end(key)
self.data[key] = value
if len(self.data) > self.cap:
self.data.popitem(last=False)
def solveLRUCacheOperations(input: str) -> List[str]:
lines = input.strip().split("\n")
cap = int(lines[0].split("=")[1])
cache = LRUCache(cap)
out: List[str] = []
for line in lines[1:]:
if line.startswith("put"):
inside = line[line.index("(") + 1: line.rindex(")")]
k, v = (int(x) for x in inside.split(","))
cache.put(k, v)
elif line.startswith("get"):
k = int(line[line.index("(") + 1: line.rindex(")")])
out.append(str(cache.get(k)))
return outimport java.util.*;
class LRUCache {
private final int cap;
private final LinkedHashMap<Integer, Integer> map;
LRUCache(int capacity) {
this.cap = capacity;
this.map = new LinkedHashMap<>(capacity, 0.75f, true) {
@Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> e) {
return size() > cap;
}
};
}
int get(int key) { return map.getOrDefault(key, -1); }
void put(int key, int value) { map.put(key, value); }
}
class Solution {
String[] solveLRUCacheOperations(String input) {
String[] lines = input.strip().split("\n");
int cap = Integer.parseInt(lines[0].split("=")[1].trim());
LRUCache cache = new LRUCache(cap);
List<String> out = new ArrayList<>();
for (int i = 1; i < lines.length; i++) {
String line = lines[i].trim();
int lp = line.indexOf('('), rp = line.lastIndexOf(')');
String inside = line.substring(lp + 1, rp);
if (line.startsWith("put")) {
String[] kv = inside.split(",");
cache.put(Integer.parseInt(kv[0].trim()), Integer.parseInt(kv[1].trim()));
} else {
out.add(String.valueOf(cache.get(Integer.parseInt(inside.trim()))));
}
}
return out.toArray(new String[0]);
}
}#include <list>
#include <unordered_map>
#include <vector>
#include <string>
#include <sstream>
class LRUCache {
int cap;
std::list<std::pair<int,int>> dll;
std::unordered_map<int, std::list<std::pair<int,int>>::iterator> idx;
public:
LRUCache(int capacity) : cap(capacity) {}
int get(int key) {
auto it = idx.find(key);
if (it == idx.end()) return -1;
dll.splice(dll.begin(), dll, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = idx.find(key);
if (it != idx.end()) {
it->second->second = value;
dll.splice(dll.begin(), dll, it->second);
return;
}
dll.push_front({key, value});
idx[key] = dll.begin();
if ((int)dll.size() > cap) {
idx.erase(dll.back().first);
dll.pop_back();
}
}
};
class Solution {
public:
std::vector<std::string> solveLRUCacheOperations(std::string input) {
std::vector<std::string> lines;
std::stringstream ss(input);
std::string line;
while (std::getline(ss, line)) lines.push_back(line);
int cap = std::stoi(lines[0].substr(lines[0].find('=') + 1));
LRUCache cache(cap);
std::vector<std::string> out;
for (size_t i = 1; i < lines.size(); i++) {
auto& l = lines[i];
size_t lp = l.find('('), rp = l.rfind(')');
std::string inside = l.substr(lp + 1, rp - lp - 1);
if (l.rfind("put", 0) == 0) {
size_t comma = inside.find(',');
int k = std::stoi(inside.substr(0, comma));
int v = std::stoi(inside.substr(comma + 1));
cache.put(k, v);
} else {
out.push_back(std::to_string(cache.get(std::stoi(inside))));
}
}
return out;
}
};