• 力扣OJ（601-800）

    目录

    604. 迭代压缩字符串

    605. 种花问题

    611. 有效三角形的个数

    617. 合并二叉树

    621. 任务调度器

    624. 数组列表中的最大距离

    625. 最小因式分解

    628. 三个数的最大乘积

    629. K 个逆序对数组

    630. 课程表 III

    632. 最小区间

    633. 平方数之和

    634. 寻找数组的错位排列

    643. 子数组最大平均数 I

    644. 子数组最大平均数 II

    646. 最长数对链

    647. 回文子串

    651. 四个键的键盘

    653. 两数之和 IV - 输入二叉搜索树

    654. 最大二叉树

    660. 移除 9

    664. 奇怪的打印机

    670. 最大交换

    672. 灯泡开关 Ⅱ

    673. 最长递增子序列的个数

    679. 24 点游戏

    680. 验证回文字符串 Ⅱ

    683. K 个关闭的灯泡

    684. 冗余连接

    685. 冗余连接 II

    686. 重复叠加字符串匹配

    690. 员工的重要性

    693. 交替位二进制数

    695. 岛屿的最大面积

    697. 数组的度

    698. 划分为k个相等的子集

    703. 数据流中的第 K 大元素

    704. 二分查找

    705. 设计哈希集合

    706. 设计哈希映射

    708. 循环有序列表的插入

    713. 乘积小于K的子数组

    714. 买卖股票的最佳时机含手续费

    716. 最大栈

    720. 词典中最长的单词

    724. 寻找数组的中心下标

    733. 图像渲染

    734. 句子相似性

    735. 小行星碰撞

    738. 单调递增的数字

    739. 每日温度

    740. 删除与获得点数

    742. 二叉树最近的叶节点

    743. 网络延迟时间

    746. 使用最小花费爬楼梯

    750. 角矩形的数量

    752. 打开转盘锁

    753. 破解保险箱

    754. 到达终点数字

    756. 金字塔转换矩阵

    760. 找出变位映射

    762. 二进制表示中质数个计算置位

    764. 最大加号标志

    767. 重构字符串

    769. 最多能完成排序的块

    771. 宝石与石头

    774. 最小化去加油站的最大距离

    776. 拆分二叉搜索树

    778. 水位上升的泳池中游泳

    785. 判断二分图

    787. K 站中转内最便宜的航班

    790. 多米诺和托米诺平铺

    791. 自定义字符串排序

    793. 阶乘函数后 K 个零

    795. 区间子数组个数

    797. 所有可能的路径

    800. 相似 RGB 颜色

    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 * 104
    • flowerbed[i] 为 0 或 1
    • flowerbed 中不存在相邻的两朵花
    • 0 <= n <= flowerbed.length
    1. class Solution {
    2. public:
    3.     bool canPlaceFlowers(vector<int>& v, int n) {
    4.         int a=-2,ans=0;
    5.         for(int i=0;isize();i++){
    6.             if(v[i]){
    7.                 if(i-a>3)ans+=(i-a)/2-1;
    8.                 a=i;
    9.             }
    10.         }
    11.         ans+=(v.size()-1-a)/2;
    12.         return ans>=n;
    13.     }
    14. };

    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 <= 1000
    • 0 <= nums[i] <= 1000
    1. class Solution:public Bsearch<int> {
    2. public:
    3. 	int triangleNumber(vector<int>& nums) {
    4. 		sort(nums.begin(), nums.end());
    5. 		this->nums = nums;
    6. 		int ans = 0;
    7. 		for (int i = 0; i < nums.size(); i++)for (int j = i + 1; j < nums.size(); j++) {
    8. 			if (nums[i] <= 0 || nums[j] <= 0)continue;
    9. 			s = nums[i] + nums[j];
    10. 			int id = find(j, nums.size() - 1);
    11. 			ans += id - j - 1;
    12. 		}
    13. 		return ans;
    14. 	}
    15. 	bool isOk(int x) const
    16. 	{
    17. 		return nums[x] >= s;
    18. 	}
    19. 	vector<int> nums;
    20. 	int s;
    21. };

    617. 合并二叉树

    rust

    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] 内。

    1. class Solution {
    2. public:
    3. 	void minmax(vectorint>>& v, int& minid, int& maxid)
    4. 	{
    5. 		minid = 0, maxid = 0;
    6. 		for (int i = 1; i < v.size(); i++) {
    7. 			if (v[minid][0] > v[i][0])minid = i;
    8. 			if (v[maxid].back() < v[i].back())maxid = i;
    9. 		}
    10. 	}
    11. 	int maxDistance(vectorint>>& v) {
    12. 		int minid = 0, maxid = 0;
    13. 		minmax(v, minid, maxid);
    14. 		int a = v[minid][0], b = v[maxid].back();
    15. 		if (minid != maxid)return b - a;
    16. 		v.erase(v.begin() + minid);
    17. 		minmax(v, minid, maxid);
    18. 		int c = v[minid][0], d = v[maxid].back();
    19. 		return max(b - c, d - a);
    20. 	}
    21. };

    625. 最小因式分解

    给定一个正整数 a，找出最小的正整数 b 使得 b 的所有数位相乘恰好等于 a。

    如果不存在这样的结果或者结果不是 32 位有符号整数，返回 0。

    样例 1

    输入：

    48 
    输出：

    68
     

    样例 2

    输入：

    15
    输出：

    35

    思路一，因式分解成2，3，5，7，再根据调整法得到贪心策略（关于2和3怎么组合）

    1. class Solution {
    2. public:
    3. 	int smallestFactorization(int num) {
    4.         if(num==1)return 1;
    5. 		int a2 = 0, a3 = 0, a5 = 0, a7 = 0;
    6. 		while (num % 2 == 0)a2++, num /= 2;
    7. 		while (num % 3 == 0)a3++, num /= 3;
    8. 		while (num % 5 == 0)a5++, num /= 5;
    9. 		while (num % 7 == 0)a7++, num /= 7;
    10. 		if (num > 1)return 0;
    11. 		vector<int>vf;
    12. 		while (a7--)vf.push_back(7);
    13. 		while (a5--)vf.push_back(5);
    14. 		while (a2 >= 3)a2 -= 3, vf.push_back(8);
    15. 		while (a3 >= 2)a3 -= 2, vf.push_back(9);
    16. 		int k = 1;
    17. 		while (a2--)k *= 2;
    18. 		while (a3--)k *= 3;
    19. 		if (k == 12)vf.push_back(2), vf.push_back(6);
    20. 		else if (k > 1)vf.push_back(k);
    21. 		if (vf.size() > 10)return 0;
    22. 		sort(vf.begin(), vf.end());
    23. 		long long n = 0;
    24. 		for (auto& vi : vf)n *= 10, n += vi;
    25. 		if (n > INT_MAX)return 0;
    26. 		return n;
    27. 	}
    28. };

    思路二，直接分成成2-9，大的优先。

    1. class Solution {
    2. public:
    3. 	int smallestFactorization(int num) {
    4. 		if (num == 1)return 1;
    5. 		vector<int>vf;
    6. 		for (int i = 9; i > 1; i--)while (num % i == 0)num/=i, vf.insert(vf.begin(),i);
    7. 		if (num>1 || vf.size() > 10)return 0;
    8. 		long long n = 0;
    9. 		for (auto& vi : vf)n *= 10, n += vi;
    10. 		if (n > INT_MAX)return 0;
    11. 		return n;
    12. 	}
    13. };

    628. 三个数的最大乘积

    rust

    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

    1. class Solution {
    2. public:
    3. 	double findMaxAverage(vector<int>& nums, int k) {
    4. 		int s = 0;
    5. 		for (int i = 0; i < k; i++)s += nums[i];
    6. 		double ans = s;
    7. 		for (int i = k; i < nums.size(); i++) {
    8. 			s += nums[i] - nums[i - k], ans = max(ans, s*1.0);
    9. 		}
    10. 		return ans / k;
    11. 	}
    12. };

    644. 子数组最大平均数 II

    数列DP

    646. 最长数对链

    数列DP

    647. 回文子串

    区间DP

    651. 四个键的键盘

    数列DP

    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
    1. class Solution {
    2. public:
    3.     bool findTarget(TreeNode* root, int k) {
    4.         map<int,int>m;
    5.         if(root)dfs(root,m);
    6.         for(auto mi:m){
    7.             if(mi.first*2!=k && m.find(k-mi.first)!=m.end())return true;
    8.         }
    9.         return false;
    10.     }
    11.     void dfs(TreeNode* root, map<int,int>&m){
    12.         m[root->val]++;
    13.         if(root->left)dfs(root->left,m);
    14.         if(root->right)dfs(root->right,m);
    15.     }
    16. };

    654. 最大二叉树

    rust

    660. 移除 9

    数位DP

    664. 奇怪的打印机


    区间DP

    670. 最大交换

    给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。

    示例 1 :

    输入: 2736
输出: 7236
解释: 交换数字2和数字7。

    示例 2 :

    输入: 9973
输出: 9973
解释: 不需要交换。

    注意:

    1. 给定数字的范围是 [0, 108]
    1. class Solution {
    2. public:
    3.     int maximumSwap(int num) {
    4.         char* str;
    5.         int len = intToStr(num,10,str);
    6.         for(int i=0;i
    7.             int id=i;
    8.             for(int j=i+1;j
    9.                 if(str[j]>=str[id])id=j;
    10.             }
    11.             if(str[id]>str[i]){
    12.                 auto c = str[id];
    13.                 str[id]=str[i],str[i]=c;
    14.                 return strToInt(str,10);
    15.             }
    16.         }
    17.         return num;
    18.     }
    19. };

    672. 灯泡开关 Ⅱ

    找规律

    673. 最长递增子序列的个数

    数列DP

    679. 24 点游戏

    24点

    680. 验证回文字符串 Ⅱ

    剑指 Offer II 019. 最多删除一个字符得到回文

    力扣OJ 剑指 Offer II_csuzhucong的博客-CSDN博客

    683. K 个关闭的灯泡

    线段树

    684. 冗余连接

    rust

    685. 冗余连接 II

    rust

    686. 重复叠加字符串匹配

    KMP

    690. 员工的重要性

    多叉树

    693. 交替位二进制数

    题目：

    给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。

    示例 1:

    输入: 5
    输出: True
    解释:
    5的二进制数是: 101
    示例 2:

    输入: 7
    输出: False
    解释:
    7的二进制数是: 111
    示例 3:

    输入: 11
    输出: False
    解释:
    11的二进制数是: 1011
     示例 4:

    输入: 10
    输出: True
    解释:
    10的二进制数是: 1010

    代码：

    1. class Solution {
    2. public:
    3. 	bool hasAlternatingBits2(int n) {
    4. 		if (n == 0)return true;
    5. 		if (n % 4 == 1)return hasAlternatingBits2(n / 4);
    6. 		return false;
    7. 	}
    8. 	bool hasAlternatingBits(int n) {
    9. 		if (n % 2 == 0)n /= 2;
    10. 		return hasAlternatingBits2(n);
    11. 	}
    12. };

    695. 岛屿的最大面积

    并查集

    697. 数组的度

    rust

    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

    代码：

    1. int s[16];
    2.  
    3. class Solution {
    4. public:
    5.     bool canPartitionKSubsets(vector<int> &nums, int k, int deep)
    6.     {
    7.         if (deep >= nums.size())return true;
    8.         for (int j = 0; j <= deep && j < k; j++) {
    9.             if (s[j] < nums[deep])continue;
    10.             s[j] -= nums[deep];
    11.             if (canPartitionKSubsets(nums, k, deep + 1))return true;
    12.             s[j] += nums[deep];
    13.         }
    14.         return false;
    15.     }
    16.     bool canPartitionKSubsets(vector<int> &nums, int k)
    17.     {
    18.         if (nums.size() < k || k <= 0 || k > 16)return false;
    19.         sort(nums.begin(),nums.end(),greater<int>());
    20.         int anss = 0;
    21.         for (auto it = nums.begin(); it != nums.end(); it++) anss += *it;
    22.         if (anss % k) return false;
    23.         anss /= k;
    24.         for (int i = 0; i < k; i++) s[i] = anss;
    25.         return canPartitionKSubsets(nums, k, 0);
    26.     }
    27. };

    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 <= 104
    • 0 <= nums.length <= 104
    • -104 <= nums[i] <= 104
    • -104 <= val <= 104
    • 最多调用 add 方法 104 次
    • 题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素
    1. class KthLargest {
    2. public:
    3.     KthLargest(int k, vector<int>& nums) {
    4.         for(auto x:nums)s.insert(x);
    5.         while(s.size()>k)s.erase(s.begin());
    6.         n=k;
    7.     }
    8.     
    9.     int add(int val) {
    10.         s.insert(val);
    11.         if(s.size()>n)s.erase(s.begin());
    12.         return *s.begin();
    13.     }
    14.     multiset<int>s;
    15.     int n;
    16. };

    704. 二分查找

    rust

    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
    1. class MyHashSet {
    2. public:
    3.     MyHashSet() {
    4.         for(int i=0;i<=1000000;i++)flag[i]=false;
    5.     }
    6.     
    7.     void add(int key) {
    8.         flag[key]=true;
    9.     }
    10.     
    11.     void remove(int key) {
    12.         flag[key]=false;
    13.     }
    14.     
    15.     bool contains(int key) {
    16.         return flag[key];
    17.     }
    18.     bool flag[1000001]; 
    19. };

    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 方法
    1. class MyHashMap {
    2. public:
    3.     MyHashMap() {
    4.         for(int i=0;i<=1000000;i++)flag[i]=-1;
    5.     }
    6.     
    7.     void put(int key, int value) {
    8.         flag[key]=value;
    9.     }
    10.     
    11.     int get(int key) {
    12.         return flag[key];
    13.     }
    14.     
    15.     void remove(int key) {
    16.         flag[key]=-1;
    17.     }
    18.     int flag[1000001]; 
    19. };
    20.  
    21. /**
    22.  * Your MyHashMap object will be instantiated and called as such:
    23.  * MyHashMap* obj = new MyHashMap();
    24.  * obj->put(key,value);
    25.  * int param_2 = obj->get(key);
    26.  * obj->remove(key);
    27.  */

    708. 循环有序列表的插入

    剑指 Offer II 029. 排序的循环链表

    713. 乘积小于K的子数组

     剑指 Offer II 009. 乘积小于 K 的子数组

    714. 买卖股票的最佳时机含手续费

    状态转换DP

    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]。

    我的代码：（动态规划的备忘录写法）

    1. mapint>exitt;
    2. mapint>m;
    3.  
    4. void init(vector& words)
    5. {
    6.     exitt.clear();
    7.     m.clear();
    8.     for(int i=0;isize();i++){
    9.         exitt[words[i]]=1;
    10.     }
    11. }
    12.  
    13. string preString(string s)
    14. {
    15.     if(s.length()<=1){
    16.         return "";
    17.     }
    18.     return s.substr(0,s.length()-1);
    19. }
    20.  
    21. int dp(string s)
    22. {
    23.     if(m[s])return m[s];
    24.     if(s.length()==1)return 1;
    25.     if(exitt[preString(s)] && dp(preString(s))>0)return m[s]=dp(preString(s))+1;
    26.     return m[s]=-1;
    27. }
    28.  
    29. class Solution {
    30. public:
    31.     string longestWord(vector& words) {
    32.         init(words);
    33.         string ans="";
    34.         for(int i=0;isize();i++){
    35.             int ret=dp(words[i]);
    36.             if(ret==-1)continue;
    37.             if(ans.length()length() || ans.length()==words[i].length() && ans>words[i])
    38.                 ans=words[i];
    39.         }
    40.         cout<"e"];
    41.         return ans;
    42.     }
    43. };

    也可以用字典树做。

    724. 寻找数组的中心下标

     剑指 Offer II 012. 左右两边子数组的和相等

    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] 范围内的一个整数。

    代码：

    1. class Solution {
    2. public:
    3. 	int monotoneIncreasingDigits(int N) {
    4. 		int key = 1111111111, ans = 0, num = 9;
    5. 		while (key)
    6. 		{
    7. 			while (N >= key && num > 0)
    8. 			{
    9. 				N -= key, ans += key, num--;
    10. 			}
    11. 			key /= 10;
    12. 		}
    13. 		return ans;
    14. 	}
    15. };

    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]范围内。

    1. class Solution {
    2. public:
    3.     int s[10001];
    4.     int ans[10001];
    5.     int dp(int k)
    6.     {
    7.         if(k<0)return 0;
    8.         if(ans[k])return ans[k];
    9.         return ans[k]=max(s[k]+dp(k-2),dp(k-1));
    10.     }
    11.     int deleteAndEarn(vector<int>& nums) {
    12.         if(nums.size()==0)return 0;
    13.         memset(ans,0,sizeof(int)*10001);
    14.         memset(s,0,sizeof(int)*10001);
    15.         for(int i=0;isize();i++)s[nums[i]]+=nums[i];
    16.         return dp(10000);
    17.     }
    18. };

    741. 摘樱桃

    高维DP

    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了。

    1. class Solution {
    2. public:
    3. 	map< TreeNode*, int>m;
    4. 	map< TreeNode*, int>m2;
    5. 	bool flag;
    6. 	int dfs(TreeNode* root, int& num)
    7. 	{
    8. 		if (!root->left && !root->right) {
    9. 			m[root] = 1, num = m2[root] = root->val;
    10. 			return 1;
    11. 		}
    12. 		int deep = INT_MAX;
    13. 		if (root->left)deep = dfs(root->left, num) + 1, m2[root] = num;
    14. 		if (root->right) {
    15. 			int ret = dfs(root->right, num);
    16. 			if (deep > ret + 1) {
    17. 				deep = min(deep, ret + 1), m2[root] = num;
    18. 			}
    19. 			else num = m2[root];
    20. 		}
    21. 		m[root] = deep;
    22. 		return deep;
    23. 	}
    24. 	int dfs2(TreeNode* root, int k, int n, int& num) {
    25. 		if (root->val == k) {
    26. 			int ans = m[root];
    27. 			num = m2[root];
    28. 			return min(ans, n + 1);
    29. 		}
    30. 		if (root->left) {
    31. 			int ans = dfs2(root->left, k, min(n + 1, m[root]), num);
    32. 			if (flag && ans == min(n + 1, m[root]) + 1)num = m2[root];
    33. 			else if (ans != -1) {
    34. 				flag = false;
    35. 				return ans + 1;
    36. 			}
    37. 			if (ans != -1)return ans - 1;
    38. 		}
    39. 		if (root->right) {
    40. 			int ans = dfs2(root->right, k, min(n + 1, m[root]), num);
    41. 			if (flag && ans == min(n + 1, m[root]) + 1)num = m2[root];
    42. 			else if (ans != -1) {
    43. 				flag = false;
    44. 				return ans + 1;
    45. 			}
    46. 			if (ans != -1)return ans - 1;
    47. 		}
    48. 		return -1;
    49. 	}
    50. 	int findClosestLeaf(TreeNode* root, int k) {
    51. 		int num;
    52. 		flag = true;
    53. 		dfs(root, num);
    54. 		dfs2(root, k, m[root] - 1, num);
    55. 		return num;
    56. 	}
    57. };

    743. 网络延迟时间

    BFS

    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.length
    • n == grid[i].length
    • 1 <= m, n <= 200
    • grid[i][j] 不是 0 就是 1
    • 网格中 1 的个数在 [1, 6000] 范围内
    1. class Solution {
    2. public:
    3.     int countCornerRectangles(vectorint>>& grid) {
    4.         int ans=0;
    5.         for(int i=0;isize();i++){
    6.             for(int j=i+1;jsize();j++){
    7.                 ans+=countCornerRectangles(grid[i],grid[j]);
    8.             }
    9.         }
    10.         return ans;
    11.     }
    12.     int countCornerRectangles(vector<int>& v1,vector<int>& v2) {
    13.         int s=0;
    14.         for(int i=0;isize();i++)if(v1[i]==1 && v2[i]==1)s++;
    15.         return s*(s-1)/2;
    16.     }
    17. };

    752. 打开转盘锁

    双向BFS

    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 <= 109
    • target != 0

    思路：第k次移动之后可能到达的位置是非常有规律的。

    1. class Solution {
    2. public:
    3.     int reachNumber(long long n) {
    4.         int x=ceil((sqrt(abs(n)*8+1)-1)/2);
    5.         return (n+1+(x-1)%4/2)%2?x+x%2+1:x;
    6.     }
    7. };

    756. 金字塔转换矩阵

    DFS

    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]，以此类推。

    注：

    1. A, B 有相同的长度，范围为 [1, 100]。
    2. A[i], B[i] 都是范围在 [0, 10^5] 的整数。
    1. ​
    2. template<typename T=int>
    3. class Solution {
    4. public:
    5.     vector<int> anagramMappings(vector& nums1, vector& nums2) {
    6.         mapint>>m1=statistics(nums1);
    7.         mapint>>m2=statistics(nums2);
    8.         vector<int>ans(nums1.size());
    9.         for(auto mi:m1){
    10.             auto v1=mi.second;
    11.             auto v2=m2[mi.first];
    12.             for(int i=0;isize();i++)ans[v1[i]]=v2[i];
    13.         }
    14.         return ans;
    15.     }
    16.     mapint>> statistics(vector&nums){
    17.         mapint>>m;
    18.         for(int i=0;isize();i++){
    19.             m[nums[i]].push_back(i);
    20.         }
    21.         return m;
    22.     }
    23. };
    24.  
    25. ​

    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。

    代码：

    1. class Solution {
    2. public:
    3. 	int hammingWeight(int n) {
    4. 		int ans = 0;
    5. 		while (n)
    6. 		{
    7. 			n ^= (n&(-n));
    8. 			ans++;
    9. 		}
    10. 		return ans;
    11. 	}
    12. 	int countPrimeSetBits(int L, int R) {
    13. 		set<int>se = { 2, 3, 5, 7 ,11,13,17,19};
    14. 		int ans = 0;
    15. 		for (int i = L; i <= R; i++)
    16. 		{
    17. 			if (se.find(hammingWeight(i)) != se.end())ans++;
    18. 		}
    19. 		return ans;
    20. 	}
    21. };

    764. 最大加号标志

    搜索else

    767. 重构字符串

     贪心（3）其他排序问题

    769. 最多能完成排序的块

    水题

    771. 宝石与石头

     给你一个字符串 jewels 代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

    字母区分大小写，因此 "a" 和 "A" 是不同类型的石头。

    示例 1：

    输入：jewels = "aA", stones = "aAAbbbb"
输出：3

    示例 2：

    输入：jewels = "z", stones = "ZZ"
输出：0

    提示：

    • 1 <= jewels.length, stones.length <= 50
    • jewels 和 stones 仅由英文字母组成
    • jewels 中的所有字符都是 唯一的
    1. class Solution {
    2. public:
    3.     int numJewelsInStones(string jewels, string stones) {
    4.         map<char,char>m;
    5.         for(auto c:jewels)m[c]++;
    6.         int ans=0;
    7.         for(auto c:stones)if(m[c])ans++;
    8.         return ans;
    9.     }
    10. };

    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

    1. class Solution {
    2. public:
    3. 	bool ok(vector<int>& stations, int k, double d)
    4. 	{
    5. 		int s = 0;
    6. 		for (int i = 1; i < stations.size(); i++)s += (stations[i] - stations[i - 1]) / d;
    7. 		return s <= k;
    8. 	}
    9. 	double minmaxGasDist(vector<int>& stations, int k) {
    10. 		double low = 1.0 / k, high = stations.back() - stations[0];
    11. 		while (high - low > 0.00001) {
    12. 			double mid = (low + high) / 2;
    13. 			if (ok(stations, k, mid))high = mid;
    14. 			else low = mid;
    15. 		}
    16. 		return high;
    17. 	}
    18. };

    776. 拆分二叉搜索树

    二叉搜索树（BST）

    778. 水位上升的泳池中游泳

    BFS

    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
    1. class Solution {
    2. public:
    3.     int numTilings(int n) {
    4.         if(n<2)return 1;
    5.         n-=2;
    6.         int a=1,b=1,c=2,d=0;
    7.         while(n--)d=(c*2%1000000007+a)%1000000007,a=b,b=c,c=d;
    8.         return c;
    9.     }
    10. };

    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 <= 26
    • 1 <= s.length <= 200
    • order 和 s 由小写英文字母组成
    • order 中的所有字符都 不同
    1. class Solution {
    2. public:
    3.     string customSortString(string order, string s) {
    4.         map<char,int>m1,m2;
    5.         for(auto c:order)m1[c]=1;
    6.         string ans;
    7.         for(auto c:s){
    8.             if(m1[c])m2[c]++;
    9.             else ans+=c;
    10.         }
    11.         for(auto c:order)while(m2[c]--)ans+=c;
    12.         return ans;
    13.     }
    14. };

    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 <= 105
    • 0 <= nums[i] <= 109
    • 0 <= left <= right <= 109
    1. class Solution {
    2. public:
    3.     long long numSubarrayBoundedMax(vector<int>& nums, int key) {
    4.         int low=0;
    5.         long long ans=0;
    6.         for(int i=0;i<=nums.size();i++){
    7.             if(isize() && nums[i]<=key)continue;
    8.             ans+=(long long)(i-low)*(i-low+1)/2;
    9.             low=i+1;
    10.         }
    11.         return ans;
    12.     }
    13.     int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
    14.         return numSubarrayBoundedMax(nums,right)-numSubarrayBoundedMax(nums,left-1);
    15.     }
    16. };

    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 进制数
    1. class Solution {
    2. public:
    3. 	int toNum(char c)
    4. 	{
    5. 		if (c >= '0' && c <= '9')return c - '0';
    6. 		return c - 'a' + 10;
    7. 	}
    8. 	char toChar(int n)
    9. 	{
    10. 		char ans = '0';
    11. 		if (n < 10)return ans + n;
    12. 		ans = 'a';
    13. 		return ans + n - 10;
    14. 	}
    15. 	string similarRGB(string color) {
    16. 		for (int i = 1; i < color.size(); i += 2) {
    17. 			int x = toNum(color[i]);
    18. 			int y = toNum(color[i+1]);
    19. 			int s = x * 16 + y;
    20. 			int k = 0, d = INT_MAX;
    21. 			for (int i = 0; i < 16; i++) {
    22. 				s -= i * 17;
    23. 				if (s * s < d)d = s * s, k = i;
    24. 				s+= i * 17;
    25. 			}
    26. 			color[i] = toChar(k);
    27. 			color[i+1] = toChar(k);
    28. 		}
    29. 		return color;
    30. 	}
    31. };

  • 相关阅读:
    1688阿里巴巴API 1688商品采集API 1688获取商品列表API 订单API
    GB28181 sip和RTSP（Real-Time Streaming Protocol）实时流控制协议
    俄罗斯方块游戏开发教程7:消除判断和处理
    小程序简单版音乐播放器
    大模型全情投入，低代码也越来越清晰
    黑马JVM总结（三十七）
    【数据分享】2023年我国上市公司数据（Excel格式/Shp格式）
    C Primer Plus(6) 中文版 第6章 C控制语句：循环 6.3 用关系运算符和表达式比较大小
    免费小程序商城搭建之b2b2c o2o 多商家入驻商城 直播带货商城 电子商务b2b2c o2o 多商家入驻商城 直播带货商城 电子商务
    springboot毕设项目超市收银与会员管理系统6l826（java+VUE+Mybatis+Maven+Mysql）
  • 原文地址：https://blog.csdn.net/nameofcsdn/article/details/127432490