8000 Add comments to explain the solutions · lyx030405/leetcode@e2be44a · GitHub
[go: up one dir, main page]
Skip to content

Commit e2be44a

Browse files
haoelhaoel
committed
Add comments to explain the solutions
1 parent 041aaf1 commit e2be44a

File tree

6 files changed

+81
-6
lines changed
  • linkedListCycle
  • swapNodesInPairs
  • twoSum

    • 6 files changed

    +81
    -6
    lines changed

    ‎src/3Sum/3Sum.cpp‎

    Lines changed: 16 additions & 1 deletion
    10BC0
    Original file line numberDiff line numberDiff line change
    @@ -29,11 +29,26 @@
    2929
    using namespace std;
    3030

    3131

    32-
    //solution: http://en.wikipedia.org/wiki/3SUM
    32+
    /*
    33+
    * Simlar like "Two Number" problem, we can have the simlar solution.
    34+
    *
    35+
    * Suppose the input array is S[0..n-1], 3SUM can be solved in O(n^2) time on average by
    36+
    * inserting each number S[i] into a hash table, and then for each index i and j,
    37+
    * checking whether the hash table contains the integer - (s[i]+s[j])
    38+
    *
    39+
    * Alternatively, the algorithm below first sorts the input array and then tests all
    40+
    * possible pairs in a careful order that avoids the need to binary search for the pairs
    41+
    * in the sorted list, achieving worst-case O(n^n)
    42+
    *
    43+
    * Solution: Quadratic algorithm
    44+
    * http://en.wikipedia.org/wiki/3SUM
    45+
    *
    46+
    */
    3347
    vector<vector<int> > threeSum(vector<int> &num) {
    3448

    3549
    vector< vector<int> > result;
    3650

    51+
    //sort the array, this is the key
    3752
    sort(num.begin(), num.end());
    3853

    3954
    int n = num.size();

    ‎src/4Sum/4Sum.cpp‎

    Lines changed: 6 additions & 1 deletion
    Original file line numberDiff line numberDiff line change
    @@ -29,6 +29,11 @@ using namespace std;
    2929

    3030
    vector<vector<int> > threeSum(vector<int> num, int target);
    3131

    32+
    /*
    33+
    * 1) Sort the array,
    34+
    * 2) traverse the array, and solve the problem by using "3Sum" soultion.
    35+
    */
    36+
    3237
    vector<vector<int> > fourSum(vector<int> &num, int target) {
    3338
    vector< vector<int> > result;
    3439
    if (num.size()<4) return result;
    @@ -51,7 +56,7 @@ vector<vector<int> > fourSum(vector<int> &num, int target) {
    5156
    vector<vector<int> > threeSum(vector<int> num, int target) {
    5257

    5358
    vector< vector<int> > result;
    54-
    59+
    //sort the array (if the qrray is sorted already, it won't waste any time)
    5560
    sort(num.begin(), num.end());
    5661

    5762
    int n = num.size();

    ‎src/linkedListCycle/linkedListCycle.II.cpp‎

    Lines changed: 6 additions & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -46,6 +46,12 @@ class Solution {
    4646

    4747
    }
    4848

    49+
    /*
    50+
    * So, the idea is:
    51+
    * 1) Using the cycle-chcking algorithm.
    52+
    * 2) Once p1 and p1 meet, then reset p1 to head, and move p1 & p2 synchronously
    53+
    * until p1 and p2 meet again, that place is the cycle's start-point
    54+
    */
    4955
    ListNode *detectCycle(ListNode *head) {
    5056

    5157
    if (hasCycle(head)==false){

    ‎src/linkedListCycle/linkedListCycle.cpp‎

    Lines changed: 7 additions & 0 deletions
    Original file line numberDiff line numberDiff line change
    @@ -12,6 +12,13 @@
    1212
    *
    1313
    **********************************************************************************/
    1414

    15+
    /*
    16+
    * if there is a cycle in the list, then we can use two pointers travers the list.
    17+
    *
    18+
    * one pointer traverse one step each time, another one traverse two steps each time.
    19+
    *
    20+
    * so, those two pointers meet together, that means there must be a cycle inside the list.
    21+
    */
    1522

    1623
    bool hasCycle(ListNode *head) {
    1724
    ListNode* p1;

    ‎src/swapNodesInPairs/swapNodesInPairs.cpp‎

    Lines changed: 11 additions & 1 deletion
    Original file line numberDiff line numberDiff line change
    @@ -28,12 +28,18 @@ class Solution {
    2828
    Solution(){
    2929
    srand(time(NULL));
    3030
    }
    31+
    /*
    32+
    * Here we have two ways to solve this problem:
    33+
    * 1) keep the list's nodes no change. only swap the data in the list node.
    34+
    * 2) swap the list node physically.
    35+
    */
    3136
    ListNode *swapPairs(ListNode *head) {
    3237
    if(random()%2){
    3338
    return swapPairs1(head);
    3439
    }
    3540
    return swapPairs2(head);
    3641
    }
    42+
    /*just swap the node's value instead of node*/
    3743
    ListNode *swapPairs1(ListNode *head) {
    3844
    for (ListNode *p = head; p && p->next; p = p->next->next) {
    3945
    int n = p->val;
    @@ -42,18 +48,22 @@ class Solution {
    4248
    }
    4349
    return head;
    4450
    }
    45-
    51+
    /*swap the list nodes physically*/
    4652
    ListNode *swapPairs2(ListNode *head) {
    4753
    ListNode *h = NULL;
    54+
    //using `*p` to traverse the linked list
    4855
    for (ListNode *p = head; p && p->next; p = p->next) {
    56+
    //`n` is `p`'s next node, and swap `p` and `n` physcially
    4957
    ListNode *n = p->next;
    5058
    p->next = n->next;
    5159
    n->next = p;
    60+
    //using `h` as `p`'s previous node
    5261
    if (h){
    5362
    h->next = n;
    5463
    }
    5564
    h=p;
    5665

    66+
    //determin the really 'head' pointer
    5767
    if (head == p){
    5868
    head = n;
    5969
    }

    ‎src/twoSum/twoSum.cpp‎

    Lines changed: 35 additions & 3 deletions
    Original file line numberDiff line numberDiff line change
    @@ -20,13 +20,45 @@
    2020

    2121
    class Solution {
    2222
    public:
    23+
    /*
    24+
    * The easy solution is O(n^2) run-time complexity.
    25+
    * ```
    26+
    * foreach(item1 in array) {
    27+
    * foreach(item2 in array){
    28+
    * if (item1 + item2 == target) {
    29+
    * return result
    30+
    * }
    31+
    * }
    32+
    * ```
    33+
    *
    34+
    * We can see the nested loop just for searching,
    35+
    * So, we can use a hashmap to reduce the searching time complexity from O(n) to O(1)
    36+
    * (the map's `key` is the number, the `value` is the position)
    37+
    *
    38+
    * But be careful, if there are duplication numbers in array,
    39+
    * how the map store the positions for all of same numbers?
    40+
    *
    41+
    */
    42+
    43+
    44+
    //
    45+
    // The implementation as below is bit tricky. but not difficult to understand
    46+
    //
    47+
    // 1) Traverse the array one by one
    48+
    // 2) just put the `target - num[i]`(not `num[i]`) into the map
    49+
    // so, when we checking the next num[i], if we found it is exisited in the map.
    50+
    // which means we found the second one.
    51+
    //
    2352
    vector<int> twoSum(vector<int> &numbers, int target) {
    2453
    map<int, int> m;
    2554
    vector<int> result;
    2655
    for(int i=0; i<numbers.size(); i++){
    27-
    if (m.find(numbers[i])==m.end() ) { // not found
    28-
    m[target - numbers[i]] = i;
    29-
    }else { // found
    56+
    // not found the second one
    57+
    if (m.find(numbers[i])==m.end() ) {
    58+
    // store the first one poisition into the second one's key
    59+
    m[target - numbers[i]] = i;
    60+
    }else {
    61+
    // found the second one
    3062
    result.push_back(m[numbers[i]]+1);
    3163
    result.push_back(i+1);
    3264
    break;

    0 commit comments

    Comments
     (0)
    0