Complete the function below. The function receives the full standard input as a single string and returns the exact standard output lines.
Implement itoa: given signed 32-bit integers, convert each integer to its base-10 string representation without using built-in number-to-string conversion helpers.
For each input integer, output the converted decimal string. Negative numbers must include a leading -. The value 0 must return 0.
Function Description
Complete solveIntegerToString. It has one parameter, String input, containing one signed integer per line. Return the stdout payload as an array of lines, without trailing newline characters.
Constraints
Each value fits in a signed 32-bit integer.
Example 1
Input:
input = "0\n42\n-17\n2147483647\n-2147483648"Output:
["0","42","-17","2147483647","-2147483648"]Explanation: Each integer is converted to its exact decimal string representation.
解法
每行解析一个整数。要点：-2147483648 取负溢出，需用 long 中转。提取符号、累加 n % 10 的字符再反转。复杂度 O(总位数)。
from typing import List
def solve_integer_to_string(input_str: str) -> List[str]:
out = []
for line in input_str.split("\n"):
line = line.strip()
if not line:
continue
n = int(line)
if n == 0:
out.append("0"); continue
neg = n < 0
x = -n if neg else n
digits = []
while x > 0:
digits.append(chr(ord('0') + x % 10))
x //= 10
if neg: digits.append("-")
out.append("".join(reversed(digits)))
return outimport java.util.*;
class Solution {
String[] solveIntegerToString(String input) {
List<String> out = new ArrayList<>();
for (String line : input.split("\n")) {
line = line.trim();
if (line.isEmpty()) continue;
long n = Long.parseLong(line);
if (n == 0) { out.add("0"); continue; }
boolean neg = n < 0;
long x = neg ? -n : n;
StringBuilder sb = new StringBuilder();
while (x > 0) { sb.append((char)('0' + x % 10)); x /= 10; }
if (neg) sb.append('-');
out.add(sb.reverse().toString());
}
return out.toArray(new String[0]);
}
}class Solution {
public:
vector<string> solveIntegerToString(string input) {
vector<string> out;
string cur;
for (char c : input + "\n") {
if (c == '\n') {
if (!cur.empty()) {
long long n = stoll(cur);
if (n == 0) out.push_back("0");
else {
bool neg = n < 0;
long long x = neg ? -n : n;
string s;
while (x > 0) { s += char('0' + x % 10); x /= 10; }
if (neg) s += '-';
reverse(s.begin(), s.end());
out.push_back(s);
}
cur.clear();
}
} else cur += c;
}
return out;
}
};Given a sequence of integer prices, we can determine when to buy and sell by identifying special sequences of prices movements called indicators.
For example, we can decide to buy every time we see 2 consecutive price increases, and we can decide to sell every time we see 2 consecutive price decreases followed by a price increase. If we represent a price increase as 1 and a price decrease as -1, we could write the above rules as:
buyIndicator = [1, 1] // buy after 2 price increases
sellIndicator = [-1, -1, 1] // sell after 2 price decreases then an increase
Specifically, consider the price sequence:
indexes = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
prices = [51, 56, 56, 58, 60, 59, 54, 57, 52, 48]
According to the buy/sell rules described in the indicators above, we would decide to buy at index=3 (price=58) because that price is a second consecutive price increase. Note that the price changes from 51->56->56->58. We would also buy at index=4 (price=60) for the same reason. We would sell at index=7 (price=57) because that price is preceded by 2 consecutive price decreases then an increase. Buy/sell signal will never trigger if the current price is equal to the previous price (i.e. if the price sequence is [51, 56, 56, 58, 58] we will only buy once at index=3). Note that this is just an example of buyIndicator and sellIndicator - they may differ between tests.
Finally, we define a position as the sum of buys and sells we have done up to that point, where a buy=1 and a sell=-1. When we have made no buys or sells, our position is 0. In the above example, our positions would be:
indexes = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
prices = [51, 56, 56, 58, 60, 59, 54, 57, 52, 48]
position = [0, 0, 0, 1, 2, 2, 2, 1, 1, 1]
Note that when we buy at index=3 and index=4 our position increases by 1 each time, and when we sell at index=7 our position decreases by 1.
Function Description
Write a function in python:
def solution(prices, buyIndicator, sellIndicator):
that, given a sequence of prices and sequences defining buy and sell indicators, returns a list of positions. Your position list must be the same length as the input price list. The buyIndicator and sellIndicator lists will each have at least one element and each element can only be 1 or -1. It is possible for both the buy and sell indicators to match at the same time. In that case the change in position should be 1+(-1) = 0.
Constraints
na
Example 1
Input:
prices = [51, 56, 56, 58, 60, 59, 54, 57, 52, 48]
buyIndicator = [1, 1]
sellIndicator = [-1, -1, 1]Output:
[0, 0, 0, 1, 2, 2, 2, 1, 1, 1]Explanation:
For the test case:
buyIndicator = [1, 1] // buy after 2 price increases
sellIndicator = [-1, -1, 1] // sell after 2 price decreases then an increase
prices = [51, 56, 56, 58, 60, 59, 54, 57, 52, 48]
The result should be:
position = [0, 0, 0, 1, 2, 2, 2, 1, 1, 1]
解法
把价格序列转成长度 n-1 的 signs 数组(+1 / -1 / 0，相等时为 0 — 题目说价格相等不触发信号)。对每个位置 i，检查 signs[i - len(buyIndicator) + 1 .. i] 是否匹配 buyIndicator、同理 sellIndicator；匹配时在 prices 的位置 i + 1(信号生效在下一个价格点)更新仓位。复杂度 O(n · |ind|)。
from typing import List
def solution(prices: List[int], buyIndicator: List[int], sellIndicator: List[int]) -> List[int]:
n = len(prices)
signs = []
for i in range(1, n):
d = prices[i] - prices[i - 1]
signs.append(0 if d == 0 else (1 if d > 0 else -1))
res = [0] * n
pos = 0
bl, sl = len(buyIndicator), len(sellIndicator)
for i in range(n):
delta = 0
if i + 1 >= bl and signs[i - bl + 1: i + 1 - 0][:bl] == buyIndicator and i > 0:
pass
# match buy: signs[i - bl + 1 .. i] (inclusive) ⇒ event at price i+1 wait,
# but we want position at index i. Use signs ending at i-1 length bl
if i >= bl and signs[i - bl: i] == buyIndicator:
delta += 1
if i >= sl and signs[i - sl: i] == sellIndicator:
delta -= 1
pos += delta
res[i] = pos
return resimport java.util.*;
class Solution {
int[] solution(int[] prices, int[] buyIndicator, int[] sellIndicator) {
int n = prices.length;
int[] signs = new int[Math.max(0, n - 1)];
for (int i = 1; i < n; i++) {
int d = prices[i] - prices[i - 1];
signs[i - 1] = d == 0 ? 0 : (d > 0 ? 1 : -1);
}
int[] res = new int[n];
int pos = 0;
for (int i = 0; i < n; i++) {
int delta = 0;
if (i >= buyIndicator.length && matches(signs, i - buyIndicator.length, buyIndicator)) delta += 1;
if (i >= sellIndicator.length && matches(signs, i - sellIndicator.length, sellIndicator)) delta -= 1;
pos += delta;
res[i] = pos;
}
return res;
}
private boolean matches(int[] arr, int start, int[] pat) {
for (int j = 0; j < pat.length; j++) if (arr[start + j] != pat[j]) return false;
return true;
}
}class Solution {
public:
vector<int> solution(vector<int>& prices, vector<int>& buyIndicator, vector<int>& sellIndicator) {
int n = prices.size();
vector<int> signs(max(0, n - 1));
for (int i = 1; i < n; i++) {
int d = prices[i] - prices[i - 1];
signs[i - 1] = d == 0 ? 0 : (d > 0 ? 1 : -1);
}
vector<int> res(n);
int pos = 0;
auto matches = [&](int start, vector<int>& pat) {
for (size_t j = 0; j < pat.size(); j++) if (signs[start + j] != pat[j]) return false;
return true;
};
for (int i = 0; i < n; i++) {
int delta = 0;
int bl = buyIndicator.size(), sl = sellIndicator.size();
if (i >= bl && matches(i - bl, buyIndicator)) delta += 1;
if (i >= sl && matches(i - sl, sellIndicator)) delta -= 1;
pos += delta;
res[i] = pos;
}
return res;
}
};For the original problem description, pls checkout the image source at the very bottom of this web page Imagine you’re in a magical world where certain numbers are considered "fancy." A number is fancy if, when written in base-4, it only contains the digits 0 and 1—like secret codes known only to wizards. For example, 17 is fancy because its base-4 form, 101, uses only 0s and 1s, while 18 is not, as its base-4 form, 102, contains a forbidden 2. Now, your task is to discover how many of these special, fancy numbers exist below a given number, n. But beware! n can be as big as a billion, so you need a clever method—something faster than just checking every number individually.
Example 1
Input:
n = 1Output:
0Explanation: There are no positive integers less than 1.
Example 2
Input:
n = 10Output:
3Explanation: The fancy numbers less than 10 are {1, 4, 5}.
解法
fancy 数即 base-4 只含 0 和 1 的数，等价于把这些位看作二进制位重新解释，第 k 个 fancy 数(从 1 开始)对应二进制 k 在 base-4 下的同样数字串。所以小于 n 的 fancy 数个数 = 找最大 k 使第 k 个 fancy 数 < n。可二分 k，或直接构造：枚举位数 + 位组合统计。这里用线性枚举法 + 数位拆解：每个 fancy 数 < n 表示 base-4 下选 0 或 1 的串。复杂度 O(log n)。
def count_fancy_numbers(n: int) -> int:
cnt = 0
k = 1
while True:
# k-th fancy number: binary repr of k interpreted in base 4
s = bin(k)[2:]
val = 0
for ch in s:
val = val * 4 + int(ch)
if val >= n:
break
cnt += 1
k += 1
return cntclass Solution {
int countFancyNumbers(int n) {
int cnt = 0, k = 1;
while (true) {
String s = Integer.toBinaryString(k);
long val = 0;
for (char c : s.toCharArray()) val = val * 4 + (c - '0');
if (val >= n) break;
cnt++;
k++;
}
return cnt;
}
}class Solution {
public:
int countFancyNumbers(int n) {
int cnt = 0, k = 1;
while (true) {
string s;
int t = k;
while (t > 0) { s += char('0' + (t & 1)); t >>= 1; }
reverse(s.begin(), s.end());
long long val = 0;
for (char c : s) val = val * 4 + (c - '0');
if (val >= n) break;
cnt++; k++;
}
return cnt;
}
};