给定一个整数数组 nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
class Solution { public: int maxSubArray(vector<int> &nums) { int sum = 0, max = nums[0]; for (int num:nums) { if (sum < 0) sum = 0; sum += num; if (sum > max) max = sum; } return max; } };
假设你是一个选择性遗忘的赌徒,数组表示你这几天来赢钱或者输钱, 你用sum来表示这几天来的输赢, 用ans来存储你手里赢到的最多的钱, 如果昨天你手上还是输钱(sum < 0),你忘记它,明天继续赌钱; 如果你手上是赢钱(sum > 0), 你记得,你继续赌钱; 你记得你手气最好的时候 作者:acnesu 链接:https://leetcode-cn.com/problems/maximum-subarray/solution/jia-she-ni-shi-yi-ge-du-tu-by-acnesu/ 来源:力扣(LeetCode)
在第一行我们写上一个 0
。接下来的每一行,将前一行中的0
替换为01
,1
替换为10
。
给定行数 N
和序数 K
,返回第 N
行中第 K
个字符。(K
从1开始)
例子:
输入: N = 1, K = 1 输出: 0 输入: N = 2, K = 1 输出: 0 输入: N = 2, K = 2 输出: 1 输入: N = 4, K = 5 输出: 1 解释: 第一行: 0 第二行: 01 第三行: 0110 第四行: 01101001
class Solution { public: int kthGrammar(int N, int K) { if (N != 1) return ((kthGrammar(N - 1, (K + 1) / 2)) + K % 2 + 1) % 2; return 0; } };
给定两个正整数 x 和 y,如果某一整数等于 x^i + y^j,其中整数 i >= 0 且 j >= 0,那么我们认为该整数是一个强整数。
返回值小于或等于 bound 的所有强整数组成的列表。
你可以按任何顺序返回答案。在你的回答中,每个值最多出现一次。
示例 1:
输入:x = 2, y = 3, bound = 10 输出:[2,3,4,5,7,9,10] 解释: 2 = 2^0 + 3^0 3 = 2^1 + 3^0 4 = 2^0 + 3^1 5 = 2^1 + 3^1 7 = 2^2 + 3^1 9 = 2^3 + 3^0 10 = 2^0 + 3^2
示例 2:
输入:x = 3, y = 5, bound = 15 输出:[2,4,6,8,10,14]
提示:
1 <= x <= 100
1 <= y <= 100
0 <= bound <= 10^6
class Solution { public: vector<int> powerfulIntegers(int x, int y, int bound) { set<int> num; if (x != 1 && y != 1) { for (int i = 0; i <= log(bound) / log(x); i++) { for (int j = 0; j <= log(bound - pow(x, i) / log(y)); j++) { if (bound >= pow(x, i) + pow(y, j)) num.insert(pow(x, i) + pow(y, j)); } } } else if (x == 1 && y == 1) { if (bound >= 2) num.insert(2); } else if (x == 1) { for (int j = 0; j <= log(bound - 1) / log(y); j++) { num.insert(pow(y, j) + 1); } } else { for (int i = 0; i <= log(bound - 1) / log(x); i++) { num.insert(pow(x, i) + 1); } } vector<int> ans; ans.assign(num.begin(), num.end()); return ans; } };
给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。
注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。
例如,
给定二叉搜索树: 4 / \ 2 7 / \ 1 3 和 插入的值: 5
你可以返回这个二叉搜索树:
4 / \ 2 7 / \ / 1 3 5
或者这个树也是有效的:
5
/ \
2 7
/ \
1 3
\
4
class Solution { public: TreeNode *insertIntoBST(TreeNode *root, int val) { if (val > root->val && root->right) { insertIntoBST(root->right, val); } else if (val < root->val && root->left) { insertIntoBST(root->left, val); } else if (val > root->val && !root->right) { root->right = new TreeNode(val); } else { root->left = new TreeNode(val); } return root; } };
https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/
在歌曲列表中,第 i 首歌曲的持续时间为 time[i] 秒。
返回其总持续时间(以秒为单位)可被 60 整除的歌曲对的数量。形式上,我们希望索引的数字 i < j 且有 (time[i] + time[j]) % 60 == 0。
示例 1:
输入:[30,20,150,100,40] 输出:3 解释:这三对的总持续时间可被 60 整数: (time[0] = 30, time[2] = 150): 总持续时间 180 (time[1] = 20, time[3] = 100): 总持续时间 120 (time[1] = 20, time[4] = 40): 总持续时间 60
示例 2:
输入:[60,60,60] 输出:3 解释:所有三对的总持续时间都是 120,可以被 60 整数。
class Solution { public: int numPairsDivisibleBy60(vector<int> &time) { int num[60] = {0}, sum = 0; for (int n:time) { num[n % 60]++; } //60+60 sum += (num[0] - 1) * num[0] / 2; //30+30 sum += (num[30] - 1) * num[30] / 2; //(1-29)+(31-59) for (int x = 1; x <= 29; x++) { sum += num[x] * num[60 - x]; } return sum; } };
https://leetcode-cn.com/problems/pairs-of-songs-with-total-durations-divisible-by-60/