给你一个字符串 s，找到 s 中最长的回文子串。
划定步长，遍历判断
class Solution {
public:
string longestPalindrome(string s) {
if(s.size() < 2){
return s;
}
int maxlen = 1;
int begin = 0;
int dp[s.size()][s.size()];
for(int i = 0 ; i < s.size() ; i++){
dp[i][i] = 1;
}
for(int l = 2 ; l <= s.size() ; l++){
for(int i = 0 ; i < s.size() ; i++){
int j = l + i - 1;
if(j >= s.size()){
break;
}
if(s[i] != s[j]){
dp[i][j] = 0;
}
else{
if(j-i < 3){
dp[i][j] = 1;
}
else{
dp[i][j] = dp[i+1][j-1];
}
}
if(dp[i][j]>0 && j-i+1 > maxlen){
maxlen = j - i + 1;
begin = i;
}
}
}
return s.substr(begin, maxlen);
}
};
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
class Solution {
public:
bool isValid(string s) {
int n = s.size();
if(n % 2 == 1){
return false;
}
unordered_map<char,char> pairs = {
{')','('},
{']','['},
{'}','{'},
};
stack<char> stk;
for(char ch:s){
if(pairs.count(ch)){
if(stk.empty() || stk.top() != pairs[ch]){
return false;
}
stk.pop();
}
else{
stk.push(ch);
}
}
return stk.empty();
}
};
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
可以理解为背包问题
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
int dp[n];
for(int i = 0 ; i < n ; i++){
dp[i] = 10000;
}
dp[0] = 0;
for(int i = 0 ; i < n - 1 ; i++){
for(int j = 1 ; j <= nums[i] ; j++){
if(i + j >= n){
break;
}
dp[i+j] = min(dp[i+j], dp[i]+1);
}
}
return dp[n-1];
}
};
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int n = digits.size() - 1;
if(digits[n] != 9){
digits[n] = digits[n] + 1;
}
else{
while(n >= 0 && digits[n] == 9){
digits[n] = 0;
n--;
}
if(n >= 0){
digits[n]++;
}
else{
digits.insert(digits.begin(),1);
}
}
return digits;
}
};
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.length();
int m = word2.length();
// 有一个字符串为空串
if(n * m == 0){
return n + m;
}
// DP数组
vector<vector<int>> D(n+1, vector<int>(m+1));
// 边界状态初始化
for(int i = 0 ; i < n + 1 ; i++){
D[i][0] = i;
}
for(int j = 0 ; j < m + 1 ; j++){
D[0][j] = j;
}
// 计算所有dp值
for(int i = 1 ; i < n + 1 ; i++){
for(int j = 1 ; j < m + 1 ; j++){
int left = D[i-1][j] + 1;
int down = D[i][j-1] + 1;
int left_down = D[i-1][j-1];
if(word1[i-1] != word2[j-1]){
left_down++;
}
D[i][j] = min(left, min(down, left_down));
}
}
return D[n][m];
}
};
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> nums3 = nums1;
int s = 0;
int t = 0;
for(int i = 0 ; i < m + n ; i++){
if(s == m){
nums1[i] = nums2[t];
t++;
}
else if(t == n){
nums1[i] = nums3[s];
s++;
}
else if(nums3[s] < nums2[t]){
nums1[i] = nums3[s];
s++;
}
else{
nums1[i] = nums2[t];
t++;
}
}
}
};
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：
"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
动态规划，注意各种判断条件
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
if(s[0] == '0'){
return 0;
}
if(n < 2){
return n;
}
int dp[n+1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2 ; i <= n ; i++){
int temp = (s[i-2] - '0') * 10 + s[i-1] - '0';
if(temp <= 26 && temp > 10 && temp != 20){
dp[i] = dp[i-1] + dp[i-2];
}
else if(temp > 26 && s[i-1]=='0'){
return 0;
}
else if((temp < 10 && temp > 0) || temp > 26){
dp[i] = dp[i-1];
}
else if(temp == 10 || temp == 20){
dp[i] = dp[i-2];
}
else if(temp == 0){
return 0;
}
}
return dp[n];
}
};
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> mid;
stack<TreeNode*> s;
while(root != nullptr || !s.empty()){
while(root != nullptr){
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
mid.push_back(root->val);
root = root->right;
}
return mid;
}
};
给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
好难，多看几次，试着理解吧。
class Solution {
public:
vector<TreeNode*> generateTrees(int start, int end) {
if (start > end) {
return { nullptr };
}
vector<TreeNode*> allTrees;
// 枚举可行根节点
for (int i = start; i <= end; i++) {
// 获得所有可行的左子树集合
vector<TreeNode*> leftTrees = generateTrees(start, i - 1);
// 获得所有可行的右子树集合
vector<TreeNode*> rightTrees = generateTrees(i + 1, end);
// 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
for (auto& left : leftTrees) {
for (auto& right : rightTrees) {
TreeNode* currTree = new TreeNode(i);
currTree->left = left;
currTree->right = right;
allTrees.emplace_back(currTree);
}
}
}
return allTrees;
}
vector<TreeNode*> generateTrees(int n) {
if (!n) {
return {};
}
return generateTrees(1, n);
}
};
给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
注意：a + b 意味着字符串 a 和 b 连接。
这道题用双指针，结果会出现错误，因此使用动态规划，考虑s1的前i个字符能否和s2的前j个字符一起组成s3的前i+j个字符
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s1.size() + s2.size() != s3.size()){
return false;
}
int dp[s1.size()+1][s2.size()+1];
for(int i = 0 ; i <= s1.size() ; i++){
for(int j = 0 ; j <= s2.size() ; j++){
dp[i][j] = 0;
}
}
dp[0][0] = 1;
for(int i = 1 ; i <= s1.size() ; i++){
dp[i][0] = s1[i-1] == s3[i-1] ? 1:0;
if(dp[i][0] == 0)
break;
}
for(int i = 1 ; i <= s2.size() ; i++){
dp[0][i] = s2[i-1] == s3[i-1] ? 1:0;
if(dp[0][i] == 0)
break;
}
for(int i = 1 ; i <= s1.size() ; i++){
for(int j = 1 ; j <= s2.size() ; j++){
if((dp[i-1][j] == 1 && s1[i-1] == s3[i+j-1]) || (dp[i][j-1] == true && s2[j-1] == s3[i+j-1])){
dp[i][j] = 1;
}
else{
dp[i][j] = 0;
}
}
}
return dp[s1.size()][s2.size()] == 1;
}
};
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res(numRows);
for(int i = 0 ; i < numRows ; i++){
res[i].resize(i+1);
res[i][0] = res[i][i] = 1;
for(int j = 1 ; j < i ; j++){
res[i][j] = res[i-1][j] + res[i-1][j-1];
}
}
return res;
}
};
给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。
在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int dp[n][2];
dp[0][0] = 0, dp[0][1] = -prices[0];
for (int i = 1; i < n; ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[n - 1][0];
}
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0;
for(int i = 1 ; i < prices.size() ; i++){
res = res + max(0, prices[i] - prices[i-1]);
}
return res;
}
};
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> dict;
for(int i = 0 ; i < wordDict.size() ; i++){
dict.insert(wordDict[i]);
}
int dp[s.size() + 1];
for(int i = 0 ; i <= s.size() ; i++){
dp[i] = 0;
}
dp[0] = 1;
for(int i = 0 ; i <= s.size() ; i++){
for(int j = 0 ; j < i ; j++){
if(dp[j]==1 && dict.find(s.substr(j, i-j)) != dict.end()){
dp[i] = 1;
break;
}
}
}
return dp[s.size()] == 1;
}
};
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> seen;
while(head != NULL){
if(seen.count(head)){
return true;
}
seen.insert(head);
head = head->next;
}
return false;
}
};
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
使用动态规划，注意负数乘负数的情况，因此要保存一个至今为止最小负数的动态规划数组。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int dp[nums.size()+1];
int fshu[nums.size()+1];
for(int i = 0 ; i <= nums.size() ; i++){
fshu[i] = 0;
}
dp[0] = 1;
fshu[0] = 1;
int maxsum = -10000;
for(int i = 1 ; i <= nums.size() ; i++){
dp[i] = max(nums[i-1], nums[i-1]*dp[i-1]);
dp[i] = max(dp[i], nums[i-1]*fshu[i-1]);
fshu[i] = min(nums[i-1], nums[i-1]*fshu[i-1]);
fshu[i] = min(fshu[i], dp[i-1]*nums[i-1]);
maxsum = max(dp[i], maxsum);
}
return maxsum;
}
};
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素
class MinStack {
stack<int> x_stack;
stack<int> min_stack;
public:
MinStack() {
min_stack.push(INT_MAX);
}
void push(int val) {
x_stack.push(val);
min_stack.push(min(min_stack.top(),val));
}
void pop() {
x_stack.pop();
min_stack.pop();
}
int top() {
return x_stack.top();
}
int getMin() {
return min_stack.top();
}
};
/**
* 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) {
unordered_set<ListNode*> map;
while(headA != NULL){
map.insert(headA);
headA = headA->next;
}
while(headB != NULL){
if(map.count(headB) == 1){
return headB;
}
headB = headB->next;
}
return NULL;
}
};
给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身
class Solution {
public:
bool isIsomorphic(string s, string t) {
unordered_map<char,char> s2t;
unordered_map<char,char> t2s;
int len = s.length();
for(int i = 0 ; i < len ; i++){
char x = s[i],y = t[i];
if((s2t.count(x) && s2t[x] != y) || (t2s.count(y) && t2s[y] != x)){
return false;
}
s2t[x] = y;
t2s[y] = x;
}
return true;
}
};
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.size() == 0 || matrix[0].size() == 0){
return 0;
}
int maxSide = 0;
int rows = matrix.size();
int columns = matrix[0].size();
vector<vector<int>> dp(rows, vector<int>(columns));
for(int i = 0 ; i < rows ; i++){
for(int j = 0 ; j < columns ; j++){
if(matrix[i][j] == '1'){
if(i == 0 || j == 0){
dp[i][j] = 1;
}
else{
dp[i][j] = min(min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]) + 1;
}
maxSide = max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root == nullptr){
return nullptr;
}
TreeNode* left = invertTree(root -> left);
TreeNode* right = invertTree(root -> right);
root -> left = right;
root -> right = left;
return root;
}
};
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* temp = root;
while(root != NULL){
if(p -> val < root ->val && q -> val < root ->val){
root = root -> left;
}
else if(p -> val > root ->val && q -> val > root ->val){
root = root -> right;
}
else{
break;
}
}
return root;
}
};
给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。
class Solution {
public:
vector<int> diffWaysToCompute(string expression) {
vector<int> vec1, vec2, res;
int n = expression.size();
int flag = 0;
for(int i = 0 ; i < n ; i++){
if(expression[i] == '+' || expression[i] == '-' || expression[i] == '*'){
flag = 1; // flag=1说明string是表达式，flag=0说明string是一个数字
vec1 = diffWaysToCompute(string(expression, 0, i)); // 从第0个开始，存i个字符
vec2 = diffWaysToCompute(string(expression, i+1, n-i-1));
for(int v1 : vec1){
for(int v2 : vec2){
if(expression[i] == '+'){
res.push_back(v1 + v2);
}
if(expression[i] == '-'){
res.push_back(v1 - v2);
}
if(expression[i] == '*'){
res.push_back(v1 * v2);
}
}
}
}
}
if(flag==0){
return {std::stoi(expression)};
}
return res;
}
};
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.length() != t.length()){
return false;
}
vector<int> res(26,0);
for(int i = 0 ; i < s.length() ; i++){
res[s[i] - 'a']++;
}
for(int i = 0 ; i < t.length() ; i++){
res[t[i] - 'a']--;
if(res[t[i]-'a'] < 0){
return false;
}
}
return true;
}
};
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void fpaths(TreeNode* root, string path, vector<string>& paths){
if(root != nullptr){
path = path + to_string(root->val);
if(root->left == nullptr && root->right == nullptr){
paths.push_back(path);
}
else{
path = path + "->";
fpaths(root->left, path, paths);
fpaths(root->right, path, paths);
}
}
}
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> paths;
fpaths(root, "", paths);
return paths;
}
};
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n + 1);
dp[1] = 1;
int p2 = 1, p3 = 1, p5 = 1;
for (int i = 2; i <= n; i++) {
int num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5;
dp[i] = min(min(num2, num3), num5);
if (dp[i] == num2) {
p2++;
}
if (dp[i] == num3) {
p3++;
}
if (dp[i] == num5) {
p5++;
}
}
return dp[n];
}
};
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1);
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 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size(), left = 0, right = 0;
while (right < n) {
if (nums[right]) {
swap(nums[left], nums[right]);
left++;
}
right++;
}
}
};
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.empty()){
return 0;
}
int n = prices.size();
// f[i][0]:手上持有股票的最大收益
// f[i][1]:手上不持有股票，并且处于冷冻期中的累计最大收益
// f[i][2]:手上不持有股票，并且不在冷冻期中的累计最大收益
vector<vector<int>> f(n, vector<int>(3));
f[0][0] = -prices[0];
for(int i = 1 ; i < n ; i++){
f[i][0] = max(f[i-1][0], f[i-1][2] - prices[i]);
f[i][1] = f[i-1][0] + prices[i];
f[i][2] = max(f[i-1][1], f[i-1][2]);
}
return max(f[n-1][1], f[n-1][2]);
}
};
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
unordered_map<TreeNode*, int> f, g;
void dfs(TreeNode* node){
if(!node){
return;
}
dfs(node -> left);
dfs(node -> right);
f[node] = node -> val + g[node -> left] + g[node -> right];
g[node] = max(f[node -> left], g[node -> left]) + max(f[node -> right], g[node -> right]);
}
int rob(TreeNode* root) {
dfs(root);
return max(f[root], g[root]);
}
};
给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：
answer[i] % answer[j] == 0 ，或
answer[j] % answer[i] == 0
如果存在多个有效解子集，返回其中任何一个均可。
class Solution {
public:
vector<int> largestDivisibleSubset(vector<int>& nums) {
sort(nums.begin(), nums.end());
int len = nums.size();
// 第1步：动态规划找出最大子集的个数、最大子集中的最大整数
vector<int> dp(len, 1);
int maxSize = 1;
int maxVal = dp[0];
for(int i = 1 ; i < len ; i++){
for(int j = 0 ; j < i ; j++){
if(nums[i] % nums[j] == 0){
dp[i] = max(dp[i], dp[j] + 1);
}
}
if(dp[i] > maxSize){
maxSize = dp[i];
maxVal = nums[i];
}
}
// 第2步：倒推获得最大子集
vector<int> res;
if(maxSize == 1){
res.push_back(nums[0]);
return res;
}
for(int i = len - 1 ; i >= 0 && maxSize > 0 ; i--){
if(dp[i] == maxSize && maxVal % nums[i] == 0){
res.push_back(nums[i]);
maxVal = nums[i];
maxSize--;
}
}
return res;
}
};
我们正在玩一个猜数游戏，游戏规则如下：
我从 1 到 n 之间选择一个数字。
你来猜我选了哪个数字。
如果你猜到正确的数字，就会 赢得游戏 。
如果你猜错了，那么我会告诉你，我选的数字比你的 更大或者更小 ，并且你需要继续猜数。
每当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。如果你花光了钱，就会 输掉游戏 。
给你一个特定的数字 n ，返回能够 确保你获胜 的最小现金数，不管我选择那个数字 。
解题思路
class Solution {
public:
int getMoneyAmount(int n) {
vector<vector<int>> f(n+1, vector<int>(n+1));
for(int i = n - 1 ; i >= 1 ; i--){
for(int j = i + 1 ; j <= n ; j++){
f[i][j] = j + f[i][j - 1];
for(int k = i ; k < j ; k++){
f[i][j] = min(f[i][j], k + max(f[i][k-1], f[k+1][j]));
}
}
}
return f[1][n];
}
};
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1);
dp[0] = 1;
for(int i = 1 ; i <= target ; i++){
for(int& num : nums){
if(num <= i && dp[i - num] < INT_MAX - dp[i]){
dp[i] = dp[i] + dp[i-num];
}
}
}
return dp[target];
}
};
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
if (n < 2) {
return false;
}
int sum = accumulate(nums.begin(), nums.end(), 0);
int maxNum = *max_element(nums.begin(), nums.end());
if (sum & 1) {
return false;
}
int target = sum / 2;
if (maxNum > target) {
return false;
}
vector<vector<int>> dp(n, vector<int>(target + 1, 0));
for (int i = 0; i < n; i++) {
dp[i][0] = true;
}
dp[0][nums[0]] = true;
for (int i = 1; i < n; i++) {
int num = nums[i];
for (int j = 1; j <= target; j++) {
if (j >= num) {
dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n - 1][target];
}
};
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
把每一个区间看作一个个体
class Solution {
public:
int compare(vector<int> a, vector<int> b){
return a[0] < b[0];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.size() == 0){
return 0;
}
sort(intervals.begin(), intervals.end(), compare);
int n = intervals.size();
vector<int> f(n, 1);
for(int i = 1 ; i < n ; i++){
for(int j = 0 ; j < i ; j++){
if (intervals[j][1] <= intervals[i][0]) {
f[i] = max(f[i], f[j] + 1);
}
}
}
return n - *max_element(f.begin(), f.end());
}
};
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.size();
for (int i = 1; i * 2 <= n; ++i) {
if (n % i == 0) {
bool match = true;
for (int j = i; j < n; ++j) {
if (s[j] != s[j - i]) {
match = false;
break;
}
}
if (match) {
return true;
}
}
}
return false;
}
};
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
class Solution {
public:
vector<int> getZerosOnes(string& str){
vector<int> zerosOnes(2);
for(int i = 0 ; i < str.size() ; i++){
zerosOnes[str[i] - '0']++;
}
return zerosOnes;
}
int findMaxForm(vector<string>& strs, int m, int n) {
int length = strs.size();
vector<vector<vector<int>>> dp(length+1, vector<vector<int>>(m+1, vector<int>(n+1)));
for(int i = 1 ; i <= length ; i++){
vector<int>&& zerosOnes = getZerosOnes(strs[i - 1]);
int zeros = zerosOnes[0], ones = zerosOnes[1];
for(int j = 0 ; j <= m ; j++){
for(int k = 0 ; k <= n ; k++){
dp[i][j][k] = dp[i-1][j][k];
if(j >= zeros && k >= ones){
dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-zeros][k-ones] + 1);
}
}
}
}
return dp[length][m][n];
}
};
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for(int i = 0 ; i < nums.size() ; i++){
sum = sum + nums[i];
}
int diff = sum - target;
if(diff < 0 || diff % 2 != 0){
return 0;
}
int n = nums.size(), neg = diff / 2;
vector<vector<int>> dp(n + 1, vector<int>(neg + 1));
dp[0][0] = 1;
for(int i = 1 ; i <= n ; i++){
int num = nums[i-1];
for(int j = 0 ; j <= neg ; j++){
dp[i][j] = dp[i-1][j];
if(j >= num){
dp[i][j] = dp[i][j] + dp[i-1][j-num];
}
}
}
return dp[n][neg];
}
};
class Solution(object):
def reverseBits(self, num):
"""
:type num: int
:rtype: int
"""
cur = 0
insert = 0
res = 1
for i in range(32):
if num & (1<<i):
cur += 1
insert +=1
else:
insert = cur + 1
cur = 0
res = max(res,insert)
return res
和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。
数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。
class Solution {
public:
int findLHS(vector<int>& nums) {
unordered_map<int, int> map;
for(int i = 0 ; i < nums.size() ; i++){
map[nums[i]]++;
}
int res = 0;
for(auto [key, val] : map){
if(map.count(key + 1)){
res = max(res, val + map[key+1]);
}
}
return res;
}
};
假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设答案总是存在。
清空vector，使用.clear()
class Solution {
public:
vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
unordered_map<string, int> index;
for(int i = 0 ; i < list1.size() ; i++){
index[list1[i]] = i;
}
vector<string> ret;
int indexsum = 10000;
for(int i = 0 ; i < list2.size() ; i++){
if(index.count(list2[i]) > 0){
int j = index[list2[i]];
if(i + j < indexsum){
ret.clear();
ret.push_back(list2[i]);
indexsum = i + j;
}
else if(i + j == indexsum){
ret.push_back(list2[i]);
}
}
}
return ret;
}
};