此前在leetcode按类别刷了一些题，不过时间久了就又忘记了，也没有稳固好自己的算法基础。恰好这学期有算法设计与分析课程，空余时间也比较多，打算好好的刷一些题并好好记录。刷题还是打算按类别刷，记录主要是备注题目情况，重点题也会记录些思路和理解。

双指针

1.盛最多水的容器

想得到是双指针，最开始想不清两个指针到底怎么移动。实际上移动时是按照排除当前柱子进行的，两个柱子里面短的柱子如果不变，就不可能有更大的结果了，所以要从短的一边移动，尝试扩大容积。 ## 2.最接近的三数之和

和三数之和是同一道题。一个数遍历，另外两个数用双指针。

*3.下一个排列

想不到怎样从当前排列转换到下一个排列。题解中的从后向前寻找第一个升序对是关键，找的是最后一个可以调整为更大的数字(先升序，此后均为降序)，再把这个数字换为其后大于该数中最小的，并对此后的数字重新排序，得到的就是下一个排列。 

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
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i,j,len,tmp;
        len = nums.size();
        if(len == 1) return;
        j = len-1, i = j-1;
        while(i>=0){
            if(nums[i]>=nums[j]){
                i--;
                j--;
            }
            else break;
        }
        if(i>=0){
            for(int k=len-1;k>=j;k--){
                if(nums[k]>nums[i]){
                    tmp = nums[k];
                    nums[k] = nums[i];
                    nums[i] = tmp;
                    break;
                }
            }
        }
        sort(nums.begin()+j,nums.end());
    }
};
## 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
25
26
27
28
29
30
31
32
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head||k==0) return head;
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode *p1,*p2,*p3;
        p1 = p2 = dummyhead;
        int len = 0;
        while(p1->next){
            p1 = p1->next;
            len++;
        }
        p1 = dummyhead;
        k = k%len;
        if(k == 0) return head;
        while(k){
            k--;
            if(p2->next!=NULL) p2 = p2->next; 
            else p2 = dummyhead->next;
        }     
        while(p2->next&&p1->next){
            p1 = p1->next;
            p2 = p2->next;
        }
        if(p1==dummyhead) return head;
        p3 = p1->next;
        p2->next = dummyhead->next;
        p1->next = NULL;
        return p3;
    }
};

5.颜色分类

直接写排序了。实际应该用双指针交换0和2。 ## 6.删除排序链表中的重复元素

重复的直接继续遍历到不重复就可以了。本题卡的问题是因为链表操作不熟练。 ## 7.分割版本号

字符串分隔不算难，不过要用双指针达到下面这个优秀题解的简洁优雅还是很值得学习： 

1
2
3
4
5
6
7
8
9
10
11
12
13
int compareVersion(string version1, string version2) {
    long long i = 0, j = 0, num1 = 0, num2 = 0;
    int len1 = version1.length(),len2 = version2.length();
    while(i<len1 || j<len2){
        num1 = 0, num2 = 0;
        while(i<len1 && version1[i]!='.') num1 = num1*10 + version1[i++] - '0';
        while(j<len2 && version2[j]!='.') num2 = num2*10 + version2[j++] - '0';
        if(num1>num2) return 1;
        else if(num1<num2) return -1;
        i++,j++;
    }
    return 0;
}
## 8.两数之和

双指针做的第一个题就是这个题，不知道为什么这里是两数之和II，而且还是中等题。 ## *9.环形链表

快慢指针经典题，最好还是多做几次，尤其是分三段abc，对距离和步数的推导。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow,*fast;
        slow = fast = head;
        while(fast!=NULL){
            if(fast->next == NULL) return NULL;
            fast = fast->next->next;
            slow = slow->next;
            if(slow == fast){
                fast = head;
                while(fast != slow){
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return NULL;
    }
};
## 10.重排链表

链表操作还是不熟练。

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
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    ListNode *reverseList(ListNode* head){
        if(head==nullptr || head->next==nullptr) return head;
        ListNode *prev = nullptr;   
        ListNode *cur = head;   
        while (cur != nullptr) {  
            ListNode* nextTemp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nextTemp;
        }
        return prev;
    }
    void reorderList(ListNode* head) {
        ListNode *slow,*fast,*p1,*p2,*reordered;
        reordered =head;
        if(head==nullptr||head->next==nullptr) return;
        slow = head, fast = head->next;
        while(fast->next&&fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = nullptr;
        fast = reverseList(fast);
        p1 = head->next;
        p2 = fast;
        bool flag = false;
        while(p1&&p2){
            if(flag){
                reordered->next = p1;
                p1 = p1->next;
            }
            else{
                reordered->next = p2;
                p2 = p2->next;
            }
            flag = !flag;
            reordered = reordered->next;
        }
        if(p1) reordered->next = p1;
        if(p2) reordered->next = p2;
        return;
    }
};

*11.排序链表

递归归并排序： 

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
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2){
        ListNode *dummyhead = new ListNode(0);
        ListNode *p1 = dummyhead;
        while(l1&&l2){
            if(l1->val<l2->val){
                p1->next = l1;
                l1 = l1->next;
            }
            else {
                p1->next = l2;
                l2 = l2->next;
            }
            p1 = p1->next;
        }
        p1->next = l1?l1:l2;
        return dummyhead->next;
    }
    ListNode* sortList(ListNode* head) {
        ListNode *slow,*fast;
        if(head==nullptr ||head->next==nullptr) return head;
        slow = head, fast = head->next;
        while(fast->next&&fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = nullptr;
        slow = sortList(head);
        fast = sortList(fast);
        head =  merge(slow,fast);
        return head;
    }
};

非递归的归并排序待完成。 ## 12.轮转数组

原地完成，每次移动i+k，自己的写法是循环移动，三次反转的想不到。

-13.寻找重复数

太抽象了，根本想不到是环形链表。

14.压缩字符串

没什么问题，就是把计数写进去的方式太笨了，还好计数是在2000内。不过笨办法的好处是比把数字写进去然后再反转要快。

*15.环形数组

有了13题，这里很快就能想出来是快慢指针遍历环形链表的思路了，但是不太明白没有符合条件的环(方向不一致和单循环的情况外)什么情况，不知道为什么单次遍历是按照方向是否相同为终止条件的。

16.供暖器

当成模拟去做了，没想到本质。

17.重拍链表

重排链表，再来一次！

递归

1.pow(x,n)

快速幂，注意负指数。

2.两数相加

**3.为运算表达式设计优先级

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
class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> res;
        vector<int> left,right;
        int len = expression.length();
        if(len<=2){
            if(len==2) res.push_back((expression[0]-'0')*10+(expression[1]-'0'));
            else res.push_back(expression[0]-'0');
            return res;
        }
        for(int i = 0;i<len;i++){
            if(expression[i]=='+'||expression[i]=='-'||expression[i]=='*'){
                left = diffWaysToCompute(expression.substr(0,i));
                right = diffWaysToCompute(expression.substr(i+1,len-i-1));
                for(int j=0;j<left.size();j++){
                    for(int k=0;k<right.size();k++){
                        if(expression[i]=='+') res.push_back(left[j]+right[k]);
                        else if(expression[i]=='-') res.push_back(left[j]-right[k]);
                        else res.push_back(left[j]*right[k]);
                    }
                }
            }
        }
        return res;
    }
};

*4.消除游戏

5.字符串解码

没有问题

6.第K个语法符号

这道题和上一题的出现一定是在挽救我消失的信心(然后明天的题继续锤我)。

7.找出第 N 个二进制字符串中的第 K 位

和字符串解码一样。

**8.找出最后的赢家

约瑟夫环，递归/链表模拟。对于下标的+1还没理解。

**9.二叉搜索树的后续遍历

重点是理解二叉搜索树后续遍历的结果序列的特点。另外本题的递归是从树的整体开始，左节点右节点递归检查。

前缀和与差分

动态规划

1.不同路径

*2.整数拆分

*3.不同的二叉搜索树

*4.0/1背包

二维dp数组的0/1背包如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solution(vector<int> &weight,vector<int> &value,int bag_weight){
    int n = weight.size();
    //dp表示到第i号物品，重量为j的最大价值
    int dp[n][bg_weight+1];				
    //dp初始化，当j>=weight[0]，dp[0][j]=value[0]
    memset(dp,0,sizeof(dp));
    for(int j=weight[0];j<=bag_weight;j++) dp[0][j]=value[0];
    //更新dp数组
    for(int i=1;i<n;i++){
        for(int j=0;j<=bag_weight;j++){
            if(j<weight[i]) dp[i][j]=dp[i-1][j];
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
        }
    }
    cout<<dp[n-1][bag_weight]<<endl;
    return;
}

二维背包中，第一维物品i要不是直接将上一层拷贝到当前层，要不就是根据上一层的情况更新当前层，这一维是可以去掉的，只要不停更新当前层就可以了。因此0/1背包可以使用一位数组解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solution(vector<int> &weight,vector<int> &value,int bag_weight){
    int n = weight.size();
    //dp表示重量为j的背包的最大价值
    int dp[bag_weight+1];
    //dp初始化
    memset(dp,0,sizeof(dp));
    //更新dp
    for(int i=0;i<n;i++){
        for(int j=bag_weight;j>=weight[i];j--){
            //反向遍历，防止一个物品多次放入背包
            dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
        }
    }
}

5.分割等和子集

6.最后一块石头的重量

和上题一样，难点在于能不能想到这个问题可以转化为背包问题，对于本题还有一个问题是怎么就等价于两堆石头碰撞，暂时还没能理解。

7.目标和

*8.1和0

总感觉滚动数组比多维数组更容易想到。到这道题基本上不用套01背包的模版，可以靠题意正常做出来了，只有内层循环反向遍历还是要注意。

*9.零钱兑换II

完全背包，计算方法数的典型例子。但是零钱兑换是一个组合问题，即1和5，5和1是同一个组合，因此要采用先遍历面值的方式，因为这样在面额为1的遍历中计算dp[6]时，还没有dp[5]中还没有包含一张5的情况。而对于排列问题，就需要采用先遍历容量，内层遍历价值的方式，这样计算dp[6]时，dp[5]里面已经有一张5的情况了，因此1和5，5和1各算作了一种情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n=coins.size();
        int dp[amount+1];            //dp[i]表示总金额i可以有多少种凑成方法
        memset(dp,0,sizeof(dp));     //初始化，dp[0]=1;
        dp[0]=1;
        for(int i=0;i<n;i++){
            for(int j=coins[i];j<=amount;j++) dp[j]+=dp[j-coins[i]];
        }
        return dp[amount];
    }
};

10.组合总和IV

上一题的组合情况。

11.零钱兑换

求最少的情况是不需要考虑遍历顺序的，因为总会取最小值。

12.完全平方和

同上。

13.字符串拆分

这题和前面几题不一样，物品变成字符串了，内部的遍历处理不一样，需要注意。

贪心

1.最小花费-彩色绳子