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. 利用异或的性质 ab;ab 异或运算表00=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;
}
};
