背景
正文
题70、爬楼梯
题目
假设你正在爬楼梯。需要爬 n 阶才能到达楼顶。每次只能爬 1 或 2 个台阶。有多少种不同的爬楼方法？
思路
根据爬楼梯的个数可以列出来公式
示意图：
解法
递归的解法
1
2
3
4
5
6
7
| public class Solution {
public int ClimbStairs(int n) {
if (n == 1) return 1;//这两条为终止条件
if (n == 2) return 2;
return ClimbStairs(n - 1) + ClimbStairs(n - 2);
}
}
|
时间复杂度为O（2^n）,由于每一个值都要进行计算，会产生多余的计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public class Solution {
private Dictionary<int, int> cache = new Dictionary<int, int>();
public int ClimbStairs(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
if (cache.ContainsKey(n))
return cache[n];
int res = ClimbStairs(n - 1) + ClimbStairs(n - 2);
cache[n] = res;
return res;
}
}
|
时间复杂度
O（n），使用字典将计算得到的值存入字典中，下一次的时候直接拿取想要的值
非递归解法：循环解法，自下而上的累加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| public class Solution {
public int ClimbStairs(int n) {
if(n == 1) return 1;
if(n == 2) return 2;
int result = 0;
int pre = 2;
int prePre = 1;
//循环从3开始，结果为前两个结果相加的集合
for (int i = 3; i <= n; ++i) {
result = pre + prePre;
//更新值，每次向上移动一位
prePre = pre;
pre = result;
}
return result;
}
}
|
时间复杂度
O（n）
题1、两数之和
题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
思路
暴力法解题思路
将数组中的所有元素的和都算一遍，
字典一遍遍历
先去寻找这个数字对于目标数所需要的数字，去字典中寻找一遍，如果没有则把当前的数字，键为数字，值为下标存入字典中，既保证了字典中到最后需要输出的数组元素，按照顺序排列，值即为数组下标，又保证了不会出现一个元素使用两次的情况
解法
暴力双层循环遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class Solution {
public int[] TwoSum(int[] nums, int target) {
for (int i = 0; i < nums.Length; i++)
{
for (int j = i + 1; j < nums.Length; j++)
{
if (nums[i] + nums[j] == target)
{
return new int[] {i, j};
}
}
}
// 题目保证一定有解，此行不会执行
return new int[0];
}
}
|
时间复杂度
O（n^2）
字典一遍遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| public class Solution {
public int[] TwoSum(int[] nums, int target)
{
// key：数组数值，value：数值对应的下标
Dictionary<int, int> hashDict = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++)
{
int current = nums[i];
// 需要寻找的互补数字
int complement = target - current;
// 如果字典里存在互补数，直接返回两个下标
if (hashDict.ContainsKey(complement))
{
return new int[] { hashDict[complement], i };
}
// 当前数字存入字典，供后续元素查找
hashDict[current] = i;
}
// 题目保证必有一组解，理论不会走到这里
return new int[0];
}
}
|
时间复杂度
O（n），每个元素最多一次插入，一次查询
使用数组的值作为Key的原因：
我们要用的是比较谁为合适的相加为目标值的元素，到最后需要返回的是下标，也就是知道了数组的值去找下标，所以应当以数组的值作为Key
补充：ContainsKey（）平均时间复杂度为O（1），
ContainsValue （）需要遍历整个数组，时间复杂度为O（n）
题88、合并两个有序数组
题目
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意： 最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了适应这种情况，nums1 的初始长度是 m + n，其中前 m 个元素是需要合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n。
思路
直接将数组2合并到数组1后面，然后进行排序
Array.sort()，的根本是快速排序，时间复杂度为O（n）
顺序双指针，递增排列
逆序双指针遍历，递减排列
解法
先合并后排序
1
2
3
4
5
6
7
8
9
10
11
| public class Solution {
public void Merge(int[] nums1, int m, int[] nums2, int n) {
// 第一步：将nums2全部复制到nums1尾部
for (int i = 0; i < n; i++)
{
nums1[m + i] = nums2[i];
}
// 第二步：整体排序
Array.Sort(nums1);
}
}
|
时间复杂度是O（M+N)
双指针遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| public class Solution {
public void Merge(int[] nums1, int m, int[] nums2, int n)
{
int k = m + n;
int[] temp = new int[k];
for (int index = 0, nums1Index = 0, nums2Index = 0; index < k; index++)
{
if (nums1Index >= m)
{
// nums1有效元素取完，直接取nums2
temp[index] = nums2[nums2Index++];
}
else if (nums2Index >= n)
{
// nums2取完，直接取nums1
temp[index] = nums1[nums1Index++];
}
else if (nums1[nums1Index] < nums2[nums2Index])
{
temp[index] = nums1[nums1Index++];
}
else
{
temp[index] = nums2[nums2Index++];
}
}
// 将临时数组拷贝回nums1
for (int i = 0; i < k; i++)
{
nums1[i] = temp[i];
}
}
}
|
时间复杂度为O（M+N）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| public class Solution {
public void Merge(int[] nums1, int m, int[] nums2, int n)
{
int p1 = m - 1;
int p2 = n - 1;
int tail = m + n - 1;
// 两个数组都还有元素时
while (p1 >= 0 && p2 >= 0)
{
if (nums1[p1] > nums2[p2])
{
nums1[tail] = nums1[p1];
p1--;
}
else
{
nums1[tail] = nums2[p2];
p2--;
}
tail--;
}
// 如果nums2还有剩余元素，直接拷贝到nums1前方
while (p2 >= 0)
{
nums1[tail] = nums2[p2];
p2--;
tail--;
}
}
}
|
复盘
