LeetCode

Posted on 2019-03-05 Edited on 2019-03-19

动态规划

70. Climbing Stairs

https://leetcode.com/problems/climbing-stairs/

主要思路：上第n级台阶 = 从第n-1级台阶上1步 + 从第n-2级台阶上2步。

由于初始的上第1、2、3阶台阶的方法均可数，因而可以计算出上任意阶台阶的情况。

62. Unique Paths

https://leetcode.com/problems/unique-paths/

根据组合数的性质：
$$
C(n, m) = C(n-1, m-1) + C(n-1, m)
$$
二维vector初始化：

1	vector<vector<int>> ans(rows, vector<int>(cols), initNo));

注意：这里的需要走的横向步数和纵向步数不是m和n，而是m-1和n-1.

数组和数字

https://leetcode.com/problems/plus-one/

直接数组转化为int计算再转回，会导致越界。循环时考虑连续进位，数组比原始+1.

238. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/

要求复杂度O(n)，且不能用除法

思路是建立两个新的数组分别从前往后、从后往前计算。

比如[a, b, c, d]，建立一个数组计算[1, a, ab, abc]，第二个数组计算[bcd, cd, d, 1]。这两次循环复杂度都是O(n).

这样第一个数组和第二个数组的对应元素相乘即可得到结果。

148. Sort List

https://leetcode.com/problems/sort-list/submissions/

时间复杂度O(nlogn) => 归并排序

递归执行：按照归并树的后序遍历而不是从下到上的“层次遍历”（这种貌似可以用循环实现）

由于是单项链表的数据结构首先遍历一遍记录总个数
递归的接口如下：
1
ListNode * mergeSort(ListNode * const node1, ListNode * const node2, const int n);
node1：归并的左边链表的头指针

node2：归并的右边链表的头指针

n：本轮归并的每段的长度
递归函数截止条件：两个node地址相同 => 说明只有一个元素，不再需要拆分，并返回该指针node

拆分结束后开始链表的排序操作（这里注意指针真的不要乱指）

这里考虑右侧链表向左侧链表插入元素，分了头节点和非头节点的情况。

// 排序
while(cur1 != NULL && cur2 != NULL) {
    if(cur1 -> val > cur2 -> val) { // cur2 接在 cur1 前面
        // 第一个
        if(ans == NULL) {
            ans = cur2;
        } else { // 否则就插在上一个操作数的next处
            lastCur -> next = cur2;
        }
        // 暂存右侧链表的头指针的
        ListNode * temp = cur2 -> next;
        // 修改当前被插入数的下一个为左侧头指针
        cur2 -> next = cur1;
        // 更新lastCur
        lastCur = cur2;
        // 更新右侧链表头指针
        cur2 = temp;
    } else {
        // 判断头指针
        if(ans == NULL) {
            ans = cur1;
        }
        // 更新last
        lastCur = cur1;
        // 左侧链表头指针右移
        cur1 = cur1 -> next;
    }
}
// 当一个链表已经遍历完而另一个没有遍历完的时候
if(cur1 != NULL && lastCur != NULL) {
    lastCur -> next = cur1;
} else if(cur2 != NULL) {
    lastCur -> next = cur2;
}

需要注意的几个地方：

当链表长度不为pow(2, x)的时候，每次计算Node2的时候，for循环的截止为(n+1)/2. 否则最后几个不能被整除的元素会被丢下。但是递归的传参不需要，只需要n/2。
lastCur只需要考虑已经排序的链表的上一个操作的位置，不需要分为两个分别考虑参与归并的两个链表。

常量指针和指针常量

疯了，怎么也记不住这里。

参考：https://blog.csdn.net/weibo_dm/article/details/80445205

int a，b；
int * const p=&a //指针常量
//那么分为一下两种操作
*p=9;//操作成功
p=&b;//操作错误
------------------------------------------
int a，b；
const int *p=&a //常量指针
//那么分为一下两种操作
*p=9;//操作错误
p=&b;//操作成功

347. Top K Frequent Elements

https://leetcode.com/problems/top-k-frequent-elements/

要求：O(nlogn)

思路：哈希表快速统计每个元素出现的个数。

之后使用vector + sort快排。

主要是哈希表unordered_map和快排函数sort的语法：

哈希表的访问是first, seconnd
vector + pair = vector<pair<int, int>>. 元素：pair<int, int>

454. 4 Sum II

https://leetcode.com/problems/4sum-ii/

思路：哈希表 + 分治

四个数组求A+B并存入unordered_map，遍历C+D的同时在HashMap使用find函数查找。（在哈希表中find比遍历快多了）. 默认O(logn)

11. Container With Most Water

https://leetcode.com/problems/container-with-most-water/

思路：剪枝？

由于短板效应，在确定左侧为短板的时候，右侧不变（这样container的width不减小）才能容量最大。同理，右侧为短板的时候，左侧不变。

这种思路下不需要循环，只要确定了哪边为短板后，将短板向内（左侧向右，右侧向左）移动1，另一侧保持不变，继续递归。

每次递归计算新的container，决定是否更新ans。

参考：https://leetcode.com/problems/container-with-most-water/discuss/6099/Yet-another-way-to-see-what-happens-in-the-O(n)-algorithm

int maxArea(vector<int>& height) {
    int ans = 0;
    recursive(0, height.size()-1, ans, height);
    return ans;
}

void recursive(const int & leftIndex, const int & rightIndex, int & ans, const vector<int>& height) {
    if(leftIndex == height.size() - 1 || rightIndex == 0 || leftIndex >= rightIndex)
        return;
    int minEdge = min(height[leftIndex], height[rightIndex]);
    ans = (rightIndex - leftIndex) * minEdge > ans ?  (rightIndex - leftIndex) * minEdge : ans; // 更新container size
    if(height[leftIndex] == minEdge) { // 左侧为短边，右侧不用看
        recursive(leftIndex + 1, rightIndex, ans, height);
    } else { // 右侧为短边，左侧不用遍历
        recursive(leftIndex, rightIndex - 1, ans, height);
    }
}