Given a long integer, num, find the number of ways to represent it as a sum of two or more consecutive positive integers. For example:
If num = 15, then there are three such ways: (1 + 2 + 3 + 4 + 5) = (4 + 5 + 6) = (7 + 8) = 15.
If num = 2, then there are zero such ways.
Complete the consecutive function in the editor below. It has one parameter: a long integer named num. The function must return an integer denoting the number of ways to represent num as a sum of two or more consecutive positive integers.
Input Format
Locked stub code in the editor reads a long integer denoting num from stdin and passes it to the function.
Constraints
1 ≤ num ≤ 10¹²Output Format Return an integer denoting the number of ways to representnumas a sum of two or more consecutive positive integers.
Constraints
1 ≤ num ≤ 10¹²
Example 1
Input:
num = 15Output:
3Explanation:
Might or might not be an accurate explanation :)
There are three ways to represent num = 15 as a sum of two or more consecutive positive integers:
(1 + 2 + 3 + 4 + 5)(4 + 5 + 6)(7 + 8)Therefore, the function returns3.
解法
连续 k 个正整数 a..a+k-1 之和 = k·a + k(k-1)/2 = num，故 a = (num − k(k-1)/2)/k > 0 且为整数。对 k = 2, 3, ... 枚举至 k(k-1)/2 < num 即 k ≤ O(√(2·num))。时间 O(√num)。
def consecutive(num: int) -> int:
cnt = 0
k = 2
while k * (k - 1) // 2 < num:
rem = num - k * (k - 1) // 2
if rem > 0 and rem % k == 0:
cnt += 1
k += 1
return cntclass Solution {
public int consecutive(long num) {
int cnt = 0;
for (long k = 2; k * (k - 1) / 2 < num; k++) {
long rem = num - k * (k - 1) / 2;
if (rem > 0 && rem % k == 0) cnt++;
}
return cnt;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int consecutive(long long num) {
int cnt = 0;
for (long long k = 2; k * (k - 1) / 2 < num; k++) {
long long rem = num - k * (k - 1) / 2;
if (rem > 0 && rem % k == 0) cnt++;
}
return cnt;
}
};Ashley loves Numbers—but only the ones without repeating digits. For example, she loves 12 but hates 11. Given two integers, n and m, Ashley wants to find the count, c, of numbers she will love that are in the inclusive range between n and m.
Complete the countNumbers function in your editor. It has 1 parameter: a 2D array of integers, arr, containing q rows of n and m values. For each row i in arr (where 0 ≤ i Input Format The locked stub code in your editor reads the following input from stdin and passes it to your function: The first line contains an integer, q, denoting the number of rows in arr. The second line contains an integer, 2, denoting the number of columns in arr. Each line iof theqsubsequent lines (where0 ≤ i Output Format
For each row i in arr, your function must print the count, c_i, of numbers Ashley loves in the inclusive range between n_i and m_i, on a new line. (I turned the output type into int[] for convience :)
Constraints
1 ≤ q ≤ 10⁵1 ≤ n ≤ m ≤ 10⁶
解法
预处理 pre[x] = [1..x] 中各位互不相同的数的个数。对每个 query (n, m) 返回 pre[m] - pre[n-1]。检查"各位互不相同"用一个位掩码或集合。预处理时间 O(max_m · log)，查询 O(1)。
from typing import List
def count_numbers(arr: List[List[int]]) -> List[int]:
max_m = max(row[1] for row in arr)
pre = [0] * (max_m + 1)
for x in range(1, max_m + 1):
seen = set()
ok = True
y = x
while y > 0:
d = y % 10
if d in seen:
ok = False; break
seen.add(d)
y //= 10
pre[x] = pre[x - 1] + (1 if ok else 0)
return [pre[m] - pre[n - 1] for n, m in arr]class Solution {
public int[] countNumbers(int[][] arr) {
int maxM = 0;
for (int[] r : arr) maxM = Math.max(maxM, r[1]);
int[] pre = new int[maxM + 1];
for (int x = 1; x <= maxM; x++) {
int mask = 0; boolean ok = true; int y = x;
while (y > 0) {
int d = y % 10;
if ((mask & (1 << d)) != 0) { ok = false; break; }
mask |= 1 << d;
y /= 10;
}
pre[x] = pre[x - 1] + (ok ? 1 : 0);
}
int[] out = new int[arr.length];
for (int i = 0; i < arr.length; i++) out[i] = pre[arr[i][1]] - pre[arr[i][0] - 1];
return out;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> countNumbers(vector<vector<int>>& arr) {
int maxM = 0;
for (auto& r : arr) maxM = max(maxM, r[1]);
vector<int> pre(maxM + 1, 0);
for (int x = 1; x <= maxM; x++) {
int mask = 0; bool ok = true; int y = x;
while (y > 0) {
int d = y % 10;
if (mask & (1 << d)) { ok = false; break; }
mask |= 1 << d;
y /= 10;
}
pre[x] = pre[x - 1] + (ok ? 1 : 0);
}
vector<int> out;
for (auto& r : arr) out.push_back(pre[r[1]] - pre[r[0] - 1]);
return out;
}
};Given a dictionary of many words:
Example 1
Input:
words = ["bac", "ac", "a", "c", "bads"]Output:
3Explanation: The longest chain that can be formed starting with "bac" is "bac" -> "ac" -> "a", which has a length of 3.
解法
类似 LeetCode 720 / 1048。把 words 按长度升序排序，逐词 DP：dp[w] = 1 + max(dp[w-1 个字符])。这里"−1 字符"指去掉任一位置后剩下的串，若该串也在字典则可衔接。用哈希表存所有词的 dp 值。最终取 max。时间 O(n · L²)。
from typing import List
def find_longest_chain(words: List[str]) -> int:
s = sorted(set(words), key=len)
dp = {}
best = 0
for w in s:
cur = 1
for i in range(len(w)):
prev = w[:i] + w[i + 1:]
if prev in dp:
cur = max(cur, dp[prev] + 1)
dp[w] = cur
best = max(best, cur)
return bestimport java.util.*;
class Solution {
public int findLongestChain(String[] words) {
String[] s = Arrays.stream(words).distinct().toArray(String[]::new);
Arrays.sort(s, (a, b) -> a.length() - b.length());
Map<String, Integer> dp = new HashMap<>();
int best = 0;
for (String w : s) {
int cur = 1;
for (int i = 0; i < w.length(); i++) {
String prev = w.substring(0, i) + w.substring(i + 1);
if (dp.containsKey(prev)) cur = Math.max(cur, dp.get(prev) + 1);
}
dp.put(w, cur);
best = Math.max(best, cur);
}
return best;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findLongestChain(vector<string>& words) {
vector<string> s(words.begin(), words.end());
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());
sort(s.begin(), s.end(), [](const string& a, const string& b) { return a.size() < b.size(); });
unordered_map<string, int> dp;
int best = 0;
for (auto& w : s) {
int cur = 1;
for (int i = 0; i < (int)w.size(); i++) {
string prev = w.substr(0, i) + w.substr(i + 1);
auto it = dp.find(prev);
if (it != dp.end()) cur = max(cur, it->second + 1);
}
dp[w] = cur;
best = max(best, cur);
}
return best;
}
};