目录
621. 任务调度器
贪心 贪心（2）活动安排问题_nameofcsdn的博客-
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;
}
};
630. 课程表 III
贪心 贪心（2）活动安排问题_nameofcsdn的博客
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
数列DP
646. 最长数对链
数列DP
660. 移除 9
数位DP
673. 最长递增子序列的个数
数列DP
680. 验证回文字符串 Ⅱ
剑指 Offer II 019. 最多删除一个字符得到回文
力扣OJ 剑指 Offer II_csuzhucong的博客-
683. K 个关闭的灯泡
n 个灯泡排成一行，编号从 1 到 n 。最初，所有灯泡都关闭。每天 只打开一个 灯泡，直到 n 天后所有灯泡都打开。
给你一个长度为 n 的灯泡数组 blubs ，其中 bulls[i] = x 意味着在第 (i+1) 天，我们会把在位置 x 的灯泡打开，其中 i 从 0 开始，x 从 1 开始。
给你一个整数 k ，请返回恰好有两个打开的灯泡，且它们中间 正好 有 k 个 全部关闭的 灯泡的 最小的天数 。如果不存在这种情况，返回 -1 。
示例 1：
输入：
bulbs = [1,3,2]，k = 1
输出：2
解释：
第一天 bulbs[0] = 1，打开第一个灯泡 [1,0,0]
第二天 bulbs[1] = 3，打开第三个灯泡 [1,0,1]
第三天 bulbs[2] = 2，打开第二个灯泡 [1,1,1]
返回2，因为在第二天，两个打开的灯泡之间恰好有一个关闭的灯泡。
示例 2：
输入：bulbs = [1,2,3]，k = 1
输出：-1
提示：
n == bulbs.length
1 <= n <= 2 * 104
1 <= bulbs[i] <= n
bulbs 是一个由从 1 到 n 的数字构成的排列
0 <= k <= 2 * 104
#define op(a,b) (a<b)?a:b //min型
int n;
int num[100000];
int ans[400000];
void build(int key, int low, int high)
{
if (low == high)
{
ans[key] = num[low];
return;
}
int mid = (low + high) / 2;
build(key * 2, low, mid);
build(key * 2 + 1, mid + 1, high);
ans[key] = op(ans[key * 2], ans[key * 2 + 1]);
}
void update(int key, int low, int high, int uplace)
{
if (low == high)
{
ans[key] = num[low];
return;
}
int mid = (low + high) / 2;
if (uplace <= mid)update(key * 2, low, mid, uplace);
else update(key * 2 + 1, mid + 1, high, uplace);
ans[key] = op(ans[key * 2], ans[key * 2 + 1]);
}
int query(long long key, int low, int high, int x, int y)
{
if (low == x && high == y)return ans[key];
int mid = (low + high) / 2;
if (mid < x)return query(key * 2 + 1, mid + 1, high, x, y);
if (mid >= y)return query(key * 2, low, mid, x, y);
int a = query(key * 2, low, mid, x, mid);
int b = query(key * 2 + 1, mid + 1, high, mid + 1, y);
return op(a, b);
}
class Solution {
public:
int kEmptySlots(vector<int>& bulbs, int k) {
n = bulbs.size();
int ans = INT_MAX;
for (int i = 0; i < n; i++)num[bulbs[i]] = i;
if (k == 0) {
for (int i = 1; i < n; i++)ans = ans = min(ans, max(num[i], num[i + 1]) + 1);
return ans;
}
build(1, 1, n);
for (int i = 0; i + k + 1 < n; i++) {
if (i % 1000 == 0)cout << i;
int q = query(1, 1, n, i + 2, i + k + 1);
if (q < num[i+1] || q < num[i + k + 2])continue;
ans = min(ans, max(num[i + 1], num[i + k + 2]) + 1);
}
if (ans == INT_MAX)ans = -1;
return ans;
}
};
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);
}
};
695. 岛屿的最大面积
并查集
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);
}
};
708. 循环有序列表的插入
713. 乘积小于K的子数组
剑指 Offer II 009. 乘积小于 K 的子数组 力扣OJ 剑指 Offer II_csuzhucong的博客
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]。
2021年2月25日做了这题，这也是我把力扣题解汇总到几篇博客之后，第一次插入新题解。
我的代码：（动态规划的备忘录写法）
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. 寻找数组的中心下标
剑指 Offer II 012. 左右两边子数组的和相等 力扣OJ 剑指 Offer II_csuzhucong的博客
733. 图像渲染
并查集
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;
}
};
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);
}
};
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. 网络延迟时间
BFS
752. 打开转盘锁
双向BFS
756. 金字塔转换矩阵
DFS
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;
}
};
767. 重构字符串
贪心 贪心（3）其他排序问题_nameofcsdn的博客-
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. 水位上升的泳池中游泳
BFS
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 == 7 -
color[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;
}
};