LeetCode 题集感想

Q1.Two Sum

题目：给定一个数组{2,3,5,7}，以及一个目标值target，要求找出两个能使为target的集合元素的下标，并按下标小的在前排序出来。

思路：

方法1. 使用二重循环扫描数组，找到i 和 j的和为target，再找出输出下标

超时

方法2. 使用一个map（用Java的HashMap），按<数组元素，下标>存入map，然后对每个数组元素遍历，纪录下target减去数组元素的值leftNum，直接在这个map里面找到key为leftNum的，取出value，就是它的序号。这样数组的index和这个value就是两个下标值，比较大小，输出

通过

官方方法:

O(n2) runtime, O(1) space – Brute force:

The brute force approach is simple. Loop through each element x and find if there is another value that equals to target – x. As finding another value requires looping through the rest of array, its runtime complexity is O(n2).

O(n) runtime, O(n) space – Hash table:

We could reduce the runtime complexity of looking up a value to O(1) using a hash map that maps a value to its index.

Q56.Merge Intervals

题目：给定一系列区间，如[1,3],[2,4],[5,6]，让你讲所有区间的重叠区间合并并输出，如前者输出[1,4],[5,6]

思路：

方法1. 先对这个区间的左值进行排序，由小到大，形成新的区间集合，然后分情况讨论（三种）：1.如果前一个区间右值比后一个区间左值小，则直接存入结果数组。2.else1的情况下，而且前一个区间的右值比后一个区间的右值小，合并，只保留前一个区间的左值和后一个区间的右值。3.else2的情况下，前一个区间的右值比后一个区间的右值大，保留大的。最后别忘了把最后一组区间也加入到结果数组（没有向后比较了）

通过

Q2.Add Two Numbers

方法1.

Q3.

Q4.

Q62.Unique Paths

给定一个m*n的方块路径，从左上角起点起，到右下角终点，只允许向右或者向下移动，问有多少种走法。

方法1. 看清本质，这个题实际上可以看作一个组合数求值。总共可以向右移动m-1种方法，向下移动n-1种方法。由于只允许向右向下一种，而且一定最后和起来是要走完最长的那一条（举个例子，m>n，则最后一定把所有m-1个向右走的方法都会用一遍），所以，当m>n，就是求C(m-1+n-1)(m-1);n>=m就是球C(m-1+n-1)(n-1)

通过

136.Single Numble

一个数组，除了一个元素外，其它元素都重复2遍，找出那个元素

方法1. 利用异或的性质 a^b;ab 异或运算表0^0=0;01=1;所以直接可以用0来异或一次得到真实值，异或两次结果不变，所以直接对数组每个元素和初始为0的result异或即可。

141.Linked List Cycle

判断一个链表是否存在环

方法1. 利用一个"快慢指针"，即有两个指针指向头节点，一个快指针每次next两次，一个每次next一次，使用while循环，只要存在一个环，必然经过一轮的循环下，一定会相遇。反之，不存在环，一定不会相遇。时间复杂度为O(n)

通过

208.Implement Trie (Prefix Tree)

实现一个字典树

字典树：一个26叉树，每个结点代表一个字母，value存一个bool值，代表是否存在这个字母。如果对一个单词进行查找，那么它只需要O(n)的时间，插入的时候也是O(n)。

方法1. 直接贴代码吧:

class TrieNode {
public:
    // Initialize your data structure here.
    TrieNode() {
        for (int i = 0;i < MAX_NODE;i++) {
            next[i] = 0;
        }
        haveValue = false;
    }
    static const int MAX_NODE = 26;
    TrieNode* next[MAX_NODE];
    bool haveValue;//true repreasent have this character
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    void insert(string s) {
        TrieNode* start = root;
        for (int i = 0;i < s.length();i++) {
            int index = s[i] - 'a';
            if (start->next[index] == 0){
                start->next[index] = new TrieNode();//new character at this node.and go on for next character
            }
            start = start->next[index];
        }
        start->haveValue = true;
    }

    // Returns if the word is in the trie.
    bool search(string key) {
        TrieNode* start = root;
        for (int i = 0;i < key.length();i++) {
            int index = key[i] - 'a';//start with character
            if (start->next[index] == 0){
                return false;
            }
            start = start->next[index];
        }
        return start && start->haveValue;//entire word
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode* start = root;
        for (int i = 0;i < prefix.length();i++) {
            int index = prefix[i] - 'a';
            if (start->next[index] == 0){
                return false;
            }
            start = start->next[index];
        }
        return start;//don't need complete all the character
    }

private:
    TrieNode* root;
};

// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");

通过

206. Reverse Linked List

就是简单的反转链表，要求有迭代和递归两种解法

1.迭代法

#include <iostream>
using namespace std;


struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL){return NULL;}
        ListNode* prev = head;
        ListNode* current = head->next;
        ListNode* next;
        while (current) {
            next = current->next;
            current->next = prev;
            prev = current;
            current = next;
        }
        head->next = NULL;
        head = prev;
        return head;
    }
};

2.递归法

#include <iostream>
using namespace std;


struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL){
            return NULL;//fuck
        }
        if(head->next == NULL){
            return head;//stop
        }
        ListNode* next = head->next;//head will stay here
        ListNode* start = reverseList(next);
        head->next = NULL;
        next->next = head;
        return start;
    }
};