You are building an App that lets the users determine the most cost-effective order that they can place in a restaurant for the food items that they want to have. You have the menu of the restaurant that contains item name, and it's price. The restaurant can also offer Value Meals, which are groups of several items, at a discounted price. Write a program that accepts a list of menu items, and a list of items that the user wants to eat, and outputs the best price at which they can get all of their desired items. To hhbond
Constraints
The user can order a maximum of 3 unique items.
Example 1
Input:
menu = [["5.00", "pizza"], ["8.00", "sandwich, coke"], ["4.00", "pasta"], ["2.00", "coke"], ["6.00", "pasta, coke, pizza"], ["8.00", "burger, coke, pizza"], ["5.00", "sandwich"]]
userWants = ["burger", "pasta"]Output:
12Explanation: The user wants to order "burger" and "pasta". The best price can be achieved by ordering the following:
- "pasta" for 4.00
- "burger, coke, pizza" for 8.00 This gives us the total best price of 4.00 + 8.00 = 12.00. (By tomtato, it may not be 100% correct)
解法
用户最多 3 个目标 item，用状态压缩 DP：把 userWants 编号 0..k-1，状态 mask 表示已覆盖的目标子集。遍历 menu 每条选项，把它能覆盖的目标 bit 集合 s 取出(注意忽略不在 userWants 里的额外 item)，转移 dp[mask | s] = min(dp[mask | s], dp[mask] + price)。答案 dp[(1<<k)-1]。复杂度 O(2^k · |menu|)，k ≤ 3。
from typing import List
def get_best_price(menu: List[List[str]], userWants: List[str]) -> int:
k = len(userWants)
want_idx = {w: i for i, w in enumerate(userWants)}
options = []
for row in menu:
price = float(row[0])
items_raw = ",".join(row[1:])
items = [x.strip() for x in items_raw.split(",")]
s = 0
for x in items:
if x in want_idx:
s |= 1 << want_idx[x]
if s != 0:
options.append((s, price))
FULL = (1 << k) - 1
INF = float("inf")
dp = [INF] * (1 << k)
dp[0] = 0
for mask in range(1 << k):
if dp[mask] == INF: continue
for s, price in options:
new_mask = mask | s
if dp[mask] + price < dp[new_mask]:
dp[new_mask] = dp[mask] + price
return int(dp[FULL]) if dp[FULL] != INF else -1import java.util.*;
class Solution {
int getBestPrice(String[][] menu, String[] userWants) {
int k = userWants.length;
Map<String, Integer> idx = new HashMap<>();
for (int i = 0; i < k; i++) idx.put(userWants[i], i);
List<int[]> options = new ArrayList<>();
List<Double> prices = new ArrayList<>();
for (String[] row : menu) {
double price = Double.parseDouble(row[0]);
StringBuilder sb = new StringBuilder();
for (int j = 1; j < row.length; j++) { if (j > 1) sb.append(","); sb.append(row[j]); }
int s = 0;
for (String x : sb.toString().split(",")) {
String t = x.trim();
if (idx.containsKey(t)) s |= 1 << idx.get(t);
}
if (s != 0) { options.add(new int[]{s}); prices.add(price); }
}
int FULL = (1 << k) - 1;
double[] dp = new double[1 << k];
Arrays.fill(dp, Double.MAX_VALUE);
dp[0] = 0;
for (int mask = 0; mask < (1 << k); mask++) {
if (dp[mask] == Double.MAX_VALUE) continue;
for (int o = 0; o < options.size(); o++) {
int nm = mask | options.get(o)[0];
if (dp[mask] + prices.get(o) < dp[nm]) dp[nm] = dp[mask] + prices.get(o);
}
}
return (int) dp[FULL];
}
}class Solution {
public:
int getBestPrice(vector<vector<string>>& menu, vector<string>& userWants) {
int k = userWants.size();
unordered_map<string, int> idx;
for (int i = 0; i < k; i++) idx[userWants[i]] = i;
vector<pair<int, double>> options;
for (auto& row : menu) {
double price = stod(row[0]);
string joined;
for (size_t j = 1; j < row.size(); ++j) {
if (j > 1) joined += ",";
joined += row[j];
}
int s = 0;
string cur;
for (char c : joined + ",") {
if (c == ',') {
string t;
for (char d : cur) if (d != ' ') t += d;
if (idx.count(t)) s |= 1 << idx[t];
cur.clear();
} else cur += c;
}
if (s) options.push_back({s, price});
}
int FULL = (1 << k) - 1;
vector<double> dp(1 << k, 1e18);
dp[0] = 0;
for (int mask = 0; mask < (1 << k); mask++) {
if (dp[mask] >= 1e17) continue;
for (auto& [s, price] : options) {
int nm = mask | s;
if (dp[mask] + price < dp[nm]) dp[nm] = dp[mask] + price;
}
}
return (int) dp[FULL];
}
};You are given a string fileContents that represents the contents of a text file. Lines are separated by newline characters .
Return the last n lines of the file in their original order. If the file has fewer than n lines, return the entire contents. If n = 0, return an empty string.
Function Description
Complete the function tailLastNLines in the editor below.
tailLastNLines has the following parameters:
int n: the number of trailing lines to keepString fileContents: the full file contents ReturnsString[]: the lastnlines in order, without adding extra formatting.
Constraints
0 ≤ nfileContentsmay be large, so an efficient solution should avoid unnecessary copies.
Example 1
Input:
n = 2
fileContents = "a\nb\nc\n"Output:
["b", "c"]Explanation:
The last two lines are b and c.
Example 2
Input:
n = 0
fileContents = "a\nb\nc"Output:
[]Explanation: Keeping zero trailing lines returns an empty array.
解法
从字符串末尾向前扫描，统计 \n 个数，找到第 n 个换行符的位置(或开头)，把那之后的子串按换行切分返回。复杂度 O(|file|)。
from typing import List
def tail_last_n_lines(n: int, fileContents: str) -> List[str]:
if n == 0:
return []
s = fileContents
if s.endswith("\n"):
s = s[:-1]
if not s:
return []
lines = s.split("\n")
return lines[-n:]class Solution {
String[] tailLastNLines(int n, String fileContents) {
if (n == 0) return new String[0];
String s = fileContents;
if (s.endsWith("\n")) s = s.substring(0, s.length() - 1);
if (s.isEmpty()) return new String[0];
String[] lines = s.split("\n", -1);
int start = Math.max(0, lines.length - n);
String[] res = new String[lines.length - start];
System.arraycopy(lines, start, res, 0, res.length);
return res;
}
}class Solution {
public:
vector<string> tailLastNLines(int n, string fileContents) {
if (n == 0) return {};
string s = fileContents;
if (!s.empty() && s.back() == '\n') s.pop_back();
if (s.empty()) return {};
vector<string> lines;
string cur;
for (char c : s) {
if (c == '\n') { lines.push_back(cur); cur.clear(); }
else cur += c;
}
lines.push_back(cur);
int start = max(0, (int) lines.size() - n);
return vector<string>(lines.begin() + start, lines.end());
}
};Given a list of numbers, each representing a bank account transaction (positive for credit, negative for debit), determine if there exists a subset of transactions that sums exactly to a given target balance.
Return 1 if such a subset exists, 0 otherwise.
Follow-up: Start with the O(2^n) subset enumeration approach, then optimize toward a dynamic programming solution. Be prepared to discuss the upper bound on n for which each approach is practical (e.g. the O(2^n) solution is feasible up to roughly n ≈ 25).
Example 1
Input:
transactions = [1,2,3]
target = 5Output:
1Explanation: The subset {2, 3} sums to 5. Return 1 (true).
Example 2
Input:
transactions = [1,2]
target = 4Output:
0Explanation: Possible subsets and their sums: {} = 0, {1} = 1, {2} = 2, {1,2} = 3. None equal 4. Return 0 (false).
解法
用哈希集合做子集和：维护当前可达和集合，初值 {0}；对每个 x，新集合 = old ∪ {s + x | s ∈ old}。最后判断 target 是否在其中。复杂度 O(n · S)，S = 可达不同和数；最坏 O(n · range)，小数据集足够。
from typing import List
def reach_target_balance(transactions: List[int], target: int) -> int:
sums = {0}
for x in transactions:
sums |= {s + x for s in sums}
return 1 if target in sums else 0import java.util.*;
class Solution {
int reachTargetBalance(int[] transactions, int target) {
Set<Long> sums = new HashSet<>();
sums.add(0L);
for (int x : transactions) {
Set<Long> next = new HashSet<>(sums);
for (long s : sums) next.add(s + x);
sums = next;
}
return sums.contains((long) target) ? 1 : 0;
}
}class Solution {
public:
int reachTargetBalance(vector<int>& transactions, int target) {
unordered_set<long long> sums{0};
for (int x : transactions) {
unordered_set<long long> next = sums;
for (long long s : sums) next.insert(s + x);
sums = next;
}
return sums.count((long long) target) ? 1 : 0;
}
};