Posted on | Edited on | In , |

题目

https://leetcode.com/problems/search-a-2d-matrix-ii/description/

想法

对角线延伸？

最直觉的是，扫一行，找到特定行再扫列
不，并不对

对角线！

二分查找：
0, 1, 2, 3, 4, 5

看别人解答吧，感觉思路不够明确

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target) {
        if (matrix.size() == 0)
            return false;
        int m = matrix.size();
        int n = matrix[0].size();
        
        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target)
                return true;
            if (matrix[i][j] > target)
                j--;
            else
                i++;
        }
        return false;
    }
};

回顾

这算是一个经典的trick吧

还是自己没能发现其中的性质
把向两边扩展转化为只向一边扩展，这真的很关键！！！

记住它吧！

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/complex-number-multiplication/description/

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string complexNumberMultiply(string a, string b) {
        auto i = a.find('+');
        int aa = stoi(a.substr(0, i + 1));
        int ab = stoi(a.substr(i + 1, a.length() - 1));
        auto j = b.find('+');
        int ba = stoi(b.substr(0, j + 1));
        int bb = stoi(b.substr(j + 1, b.length() - 1));
        
        int ca = aa * ba - ab * bb;
        int cb = aa * bb + ab * ba;
        
        return (to_string(ca) + '+' + to_string(cb) + 'i');
    }
};

用stringstream写起来更简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string complexNumberMultiply(string a, string b) {
        std::stringstream a_in(a), b_in(b);
        int aa, ab, ba, bb;
        char tmp;
        a_in >> aa >> tmp >> ab >> tmp;
        b_in >> ba >> tmp >> bb >> tmp;
        std::stringstream ans;
        ans << aa * ba - ab * bb << '+' << aa * bb + ab * ba << 'i';
        return ans.str();
        // return to_string(aa * ba - ab * bb) + '+' + to_string(aa * bb + ab * ba) + 'i';
    }
};

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/4sum/description/

想法

跟昨天的那个combination sum应该差不多，回溯就可以了

唔 试了半天并不可以
有错误的代码：

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
class Solution {
public:
    vector<vector<int>> ans;
    void sumIt(vector<int> &curr, vector<int> &nums, int idx, int k, int target) {
        if (k == 0 || idx == nums.size())
            return;
        if (nums[idx] == target && k == 1) {
            curr.push_back(nums[idx]);
            ans.push_back(curr);
            curr.pop_back();
        } else if (nums[idx] < target) {
            if (k > 1) {
                curr.push_back(nums[idx]);
                sumIt(curr, nums, idx + 1, k - 1, target - nums[idx]);
                curr.pop_back();
            } else {
                sumIt(curr, nums, idx + 1, k, target);
            }
        }
//        curr.pop_back();
    }
    vector<vector<int>> fourSum(vector<int> &nums, int target) {
        std::sort(nums.begin(), nums.end());
        vector<int> curr;
        sumIt(curr, nums, 0, 4, target);
        return ans;
    }
};

答案

看了其他人的答案，发现没有用这种方式的，想必会超时吧

待研究…

这里并没有限制数的范围，如果用回溯的话，需要遍历剩余的的所有的数，那么将是O(n^2)的复杂度，不现实

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/maximum-width-of-binary-tree/description/

想法

初看应该还是比较简单的吧，记录下头在哪，尾在哪应该就可以了吧

啊，没那么简单！！！
不能简单的一直向边上走
看来很遍历一下来设置了

答案

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> l, r;
    void travel(int level, int index, TreeNode* root) {
        if (!root)
            return;
        if (l.size() == level) {
            l.push_back(index);
            r.push_back(index);
        } else {
            if (index > r[level]) {
                r[level] = index;
            }
        }
        travel(level + 1, 2 * index - 1, root->left);
        travel(level + 1, 2 * index, root->right);
    }
    int widthOfBinaryTree(TreeNode* root) {
        
        if (!root)
            return 0;
        travel(0, 1, root);
        
        int max = 0;
        for (int i = 0; i < l.size(); i++) {
            if (r[i] - l[i] + 1 > max)
                max = r[i] - l[i] + 1;
        }
        return max;
    }
};

回顾

一开始想的有点简单了，不过后来也只是需要稍微改变下思路

LeetCode相比于CodeWars可能整体难度的确有点小，可能自己也进步了，好多medium的题目原来做起来很费劲，现在比较轻松了，great！

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/swap-nodes-in-pairs/description/

想法

比较简单，虽然没啥意思，但还是做一下

考虑头的变化，以及尾就没有问题了

答案

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *p = head;
        if (p == NULL || p->next == NULL)
            return p;
        p = head;
        ListNode *q = head->next->next;
        head = head->next;
        head->next = p;
        p->next = q;
        while(q != NULL && q->next != NULL) {
            p->next = q->next;
            ListNode *tmp = q->next->next;
            q->next = tmp;
            p = p->next->next;
            q = q->next;
        }
        return head;
    }
};

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/combination-sum-iii/description/

想法

首先是unique的，其次所有的数的数量是定死的

遍历应该是不行的，那样，简单的递归应该也不可以，

用DP也不现实，会算好多没用的

这样想，先分配：
1, 2, …, k
然后减去之后剩下的，问题变成了剩下的里边选几个再加
不好操作

先分配：1, 1, 1, …, 1
然后变成剩下的用0-8来分
没有区别。。。

答案

没有想出来，其它人的想法：

backtracking!!!这应该是一个比较经典的backtracking的题目，只是自己不是很会backtracking罢了，趁机学习一下

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<vector<int>> ans;
    void combination(vector<int> &vec, int current_sum, int start, int k, int n) {
        if (k == 0)
            return;
        for (int i = start; i <= 9; i++) {
            if (current_sum + i == n && k == 1) {
                vec.push_back(i);
                ans.push_back(vec);
                vec.pop_back();
                return;
            } else if (current_sum + i < n) {
                vec.push_back(i);
                combination(vec, current_sum + i, i + 1, k - 1, n);
                vec.pop_back();
            } else {
                return;
            }
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> vec;
        combination(vec, 0, 1, k, n);
        return ans;
    }
};

回顾

其实自己一开始是这样想的，但是觉得这种递归是很低效的。但其实还是没有理解回溯的思想，没有条件反射地想到。

回溯核心在于维护一个序列，当不满足条件时便退回，这个序列保证了不会做多余的工作，不像简单的递归一样！

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/sliding-window-maximum/description/

想法

初看觉得，直接扫一遍就好了，但是细想想，最大值是不断更新的，要各个状态下的最大值。

记录下最大的两个值看怎么样，不行，还是会更新

要不还是用DP试试，也不知道从何下手啊～

或许可以这样 先算出 1～k的最大值，再求2～k的是大值，再求2～k+1的最大值，再3～k+1最大值！
但是同样没有考虑重复，比如：5，3，3，2，2 (k = 3)

额，没有思路，如果完全用DP做，算出各段的最大值，真的好傻啊
算了，先这样做吧

放弃，看答案吧 这应该是一个很经典的问题，就算是记也要住

原理

Monotonic Queue
https://abitofcs.blogspot.com/2014/11/data-structure-sliding-window-minimum.html

答案

参考他人的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ans;
        
        for (int i = 0; i < nums.size(); i++) {
            if (!dq.empty() && dq.front() == i - k)
                dq.pop_front();
            while(!dq.empty() && nums[i] > nums[dq.back()])
                dq.pop_back();
            dq.push_back(i);
            if (i >= k - 1)
                ans.push_back(nums[dq.front()]);
        }
        return ans;
    }
};

回顾

很经典的题目了

deque运用，用deque存索引是我没有想到的，这是一个值得学习的地方

还是注意分析表象背后的条件，一个个的往过移，那个一个较大的值出现，前边较小的就不再会成为最大值了，如代码中的：

1
2
while(!dq.empty() && nums[i] > nums[dq.back()])
    dp.pop_back();

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/find-all-duplicates-in-an-array/description/

想法

no extra space…

注意到 $ 1 <= a[i] <= n$

用下标对应的关系应该就可以了吧

答案

第一个AC的答案
噗，0.61% hhh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != i+1 && nums[nums[i] - 1] != nums[i]) {
                swap(nums[i], nums[nums[i] - 1]);
                i--;                
            }
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == i+1)
                nums[i] = 0;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 0) {
                nums.erase(nums.begin() + i);
                i--;                
            }
        }
        return nums;
    }
};

尽管是O(n)，但是应该是做了好多无用的事

回顾

唔，看了别人的答案，只是觉得，想法基本上是一样的，只是without extra space，自己也没有新开一个vector来存结果

有一些粗心，注意下标的一些获取！

Posted on | Edited on | In |

C++ 测试框架Catch使用

今天第一次接触并使用C++测试框架，也是有需求的，是因为自己跟着lept_json教程来写json的parser，顺便可以学一下测试框架的使用。

Google Test还是没有配好，可能之后等熟悉测试框架了之后再说。这次使用的是Catch。

引入方式

https://github.com/philsquared/Catch
https://github.com/philsquared/Catch/blob/master/docs/tutorial.md
GitHub上的Repo已经说得比较清楚了

  1. 下载catch.hpp 就一个单的头文件
  2. 放到想要放的地方
  3. 按正常的头文件引入就可以了，在CMake里写相应的东西

但为了测试与原有的项目分离，还是需要有所规划，因为这个json parser的项目很简单，没有分得很清晰严格。

工程示例

工程结构

  • my_lept_json
    • lib
      • catch.cpp
    • CMakeLists.txt
    • lept_json.h
    • lept_json.cpp
    • test.cpp

CMake配置：CMakeLists.txt

1
2
3
4
5
6
7
8
9
10
cmake_minimum_required(VERSION 3.8)
project(my_lept_json)
set(CMAKE_CXX_STANDARD 11)
set(CATCH_TEST_HEADER lib/catch.hpp)
set(SOURCE_FILES lept_json.h lept_json.cpp)
set(TEST_FILES test.cpp)
add_executable(my_lept_json ${SOURCE_FILES} ${CATCH_TEST_HEADER} ${TEST_FILES})
target_link_libraries(my_lept_json)

测试文件示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//
// Created by Zhao Xiaodong on 2017/8/28.
//
#define CATCH_CONFIG_MAIN
#include "lib/catch.hpp"
#include "lept_json.h"
void test(const char *json, leptType originType, leptType expectedType, leptParseResponse response) {
    LeptValue value;
    value.type = originType;
    REQUIRE(leptParse(&value, json) == response);
    REQUIRE(getType(&value) == expectedType);
}
TEST_CASE("Parse null") {
    test("null", LEPT_TRUE, LEPT_NULL, LEPT_PARSE_OK);
}
TEST_CASE("Parse true") {
    test("true", LEPT_NULL, LEPT_TRUE, LEPT_PARSE_OK);
}