给你一个整数 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 < = 1 0 4 1 <= n <= 10^4 1<=n<=104
这道题采用动态规划进行求解，不能用贪心去做，否则结果是错误的，反例就是示例1，如果用贪心，12=9+1+1+1，需要4个数。
另外一种方法是利用了一个数学定理(四平方和定理)，见https://leetcode.cn/problems/perfect-squares/solution/wan-quan-ping-fang-shu-by-leetcode-solut-t99c/
#include<math.h>
#include<vector>
using namespace std;
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
int minn = INT_MAX;
for (int j = 1; j * j <= i; j++) {
minn = min(minn, dp[i - j * j]);
}
dp[i] = minn + 1;
}
return dp[n];
}
};
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
进阶：你能尽量减少完成的操作次数吗？
这道题目的思路就是冒泡排序，但是不同点是 if 语句里面交换的条件为当前位是否为0且下一位是否不为0。
并设置一个 isFinish 来判断是否需要结束算法。如果当前循环中一次交换都没有发生(已经没有0了)，那么算法也就可以结束了。
#include<vector>
#include<iostream>
using namespace std;
class Solution {
public:
void moveZeroes(vector<int>& nums) {
for (int i = 0; i < nums.size(); i++) {
bool isFinish = true;
for (int j = 0; j < nums.size() - i - 1; j++) {
if (nums[j] == 0 && nums[j + 1] != 0) {
swap(nums[j], nums[j + 1]);
isFinish = false;
}
}
if (isFinish) {
break;
}
}
}
};
int main() {
Solution sol;
vector<int> vec = { 1,0,2,0,3 };
sol.moveZeroes(vec);
for (auto it : vec) {
cout << it << " ";
}
}
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
提示：
1
<
=
n
<
=
1
0
5
1 <= n <= 10^5
1<=n<=105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？
最初是采用冒泡排序，发现有个很大的测试用例会导致超时，然后发现复杂度搞错了，不应该到 O ( n 2 ) O(n^2) O(n2)级别的，可以用快排搞到 O ( n l o g n + n ) O(nlogn+n) O(nlogn+n)，即排序后再遍历一遍。
一种时间复杂度为O(n)的快慢指针的方法，很巧妙：https://leetcode.cn/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
//class Solution {
//public:
// int findDuplicate(vector<int>& nums) {
// for (int i = 0; i < nums.size(); i++) {
// for (int j = 0; j < nums.size() - i - 1; j++) {
// if (nums[j] > nums[j + 1]) {
// swap(nums[j], nums[j + 1]);
// }
// else if (nums[j] == nums[j + 1]) {
// return nums[j];
// }
// }
// }
// }
//};
class Solution {
public:
int findDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
int i;
for (i = 0; i < nums.size() - 1; i++) {
if (nums[i] == nums[i + 1])break;
}
return nums[i];
}
};
int main() {
vector<int> vec = { 1,3,4,2,2 };
Solution sol;
int res = sol.findDuplicate(vec);
cout << res;
}
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = “()())()”
输出：[“(())()”,“()()()”]
示例 2：
输入：s = “(a)())()”
输出：[“(a())()”,“(a)()()”]
示例 3：
输入：s = “)(”
输出：[“”]
提示：
1 <= s.length <= 25
s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成
s 中至多含 20 个括号
暴力搜索，枚举每一种情况，对于肯定不符合的情况，比如右边括号数量已经大于了左边括号数量（score为负，剪枝），预处理时统计了左括号和右括号的数量（score应该小于他们俩的最小值，如果大于了证明当前情况已经不满足了）。
基于上述两种思想就可以进行剪枝了。
#include<vector>
#include<string>
#include<unordered_set>
using namespace std;
class Solution {
int maxMaybeResult;
int strLength; // 字符串的长度
int len; // 当前找到的最长的合法字符串
unordered_set<string> subStrs; // 用来存储找到的合法字符串，因为不能存在重复的情况，因此采用集合
string str;
private:
void dfs(int pos, string cur, int score) {
// 递归结束条件 -> 中途不符合条件（剪枝）
if (score<0 || score>maxMaybeResult) {
return;
}
// 递归结束条件 -> 符合条件，或者最后不符合条件
if (pos == strLength) {
if (score == 0 && cur.length() >= len) {
// 如果当前的更长，之前的全部作废，同时更新len
if (cur.length() > len) {
subStrs.clear();
len = cur.length();
}
// 插入到当前集合中来
subStrs.insert(cur);
}
return;
}
char ch = str[pos];
if (ch == '(') {
dfs(pos + 1, cur + ch, score + 1);
dfs(pos + 1, cur, score);
}
else if (ch == ')') {
dfs(pos + 1, cur + ch, score - 1);
dfs(pos + 1, cur, score);
}
else {
dfs(pos + 1, cur + ch, score);
}
}
public:
vector<string> removeInvalidParentheses(string s) {
len = 0;
strLength = s.length();
str = s;
int leftNum = 0, rightNum = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
leftNum++;
}
else if (s[i] == ')') {
rightNum++;
}
}
maxMaybeResult = min(leftNum, rightNum);
dfs(0, "", 0);
vector<string> res;
for (auto it : subStrs) {
res.push_back(it);
}
return res;
}
};