目录
604. 迭代压缩字符串
605. 种花问题
假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。
示例 1：
输入：flowerbed = [1,0,0,0,1], n = 1 输出：true
示例 2：
输入：flowerbed = [1,0,0,0,1], n = 2 输出：false
提示：
1 <= flowerbed.length <= 2 * 104flowerbed[i]为0或1flowerbed中不存在相邻的两朵花0 <= n <= flowerbed.length
class Solution {
public:
bool canPlaceFlowers(vector<int>& v, int n) {
int a=-2,ans=0;
for(int i=0;i<v.size();i++){
if(v[i]){
if(i-a>3)ans+=(i-a)/2-1;
a=i;
}
}
ans+=(v.size()-1-a)/2;
return ans>=n;
}
};611. 有效三角形的个数
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums = [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3
示例 2:
输入: nums = [4,2,3,4] 输出: 4
提示:
1 <= nums.length <= 10000 <= nums[i] <= 1000
class Solution:public Bsearch<int> {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
this->nums = nums;
int ans = 0;
for (int i = 0; i < nums.size(); i++)for (int j = i + 1; j < nums.size(); j++) {
if (nums[i] <= 0 || nums[j] <= 0)continue;
s = nums[i] + nums[j];
int id = find(j, nums.size() - 1);
ans += id - j - 1;
}
return ans;
}
bool isOk(int x) const
{
return nums[x] >= s;
}
vector<int> nums;
int s;
};617. 合并二叉树
621. 任务调度器
贪心 贪心（2）活动安排问题_nameofcsdn的博客-CSDN博客
624. 数组列表中的最大距离
给定 m 个数组，每个数组都已经按照升序排好序了。现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数 a 和 b 之间的距离定义为它们差的绝对值 |a-b| 。你的任务就是去找到最大距离
示例 1：
输入：
[[1,2,3],
[4,5],
[1,2,3]]
输出： 4
解释：
一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5 。
注意：
每个给定数组至少会有 1 个数字。列表中至少有两个非空数组。
所有 m 个数组中的数字总数目在范围 [2, 10000] 内。
m 个数组中所有整数的范围在 [-10000, 10000] 内。
class Solution {
public:
void minmax(vector<vector<int>>& v, int& minid, int& maxid)
{
minid = 0, maxid = 0;
for (int i = 1; i < v.size(); i++) {
if (v[minid][0] > v[i][0])minid = i;
if (v[maxid].back() < v[i].back())maxid = i;
}
}
int maxDistance(vector<vector<int>>& v) {
int minid = 0, maxid = 0;
minmax(v, minid, maxid);
int a = v[minid][0], b = v[maxid].back();
if (minid != maxid)return b - a;
v.erase(v.begin() + minid);
minmax(v, minid, maxid);
int c = v[minid][0], d = v[maxid].back();
return max(b - c, d - a);
}
};625. 最小因式分解
给定一个正整数 a，找出最小的正整数 b 使得 b 的所有数位相乘恰好等于 a。
如果不存在这样的结果或者结果不是 32 位有符号整数，返回 0。
样例 1
输入：
48
输出：
68
样例 2
输入：
15
输出：
35
思路一，因式分解成2，3，5，7，再根据调整法得到贪心策略（关于2和3怎么组合）
class Solution {
public:
int smallestFactorization(int num) {
if(num==1)return 1;
int a2 = 0, a3 = 0, a5 = 0, a7 = 0;
while (num % 2 == 0)a2++, num /= 2;
while (num % 3 == 0)a3++, num /= 3;
while (num % 5 == 0)a5++, num /= 5;
while (num % 7 == 0)a7++, num /= 7;
if (num > 1)return 0;
vector<int>vf;
while (a7--)vf.push_back(7);
while (a5--)vf.push_back(5);
while (a2 >= 3)a2 -= 3, vf.push_back(8);
while (a3 >= 2)a3 -= 2, vf.push_back(9);
int k = 1;
while (a2--)k *= 2;
while (a3--)k *= 3;
if (k == 12)vf.push_back(2), vf.push_back(6);
else if (k > 1)vf.push_back(k);
if (vf.size() > 10)return 0;
sort(vf.begin(), vf.end());
long long n = 0;
for (auto& vi : vf)n *= 10, n += vi;
if (n > INT_MAX)return 0;
return n;
}
};
思路二，直接分成成2-9，大的优先。
class Solution {
public:
int smallestFactorization(int num) {
if (num == 1)return 1;
vector<int>vf;
for (int i = 9; i > 1; i--)while (num % i == 0)num/=i, vf.insert(vf.begin(),i);
if (num>1 || vf.size() > 10)return 0;
long long n = 0;
for (auto& vi : vf)n *= 10, n += vi;
if (n > INT_MAX)return 0;
return n;
}
};
628. 三个数的最大乘积
629. K 个逆序对数组
630. 课程表 III
贪心 贪心（2）活动安排问题_nameofcsdn的博客-CSDN博客
632. 最小区间
633. 平方数之和
634. 寻找数组的错位排列
643. 子数组最大平均数 I
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。
示例 1：
输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
示例 2：
输入：nums = [5], k = 1
输出：5.00000
提示：
n == nums.length
1 <= k <= n <= 105
-104 <= nums[i] <= 104
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int s = 0;
for (int i = 0; i < k; i++)s += nums[i];
double ans = s;
for (int i = k; i < nums.size(); i++) {
s += nums[i] - nums[i - k], ans = max(ans, s*1.0);
}
return ans / k;
}
};644. 子数组最大平均数 II
646. 最长数对链
647. 回文子串
651. 四个键的键盘
653. 两数之和 IV - 输入二叉搜索树
给定一个二叉搜索树 root 和一个目标结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true。
示例 1：
输入: root = [5,3,6,2,4,null,7], k = 9 输出: true
示例 2：
输入: root = [5,3,6,2,4,null,7], k = 28 输出: false
提示:
- 二叉树的节点个数的范围是
[1, 104]. -104 <= Node.val <= 104- 题目数据保证，输入的
root是一棵 有效 的二叉搜索树 -105 <= k <= 105
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
map<int,int>m;
if(root)dfs(root,m);
for(auto mi:m){
if(mi.first*2!=k && m.find(k-mi.first)!=m.end())return true;
}
return false;
}
void dfs(TreeNode* root, map<int,int>&m){
m[root->val]++;
if(root->left)dfs(root->left,m);
if(root->right)dfs(root->right,m);
}
};654. 最大二叉树
660. 移除 9
664. 奇怪的打印机
661. 图片平滑器
图像平滑器 是大小为 3 x 3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。
每个单元格的 平均灰度 定义为：该单元格自身及其周围的 8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 9 个单元格的平均值）。
如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 4 个单元格的平均值）。
给你一个表示图像灰度的 m x n 整数矩阵 img ，返回对图像的每个单元格平滑处理后的图像 。
示例 1:
输入:img = [[1,1,1],[1,0,1],[1,1,1]] 输出:[[0, 0, 0],[0, 0, 0], [0, 0, 0]] 解释: 对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0 对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0 对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0
示例 2:
输入: img = [[100,200,100],[200,50,200],[100,200,100]] 输出: [[137,141,137],[141,138,141],[137,141,137]] 解释: 对于点 (0,0), (0,2), (2,0), (2,2): floor((100+200+200+50)/4) = floor(137.5) = 137 对于点 (0,1), (1,0), (1,2), (2,1): floor((200+200+50+200+100+100)/6) = floor(141.666667) = 141 对于点 (1,1): floor((50+200+200+200+200+100+100+100+100)/9) = floor(138.888889) = 138
提示:
m == img.lengthn == img[i].length1 <= m, n <= 2000 <= img[i][j] <= 255
class Solution {
public:
vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
vector<vector<int>>ans;
for(int i=0;i<img.size();i++){
vector<int>v;
for(int j=0;j<img[0].size();j++){
int s=0,n=0;
for(int ii=i-1;ii<=i+1;ii++){
for(int jj=j-1;jj<=j+1;jj++){
if(ii<0||ii>=img.size())continue;
if(jj<0||jj>=img[0].size())continue;
n++;
s+=img[ii][jj];
}
}
v.push_back(n?(s/n):0);
}
ans.push_back(v);
}
return ans;
}
};670. 最大交换
给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
示例 1 :
输入: 2736 输出: 7236 解释: 交换数字2和数字7。
示例 2 :
输入: 9973 输出: 9973 解释: 不需要交换。
注意:
- 给定数字的范围是 [0, 108]
class Solution {
public:
int maximumSwap(int num) {
char* str;
int len = intToStr(num,10,str);
for(int i=0;i<len;i++){
int id=i;
for(int j=i+1;j<len;j++){
if(str[j]>=str[id])id=j;
}
if(str[id]>str[i]){
auto c = str[id];
str[id]=str[i],str[i]=c;
return strToInt(str,10);
}
}
return num;
}
};672. 灯泡开关 Ⅱ
673. 最长递增子序列的个数
679. 24 点游戏
680. 验证回文字符串 Ⅱ
剑指 Offer II 019. 最多删除一个字符得到回文
力扣OJ 剑指 Offer II_csuzhucong的博客-CSDN博客
683. K 个关闭的灯泡
684. 冗余连接
685. 冗余连接 II
686. 重复叠加字符串匹配
690. 员工的重要性
693. 交替位二进制数
题目：
给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。
示例 1:
输入: 5
输出: True
解释:
5的二进制数是: 101
示例 2:
输入: 7
输出: False
解释:
7的二进制数是: 111
示例 3:
输入: 11
输出: False
解释:
11的二进制数是: 1011
示例 4:
输入: 10
输出: True
解释:
10的二进制数是: 1010
代码：
class Solution {
public:
bool hasAlternatingBits2(int n) {
if (n == 0)return true;
if (n % 4 == 1)return hasAlternatingBits2(n / 4);
return false;
}
bool hasAlternatingBits(int n) {
if (n % 2 == 0)n /= 2;
return hasAlternatingBits2(n);
}
};694. 不同岛屿的数量
695. 岛屿的最大面积
697. 数组的度
698. 划分为k个相等的子集
题目：
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
示例 1：
输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
注意:
1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
思路：
DFS，注意剪枝，我这里采用的是简单的降序排序，排序可以让执行时间从2000ms降为4ms
代码：
int s[16];
class Solution {
public:
bool canPartitionKSubsets(vector<int> &nums, int k, int deep)
{
if (deep >= nums.size())return true;
for (int j = 0; j <= deep && j < k; j++) {
if (s[j] < nums[deep])continue;
s[j] -= nums[deep];
if (canPartitionKSubsets(nums, k, deep + 1))return true;
s[j] += nums[deep];
}
return false;
}
bool canPartitionKSubsets(vector<int> &nums, int k)
{
if (nums.size() < k || k <= 0 || k > 16)return false;
sort(nums.begin(),nums.end(),greater<int>());
int anss = 0;
for (auto it = nums.begin(); it != nums.end(); it++) anss += *it;
if (anss % k) return false;
anss /= k;
for (int i = 0; i < k; i++) s[i] = anss;
return canPartitionKSubsets(nums, k, 0);
}
};702. 搜索长度未知的有序数组
这是一个交互问题。
您有一个升序整数数组，其长度未知。您没有访问数组的权限，但是可以使用 ArrayReader 接口访问它。你可以调用 ArrayReader.get(i):
-
返回数组第
ith个索引(0-indexed)处的值(即secret[i])，或者 -
如果
i超出了数组的边界，则返回231 - 1
你也会得到一个整数 target。
如果存在secret[k] == target，请返回索引 k 的值；否则返回 -1
你必须写一个时间复杂度为 O(log n) 的算法。
示例 1：
输入:secret= [-1,0,3,5,9,12],target= 9 输出: 4 解释: 9 存在在 nums 中，下标为 4
示例 2：
输入:secret= [-1,0,3,5,9,12],target= 2 输出: -1 解释: 2 不在数组中所以返回 -1
提示：
1 <= secret.length <= 104-104 <= secret[i], target <= 104secret严格递增
class SS:public Bsearch<int> {
public:
SS(const ArrayReader& reader, int target):reader(reader){
this->target=target;
}
bool isOk(int x) //若isOk(x)且!isOk(y)则必有y<x
{
return reader.get(x)>=target;
}
const ArrayReader &reader;
int target;
};
class Solution:public Bsearch<int> {
public:
int search(const ArrayReader& reader, int target) {
int id = SS(reader,target).find(0,10001);
return reader.get(id)==target?id:-1;
}
};703. 数据流中的第 K 大元素
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
KthLargest(int k, int[] nums)使用整数k和整数流nums初始化对象。int add(int val)将val插入数据流nums后，返回当前数据流中第k大的元素。
示例：
输入： ["KthLargest", "add", "add", "add", "add", "add"] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] 输出： [null, 4, 5, 5, 8, 8] 解释： KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8
提示：
1 <= k <= 1040 <= nums.length <= 104-104 <= nums[i] <= 104-104 <= val <= 104- 最多调用
add方法104次 - 题目数据保证，在查找第
k大元素时，数组中至少有k个元素
class KthLargest {
public:
KthLargest(int k, vector<int>& nums) {
for(auto x:nums)s.insert(x);
while(s.size()>k)s.erase(s.begin());
n=k;
}
int add(int val) {
s.insert(val);
if(s.size()>n)s.erase(s.begin());
return *s.begin();
}
multiset<int>s;
int n;
};704. 二分查找
705. 设计哈希集合
不使用任何内建的哈希表库设计一个哈希集合（HashSet）。
实现 MyHashSet 类：
void add(key)向哈希集合中插入值key。bool contains(key)返回哈希集合中是否存在这个值key。void remove(key)将给定值key从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
示例：
输入： ["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"] [[], [1], [2], [1], [3], [2], [2], [2], [2]] 输出： [null, null, null, true, false, null, true, null, false] 解释： MyHashSet myHashSet = new MyHashSet(); myHashSet.add(1); // set = [1] myHashSet.add(2); // set = [1, 2] myHashSet.contains(1); // 返回 True myHashSet.contains(3); // 返回 False ，（未找到） myHashSet.add(2); // set = [1, 2] myHashSet.contains(2); // 返回 True myHashSet.remove(2); // set = [1] myHashSet.contains(2); // 返回 False ，（已移除）
提示：
0 <= key <= 106- 最多调用
104次add、remove和contains
class MyHashSet {
public:
MyHashSet() {
for(int i=0;i<=1000000;i++)flag[i]=false;
}
void add(int key) {
flag[key]=true;
}
void remove(int key) {
flag[key]=false;
}
bool contains(int key) {
return flag[key];
}
bool flag[1000001];
};706. 设计哈希映射
不使用任何内建的哈希表库设计一个哈希映射（HashMap）。
实现 MyHashMap 类：
MyHashMap()用空映射初始化对象void put(int key, int value)向 HashMap 插入一个键值对(key, value)。如果key已经存在于映射中，则更新其对应的值value。int get(int key)返回特定的key所映射的value；如果映射中不包含key的映射，返回-1。void remove(key)如果映射中存在key的映射，则移除key和它所对应的value。
示例：
输入： ["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"] [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]] 输出： [null, null, null, 1, -1, null, 1, null, -1] 解释： MyHashMap myHashMap = new MyHashMap(); myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]] myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]] myHashMap.get(1); // 返回 1 ，myHashMap 现在为 [[1,1], [2,2]] myHashMap.get(3); // 返回 -1（未找到），myHashMap 现在为 [[1,1], [2,2]] myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]]（更新已有的值） myHashMap.get(2); // 返回 1 ，myHashMap 现在为 [[1,1], [2,1]] myHashMap.remove(2); // 删除键为 2 的数据，myHashMap 现在为 [[1,1]] myHashMap.get(2); // 返回 -1（未找到），myHashMap 现在为 [[1,1]]
提示：
0 <= key, value <= 106- 最多调用
104次put、get和remove方法
class MyHashMap {
public:
MyHashMap() {
for(int i=0;i<=1000000;i++)flag[i]=-1;
}
void put(int key, int value) {
flag[key]=value;
}
int get(int key) {
return flag[key];
}
void remove(int key) {
flag[key]=-1;
}
int flag[1000001];
};
/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap* obj = new MyHashMap();
* obj->put(key,value);
* int param_2 = obj->get(key);
* obj->remove(key);
*/708. 循环有序列表的插入
713. 乘积小于K的子数组
714. 买卖股票的最佳时机含手续费
716. 最大栈
720. 词典中最长的单词
给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。
若无答案，则返回空字符串。
示例 1：
输入：
words = ["w","wo","wor","worl", "world"]
输出："world"
解释：
单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。
示例 2：
输入：
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
输出："apple"
解释：
"apply"和"apple"都能由词典中的单词组成。但是"apple"的字典序小于"apply"。
提示：
所有输入的字符串都只包含小写字母。
words数组长度范围为[1,1000]。
words[i]的长度范围为[1,30]。
我的代码：（动态规划的备忘录写法）
map<string,int>exitt;
map<string,int>m;
void init(vector<string>& words)
{
exitt.clear();
m.clear();
for(int i=0;i<words.size();i++){
exitt[words[i]]=1;
}
}
string preString(string s)
{
if(s.length()<=1){
return "";
}
return s.substr(0,s.length()-1);
}
int dp(string s)
{
if(m[s])return m[s];
if(s.length()==1)return 1;
if(exitt[preString(s)] && dp(preString(s))>0)return m[s]=dp(preString(s))+1;
return m[s]=-1;
}
class Solution {
public:
string longestWord(vector<string>& words) {
init(words);
string ans="";
for(int i=0;i<words.size();i++){
int ret=dp(words[i]);
if(ret==-1)continue;
if(ans.length()<words[i].length() || ans.length()==words[i].length() && ans>words[i])
ans=words[i];
}
cout<<exitt["e"];
return ans;
}
};也可以用字典树做。
724. 寻找数组的中心下标
729. 我的日程安排表 I
实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。
当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。
日程可以用一对整数 startTime 和 endTime 表示，这里的时间是半开区间，即 [startTime, endTime), 实数 x 的范围为， startTime <= x < endTime 。
实现 MyCalendar 类：
MyCalendar()初始化日历对象。boolean book(int startTime, int endTime)如果可以将日程安排成功添加到日历中而不会导致重复预订，返回true。否则，返回false并且不要将该日程安排添加到日历中。
示例：
输入： ["MyCalendar", "book", "book", "book"] [[], [10, 20], [15, 25], [20, 30]] 输出： [null, true, false, true] 解释： MyCalendar myCalendar = new MyCalendar(); myCalendar.book(10, 20); // return True myCalendar.book(15, 25); // return False ，这个日程安排不能添加到日历中，因为时间 15 已经被另一个日程安排预订了。 myCalendar.book(20, 30); // return True ，这个日程安排可以添加到日历中，因为第一个日程安排预订的每个时间都小于 20 ，且不包含时间 20 。
提示：
0 <= start < end <= 109- 每个测试用例，调用
book方法的次数最多不超过1000次。
class MyCalendar {
public:
MyCalendar() {
opt = CloseInterval<0>{};
}
bool book(int startTime, int endTime) {
auto ci = CloseIval<0, int>{ startTime, endTime - 1 };
auto it = lower_bound(opt.allCi.begin(), opt.allCi.end(), ci);
if (it != opt.allCi.end() && it->high >= ci.low && it->low <= ci.high) {
return false;
}
if (it != opt.allCi.begin()) {
it--;
}
if (it != opt.allCi.end() && it->high >= ci.low && it->low <= ci.high) {
return false;
}
opt.push(ci);
return true;
}
CloseInterval<0> opt;
};
731. 我的日程安排表 II
实现一个程序来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。
当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生 三重预订。
事件能够用一对整数 startTime 和 endTime 表示，在一个半开区间的时间 [startTime, endTime) 上预定。实数 x 的范围为 startTime <= x < endTime。
实现 MyCalendarTwo 类：
MyCalendarTwo()初始化日历对象。boolean book(int startTime, int endTime)如果可以将日程安排成功添加到日历中而不会导致三重预订，返回true。否则，返回false并且不要将该日程安排添加到日历中。
示例 1：
输入： ["MyCalendarTwo", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]] 输出： [null, true, true, true, false, true, true] 解释： MyCalendarTwo myCalendarTwo = new MyCalendarTwo(); myCalendarTwo.book(10, 20); // 返回 True，能够预定该日程。 myCalendarTwo.book(50, 60); // 返回 True，能够预定该日程。 myCalendarTwo.book(10, 40); // 返回 True，该日程能够被重复预定。 myCalendarTwo.book(5, 15); // 返回 False，该日程导致了三重预定，所以不能预定。 myCalendarTwo.book(5, 10); // 返回 True，能够预定该日程，因为它不使用已经双重预订的时间 10。 myCalendarTwo.book(25, 55); // 返回 True，能够预定该日程，因为时间段 [25, 40) 将被第三个日程重复预定，时间段 [40, 50) 将被单独预定，而时间段 [50, 55) 将被第二个日程重复预定。
提示：
0 <= start < end <= 109- 最多调用
book1000 次。
class MyCalendarTwo {
public:
bool book(int startTime, int endTime) {
auto vsbk = vs;
auto vebk = ve;
vs.push_back(startTime);
sort(vs.begin(),vs.end());
ve.push_back(endTime);
sort(ve.begin(), ve.end());
int n = 0, i = 0, j = 0;
while (i < vs.size() && j < ve.size()) {
if (vs[i] < ve[j]) {
i++;
if (++n >= 3) {
vs = vsbk, ve = vebk;
return false;
}
}
else {
j++;
n--;
}
}
while (i < vs.size()) {
if (vs[i] < ve[j]) {
i++;
if (++n >= 3) {
vs = vsbk, ve = vebk;
return false;
}
}
}
return true;
}
vector<int>vs;
vector<int>ve;
};733. 图像渲染
734. 句子相似性
735. 小行星碰撞
738. 单调递增的数字
题目：
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
示例 1:
输入: N = 10
输出: 9
示例 2:
输入: N = 1234
输出: 1234
示例 3:
输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。
代码：
class Solution {
public:
int monotoneIncreasingDigits(int N) {
int key = 1111111111, ans = 0, num = 9;
while (key)
{
while (N >= key && num > 0)
{
N -= key, ans += key, num--;
}
key /= 10;
}
return ans;
}
};739. 每日温度
740. 删除与获得点数
给定一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1:
输入: nums = [3, 4, 2]
输出: 6
解释:
删除 4 来获得 4 个点数，因此 3 也被删除。
之后，删除 2 来获得 2 个点数。总共获得 6 个点数。
示例 2:
输入: nums = [2, 2, 3, 3, 3, 4]
输出: 9
解释:
删除 3 来获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。
注意:
nums的长度最大为20000。
每个整数nums[i]的大小都在[1, 10000]范围内。
class Solution {
public:
int s[10001];
int ans[10001];
int dp(int k)
{
if(k<0)return 0;
if(ans[k])return ans[k];
return ans[k]=max(s[k]+dp(k-2),dp(k-1));
}
int deleteAndEarn(vector<int>& nums) {
if(nums.size()==0)return 0;
memset(ans,0,sizeof(int)*10001);
memset(s,0,sizeof(int)*10001);
for(int i=0;i<nums.size();i++)s[nums[i]]+=nums[i];
return dp(10000);
}
};741. 摘樱桃
742. 二叉树最近的叶节点
给定一个 每个结点的值互不相同 的二叉树，和一个目标整数值 k，返回 树中与目标值 k 最近的叶结点 。
与叶结点最近 表示在二叉树中到达该叶节点需要行进的边数与到达其它叶结点相比最少。而且，当一个结点没有孩子结点时称其为叶结点。
示例 1：
输入：root = [1, 3, 2], k = 1
输出： 2
解释： 2 和 3 都是距离目标 1 最近的叶节点。
示例 2：
输入：root = [1], k = 1
输出：1
解释：最近的叶节点是根结点自身。
示例 3：
输入：root = [1,2,3,4,null,null,null,5,null,6], k = 2
输出：3
解释：值为 3（而不是值为 6）的叶节点是距离结点 2 的最近结点。
提示：
二叉树节点数在 [1, 1000] 范围内
1 <= Node.val <= 1000
每个节点值都 不同
给定的二叉树中有某个结点使得 node.val == k
这个代码写的很烂很痛苦，最终还是AC了。
class Solution {
public:
map< TreeNode*, int>m;
map< TreeNode*, int>m2;
bool flag;
int dfs(TreeNode* root, int& num)
{
if (!root->left && !root->right) {
m[root] = 1, num = m2[root] = root->val;
return 1;
}
int deep = INT_MAX;
if (root->left)deep = dfs(root->left, num) + 1, m2[root] = num;
if (root->right) {
int ret = dfs(root->right, num);
if (deep > ret + 1) {
deep = min(deep, ret + 1), m2[root] = num;
}
else num = m2[root];
}
m[root] = deep;
return deep;
}
int dfs2(TreeNode* root, int k, int n, int& num) {
if (root->val == k) {
int ans = m[root];
num = m2[root];
return min(ans, n + 1);
}
if (root->left) {
int ans = dfs2(root->left, k, min(n + 1, m[root]), num);
if (flag && ans == min(n + 1, m[root]) + 1)num = m2[root];
else if (ans != -1) {
flag = false;
return ans + 1;
}
if (ans != -1)return ans - 1;
}
if (root->right) {
int ans = dfs2(root->right, k, min(n + 1, m[root]), num);
if (flag && ans == min(n + 1, m[root]) + 1)num = m2[root];
else if (ans != -1) {
flag = false;
return ans + 1;
}
if (ans != -1)return ans - 1;
}
return -1;
}
int findClosestLeaf(TreeNode* root, int k) {
int num;
flag = true;
dfs(root, num);
dfs2(root, k, m[root] - 1, num);
return num;
}
};743. 网络延迟时间
746. 使用最小花费爬楼梯
https://blog.csdn.net/nameofcsdn/article/details/119833252
750. 角矩形的数量
给定一个只包含 0 和 1 的 m x n 整数矩阵 grid ，返回 其中 「角矩形 」的数量 。
一个「角矩形」是由四个不同的在矩阵上的 1 形成的 轴对齐 的矩形。注意只有角的位置才需要为 1。
注意：4 个 1 的位置需要是不同的。
示例 1：
输入：grid = [[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]] 输出：1 解释：只有一个角矩形，角的位置为 grid[1][2], grid[1][4], grid[3][2], grid[3][4]。
示例 2：
输入：grid = [[1,1,1],[1,1,1],[1,1,1]] 输出：9 解释：这里有 4 个 2x2 的矩形，4 个 2x3 和 3x2 的矩形和 1 个 3x3 的矩形。
示例 3：
输入：grid = [[1,1,1,1]] 输出：0 解释：矩形必须有 4 个不同的角。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 200grid[i][j]不是0就是1- 网格中
1的个数在[1, 6000]范围内
class Solution {
public:
int countCornerRectangles(vector<vector<int>>& grid) {
int ans=0;
for(int i=0;i<grid.size();i++){
for(int j=i+1;j<grid.size();j++){
ans+=countCornerRectangles(grid[i],grid[j]);
}
}
return ans;
}
int countCornerRectangles(vector<int>& v1,vector<int>& v2) {
int s=0;
for(int i=0;i<v1.size();i++)if(v1[i]==1 && v2[i]==1)s++;
return s*(s-1)/2;
}
};752. 打开转盘锁
753. 破解保险箱
754. 到达终点数字
在一根无限长的数轴上，你站在0的位置。终点在target的位置。
你可以做一些数量的移动 numMoves :
- 每次你可以选择向左或向右移动。
- 第
i次移动（从i == 1开始，到i == numMoves），在选择的方向上走i步。
给定整数 target ，返回 到达目标所需的 最小 移动次数(即最小 numMoves ) 。
示例 1:
输入: target = 2 输出: 3 解释: 第一次移动，从 0 到 1 。 第二次移动，从 1 到 -1 。 第三次移动，从 -1 到 2 。
示例 2:
输入: target = 3 输出: 2 解释: 第一次移动，从 0 到 1 。 第二次移动，从 1 到 3 。
提示:
-109 <= target <= 109target != 0
思路：第k次移动之后可能到达的位置是非常有规律的。
class Solution {
public:
int reachNumber(long long n) {
int x=ceil((sqrt(abs(n)*8+1)-1)/2);
return (n+1+(x-1)%4/2)%2?x+x%2+1:x;
}
};756. 金字塔转换矩阵
760. 找出变位映射
给定两个列表 Aand B，并且 B 是 A 的变位（即 B 是由 A 中的元素随机排列后组成的新列表）。
我们希望找出一个从 A 到 B 的索引映射 P 。一个映射 P[i] = j 指的是列表 A 中的第 i 个元素出现于列表 B 中的第 j 个元素上。
列表 A 和 B 可能出现重复元素。如果有多于一种答案，输出任意一种。
例如，给定
A = [12, 28, 46, 32, 50] B = [50, 12, 32, 46, 28]
需要返回
[1, 4, 3, 2, 0]
P[0] = 1 ，因为 A 中的第 0 个元素出现于 B[1]，而且 P[1] = 4 因为 A 中第 1 个元素出现于 B[4]，以此类推。
注：
A, B有相同的长度，范围为[1, 100]。A[i], B[i]都是范围在[0, 10^5]的整数。
template<typename T=int>
class Solution {
public:
vector<int> anagramMappings(vector<T>& nums1, vector<T>& nums2) {
map<T,vector<int>>m1=statistics(nums1);
map<T,vector<int>>m2=statistics(nums2);
vector<int>ans(nums1.size());
for(auto mi:m1){
auto v1=mi.second;
auto v2=m2[mi.first];
for(int i=0;i<v1.size();i++)ans[v1[i]]=v2[i];
}
return ans;
}
map<T,vector<int>> statistics(vector<T>&nums){
map<T,vector<int>>m;
for(int i=0;i<nums.size();i++){
m[nums[i]].push_back(i);
}
return m;
}
};
762. 二进制表示中质数个计算置位
题目：
给定两个整数 L 和 R ，找到闭区间 [L, R] 范围内，计算置位位数为质数的整数个数。
（注意，计算置位代表二进制表示中1的个数。例如 21 的二进制表示 10101 有 3 个计算置位。还有，1 不是质数。）
示例 1:
输入: L = 6, R = 10
输出: 4
解释:
6 -> 110 (2 个计算置位，2 是质数)
7 -> 111 (3 个计算置位，3 是质数)
9 -> 1001 (2 个计算置位，2 是质数)
10-> 1010 (2 个计算置位，2 是质数)
示例 2:
输入: L = 10, R = 15
输出: 5
解释:
10 -> 1010 (2 个计算置位, 2 是质数)
11 -> 1011 (3 个计算置位, 3 是质数)
12 -> 1100 (2 个计算置位, 2 是质数)
13 -> 1101 (3 个计算置位, 3 是质数)
14 -> 1110 (3 个计算置位, 3 是质数)
15 -> 1111 (4 个计算置位, 4 不是质数)
注意:
L, R 是 L <= R 且在 [1, 10^6] 中的整数。
R - L 的最大值为 10000。
代码：
class Solution {
public:
int hammingWeight(int n) {
int ans = 0;
while (n)
{
n ^= (n&(-n));
ans++;
}
return ans;
}
int countPrimeSetBits(int L, int R) {
set<int>se = { 2, 3, 5, 7 ,11,13,17,19};
int ans = 0;
for (int i = L; i <= R; i++)
{
if (se.find(hammingWeight(i)) != se.end())ans++;
}
return ans;
}
};764. 最大加号标志
767. 重构字符串
769. 最多能完成排序的块
771. 宝石与石头
给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。
示例 1：
输入：jewels = "aA", stones = "aAAbbbb" 输出：3
示例 2：
输入：jewels = "z", stones = "ZZ" 输出：0
提示：
1 <= jewels.length, stones.length <= 50jewels和stones仅由英文字母组成jewels中的所有字符都是 唯一的
class Solution {
public:
int numJewelsInStones(string jewels, string stones) {
map<char,char>m;
for(auto c:jewels)m[c]++;
int ans=0;
for(auto c:stones)if(m[c])ans++;
return ans;
}
};772. 基本计算器 III
实现一个基本的计算器来计算简单的表达式字符串。
表达式字符串只包含非负整数，算符 +、-、*、/ ，左括号 ( 和右括号 ) 。整数除法需要 向下截断 。
你可以假定给定的表达式总是有效的。所有的中间结果的范围均满足 [-231, 231 - 1] 。
注意：你不能使用任何将字符串作为表达式求值的内置函数，比如 eval() 。
示例 1：
输入：s = "1+1" 输出：2
示例 2：
输入：s = "6-4/2" 输出：4
示例 3：
输入：s = "2*(5+5*2)/3+(6/2+8)" 输出：21
提示：
1 <= s <= 104s由整数、'+'、'-'、'*'、'/'、'('和')'组成s是一个 有效的 表达式
class Solution {
public:
int calculate(string s) {
stack<int> stk;
int num = 0;
char sign = '+';
for (int i = 0; i < s.size(); i++) {
char c = s[i];
if (isdigit(c)) {
num = num * 10 + (c - '0');
}
if (c == '(') {
int n = 1;
for (int j = i + 1; j < s.size(); j++) {
if (s[j] == '(')n++;
if (s[j] == ')')n--;
if(n==0) {
num = calculate(s.substr(i + 1, j - i - 1));
i = j;
break;
}
}
}
if (!isdigit(c) && c != ' ' || i == s.size() - 1) {
if (sign == '+') {
stk.push(num);
}
else if (sign == '-') {
stk.push(-num);
}
else if (sign == '*') {
int top = stk.top();
stk.pop();
stk.push(top * num);
}
else if (sign == '/') {
int top = stk.top();
stk.pop();
stk.push(top / num);
}
sign = c;
num = 0;
}
}
int res = 0;
while (!stk.empty()) {
res += stk.top();
stk.pop();
}
return res;
}
};774. 最小化去加油站的最大距离
整数数组 stations 表示 水平数轴 上各个加油站的位置。给你一个整数 k 。
请你在数轴上增设 k 个加油站，新增加油站可以位于 水平数轴 上的任意位置，而不必放在整数位置上。
设 penalty() 是：增设 k 个新加油站后，相邻 两个加油站间的最大距离。
请你返回 penalty() 可能的最小值。与实际答案误差在 10-6 范围内的答案将被视作正确答案。
示例 1：
输入：stations = [1,2,3,4,5,6,7,8,9,10], k = 9
输出：0.50000
示例 2：
输入：stations = [23,24,36,39,46,56,57,65,84,98], k = 1
输出：14.00000
提示：
10 <= stations.length <= 2000
0 <= stations[i] <= 108
stations 按 严格递增 顺序排列
1 <= k <= 106
class Solution {
public:
bool ok(vector<int>& stations, int k, double d)
{
int s = 0;
for (int i = 1; i < stations.size(); i++)s += (stations[i] - stations[i - 1]) / d;
return s <= k;
}
double minmaxGasDist(vector<int>& stations, int k) {
double low = 1.0 / k, high = stations.back() - stations[0];
while (high - low > 0.00001) {
double mid = (low + high) / 2;
if (ok(stations, k, mid))high = mid;
else low = mid;
}
return high;
}
};776. 拆分二叉搜索树
778. 水位上升的泳池中游泳
785. 判断二分图
787. K 站中转内最便宜的航班
790. 多米诺和托米诺平铺
有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。
给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。
平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。
示例 1:
输入: n = 3 输出: 5 解释: 五种不同的方法如上所示。
示例 2:
输入: n = 1 输出: 1
提示：
1 <= n <= 1000
class Solution {
public:
int numTilings(int n) {
if(n<2)return 1;
n-=2;
int a=1,b=1,c=2,d=0;
while(n--)d=(c*2%1000000007+a)%1000000007,a=b,b=c,c=d;
return c;
}
};791. 自定义字符串排序
给定两个字符串 order 和 s 。order 的所有单词都是 唯一 的，并且以前按照一些自定义的顺序排序。
对 s 的字符进行置换，使其与排序的 order 相匹配。更具体地说，如果在 order 中的字符 x 出现字符 y 之前，那么在排列后的字符串中， x 也应该出现在 y 之前。
返回 满足这个性质的 s 的任意排列 。
示例 1:
输入: order = "cba", s = "abcd" 输出: "cbad" 解释: “a”、“b”、“c”是按顺序出现的，所以“a”、“b”、“c”的顺序应该是“c”、“b”、“a”。 因为“d”不是按顺序出现的，所以它可以在返回的字符串中的任何位置。“dcba”、“cdba”、“cbda”也是有效的输出。
示例 2:
输入: order = "cbafg", s = "abcd" 输出: "cbad"
提示:
1 <= order.length <= 261 <= s.length <= 200order和s由小写英文字母组成order中的所有字符都 不同
class Solution {
public:
string customSortString(string order, string s) {
map<char,int>m1,m2;
for(auto c:order)m1[c]=1;
string ans;
for(auto c:s){
if(m1[c])m2[c]++;
else ans+=c;
}
for(auto c:order)while(m2[c]--)ans+=c;
return ans;
}
};793. 阶乘函数后 K 个零
795. 区间子数组个数
给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。
生成的测试用例保证结果符合 32-bit 整数范围。
示例 1：
输入：nums = [2,1,4,3], left = 2, right = 3 输出：3 解释：满足条件的三个子数组：[2], [2, 1], [3]
示例 2：
输入：nums = [2,9,2,5,6], left = 2, right = 8 输出：7
提示：
1 <= nums.length <= 1050 <= nums[i] <= 1090 <= left <= right <= 109
class Solution {
public:
long long numSubarrayBoundedMax(vector<int>& nums, int key) {
int low=0;
long long ans=0;
for(int i=0;i<=nums.size();i++){
if(i<nums.size() && nums[i]<=key)continue;
ans+=(long long)(i-low)*(i-low+1)/2;
low=i+1;
}
return ans;
}
int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
return numSubarrayBoundedMax(nums,right)-numSubarrayBoundedMax(nums,left-1);
}
};797. 所有可能的路径
800. 相似 RGB 颜色
RGB 颜色 "#AABBCC" 可以简写成 "#ABC" 。
- 例如，
"#15c"其实是"#1155cc"的简写。
现在，假如我们分别定义两个颜色 "#ABCDEF" 和 "#UVWXYZ"，则他们的相似度可以通过这个表达式 -(AB - UV)^2 - (CD - WX)^2 - (EF - YZ)^2 来计算。
那么给你一个按 "#ABCDEF" 形式定义的字符串 color 表示 RGB 颜色，请你以字符串形式，返回一个与它相似度最大且可以简写的颜色。（比如，可以表示成类似 "#XYZ" 的形式）
任何 具有相同的（最大）相似度的答案都会被视为正确答案。
示例 1：
输入：color = "#09f166" 输出："#11ee66" 解释： 因为相似度计算得出 -(0x09 - 0x11)^2 -(0xf1 - 0xee)^2 - (0x66 - 0x66)^2 = -64 -9 -0 = -73 这已经是所有可以简写的颜色中最相似的了
示例 2：
输入：color = "#4e3fe1" 输出："#5544dd"
提示：
color.length == 7color[0] == '#'- 对于任何
i > 0，color[i]都是一个在范围['0', 'f']内的 16 进制数
class Solution {
public:
int toNum(char c)
{
if (c >= '0' && c <= '9')return c - '0';
return c - 'a' + 10;
}
char toChar(int n)
{
char ans = '0';
if (n < 10)return ans + n;
ans = 'a';
return ans + n - 10;
}
string similarRGB(string color) {
for (int i = 1; i < color.size(); i += 2) {
int x = toNum(color[i]);
int y = toNum(color[i+1]);
int s = x * 16 + y;
int k = 0, d = INT_MAX;
for (int i = 0; i < 16; i++) {
s -= i * 17;
if (s * s < d)d = s * s, k = i;
s+= i * 17;
}
color[i] = toChar(k);
color[i+1] = toChar(k);
}
return color;
}
};
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
