【Day31】461. 汉明距离
461. 汉明距离
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意：
- 0 ≤ x, y < 231.
示例:
输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。题解：
可以考虑为求异或结果值当中1的个数，进一步转换为求二进制中1的个数。
class Solution {
public:
int lowbit(int x) {
return x & (-x);
}
int hammingDistance(int x, int y) {
int ret = x ^ y;
int ans = 0;
while (ret) {
ret -= lowbit(ret);
ans++;
}
return ans;
}
};【Day32】477.汉明距离总和
477. 汉明距离总和
两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
计算一个数组中，任意两个数之间汉明距离的总和。
示例:
输入: 4, 14, 2
输出: 6
解释: 在二进制表示中，4表示为0100，14表示为1110，2表示为0010。（这样表示是为了体现后四位之间关系）
所以答案为：
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.注意:
- 数组中元素的范围为从 0到 10^9。
- 数组的长度不超过 10^4。
题解：
class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int ans = 0;
for (int i = 0; i < 31; i++) {
int cnt[] = {0, 0};
for (auto& num : nums) {
cnt[num & 1]++;
num >>= 1;
}
ans += cnt[0] * cnt[1];
}
return ans;
}
};【Day33】1074.元素和为目标值的子矩阵数量
1074. 元素和为目标值的子矩阵数量
给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。
子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。
如果 (x1, y1, x2, y2) 和 (x1’, y1’, x2’, y2’) 两个子矩阵中部分坐标不同（如：x1 != x1’），那么这两个子矩阵也不同。
示例 1：
输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
输出：4
解释：四个只含 0 的 1x1 子矩阵。示例 2：
输入：matrix = [[1,-1],[-1,1]], target = 0
输出：5
解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。示例 3：
输入：matrix = [[904]], target = 0
输出：0提示：
- 1 <= matrix.length <= 100
- 1 <= matrix[0].length <= 100
- -1000 <= matrix[i] <= 1000
- -10^8 <= target <= 10^8
题解：
二维前缀和的题目，使用哈希表来优化
#define HT_LENGTH 256
struct HashTable {
int keys[HT_LENGTH];
int vals[HT_LENGTH];
HashTable() {
this->clear();
}
void clear() {
keys[0] = 0; vals[0] = 1;
for (int i = 1;i < HT_LENGTH;i++) keys[i] = -1;
}
bool find(int key, int& ret) {
uint32_t ikey = (uint32_t)key % HT_LENGTH;
for (int i = 0;i < HT_LENGTH;i++) {
if (keys[ikey] == -1) return false;
if (keys[ikey] == key) {
ret = vals[ikey];
return true;
}
ikey ++;
ikey = ikey == HT_LENGTH ? 0 : ikey;
}
return false;
}
void inc(int key) {
uint32_t ikey = (uint32_t)key % HT_LENGTH;
for (int i = 0;i < HT_LENGTH;i++) {
if (keys[ikey] == -1) {
keys[ikey] = key;
vals[ikey] = 1;
return;
}
if (keys[ikey] == key) {
vals[ikey]++;
return;
}
ikey ++;
ikey = ikey == HT_LENGTH ? 0 : ikey;
}
}
};
class Solution {
private:
HashTable ht;
public:
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
int rprefix[100][101];
int m = matrix.size(), n = matrix[0].size();
int ret = 0;
for (int i = 0;i < m;i++) {
rprefix[i][0] = 0;
for (int j = 1;j <= n;j ++) {
rprefix[i][j] = rprefix[i][j - 1] + matrix[i][j - 1];
}
}
for (int i = 1;i <= n;i++) {
for (int j = i;j <= n;j++) {
ht.clear();
int cprefix = 0, val;
for (int row = 0;row < m;row++) {
cprefix += rprefix[row][j] - rprefix[row][i - 1];
if (ht.find(cprefix - target, val)) ret += val;
ht.inc(cprefix);
}
}
}
return ret;
}
};【Day34】231. 2 的幂
231. 2 的幂
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
示例 1：
输入：n = 1
输出：true
解释：20 = 1示例 2：
输入：n = 16
输出：true
解释：24 = 16示例 3：
输入：n = 3
输出：false示例 4：
输入：n = 4
输出：true示例 5：
输入：n = 5
输出：false提示：
- -231 <= n <= 231 - 1
题解：
位运算
若 n = 2^x 且 x为自然数（即 n 为 2 的幂），则一定满足以下条件：
首先，恒有 n & (n - 1) == 0，因为：
- n 二进制最高位为 11，其余所有位为 00；
- n−1 二进制最高位为 00，其余所有位为 11；
其次，我们只需要限定n > 0 即可。
class Solution {
public:
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
};【Day35】342. 4的幂
342. 4的幂
给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x
示例 1：
输入：n = 16
输出：true示例 2：
输入：n = 5
输出：false示例 3：
输入：n = 1
输出：true提示：
- -231 <= n <= 231 - 1
题解：
一个数是2的幂，那么二进制从右边数奇数位是1的一定是4的幂。判断是2的幂，我们只需要判断二进制中1的个数，用昨天的解即可。
0x55555555的 二进制是 01010101 01010101 01010101 01010101class Solution {
public:
bool isPowerOfFour(int n) {
return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555) == n;
}
};【Day36】LeetCode 1744
1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？
给你一个下标从 0 开始的正整数数组 candiesCount ，其中 candiesCount[i] 表示你拥有的第 i 类糖果的数目。同时给你一个二维数组 queries ，其中 queries[i] = [favoriteTypei, favoriteDayi, dailyCapi] 。
你按照如下规则进行一场游戏：
- 你从第 0 天开始吃糖果。
- 你在吃完 所有 第 i - 1 类糖果之前，不能 吃任何一颗第 i 类糖果。
- 在吃完所有糖果之前，你必须每天 至少 吃 一颗 糖果。
请你构建一个布尔型数组 answer ，满足 answer.length == queries.length 。answer[i] 为 true 的条件是：在每天吃 不超过 dailyCapi 颗糖果的前提下，你可以在第 favoriteDayi 天吃到第 favoriteTypei 类糖果；否则 answer[i] 为 false 。注意，只要满足上面 3 条规则中的第二条规则，你就可以在同一天吃不同类型的糖果。
请你返回得到的数组 answer 。
示例 1：
输入：candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
输出：[true,false,true]
提示：
1- 在第 0 天吃 2 颗糖果(类型 0），第 1 天吃 2 颗糖果（类型 0），第 2 天你可以吃到类型 0 的糖果。
2- 每天你最多吃 4 颗糖果。即使第 0 天吃 4 颗糖果（类型 0），第 1 天吃 4 颗糖果（类型 0 和类型 1），你也没办法在第 2 天吃到类型 4 的糖果。换言之，你没法在每天吃 4 颗糖果的限制下在第 2 天吃到第 4 类糖果。
3- 如果你每天吃 1 颗糖果，你可以在第 13 天吃到类型 2 的糖果。示例 2：
输入：candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
输出：[false,true,true,false,false]提示：
- 1 <= candiesCount.length <= 105
- 1 <= candiesCount[i] <= 105
- 1 <= queries.length <= 105
- queries[i].length == 3
- 0 <= favoriteTypei < candiesCount.length
- 0 <= favoriteDayi <= 109
- 1 <= dailyCapi <= 109
题解：
使用前缀和解题：
class Solution {
public:
vector<long long> sum;
bool check(vector<int>& candiesCount, vector<int>& q) {
int favoriteType = q[0], favoriteDay = q[1], dailyCap = q[2];
// 第favoriteType类型的前缀和
int l = sum[favoriteType + 1];
// 每天吃一颗糖
if (favoriteDay + 1 > sum[favoriteType + 1]) return false;
// 吃最多糖
if (sum[favoriteType] >= 1ll*(favoriteDay + 1) * dailyCap) return false;
return true;
}
vector<bool> canEat(vector<int>& candiesCount, vector<vector<int>>& queries) {
int n = candiesCount.size();
sum = vector<long long>(n + 1, 0);
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + candiesCount[i - 1];
}
vector<bool> ans;
for (auto q : queries)
ans.push_back(check(candiesCount, q));
return ans;
}
};【Day37】523.连续的子数组和
523. 连续的子数组和
给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：
- 子数组大小 至少为 2 ，且
- 子数组元素总和为 k 的倍数。
如果存在，返回 true ；否则，返回 false 。
如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。
示例 1：
输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。示例 2：
输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。示例 3：
输入：nums = [23,2,6,4,7], k = 13
输出：false提示：
- 1 <= nums.length <= 105
- 0 <= nums[i] <= 109
- 0 <= sum(nums[i]) <= 231 - 1
- 1 <= k <= 231 - 1
题解：
经典的前缀和
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
int sum = 0;
unordered_set<int> st;
for(int i = 0; i < nums.size(); i++) {
sum += nums[i];
if(st.count(sum % k)) return true;
st.insert((sum - nums[i]) % k);
}
return false;
}
};【Day38】525.连续数组
525. 连续数组
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
示例 1:
输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。示例 2:
输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。提示：
- 1 <= nums.length <= 105
- nums[i] 不是 0 就是 1
题解：
前缀和＋哈希
class Solution {
public:
int findMaxLength(vector<int>& nums) {
for (auto& num : nums) {
num = num == 0 ? -1 : num;
}
map<int, int> m;
int sum = 0, ans = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
if (sum == 0) {
ans = i + 1;
}
if (m.count(sum)) {
ans = max(i - m[sum], ans);
} else {
m[sum] = i;
}
}
return ans;
}
};【Day39】160.相交链表
160. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意：函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。示例 2：
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。提示：
- listA 中节点数目为 m
- listB 中节点数目为 n
- 0 <= m, n <= 3 * 104
- 1 <= Node.val <= 105
- 0 <= skipA <= m
- 0 <= skipB <= n
- 如果 listA 和 listB 没有交点，intersectVal 为 0
- 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？
题解：
pA走过的路径为A链+B链
pB走过的路径为B链+A链
pA和pB走过的长度都相同，都是A链和B链的长度之和，相当于将两条链从尾端对齐，如果相交，则会提前在相交点相遇，如果没有相交点，则会在最后相遇。
pA:1->2->3->4->5->6->null->9->5->6->null
pB:9->5->6->null->1->2->3->4->5->6->null/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p = headA, *q = headB;
while (p != q) {
p = p ? p->next : headB;
q = q ? q->next : headA;
}
return p;
}
};【Day40】203.移除链表元素
203. 移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]示例 2：
输入：head = [], val = 1
输出：[]示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]提示：
- 列表中的节点在范围 [0, 104] 内
- 1 <= Node.val <= 50
- 0 <= k <= 50
题解：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode *removeElements(ListNode *head, int val)
{
if (!head)
return head;
head->next = removeElements(head->next, val);
return head->val == val ? head->next : head;
}
};【Day41】474.一和零
474. 一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。提示：
- 1 <= strs.length <= 600
- 1 <= strs[i].length <= 100
- strs[i] 仅由 ‘0’ 和 ‘1’ 组成
- 1 <= m, n <= 100
题解：
动态规划
const int N = 101;
class Solution {
public:
int dp[N][N];
int findMaxForm(vector<string>& strs, int m, int n)
{
for (auto &str:strs)
{
int one = 0, zero = 0;
for (auto &c:str)
{
if(c=='1')
++one;
else
++zero;
}
// zero = str.size() - one;
for (int j=m; j>=zero; --j)
{
for (int k=n; k>=one; --k)
{
dp[j][k] = max(dp[j][k], dp[j-zero][k-one] + 1);
}
}
}
return dp[m][n];
}
};【Day42】494. 目标和
494. 目标和
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3示例 2：
输入：nums = [1], target = 1
输出：1提示：
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 100
题解：
还是动态规划
class Solution {
int n;
int ans = 0;
int t;
public:
int findTargetSumWays(vector<int>& nums, int target) {
n = nums.size();
t = target;
dfs(0,nums, 0);
return ans;
}
void dfs(int u, vector <int> & nums, int s){
if(u == n){
if(s == t) ++ans;
return;
}
dfs(u + 1, nums, s + nums[u]);
dfs(u + 1, nums, s - nums[u]);
}
};【Day43】1049. 最后一块石头的重量 II
1049. 最后一块石头的重量 II
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果 x == y，那么两块石头都会被完全粉碎；
- 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。示例 2：
输入：stones = [31,26,33,21,40]
输出：5示例 3：
输入：stones = [1,2]
输出：1提示：
1 <= stones.length <= 30
1 <= stones[i] <= 100
题解：
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
auto sum = accumulate(stones.begin(), stones.end(), 0);
vector<int> dp(sum / 2 + 1);
for (const auto& stone : stones) {
for (auto j = sum / 2; j >= stone; j--) {
dp[j] = max(dp[j], dp[j - stone] + stone);
}
}
return sum - dp[sum / 2] * 2;
}
};
【Day44】879. 盈利计划
879. 盈利计划
集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。
示例 1：
输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
总的来说，有两种计划。示例 2：
输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
输出：7
解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。提示：
- 1 <= n <= 100
- 0 <= minProfit <= 100
- 1 <= group.length <= 100
- 1 <= group[i] <= 100
- profit.length == group.length
- 0 <= profit[i] <= 100
题解：
这题不会，贴一个题解吧
class Solution {
public:
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
int mod = 1e9 + 7;
int size = group.size();
int dp[n + 1][minProfit + 1];
memset(dp, 0, sizeof(dp));
for (int i = 0; i <= n; ++i) {
dp[i][0] = 1;
}
for (int i = 1; i <= size; ++i) {
int cur_group = group[i - 1], cur_profit = profit[i - 1];
for (int j = n; j >= cur_group; --j) {
for (int k = minProfit; k >= 0; --k) {
dp[j][k] += dp[j - cur_group][max(k - cur_profit, 0)];
dp[j][k] %= mod;
}
}
}
return dp[n][minProfit];
}
};【Day45】518. 零钱兑换 II
518. 零钱兑换 II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。示例 3:
输入: amount = 10, coins = [10]
输出: 1注意:
- 0 <= amount (总金额) <= 5000
- 1 <= coin (硬币面额) <= 5000
- 硬币种类不超过 500 种
- 结果符合 32 位符号整数
题解：
class Solution {
public:
int change(int amount, vector<int>& coins) {
int n = coins.size();
vector<int> dp(amount+1);
dp[0] = 1;
for(int i = 1; i<=n; i++)
{
int val = coins[i-1];
for(int j = val; j <= amount;++j)
{
dp[j] += dp[j-val];
}
}
return dp[amount];
}
};【Day46】279. 完全平方数
279. 完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9提示：
- 1 <= n <= 104
题解：
//假设最小公式值m = ƒ(n)
//那么n的值满足下列公式 ∑(A[i] * A[i]) = n
//令 k 为满足最小值 m 的时候，最大的平方数 。 令 d + k * k; = n ; d >= 0;
// 注意：一定要是满足m最小的时候的k值,一味的取最大平方数,就是贪心算法了
//得出 f(d) + f(k*k) = f(n);
//显然 f(k*k) = 1; 则 f(d) + 1 = f(n); 因为 d = n - k*k;
//则可以推出ƒ(n - k * k) + 1 = ƒ(n) ; 且 k * k <= n;
class Solution {
public:
int numSquares(int n) {
if (n <= 0) return 0;
std::vector<int> nums(n+1);
for(int i = 1; i <= n;i++)
{
int min = i;
for(int j = 1;i - j*j >= 0;j++)
{
int tmp = nums[i-j*j] + 1;
min = min > tmp ? tmp:min;
}
nums[i] = min;
}
return nums[n];
}
};【Day47】1449. 数位成本和为目标值的最大数字
1449. 数位成本和为目标值的最大数字
给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数：
- 给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
- 总成本必须恰好等于 target 。
- 添加的数位中没有数字 0 。
由于答案可能会很大，请你以字符串形式返回。
如果按照上述要求无法得到任何整数，请你返回 “0” 。
示例 1：
输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出："7772"
解释：添加数位 '7' 的成本为 2 ，添加数位 '2' 的成本为 3 。所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "977" 也是满足要求的数字，但 "7772" 是较大的数字。
数字 成本
1 -> 4
2 -> 3
3 -> 2
4 -> 5
5 -> 6
6 -> 7
7 -> 2
8 -> 5
9 -> 5示例 2：
输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出："85"
解释：添加数位 '8' 的成本是 7 ，添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。示例 3：
输入：cost = [2,4,6,2,4,6,4,4,4], target = 5
输出："0"
解释：总成本是 target 的条件下，无法生成任何整数。示例 4：
输入：cost = [6,10,15,40,40,40,40,40,40], target = 47
输出："32211"提示：
- cost.length == 9
- 1 <= cost[i] <= 5000
- 1 <= target <= 5000
题解：
class Solution {
public:
string largestNumber(vector<int>& cost, int target) {
int len=cost.size();
vector<string> dp(target+1,"#");
dp[0]="";
//因为i遍历的顺序是从小到大，就保证了整数的高位一定大于等于整数的低位，也就保证了整数最大
for(int i=1;i<len+1;++i)
for(int j=1;j<target+1;++j){
if(j>=cost[i-1]&&dp[j-cost[i-1]]!="#"){
dp[j]=CompareString(dp[j],to_string(i)+dp[j-cost[i-1]]);
}
}
return dp[target]=="#"?"0":dp[target];
}
private:
string CompareString(const string& s1,const string& s2){
int m=s1.size(),n=s2.size();
if(m==n)return max(s1,s2);
return m>n?s1:s2;
}
};【Day48】278. 第一个错误的版本
278. 第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。 题解：
二分
bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int lo = 1;
int hi = n;
while(lo < hi) {
int mid = lo + (hi - lo) / 2;
if (isBadVersion(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
return hi;
}
};【Day49】374. 猜数字大小
374. 猜数字大小
猜数字游戏的规则如下：
- 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
- 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
- -1：我选出的数字比你猜的数字小 pick < num
- 1：我选出的数字比你猜的数字大 pick > num
- 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
返回我选出的数字。
示例 1：
输入：n = 10, pick = 6
输出：6示例 2：
输入：n = 1, pick = 1
输出：1示例 3：
输入：n = 2, pick = 1
输出：1示例 4：
输入：n = 2, pick = 2
输出：2提示：
- 1 <= n <= 231 - 1
- 1 <= pick <= n
题解：
/**
* Forward declaration of guess API.
* @param num your guess
* @return -1 if num is lower than the guess number
* 1 if num is higher than the guess number
* otherwise return 0
* int guess(int num);
*/
class Solution {
public:
int guessNumber(int n) {
int l = 0;
int r = n;
while (l <= r)
{
int m = (l-r)/2 + r;
int res = guess(m);
if (res == 0)
{
return m;
}
else if (res < 0)
{
r = m-1;
}
else
{
l = m + 1;
}
}
return -1;
}
};【Day50】852. 山脉数组的峰顶索引
852. 山脉数组的峰顶索引
符合下列属性的数组 arr 称为 山脉数组 ：
arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
- arr[0] < arr[1] < … arr[i-1] < arr[i]
- arr[i] > arr[i+1] > … > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。
示例 1：
输入：arr = [0,1,0]
输出：1示例 2：
输入：arr = [0,2,1,0]
输出：1示例 3：
输入：arr = [0,10,5,2]
输出：1示例 4：
输入：arr = [3,4,5,1]
输出：2示例 5：
输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2提示：
- 3 <= arr.length <= 104
- 0 <= arr[i] <= 106
- 题目数据保证 arr 是一个山脉数组
题解：
二分法
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
//根据 arr[mid-1]和arr[mid]对比
//所以搜索范围是 [1,arr.length -1]
int left = 1;
int right = arr.size() - 1;
while(left < right){
//如果check 函数调整的是left，则+1. 否则有可能陷入死循环
int mid = left + right + 1 >> 1;
if(arr[mid-1] < arr[mid])
left = mid;
else
right = mid -1;
}
return right;
}
};【Day51】877. 石子游戏
877. 石子游戏
亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。
游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。
亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。
假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false 。
示例：
输入：[5,3,4,5]
输出：true
解释：
亚历克斯先开始，只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果李拿走前 3 颗，那么剩下的是 [4,5]，亚历克斯拿走后 5 颗赢得 10 分。
如果李拿走后 5 颗，那么剩下的是 [3,4]，亚历克斯拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对亚历克斯来说是一个胜利的举动，所以我们返回 true 。提示：
- 2 <= piles.length <= 500
- piles.length 是偶数。
- 1 <= piles[i] <= 500
- sum(piles) 是奇数。
题解：
博弈论
class Solution {
public:
bool stoneGame(vector<int>& piles) {
return true;
}
};【Day52】65. 有效数字
有效数字（按顺序）可以分成以下几个部分：
- 一个 小数 或者 整数
- （可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个 整数
小数（按顺序）可以分成以下几个部分：
- （可选）一个符号字符（’+’ 或 ‘-‘）
- 下述格式之一：
- 至少一位数字，后面跟着一个点 ‘.’
- 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
- 一个点 ‘.’ ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：
- （可选）一个符号字符（’+’ 或 ‘-‘）
- 至少一位数字
部分有效数字列举如下：
- [“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”]
部分无效数字列举如下：
- [“abc”, “1a”, “1e”, “e3”, “99e2.5”, “–6”, “-+3”, “95a54e53”]
给你一个字符串 s ，如果 s 是一个 有效数字 ，请返回 true 。
示例 1：
输入：s = "0"
输出：true示例 2：
输入：s = "e"
输出：false示例 3：
输入：s = "."
输出：false示例 4：
输入：s = ".1"
输出：true提示：
- 1 <= s.length <= 20
- s 仅含英文字母（大写和小写），数字（0-9），加号 ‘+’ ，减号 ‘-‘ ，或者点 ‘.’ 。
题解：
class Solution {
public:
bool isNumber(string s) {
int l = 0, r = s.size() - 1;
//去掉前后空格
while (l <= r && s[l] == ' ') l ++ ;
while (l <= r && s[r] == ' ') r -- ;
if (l > r) return false;
s = s.substr(l, r - l + 1);
//去掉正负号
if (s[0] == '+' || s[0] == '-') s = s.substr(1);
//如果只有正负号，false
if (s.empty()) return false;
//如果只有一个点，或者.e || .E 返回false
if (s[0] == '.' && (s.size() == 1 || s[1] == 'e' || s[1] == 'E'))
return false;
//记录点和e的次数
int dot = 0, e = 0;
for (int i = 0; i < s.size(); i ++ ) {
if (s[i] == '.') {
//如果出现多个点或者e ，fasle
if (dot > 0 || e > 0) return false;
dot ++ ;
} else if (s[i] == 'e' || s[i] == 'E') {
//如果e的前面没东西或者后面没东西，或者多个e ，false
if (!i || i + 1 == s.size() || e > 0) return false;
//如果e的后面是正负号
if (s[i + 1] == '+' || s[i + 1] == '-') {
//但是后面没东西了，返回false
if (i + 2 == s.size()) return false;
i ++ ;
}
e ++ ;
//不合法
} else if (s[i] < '0' || s[i] > '9') return false;
}
return true;
}
};【Day53】483. 最小好进制
483. 最小好进制
对于给定的整数 n, 如果n的k（k>=2）进制数的所有数位全为1，则称 k（k>=2）是 n 的一个好进制。
以字符串的形式给出 n, 以字符串的形式返回 n 的最小好进制。
示例 1：
输入："13"
输出："3"
解释：13 的 3 进制是 111。示例 2：
输入："4681"
输出："8"
解释：4681 的 8 进制是 11111。示例 3：
输入："1000000000000000000"
输出："999999999999999999"
解释：1000000000000000000 的 999999999999999999 进制是 11。提示：
- n的取值范围是 [3, 10^18]。
- 输入总是有效且没有前导 0。
题解：
class Solution {
public:
using LL = long long;
string smallestGoodBase(string n) {
LL x = stoll(n);
for(int m = 2; m <= 60; m++){
LL k = (LL)pow(x, 1. / m);
if(k > 1){
LL cur = 1;
for(LL i = 1, base = 1; i <= m; i++){
base *= k;
cur += base;
}
if(cur == x) return to_string(k);
}
}
return to_string(x - 1);
}
};【Day54】1239. 串联字符串的最大长度
1239. 串联字符串的最大长度
给定一个字符串数组 arr，字符串 s 是将 arr 某一子序列字符串连接所得的字符串，如果 s 中的每一个字符都只出现过一次，那么它就是一个可行解。
请返回所有可行解 s 中最长长度。
示例 1：
输入：arr = ["un","iq","ue"]
输出：4
解释：所有可能的串联组合是 "","un","iq","ue","uniq" 和 "ique"，最大长度为 4。示例 2：
输入：arr = ["cha","r","act","ers"]
输出：6
解释：可能的解答有 "chaers" 和 "acters"。示例 3：
输入：arr = ["abcdefghijklmnopqrstuvwxyz"]
输出：26提示：
- 1 <= arr.length <= 16
- 1 <= arr[i].length <= 26
- arr[i] 中只含有小写英文字母
题解：
class Solution {
public:
int maxLength(vector<string> &arr) {
int ans = 0;
vector<int> masks = {0};
for (string &s : arr) {
int mask = 0;
for (char ch : s) {
ch -= 'a';
if ((mask >> ch) & 1) { // 若 mask 已有 ch，则说明 s 含有重复字母，无法构成可行解
mask = 0;
break;
}
mask |= 1 << ch; // 将 ch 加入 mask 中
}
if (mask == 0) {
continue;
}
int n = masks.size();
for (int i = 0; i < n; ++i) {
int m = masks[i];
if ((m & mask) == 0) { // m 和 mask 无公共元素
masks.push_back(m | mask);
ans = max(ans, __builtin_popcount(m | mask));
}
}
}
return ans;
}
};【Day55】1600.皇位继承顺序
1600. 皇位继承顺序
一个王国里住着国王、他的孩子们、他的孙子们等等。每一个时间点，这个家庭里有人出生也有人死亡。
这个王国有一个明确规定的皇位继承顺序，第一继承人总是国王自己。我们定义递归函数 Successor(x, curOrder) ，给定一个人 x 和当前的继承顺序，该函数返回 x 的下一继承人。
Successor(x, curOrder):
如果 x 没有孩子或者所有 x 的孩子都在 curOrder 中：
如果 x 是国王，那么返回 null
否则，返回 Successor(x 的父亲, curOrder)
否则，返回 x 不在 curOrder 中最年长的孩子
比方说，假设王国由国王，他的孩子 Alice 和 Bob （Alice 比 Bob 年长）和 Alice 的孩子 Jack 组成。
- 一开始， curOrder 为 [“king”].
- 调用 Successor(king, curOrder) ，返回 Alice ，所以我们将 Alice 放入 curOrder 中，得到 [“king”, “Alice”] 。
- 调用 Successor(Alice, curOrder) ，返回 Jack ，所以我们将 Jack 放入 curOrder 中，得到 [“king”, “Alice”, “Jack”] 。
- 调用 Successor(Jack, curOrder) ，返回 Bob ，所以我们将 Bob 放入 curOrder 中，得到 [“king”, “Alice”, “Jack”, “Bob”] 。
- 调用 Successor(Bob, curOrder) ，返回 null 。最终得到继承顺序为 [“king”, “Alice”, “Jack”, “Bob”] 。
通过以上的函数，我们总是能得到一个唯一的继承顺序。
请你实现 ThroneInheritance 类：
- ThroneInheritance(string kingName) 初始化一个 ThroneInheritance 类的对象。国王的名字作为构造函数的参数传入。
- void birth(string parentName, string childName) 表示 parentName 新拥有了一个名为 childName 的孩子。
- void death(string name) 表示名为 name 的人死亡。一个人的死亡不会影响 Successor 函数，也不会影响当前的继承顺序。你可以只将这个人标记为死亡状态。
- string[] getInheritanceOrder() 返回 除去 死亡人员的当前继承顺序列表。
示例：
输入：
["ThroneInheritance", "birth", "birth", "birth", "birth", "birth", "birth", "getInheritanceOrder", "death", "getInheritanceOrder"]
[["king"], ["king", "andy"], ["king", "bob"], ["king", "catherine"], ["andy", "matthew"], ["bob", "alex"], ["bob", "asha"], [null], ["bob"], [null]]输出：
[null, null, null, null, null, null, null, ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"], null, ["king", "andy", "matthew", "alex", "asha", "catherine"]]解释：
ThroneInheritance t= new ThroneInheritance("king"); // 继承顺序：king
t.birth("king", "andy"); // 继承顺序：king > andy
t.birth("king", "bob"); // 继承顺序：king > andy > bob
t.birth("king", "catherine"); // 继承顺序：king > andy > bob > catherine
t.birth("andy", "matthew"); // 继承顺序：king > andy > matthew > bob > catherine
t.birth("bob", "alex"); // 继承顺序：king > andy > matthew > bob > alex > catherine
t.birth("bob", "asha"); // 继承顺序：king > andy > matthew > bob > alex > asha > catherine
t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "bob", "alex", "asha", "catherine"]
t.death("bob"); // 继承顺序：king > andy > matthew > bob（已经去世）> alex > asha > catherine
t.getInheritanceOrder(); // 返回 ["king", "andy", "matthew", "alex", "asha", "catherine"]提示：
- 1 <= kingName.length, parentName.length, childName.length, name.length <= 15
- kingName，parentName， childName 和 name 仅包含小写英文字母。
- 所有的参数 childName 和 kingName 互不相同。
- 所有 death 函数中的死亡名字 name 要么是国王，要么是已经出生了的人员名字。
- 每次调用 birth(parentName, childName) 时，测试用例都保证 parentName 对应的人员是活着的。
- 最多调用 105 次birth 和 death 。
- 最多调用 10 次 getInheritanceOrder 。
题解：
class ThroneInheritance {
public:
string root;
unordered_map<string, bool> isdeath;
unordered_map<string, vector<string>> family;
ThroneInheritance(string kingName) {
root = kingName;
}
void birth(string parentName, string childName) {
family[parentName].push_back(childName);
}
void death(string name) {
isdeath[name] = true;
}
void dfs(vector<string>& ans, string root) {
if (!isdeath[root])
ans.push_back(root);
for (string str: family[root])
dfs(ans, str);
}
vector<string> getInheritanceOrder() {
vector<string> ans;
dfs(ans, root);
return ans;
}
};
/**
* Your ThroneInheritance object will be instantiated and called as such:
* ThroneInheritance* obj = new ThroneInheritance(kingName);
* obj->birth(parentName,childName);
* obj->death(name);
* vector<string> param_3 = obj->getInheritanceOrder();
*/【Day56】401.二进制手表
401. 二进制手表
二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。
- 例如，下面的二进制手表读取 “3:25” 。
给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。
小时不会以零开头：
- 例如，”01:00” 是无效的时间，正确的写法应该是 “1:00” 。
分钟必须由两位数组成，可能会以零开头：
例如，”10:2” 是无效的时间，正确的写法应该是 “10:02” 。
示例 1：
输入：turnedOn = 1
输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]示例 2：
输入：turnedOn = 9
输出：[]提示：
- 0 <= turnedOn <= 10
题解：
class Solution {
public:
vector<string> readBinaryWatch(int num) {
vector<string> res;
//直接遍历 0:00 -> 12:00 每个时间有多少1
for (int i = 0; i < 12; i++) {
for (int j = 0; j < 60; j++) {
if (count1(i) + count1(j) == num) {
res.push_back(to_string(i)+":"+
(j < 10 ? "0"+to_string(j) : to_string(j)));
}
}
}
return res;
}
//计算二进制中1的个数
int count1(int n) {
int res = 0;
while (n != 0) {
n = n & (n - 1);
res++;
}
return res;
}
};
【Day57】剑指 Offer 15.二进制中1的个数
剑指 Offer 15. 二进制中1的个数
请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。示例 2：
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。示例 3：
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。提示：
- 输入必须是长度为 32 的 二进制串 。
注意：本题与主站 191 题相同：https://leetcode-cn.com/problems/number-of-1-bits/
题解：
右移再 & 1
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans = 0;
for (int i = 0; i < 32; i++) {
ans += ((n >> i) & 1);
}
return ans;
}
};【Day58】149. 直线上最多的点数
149. 直线上最多的点数
给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
示例 1：
输入：points = [[1,1],[2,2],[3,3]]
输出：3示例 2：
输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4提示：
- 1 <= points.length <= 300
- points[i].length == 2
- -104 <= xi, yi <= 104
- points 中的所有点 互不相同
题解：
直接枚举，比较斜率
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int len = points.size();
// 点的数量不够
if(len < 3) {
return len;
}
int maxNum = 2;
// 遍历每两个点
for(int i = 0; i < len - 1; i ++) {
for(int j = i + 1; j < len; j ++) {
// 统计斜率相等个数
int count = 2;
long long dx = points[i][0] - points[j][0];
long long dy = points[i][1] - points[j][1];
// 与其他点比较
for(int k = j + 1; k < len; k ++) {
// 如果斜率相等
if(dx * (points[i][1] - points[k][1]) == dy * (points[i][0] - points[k][0])) {
count ++;
}
}
maxNum = max(maxNum, count);
if(maxNum > len / 2) return maxNum;
}
}
return maxNum;
}
};【Day59】752.打开转盘锁
752. 打开转盘锁
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，’0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
示例 1:
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。示例 2:
输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。示例 3:
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。示例 4:
输入: deadends = ["0000"], target = "8888"
输出：-1提示：
- 1 <= deadends.length <= 500
- deadends[i].length == 4
- target.length == 4
- target 不在 deadends 之中
- target 和 deadends[i] 仅由若干位数字组成
题解：
class Solution {
public:
int seen[10010];//记录搜到过的轮盘锁数字
int ans = -1;
bool dead[10010];//记录死亡数字
int q[10010];//模拟队列
int openLock(vector<string>& deadends, string target) {
for(auto d : deadends){
//将死亡数字转int作为下标存储在dead数组中
int tmp = stoi(d);
dead[tmp] = 1;
}
//如果"0000"是死亡数字直接返回0,如果target为0000直接返回-1
if(dead[0])return -1;
if(target == "0000") return 0;
int tar=stoi(target);
bfs(tar);
return ans;
}
int numsadd(int num)
{
if(num == 10)
return -9;
if(num == -1)
return -9;
else return 1;
}
void bfs(int target)
{
//hh队头，tt队尾
int hh=0,tt=0;
//先将队头初始化为0,代表从"0000"开始旋转
q[0] = 0;
while(hh <= tt){
auto t = q[hh++];
int prev = t;
for(int i = 1 ; i <= 1000 ; i *= 10){
int num = t / i % 10;
int temp=t;
//正向旋转当前位的数字
int tmp = temp + numsadd(num+1)*i;
if(!seen[tmp] && !dead[tmp]){
//满足条件就将temp插入队尾
q[++tt] = tmp;
//更新新转盘锁数字的操作次数
seen[tmp] = seen[prev]+1;
}
//反向旋转当前位的数字
tmp = temp - numsadd(num-1)*i;
if(!seen[tmp] && !dead[tmp]){
q[++tt] = tmp;
seen[tmp] = seen[prev]+1;
}
}
if(seen[target] != 0){
ans = seen[target];
break;
}
}
}
};整整两个月就刷完啦，发现这些题更适合于找工作，而我目前没有这方面的需要，所以以后偶尔刷一下，有时间就发在博客上hh
