Box's Online Sales team is looking to expand their payment options to accept crypto currency. To ensure that they detect any attempts at fake payments, we need you to help our team validate each attempted crypto payment. You will help us identify bad currency by using a few rules. Each piece of crypto currency has a serial number that can be used to determine whether it is valid. The serial number also can be used to determine the value of the coin. A valid serial number will have the following characteristics:
The serial number is 10 ~ 12 characters.
The first 3 characters are distinct uppercase English letters.
The next 4 characters represent the year the coin was minted and will always be between 1900 and 2019 inclusive.
The next characters represent the coin value and may be any one of (10, 20, 50, 100, 200, 500, 1000).
The final character should be an uppercase letter of the serial number. The serial number must end with exactly one uppercase English letter only.
Please note - a crypto processing tax of 1% must be taken from each valid transaction. Our system cannot handle fractional coins, so we will need to round down to an integer.
Below are a few serial numbers, determine the value of those with valid currency with the correct tax removed.
Function Description
Complete the function countCounterfeit in the editor below. Each element is a string that represents a transaction. The function must return an integer sum of values of valid currency with the processed tax removed from the transaction.
The function is currently written, but we've been struggling to fix the bugs. The bugs will need your help fixing as of Q4 2022, so we can release this new feature! Debug the method below and fix the bugs you find. Once all the bugs have been fixed the method will pass all test cases and we can move forward with the feature release.
countCounterfeit has the following parameter(s):
serialNumber[serialNumber[0]...serialNumber[n-1]]: an array of strings
Constraints
- 0 < n ≤ 10⁵
- 1 ≤ |serialNumber[i]| ≤ 14
Example 1
Input:
serialNumber = ["AVG190420T", "RTF200010002", "QWER201850G", "AFA199620E", "ERT1947200T", "RTY20202004", "DRV1984500V", "ETB2010400G"]Output:
1720Explanation: In total, there are valid coins worth 20 + 1000 + 200 + 500 = 1720.
解法
用正则或者按位置切片校验各字段：前 3 字符为 3 个互异大写、4 位年份在 [1900, 2019]、中间面值为 {10, 20, 50, 100, 200, 500, 1000} 中之一、最后 1 个字符大写且在前面序列号中出现过。合法则累加 value * 0.99 向下取整。复杂度 O(Σ |s|)。
from typing import List
def count_counterfeit(serial_number: List[str]) -> int:
valid_values = {"10", "20", "50", "100", "200", "500", "1000"}
total = 0
for s in serial_number:
if not (10 <= len(s) <= 12):
continue
head, year, last = s[:3], s[3:7], s[-1]
value = s[7:-1]
if not head.isalpha() or not head.isupper() or len(set(head)) != 3:
continue
if not year.isdigit() or not (1900 <= int(year) <= 2019):
continue
if value not in valid_values:
continue
if not last.isalpha() or not last.isupper() or last not in head:
continue
total += (int(value) * 99) // 100
return totalimport java.util.*;
class Solution {
int countCounterfeit(String[] serialNumber) {
Set<String> validVal = Set.of("10", "20", "50", "100", "200", "500", "1000");
long total = 0;
for (String s : serialNumber) {
if (s.length() < 10 || s.length() > 12) continue;
String head = s.substring(0, 3), year = s.substring(3, 7);
String value = s.substring(7, s.length() - 1);
char last = s.charAt(s.length() - 1);
if (!head.chars().allMatch(c -> c >= 'A' && c <= 'Z')) continue;
if (head.chars().distinct().count() != 3) continue;
if (!year.chars().allMatch(Character::isDigit)) continue;
int y = Integer.parseInt(year);
if (y < 1900 || y > 2019) continue;
if (!validVal.contains(value)) continue;
if (!Character.isUpperCase(last) || head.indexOf(last) < 0) continue;
total += (Integer.parseInt(value) * 99L) / 100L;
}
return (int) total;
}
}class Solution {
public:
int countCounterfeit(vector<string>& serialNumber) {
set<string> validVal{"10", "20", "50", "100", "200", "500", "1000"};
long long total = 0;
for (auto& s : serialNumber) {
if (s.size() < 10 || s.size() > 12) continue;
string head = s.substr(0, 3), year = s.substr(3, 4);
string value = s.substr(7, s.size() - 8);
char last = s.back();
bool ok = true;
for (char c : head) if (c < 'A' || c > 'Z') ok = false;
if (!ok) continue;
set<char> dist(head.begin(), head.end());
if (dist.size() != 3) continue;
for (char c : year) if (!isdigit((unsigned char) c)) ok = false;
if (!ok) continue;
int y = stoi(year);
if (y < 1900 || y > 2019) continue;
if (!validVal.count(value)) continue;
if (!isupper((unsigned char) last) || head.find(last) == string::npos) continue;
total += (stoll(value) * 99LL) / 100LL;
}
return (int) total;
}
};Box Governance customers can create Retention Policies that will hold files for a certain length of time. When placed on a folder, all files in that folder can not be deleted until the length of time has passed. Once a Retention Policy has been created and put on a folder, the customers can move the policy up and down their folder tree onto different folders.
There are n Retention Policies placed on the Box folder tree that constantly love up or down the folder tree onto
different folders. The folder tree is infinitely long, so policies will move up or down infinitely.
direction[i] represents the direction in which the i-th Retention Policy is moving with -1 meaning that it is
moving up the folder tree and 1 meaning it is down the folder tree. The policy length (how long the policy will hold files for) of
the i-th Retention Policy is described by length[i]. If 2 Retention Policy collide, the one with the higher length destroys the
smaller one. If both have the same length, both are destroyed. Return a list of the indices of the policies that remain after all the collisions have occured, in an ascending order.
Note that the array direction and length are 0-indexed.
Function Description
Complete the function findRemainingPolicies in the editor.
解法
经典小行星碰撞变形(LeetCode 735)。按数组顺序遍历，用栈维护"幸存"策略。direction == -1(向上)类似 "+"；direction == 1(向下)类似 "-"。 这里题意：方向相对运动，向下 (1) 接着向上 (-1) 即对撞。维护栈，遇到向上 (-1) 时若栈顶向下 (1) 则碰撞处理；其它情况直接入栈。最后输出剩余策略的原始索引升序。复杂度 O(n)。
from typing import List
def find_remaining_policies(direction: List[int], length: List[int]) -> List[int]:
stk = []
for i, (d, L) in enumerate(zip(direction, length)):
alive = True
while alive and d == -1 and stk and stk[-1][1] == 1:
j = stk[-1][0]
if length[j] < L:
stk.pop()
elif length[j] == L:
stk.pop()
alive = False
else:
alive = False
if alive:
stk.append((i, d))
return sorted(i for i, _ in stk)import java.util.*;
class Solution {
int[] findRemainingPolicies(int[] direction, int[] length) {
Deque<int[]> stk = new ArrayDeque<>();
for (int i = 0; i < direction.length; i++) {
int d = direction[i], L = length[i];
boolean alive = true;
while (alive && d == -1 && !stk.isEmpty() && stk.peek()[1] == 1) {
int j = stk.peek()[0];
if (length[j] < L) stk.pop();
else if (length[j] == L) { stk.pop(); alive = false; }
else alive = false;
}
if (alive) stk.push(new int[]{i, d});
}
List<Integer> idx = new ArrayList<>();
for (int[] a : stk) idx.add(a[0]);
Collections.sort(idx);
return idx.stream().mapToInt(Integer::intValue).toArray();
}
}class Solution {
public:
vector<int> findRemainingPolicies(vector<int>& direction, vector<int>& length) {
vector<pair<int, int>> stk;
for (int i = 0; i < (int) direction.size(); i++) {
int d = direction[i], L = length[i];
bool alive = true;
while (alive && d == -1 && !stk.empty() && stk.back().second == 1) {
int j = stk.back().first;
if (length[j] < L) stk.pop_back();
else if (length[j] == L) { stk.pop_back(); alive = false; }
else alive = false;
}
if (alive) stk.push_back({i, d});
}
vector<int> res;
for (auto& p : stk) res.push_back(p.first);
sort(res.begin(), res.end());
return res;
}
};The Box office is thinking about investing in a rotating frozen yogurt (froyo) machine. The froyo machine has a menu with frozen yogurt flavors that may be included. The machine must move through the flavors one at a time, either moving left or right. The machine is circular, so when the last flavor in the flavors array is reached in either direction, the next flavor is at the other end of the array.
Given the name of the next flavor needed, determine the minimum number of left or right moves to reach it.
Function Description
Complete the function flavorchanger in the editor below.
flavorchanger has the following parameter(s):
String[] flavors[n]: array of flavor names arranged in the order they appear in the frozen yogurt machineint startIndex: index of the flavor currently dispensingString target: name of the flavor needed Returnsint: minimum number of moves required to reach the desired flavor Constraints- 1 ≤ n ≤ 100
- 0 ≤ startIndex ≤ n-1
- 1 ≤ length of flavors[i] and target ≤ 100
- target is in flavors
Constraints
- 1 ≤ n ≤ 100
- 0 ≤ start
Example 1
Input:
flavors = ["originalart", "banana", "custard", "mango"]
startIndex = 1
target = "banana"Output:
1Explanation: The flavor currently dispensing is banana at index 1. The desired flavor is originalart at index 0. It can be reached by moving right 3 steps or left 1 step. The minimum number of moves is 1.
解法
找到目标 flavor 的索引 t，两个方向距离 min(|t - startIndex|, n - |t - startIndex|)。复杂度 O(n)。
from typing import List
def flavorchanger(flavors: List[str], startIndex: int, target: str) -> int:
t = flavors.index(target)
n = len(flavors)
d = abs(t - startIndex)
return min(d, n - d)class Solution {
int flavorchanger(String[] flavors, int startIndex, String target) {
int n = flavors.length, t = -1;
for (int i = 0; i < n; i++) if (flavors[i].equals(target)) { t = i; break; }
int d = Math.abs(t - startIndex);
return Math.min(d, n - d);
}
}class Solution {
public:
int flavorchanger(vector<string>& flavors, int startIndex, string target) {
int n = flavors.size(), t = -1;
for (int i = 0; i < n; i++) if (flavors[i] == target) { t = i; break; }
int d = abs(t - startIndex);
return min(d, n - d);
}
};