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;
}
};You are given a list containing multiple decks of cards, where each deck consists of 52 unique cards. The total number of cards, n, is guaranteed to be a multiple of 52. Each card is represented as a structure containing two fields: suit and rank. Write a function to shuffle all the cards together using a custom algorithm that mimics manual shuffling.
Constraints
- The total number of cards,
n, is guaranteed to be a multiple of 52, indicating that there are multiple decks. - Each card has a suit and a rank.
- Suits are one of "Hearts", "Diamonds", "Clubs", "Spades".
- Ranks are one of "A", "2", "3", ..., "10", "J", "Q", "K".
Function Signature
std::list<Card> shuffleAllDecks(const std::list<Card>& all_decks);Input The inputall_decksis astd::listofCardstructures containing one or more decks of cards. All the decks are combined into a single list for shuffling. Output Return astd::list<Card>where all the cards from the input have been shuffled together.
Constraints
N/A
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理