目录
404. 左叶子之和
416. 分割等和子集
419. 甲板上的战舰
421. 数组中两个数的最大异或值
426. 将二叉搜索树转化为排序的双向链表
429. N叉树的层序遍历
431. 将 N 叉树编码为二叉树
438. 找到字符串中所有字母异位词
剑指 Offer II 015. 字符串中的所有变位词
https://blog.csdn.net/nameofcsdn/article/details/119833252
445. 两数相加 II
451. 根据字符出现频率排序
题目：
给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
示例 1:
输入:
“tree”
输出:
“eert”
解释:
‘e’出现两次，’r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外，”eetr”也是一个有效的答案。
示例 2:
输入:
“cccaaa”
输出:
“cccaaa”
解释:
‘c’和’a’都出现三次。此外，”aaaccc”也是有效的答案。
注意”cacaca”是不正确的，因为相同的字母必须放在一起。
示例 3:
输入:
“Aabb”
输出:
“bbAa”
解释:
此外，”bbaA”也是一个有效的答案，但”Aabb”是不正确的。
注意’A’和’a’被认为是两种不同的字符。
代码：
struct dist
{
char c;
int fre;
};
struct cmp
{
bool operator()(dist a, dist b)
{
return a.fre < b.fre;
}
};
class Solution {
public:
string frequencySort(string s) {
map<char, int> m;
priority_queue<dist, vector<dist>, cmp>que;
dist d;
for (int i = 0; i < s.length();i++)
{
m[s[i]]++;
}
for (auto it = m.begin(); it != m.end(); it++)
{
d.c = (*it).first, d.fre = (*it).second, que.push(d);
}
string ans = "";
while (!que.empty())
{
d = que.top();
que.pop();
while(d.fre--)ans += d.c;
}
return ans;
}
};
454. 四数相加 II
数组和集合的搜索
数组和集合的搜索_nameofcsdn的博客-CSDN博客
459. 重复的子字符串
461. 汉明距离
题目：
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意：
0 ≤ x, y < 231.
示例:
输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
代码：
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans = 0;
while (n)
{
n ^= (n&(-n));
ans++;
}
return ans;
}
int hammingDistance(int x, int y) {
return hammingWeight(x^y);
}
};
469. 凸多边形
470. 用 Rand7() 实现 Rand10()
478. 在圆内随机生成点
485. 最大连续 1 的个数
给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。
示例 1：
输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.
示例 2:
输入：nums = [1,0,1,1,0,1]
输出：2
提示：
1 <= nums.length <= 105
nums[i] 不是 0 就是 1.
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int n = 0, ans = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i])n++;
else ans = max(ans, n), n = 0;
}
return max(ans, n);
}
};
486. 预测赢家
487. 最大连续1的个数 II
给定一个二进制数组 nums ，如果最多可以翻转一个 0 ，则返回数组中连续 1 的最大个数。
示例 1：
输入：nums = [1,0,1,1,0]
输出：4
解释：翻转第一个 0 可以得到最长的连续 1。
当翻转以后，最大连续 1 的个数为 4。
示例 2:
输入：nums = [1,0,1,1,0,1]
输出：4
提示:
1 <= nums.length <= 105
nums[i] 不是 0 就是 1.
进阶：如果输入的数字是作为 无限流 逐个输入如何处理？换句话说，内存不能存储下所有从流中输入的数字。您可以有效地解决吗？
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int a = -1, b = -1, c = -1, d = -1, ans = 0;
for (int i = 0; i <= nums.size(); i++) {
if (i == nums.size() || nums[i] == 0) {
d = i;
ans = max(ans, d - b - 1);
a = b, b = c, c = d;
}
}
return ans;
}
};
490. 迷宫
496. 下一个更大元素 I
给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
提示：
nums1和nums2中所有元素是唯一的。
nums1和nums2 的数组大小都不超过1000。
这个题目很简单，我主要用来锻造我的模板：
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
vector<int>ans=GetNumFromId(nums2,Fmaxrig(nums2));
map<int,int>m=VectorToMap(nums2,ans);
ans=VmToVector(nums1,m);
return ans;
}
};
499. 迷宫 III
503. 下一个更大元素 II
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int>t=nums;
t.resize(nums.size()*2);
copy(nums.begin(),nums.end(),t.begin()+nums.size());
vector<int>tmp=GetNumFromId(t,Fmaxrig(t));
vector<int>ans=nums;
copy(tmp.begin(),tmp.begin()+tmp.size()/2,ans.begin());
return ans;
}
};
505. 迷宫 II
509. 斐波那契数
510. 二叉搜索树中的中序后继 II
二叉搜索树
二叉搜索树（BST）_nameofcsdn的博客-CSDN博客
515. 在每个树行中找最大值
剑指 Offer II 044. 二叉树每层的最大值
https://blog.csdn.net/nameofcsdn/article/details/119833252
523. 连续的子数组和
给定一个包含非负数的数组和一个目标整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
示例 1:
输入: [23,2,4,6,7], k = 6
输出: True
解释: [2,4] 是一个大小为 2 的子数组，并且和为 6。
示例 2:
输入: [23,2,6,4,7], k = 6
输出: True
解释: [23,2,6,4,7]是大小为 5 的子数组，并且和为 42。
说明:
数组的长度不会超过10,000。
你可以认为所有数字总和在 32 位有符号整数范围内。
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
if(k==0)
{
for(int i=1;i<nums.size();i++)
{
if(nums[i]==0&&nums[i-1]==0)return true;
}
return false;
}
map<int,int>m;
int s=0;
if(k<0)k=-k;
for(int i=0;i<nums.size();i++)
{
s+=nums[i];
s%=k;
if(m[s]>0||s==0)
{
if(m[s]<i)return true;
}
else m[s]=i+1;
}
return false;
}
};
525. 连续数组
剑指 Offer II 010. 和为 k 的子数组
https://blog.csdn.net/nameofcsdn/article/details/119833252
528. 按权重随机选择
剑指 Offer II 071. 按权重生成随机数
https://blog.csdn.net/nameofcsdn/article/details/119833252
529. 扫雷游戏
535. TinyURL 的加密与解密
538. 把二叉搜索树转换为累加树
539. 最小时间差
https://blog.csdn.net/nameofcsdn/article/details/119833252
540. 有序数组中的单一元素
二分、三分
二分、三分_nameofcsdn的博客-CSDN博客
542. 01 矩阵
547. 省份数量
552. 学生出勤记录 II
556. 下一个更大元素 III
给定一个32位正整数 n，你需要找到最小的32位整数，其与 n 中存在的位数完全相同，并且其值大于n。如果不存在这样的32位整数，则返回-1。
示例 1:
输入: 12
输出: 21
示例 2:
输入: 21
输出: -1
class Solution {
public:
int nextGreaterElement(int n) {
char*sn;
int len=IntToStr(n,10,sn);
if(!next_permutation(sn,sn+len))return -1;
long long res = StrToInt(sn,10);
if(res==int(res))return res;
return -1;
}
};
559. N 叉树的最大深度
560. 和为K的子数组
剑指 Offer II 010. 和为 k 的子数组
https://blog.csdn.net/nameofcsdn/article/details/119833252
565. 数组嵌套
567. 字符串的排列
剑指 Offer II 014. 字符串中的变位词
https://blog.csdn.net/nameofcsdn/article/details/119833252
589. N 叉树的前序遍历
590. N 叉树的后序遍历