2917. 找出数组中的 K-or 值
给你一个整数数组 nums 和一个整数 k 。让我们通过扩展标准的按位或来介绍 K-or 操作。在 K-or 操作中，如果在 nums 中，至少存在 k 个元素的第 i 位值为 1 ，那么 K-or 中的第 i 位的值是 1 。
返回 nums 的 K-or 值。
示例 1：
输入：nums = [7,12,9,8,9,15], k = 4
输出：9
解释：
用二进制表示 numbers：
Number Bit 3 Bit 2 Bit 1 Bit 0
7 0 1 1 1
12 1 1 0 0
9 1 0 0 1
8 1 0 0 0
9 1 0 0 1
15 1 1 1 1
Result = 9 1 0 0 1
位 0 在 7, 9, 9, 15 中为 1。位 3 在 12, 9, 8, 9, 15 中为 1。 只有位 0 和 3 满足。结果是 (1001)2 = 9。
示例 2：
输入：nums = [2,12,1,11,4,5], k = 6
输出：0
解释：没有位在所有 6 个数字中都为 1，如 k = 6 所需要的。所以，答案为 0。
示例 3：
输入：nums = [10,8,5,9,11,6,8], k = 1
输出：15
解释：因为 k == 1 ，数组的 1-or 等于其中所有元素按位或运算的结果。因此，答案为 10 OR 8 OR 5 OR 9 OR 11 OR 6 OR 8 = 15 。
提示：
1 <= nums.length <= 50
0 <= nums[i] < 231
1 <= k <= nums.length
枚举模拟即可：
class Solution {
public:
int findKOr(vector<int>& nums, int k) {
int res = 0;
int n = nums.size();
for (int i = 0; i < 32; ++i) {
int count = 0;
for (int num : nums) {
if ((num >> i) & 1) {
count++;
}
}
if (count >= k) {
res |= (1 << i);
}
}
return res;
}
};
2575. 找出字符串的可整除数组
给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。
word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：
如果 word[0,…,i] 所表示的 数值 能被 m 整除，div[i] = 1
否则，div[i] = 0
返回 word 的可整除数组。
示例 1：
输入：word = “998244353”, m = 3
输出：[1,1,0,0,0,1,1,0,0]
解释：仅有 4 个前缀可以被 3 整除：“9”、“99”、“998244” 和 “9982443” 。
示例 2：
输入：word = “1010”, m = 10
输出：[0,1,0,1]
解释：仅有 2 个前缀可以被 10 整除：“10” 和 “1010” 。
提示：
1 <= n <= 1e5
word.length == n
word 由数字 0 到 9 组成
1 <= m <= 1e9
模拟题,遍历取模：
class Solution {
public:
vector<int> divisibilityArray(string word, int m) {
int n = word.size();
vector<int> div(n, 0);
long long rem = 0;
for (int i = 0; i < n; ++i) {
rem = (rem * 10 + (word[i] - '0')) % m;
if (rem == 0) {
div[i] = 1;
}
}
return div;
}
};
2834. 找出美丽数组的最小和
给你两个正整数：n 和 target 。
如果数组 nums 满足下述条件，则称其为 美丽数组 。
nums.length == n.
nums 由两两互不相同的正整数组成。
在范围 [0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。
返回符合条件的美丽数组所可能具备的 最小 和，并对结果进行取模 109 + 7。
示例 1：
输入：n = 2, target = 3
输出：4
解释：nums = [1,3] 是美丽数组。
- nums 的长度为 n = 2 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 4 是符合条件的美丽数组所可能具备的最小和。
示例 2：
输入：n = 3, target = 3
输出：8
解释：
nums = [1,3,4] 是美丽数组。
- nums 的长度为 n = 3 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 8 是符合条件的美丽数组所可能具备的最小和。
示例 3：
输入：n = 1, target = 1
输出：1
解释：nums = [1] 是美丽数组。
提示：
1 <= n <= 1e9
1 <= target <= 1e9
2386. 找出数组的第 K 大和(Hard)
给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。
数组的 第 k 大和 定义为：可以获得的第 k 个 最大 子序列和（子序列和允许出现重复）
返回数组的 第 k 大和 。
子序列是一个可以由其他数组删除某些或不删除元素派生而来的数组，且派生过程不改变剩余元素的顺序。
注意：空子序列的和视作 0 。
示例 1：
输入：nums = [2,4,-2], k = 5
输出：2
解释：所有可能获得的子序列和列出如下，按递减顺序排列：
- 6、4、4、2、2、0、0、-2
数组的第 5 大和是 2 。
示例 2：
输入：nums = [1,-2,3,4,-10,12], k = 16
输出：10
解释：数组的第 16 大和是 10 。
提示：
n == nums.length
1 <= n <= 1e5
-109 <= nums[i] <= 1e9
1 <= k <= min(2000, 2n)
参考灵神题解：两种方法：二分答案+爆搜/最小堆
class Solution {
public:
long long kSum(vector<int>& nums, int k) {
long sum = 0;
for (int& x : nums) {
if (x >= 0) {
sum += x;
} else {
x = -x;
}
}
ranges::sort(nums);
auto check = [&](long sum_limit) -> bool {
int cnt = 1; // 空子序列算一个
function<void(int, long long)> dfs = [&](int i, long long s) {
if (cnt == k || i == nums.size() || s + nums[i] > sum_limit) {
return;
}
cnt++; // s + nums[i] <= sum_limit
dfs(i + 1, s + nums[i]); // 选
dfs(i + 1, s); // 不选
};
dfs(0, 0);
return cnt == k; // 找到 k 个元素和不超过 sum_limit 的子序列
};
long long left = -1, right = accumulate(nums.begin(), nums.end(), 0LL);
while (left + 1 < right) { // 开区间二分，原理见【前置知识】
long long mid = (left + right) / 2;
(check(mid) ? right : left) = mid;
}
return sum - right;
}
};
299. 猜数字游戏
你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：
写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：
猜测数字中有多少位属于数字和确切位置都猜对了（称为 “Bulls”，公牛），
有多少位属于数字猜对了但是位置不对（称为 “Cows”，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。
给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。
提示的格式为 “xAyB” ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。
请注意秘密数字和朋友猜测的数字都可能含有重复数字。
示例 1：
输入：secret = “1807”, guess = “7810”
输出：“1A3B”
解释：数字和位置都对（公牛）用 ‘|’ 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
“1807”
|
“7810”
示例 2：
输入：secret = “1123”, guess = “0111”
输出：“1A1B”
解释：数字和位置都对（公牛）用 ‘|’ 连接，数字猜对位置不对（奶牛）的采用斜体加粗标识。
“1123” “1123”
| or |
“0111” “0111”
注意，两个不匹配的 1 中，只有一个会算作奶牛（数字猜对位置不对）。通过重新排列非公牛数字，其中仅有一个 1 可以成为公牛数字。
提示：
1 <= secret.length, guess.length <= 1000
secret.length == guess.length
secret 和 guess 仅由数字组成
模拟（虽然模拟我还是看了题解，菜鸡orz）：
class Solution {
public:
string getHint(string secret, string guess) {
int bulls = 0;
int cows = 0;
vector<int> numbers(10, 0);
for (int i = 0; i < secret.size(); i++) {
if (secret[i] == guess[i]) {
bulls++;
} else {
if (numbers[secret[i] - '0']++ < 0) cows++;
if (numbers[guess[i] - '0']-- > 0) cows++;
}
}
return to_string(bulls) + "A" + to_string(cows) + "B";
}
};
2129. 将标题首字母大写
给你一个字符串 title ，它由单个空格连接一个或多个单词组成，每个单词都只包含英文字母。请你按以下规则将每个单词的首字母 大写 ：
如果单词的长度为 1 或者 2 ，所有字母变成小写。
否则，将单词首字母大写，剩余字母变成小写。
请你返回 大写后 的 title 。
示例 1：
输入：title = “capiTalIze tHe titLe”
输出：“Capitalize The Title”
解释：
由于所有单词的长度都至少为 3 ，将每个单词首字母大写，剩余字母变为小写。
示例 2：
输入：title = “First leTTeR of EACH Word”
输出：“First Letter of Each Word”
解释：
单词 “of” 长度为 2 ，所以它保持完全小写。
其他单词长度都至少为 3 ，所以其他单词首字母大写，剩余字母小写。
示例 3：
输入：title = “i lOve leetcode”
输出：“i Love Leetcode”
解释：
单词 “i” 长度为 1 ，所以它保留小写。
其他单词长度都至少为 3 ，所以其他单词首字母大写，剩余字母小写。
提示：
1 <= title.length <= 100
title 由单个空格隔开的单词组成，且不含有任何前导或后缀空格。
每个单词由大写和小写英文字母组成，且都是 非空 的。
模拟：
class Solution {
public:
string capitalizeTitle(string title) {
istringstream iss(title);
string ans, s;
while (iss >> s) {
if (!ans.empty()) {
ans += ' ';
}
if (s.length() > 2) {
ans += toupper(s[0]);
s = s.substr(1);
}
for (char c : s) {
ans += tolower(c);
}
}
return ans;
}
};
1261. 在受污染的二叉树中查找元素
给出一个满足下述规则的二叉树：
root.val == 0
如果 treeNode.val == x 且 treeNode.left != null，那么 treeNode.left.val == 2 * x + 1
如果 treeNode.val == x 且 treeNode.right != null，那么 treeNode.right.val == 2 * x + 2
现在这个二叉树受到「污染」，所有的 treeNode.val 都变成了 -1。
请你先还原二叉树，然后实现 FindElements 类：
FindElements(TreeNode* root) 用受污染的二叉树初始化对象，你需要先把它还原。
bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。
示例 1：
输入：
[“FindElements”,“find”,“find”]
[[[-1,null,-1]],[1],[2]]
输出：
[null,false,true]
解释：
FindElements findElements = new FindElements([-1,null,-1]);
findElements.find(1); // return False
findElements.find(2); // return True
示例 2：
输入：
[“FindElements”,“find”,“find”,“find”]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
输出：
[null,true,true,false]
解释：
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False
示例 3：
输入：
[“FindElements”,“find”,“find”,“find”,“find”]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
输出：
[null,true,false,false,true]
解释：
FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // return True
findElements.find(3); // return False
findElements.find(4); // return False
findElements.find(5); // return True
提示：
TreeNode.val == -1
二叉树的高度不超过 20
节点的总数在 [1, 10^4] 之间
调用 find() 的总次数在 [1, 10^4] 之间
0 <= target <= 10^6
哈希表：
class FindElements {
public:
unordered_set<int> values;
FindElements(TreeNode* root)
{
recover(root, 0);
}
void recover(TreeNode* node, int val) {
if (node == nullptr)
{
return;
}
node->val = val;
values.insert(val);
recover(node->left, 2 * val + 1);
recover(node->right, 2 * val + 2);
}
bool find(int target)
{
return values.find(target) != values.end();
}
};
