You are given a string that contains a name followed by Roman numerals. Your task is to return a vector of strings that stores:
-
- The string name.
-
- The numerical value of the Roman numeral (converted to integer). The names should be in ascending order, and if the names are the same, the numbers should also be sorted in ascending order. Input Format:
- A list of strings where each string is in the format: name RomanNumeral. Output: Return a vector of strings, sorted by name and numeral value. Notes:
- The Roman numeral, when converted to a number, is at most two digits.
Example 1
Input:
strings = ["John IX", "Mary XV", "John VIII", "Mary IX"]Output:
["John 8", "John 9", "Mary 9", "Mary 15"]Explanation: The names and their corresponding Roman numerals are sorted in ascending order. The Roman numerals are converted to integers as follows:
- IX -> 9
- XV -> 15
- VIII -> 8
- IX -> 9 The sorted output is: ["John 8", "John 9", "Mary 9", "Mary 15"].
解法
每条字符串以空格分割得到 (name, roman)，把 roman 转为 int(标准罗马规则)。按 (name, value) 二级排序后拼回 "name value"。时间 O(N log N · L)。
from typing import List
VAL = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
def roman_to_int(r: str) -> int:
total = 0
for i, c in enumerate(r):
v = VAL[c]
if i + 1 < len(r) and v < VAL[r[i + 1]]:
total -= v
else:
total += v
return total
def roman_in_strings(strings: List[str]) -> List[str]:
pairs = []
for s in strings:
name, roman = s.rsplit(" ", 1)
pairs.append((name, roman_to_int(roman)))
pairs.sort()
return [f"{n} {v}" for n, v in pairs]import java.util.*;
class Solution {
static int romanToInt(String r) {
Map<Character, Integer> v = Map.of('I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000);
int total = 0;
for (int i = 0; i < r.length(); i++) {
int cur = v.get(r.charAt(i));
if (i + 1 < r.length() && cur < v.get(r.charAt(i + 1))) total -= cur; else total += cur;
}
return total;
}
public String[] romanInStrings(String[] strings) {
String[][] pairs = new String[strings.length][2];
Integer[] vals = new Integer[strings.length];
for (int i = 0; i < strings.length; i++) {
int idx = strings[i].lastIndexOf(' ');
pairs[i][0] = strings[i].substring(0, idx);
vals[i] = romanToInt(strings[i].substring(idx + 1));
}
Integer[] order = new Integer[strings.length];
for (int i = 0; i < strings.length; i++) order[i] = i;
Arrays.sort(order, (a, b) -> { int c = pairs[a][0].compareTo(pairs[b][0]); return c != 0 ? c : vals[a] - vals[b]; });
String[] out = new String[strings.length];
for (int i = 0; i < strings.length; i++) out[i] = pairs[order[i]][0] + " " + vals[order[i]];
return out;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
int romanToInt(const string& r) {
unordered_map<char, int> v = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = 0; i < (int)r.size(); i++) {
int cur = v[r[i]];
if (i + 1 < (int)r.size() && cur < v[r[i+1]]) total -= cur; else total += cur;
}
return total;
}
public:
vector<string> romanInStrings(vector<string>& strings) {
vector<pair<string, int>> p;
for (auto& s : strings) {
auto idx = s.rfind(' ');
p.push_back({s.substr(0, idx), romanToInt(s.substr(idx + 1))});
}
sort(p.begin(), p.end());
vector<string> out;
for (auto& x : p) out.push_back(x.first + " " + to_string(x.second));
return out;
}
};You are given an array of n elements and two variables, x and y.
In each operation, you can:
Subtract x from one element of the array.
Subtract y from the remaining elements.
Your task is to find the minimum number of operations required to make every element of the array ≤ 0.
Input Format:
The first line contains an integer n, the number of elements in the array.
The second line contains n space-separated integers representing the array.
The third line contains two integers, x and y, where x > y.
Output:
Print the minimum number of operations to make each element ≤ 0.
Example 1
Input:
arr = [10, 20, 30, 40, 50]
x = 5
y = 2Output:
13Explanation: To make every element ≤ 0, the minimum number of operations required is 13.
解法
二分操作次数 m。一次操作每个元素至少减 y，被选中的那个再多减 x − y。共 m 次操作后元素 a_i 至少被减 m·y，最多再额外减 m·(x−y)(若每次都被选)。所以可行 iff 存在分配 c_i ≥ 0、∑ c_i = m，使 a_i − m·y − c_i·(x−y) ≤ 0，即 c_i ≥ max(0, a_i − m·y)/(x − y)。可行 iff ∑ ≤ m。二分上界用 max(a)/y + 1。时间 O(n log V)。
from typing import List
def array_operations(arr: List[int], x: int, y: int) -> int:
def feasible(m: int) -> bool:
need = 0
for a in arr:
rem = a - m * y
if rem > 0:
need += (rem + (x - y) - 1) // (x - y)
if need > m:
return False
return need <= m
lo, hi = 0, max(arr) // y + 2
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return loclass Solution {
public long arrayOperations(int[] arr, int x, int y) {
long maxA = 0; for (int a : arr) maxA = Math.max(maxA, a);
long lo = 0, hi = maxA / y + 2;
while (lo < hi) {
long mid = (lo + hi) / 2;
if (feasible(arr, x, y, mid)) hi = mid; else lo = mid + 1;
}
return lo;
}
boolean feasible(int[] arr, int x, int y, long m) {
long need = 0;
for (int a : arr) {
long rem = a - m * y;
if (rem > 0) { need += (rem + (x - y) - 1) / (x - y); if (need > m) return false; }
}
return need <= m;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
long long arrayOperations(vector<int>& arr, int x, int y) {
long long maxA = 0; for (int a : arr) maxA = max(maxA, (long long)a);
long long lo = 0, hi = maxA / y + 2;
auto feasible = [&](long long m) {
long long need = 0;
for (int a : arr) {
long long rem = a - m * y;
if (rem > 0) { need += (rem + (x - y) - 1) / (x - y); if (need > m) return false; }
}
return need <= m;
};
while (lo < hi) { long long mid = (lo + hi) / 2; if (feasible(mid)) hi = mid; else lo = mid + 1; }
return lo;
}
};You are given the coordinates of a triangle with three vertices:
- (x1, y1)
- (x2, y2)
- (x3, y3) Additionally, you are provided the coordinates of two points:
- Point p: (xp, yp)
- Point q: (xq, yq) Your task is to determine the following:
- Print '1' if the triangle cannot be formed.
- Print '2' if both p and q lie inside the triangle.
- Print '3' if only point p lies within the triangle.
- Print '4' if only point q lies within the triangle.
- Print '5' if neither point lies inside the triangle. Input Format:
- Coordinates of the triangle vertices:
x1, y1, x2, y2, x3, y3 - Coordinates of the points p and q:
p(xp, yp), q(xq, yq)
Example 1
Input:
x1 = 0
y1 = 0
x2 = 5
y2 = 0
x3 = 0
y3 = 5
xp = 1
yp = 1
xq = 6
yq = 6Output:
3Explanation: Only point p lies inside the triangle.
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理