合并两个有序数组
给定两个有序整数数组 nums1 和 nums2*，将 *nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
- 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
- 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n*）来保存 *nums2 中的元素。
示例:
1
2
3
4
5
| 输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
|
从后往前进行merge，因为nums1是有足够空间的，避免覆盖问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int count = m + n - 1;
--m;
--n;
while(m >= 0 && n >= 0)
{
nums1[count--] = nums1[m] > nums2[n] ? nums1[m--]:nums2[n--];
}
if(n >= 0)
{
nums1[count--] = nums2[n--];
}
}
};
|
第一个错误的版本
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例:
1
2
3
4
5
6
7
| 给定 n = 5，并且 version = 4 是第一个错误的版本。
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
|
采用二分的思想：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
unsigned int res = n, left = 1, right = n;
if(isBadVersion(n))
{
while(!(isBadVersion(res) && !isBadVersion(res - 1)))
{
res = (left + right) / 2;
if(isBadVersion(res))
{
right = res;
}
else
{
left = res;
}
}
}
return res;
}
};
|
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
1
2
3
4
5
| 输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
|
示例 2：
1
2
3
4
5
6
| 输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
|
到达第 i 阶的方法总数就是到第 (i-1)(i−1) 阶和第 (i-2)(i−2) 阶的方法数之和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int climbStairs(int n) {
int n1 = 1, n2 = 2;
int res, n3 = 3;
if(n == 1)
return n1;
if(n == 2)
return n2;
res = n1 + n2;
if(n == 3)
return res;
while(n3 < n)
{
n1 = n2;
n2 = res;
res = n2 + n1;
++n3;
}
return res;
}
};
|
买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
1
2
3
4
| 输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
|
示例 2:
1
2
3
| 输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
|
只要用两个变量，一个保存到目前为止最大利润（卖出价格和最低价格之间的差值），和目前为止最低价格。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX;
int maxProfit = 0;
int temp = 0;
for(int i = 0; i < prices.size(); ++i)
{
if(prices[i] < minPrice)
minPrice = prices[i];
temp = prices[i] - minPrice;
maxProfit = max(maxProfit, temp);
}
return maxProfit;
}
};
|
最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
1
2
3
| 输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
|
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
经典的动态规划算法。在遍历的过程中计算得到以每个位置为终点的最大子序列的和。遍历一遍同时得到结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sumTemp = nums[0];
int sum = sumTemp;
for(int i = 1; i < nums.size(); ++i)
{
if(sumTemp >= 0) sumTemp += nums[i];
else sumTemp = nums[i];
if(sumTemp > sum)
sum = sumTemp;
}
return sum;
}
};
|
很详细的解释
打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
1
2
3
4
| 输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
|
示例 2:
1
2
3
4
| 输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
|
动态规划，创建数组dp，以dp[i]记录到前i家最多能偷到的钱数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size() == 0)
return 0;
if(nums.size() == 1)
return nums[0];
vector<int> dp(nums.size() + 1, 0);
dp[0] = 0;
dp[1] = nums[0];
for(int i = 2; i <= nums.size(); ++i)
{
dp[i] = max(dp[i-1], nums[i-1] + dp[i-2]);
}
return dp[dp.size() - 1];
}
};
|
