您正在查看：2020年2月
2020-02-06 |HHR
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
class Solution {
public:
int climbStairs(int n) {
vector<int> ans;
ans.push_back(1);
ans.push_back(2);
for (int x = 2; x < n; x++) {
ans.push_back(ans[x - 1] + ans[x - 2]);
}
return ans[n-1];
}
};到每一阶的方法数是前两阶方法数之和
2020-02-06 |HHR
给定一个整数数组 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）
2020-02-05 |HHR
在第一行我们写上一个 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;
}
};
2020-02-05 |HHR
给定两个正整数 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 <= 1001 <= y <= 1000 <= 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;
}
};
2020-02-05 |HHR
给定二叉搜索树（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/