Category: 不学无术

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 andnums2 are m and n respectively.
代码：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for(int i=0; i<n; i++) {
            // /!\ Mind that m might be less than the actual size of nums1
            if(nums1.size() < m + i + 1)
                nums1.push_back(-1);
        }
        int pos_1 = m-1;
        int pos_2 = n-1;
        int end = m + n - 1;
        while(pos_1 >= 0 && pos_2 >= 0) {
            if(nums1[pos_1] > nums2[pos_2]) {
                nums1[end] = nums1[pos_1];
                pos_1--;
            } else {
                nums1[end] = nums2[pos_2];
                pos_2--;
            }
            end--;
        }
        while(pos_2 >= 0){
            nums1[end--] = nums2[pos_2--];
        }
    }
};

题目: https://leetcode.com/problems/climbing-stairs/
思路：
递归递归，但是跟斐波那契数那个一样，要保存一些中间算出来的结果备用，不然会超时！
代码：

class Solution {
public:
    map<int, int> resultMap;
    int climbStairs(int n) {
        if(n == 2){
            // 2 or 1+1, two ways
            return 2;
        } else if(n == 1) {
            return 1;
        } else if (n == 0) {
            return 0;
        } else {
            int c_n1, c_n2;
            if(resultMap.count(n-1) > 0)
                c_n1 = resultMap[n-1];
            else {
                c_n1 = climbStairs(n-1);
                resultMap[n-1] = c_n1;
            }
            if(resultMap.count(n-2) > 0)
                c_n2 = resultMap[n-2];
            else {
                c_n2 = climbStairs(n-2);
                resultMap[n-2] = c_n2;
            }
            return c_n1 + c_n2;
        }
    }
};

题目：https://leetcode.com/problems/kth-largest-element-in-an-array/
思路：
找第k大的元素，最简单的方法就是排个序，然后找一下（中位数其实也类似），时间复杂度是O(nlogn)
另一种方案是，参考快速排序的方法找个pivot，然后分三种情况：

• pivot的位置刚好就是第k大的，那么大功告成；
• pivot的位置在k前头，那么就得找pivot后面一堆了；
• pivot的位置在k后头，那么得找pivot前面的一堆；

代码：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return findKthLargest1(nums, 0, nums.size()-1, k);
    }
    int findKthLargest1(vector<int>& nums, int start, int end, int k) {
        int small = start;
        int large = end;
        int pivot = nums[large];
        while(true){
            while(nums[small] > pivot && small < large)
                small ++;
            while(nums[large] <=pivot && small < large)
                large --;
            if(small == large)
                break;
            swap(nums, small, large);
        }
        swap(nums, small, end);
        if(small == k - 1){
            return pivot;
        } else if (small > k - 1) {
            return findKthLargest1(nums, start, small - 1, k);
        } else {
            return findKthLargest1(nums, small + 1, end, k);
        }
    }
    void swap(vector<int>& nums, int small, int large) {
        int temp = nums[small];
        nums[small] = nums[large];
        nums[large] = temp;
    }
};

题目：https://leetcode.com/problems/implement-trie-prefix-tree/
思路：
前缀树的概念，参考这里。谷歌搜到的，其实有一大把~
判断是否有这么个“儿子”的时候，增加了一个hasEnd布尔值，如果有以这个点为结束的字符则设置成true.
限制：为了实现方便，现在只能存储a-z共26个字符，如果再扩展可以考虑用map来存字符对应的孩子指针。
单词的字符数量为M，插入节点的时间复杂度是O(M)
startWith(..)和search(..)一大半部分可以合并
代码：

class TrieNode {
public:
	bool hasEnd;
	TrieNode** children;
	// Initialize your data structure here.
	TrieNode() {
		children = NULL;
		hasEnd = false;
	}
	bool hasChild(char c) {
		if (NULL == children)
			return false;
		return !(NULL == children[c - 'a']);
	}
	TrieNode* addChild(char c) {
		if (NULL == children) {
			children = new TrieNode*[26];
			for (int i = 0; i<26; i++)
				children[i] = NULL;
		}
		int pos = c - 'a';
		children[pos] = new TrieNode;
		return children[pos];
	}
};
class Trie {
public:
	Trie() {
		root = new TrieNode();
	}
	// Inserts a word into the trie.
	void insert(string word) {
		int wordSz = word.size();
		char c;
		TrieNode *currNode = root;
		for (int i = 0; i<wordSz; i++) {
			c = word[i];
			if (currNode->hasChild(c))
				currNode = currNode->children[c - 'a'];
			else {
				currNode = currNode->addChild(c);
			}
			if (i == wordSz - 1)
				currNode->hasEnd = true;
		}
	}
	// Returns if the word is in the trie.
	bool search(string word) {
		int wordSz = word.size();
		char c;
		TrieNode *currNode = root;
		for (int i = 0; i<wordSz; i++) {
			c = word[i];
			if (currNode->hasChild(c))
				currNode = currNode->children[c - 'a'];
			else
				return false;
		}
		return currNode->hasEnd;
	}
	// Returns if there is any word in the trie
	// that starts with the given prefix.
	bool startsWith(string prefix) {
		int wordSz = prefix.size();
		char c;
		TrieNode *currNode = root;
		for (int i = 0; i<wordSz; i++) {
			c = prefix[i];
			if (currNode->hasChild(c))
				currNode = currNode->children[c - 'a'];
			else
				return false;
		}
		return true;
	}
private:
	TrieNode* root;
};
// Your Trie object will be instantiated and called as such:
// Trie trie;
// trie.insert("somestring");
// trie.search("key");

题目：https://leetcode.com/problems/search-for-a-range/
思路：看LogN级别时间复杂度的要求就应该可以想到要用二分查找类似的做，关键问题是有重复元素，就是说如果找到了a[i]==target，还得顾及一下他的左右邻居的值是不是也一样的，如果是的话，那说明还得继续找
代码：

class Solution {
public:
    int searchMin(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        int m;
        while (l <= r) {
            m = (l + r)/2;
            if(nums[m] == target){
                if(m == 0)
                    return m;
                else if(nums[m-1] < target) //targst cannot be in the left part
                    return m;
                else {
                    r = m - 1;
                }
            } else if(nums[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }
    int searchMax(vector<int>& nums, int target) {
        int l=0;
        int r = nums.size() - 1;
        int m;
        while(l <= r) {
            m = (l + r)/2;
            if(nums[m] == target){
                if (m == r)
                    return m;
                else if(nums[m+1] > target)
                    return m;
                else
                    l = m + 1;
            } else if (nums[m] < target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return -1;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> result;
        result.push_back(searchMin(nums, target));
        result.push_back(searchMax(nums, target));
        return result;
    }
};

题目：https://leetcode.com/problems/search-in-rotated-sorted-array/
思路：
有序数列里头找元素，第一想到的肯定是二分法，但是现在数组的一部分被旋转过了，这怎么改进呢？假定输入是[4 5 6 7 0 1 2]，如果仍用二分法，那么第一次搜索时，左中右的元素分别是a[left] = 4; a[mid]=7; a[right]=2
从题设可以知道，问题的关键是，被拆分的两个部分里，肯定是一半有序一半无序的(因为旋转点，即a[i+1] > a[i]的i点)肯定只能在两部分的其一里头，而对于有序的那一半，我们可以通过首末元素判断target是否在其中，于是有了下面的规则：

• 观察被二分出来的左半段（当然右半段也可以），根据a[left],a[mid]的值判断这半段是否有序
  • 如果有序，根据头尾元素判断target是否在里头，如果在，那就搜索左半端，否则只能在无序的右半段里找了
  • 如果无序，那右半段肯定是有序的，去判断target是否在右半段里头：如果在，则搜索右半段，否则还是老老实实把左半端再二分了找吧..

想比普通的二分，这个方法多了几个判断的步骤，但整体的时间复杂度还是O(logN)
代码：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int mid;
        while(left <= right){
            mid = (left + right) / 2;
            if(target == nums[mid])
                return mid;
            if(nums[left] <= nums[mid]){
                //The left part is in order, check if target is inside
                if(nums[left] <= target && nums[mid] >= target){
                    //Yep, move to the left part
                    right = mid - 1;
                } else {
                    //Nope, move to the right part
                    left = mid + 1;
                }
            } else {
                //The left part is not in order, but the right one should be, check if target is in the right wing
                if(nums[mid] <= target && nums[right] >= target){
                    //Yep, move to the right wing
                    left = mid + 1;
                } else {
                    //Nope, try in the left wing
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};

题目：https://leetcode.com/problems/swap-nodes-in-pairs/
思路：
真是个让人头晕的问题，头晕的地方在于指针，不过记住指针其实就是个地址就行了。题目的意思是奇数项和偶数项交换，先假设输入数组就是偶数个数字的，那其实就是a[i]与a[i+1]为一对一对的交换，但是由于是单链表而且不允许做值交换，只能通过改变next指针实现了。
我们假设有这么个数组/地址：

value   [1,   2,   3,   4,   5,   6]
address [0x1, 0x2, 0x3, 0x4, 0x5, 0x6]

很显然的，如果两个数的值进行交换，我们就需要找个临时变量存着，这里也是一样。本题的主要思路就是，不能乱，一对一对的来…
只看中间的3,4两项为一对，且假设其他一切都安排妥当了[2, 1, (当前对), 5, 6]，那么变换后的结果是 [3]->next = [5], [4]->next = [3]并且[1]->next = [4]. 然后具体而言分下面几步：

1. 当前工作指针curr是[3],记住[3]的后续节点[4]的位置，即temp = 0x4;
2. 把[3]和[5]连上，即 [3]->next = temp->next = 0x5;
3. 把[4]放到[3]前面，即temp->next = [3] (0x3);
4. 把[2]和[4]连上，即[2]->next = temp; 所以整个环节中还需要存一个[3]的前序节点的指针(这里是0x2);
5. 挪动指针，注意的是只要往后next一下就行了，因为目前的排序已经是[2,1, 4,3, …]了：curr = curr->next (0x5);

搞定主要部分后要注意特殊情况：0输入，1输入，奇数项输入（最后一项不处理就行）
代码:

/**
 * 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) {
        if(head == NULL)
            return head;
        if(head->next == NULL)
            return head;
        ListNode* curr = head;
        ListNode* prev = NULL;
        head = head->next;
        ListNode* temp;
        while(curr != NULL && curr->next != NULL){
            temp = curr->next;
            if(prev != NULL) {
                prev->next = temp;
            }
            curr->next = temp->next;
            temp->next = curr;
            prev = curr;
            //Change of current node
            curr = curr->next;
        }
        return head;
    }
};

题目：https://leetcode.com/problems/merge-two-sorted-lists/
代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *currNode1 = l1;
        ListNode *currNode2 = l2;
        ListNode *retRoot = new ListNode(-1);
        ListNode *prev = retRoot;
        ListNode *curr;
        while(currNode1 != NULL || currNode2 != NULL){
            if(currNode1 != NULL && currNode2 != NULL) {
                if(currNoåde1->val <= currNode2->val) {
                    curr = new ListNode(currNode1->val);
                    currNode1 = currNode1->next;
                } else {
                    curr = new ListNode(currNode2->val);
                    currNode2 = currNode2->next;
                }
                prev->next = curr;
                prev = prev->next;
            } else if (currNode2 == NULL) {
                prev->next = currNode1;
                break;
            } else {
                prev->next = currNode2;
                break;
            }
        }
        return retRoot->next;
    }
};

题目：https://leetcode.com/problems/generate-parentheses/
思路：
主要问题是，什么时候可以加左括号，什么时候可以加右括号。这需要判断当前已有字串的左右括号个数，有以下三种情况：

1. 如果当前左括号的数目等于(也可以说小等于，不过小于的情况是出错了)右括号了，比如()，那只能加左括号；
2. 如果当前左括号数目大于右括号，比如((()，那么
   1. 如果还有剩左括号的配额，可以加左括号（新分支了）；
   2. 否则只能加右括号（在原有答案上操作即可）；

代码：

class Solution {
public:
	vector<string> generateParenthesis(int n) {
		vector<string> results;
		vector<pair<int, int>> parSize;
		// If size('(') <= size(')'), we can only append '(';
		// Else, append '(' or ')' if it doesn't reach the quota
		int count = 1;
		results.push_back(string("("));
		parSize.push_back(pair<int, int>(1, 0));
		int resultSz;
		while (count < n * 2) {
			resultSz = results.size();
			int lsize, rsize;
			for (int i = 0; i<resultSz; i++) {
				lsize = parSize[i].first;
				rsize = parSize[i].second;
				if (lsize <= rsize) {
					results[i] += "(";
					parSize[i].first++;
				}
				else {
					if (lsize < n) {
						string cpStr = results[i] + "(";
						pair<int, int> cpSz = parSize[i];
						cpSz.first++;
						results.push_back(cpStr);
						parSize.push_back(cpSz);
					}
					results[i] += ")";
					parSize[i].second++;
				}
			}
			count++;
		}
		return results;
	}
};

原题：https://leetcode.com/problems/letter-combinations-of-a-phone-number/
思路：
就是排列组合全部输出嘛！如果用递归做的话，函数进栈出栈估计会挺费事儿的，所以想个循环呗。假设我们要输出的是一个矩阵形式的东西，第i行j列是第i个答案的第j个字幕，那么主要问题是求出这个字母是啥。
拿原题中给的例子看，对应第一列的输出是a,a,a,b,b,b,c,c,c；第二列是d,e,f,d,e,f,d,e,f. 可以比较容易知道，第一列的字母是每3列变换一次，第二列则是每1列变换一次。即，假设最终由N个可能结果（N行），每一列代表按了一个数字键，其对应字母有m[j]个那么：

1. 第1列(j=0)字母是每Y[0] = N/m[j]改变一次的；
2. 第2列(j=1)字母是每Y[1]/m[j]改变一次的；
3. 以此类推…

所以第i行第j列的字符应该是chr[ dight[i] ] [ (j/Y[j])%当前数字对应可能结果的个数 ]
其中j/Y[j]是当前跳到了哪一个“轮回”了，比如例子里面j=4,Y[0]=9/3=3，那么就应该跑到第二个字母”b”了。
代码：

struct ChrNode{
    int size;
    ChrNode() {}
};
const char chrs[][4] = { {' '}, {'X'}, {'a','b','c'}, {'d','e','f'},
                         {'g','h','i'}, {'j','k','l'}, {'m','n','o'},
                         {'p','q','r','s'}, {'t','u','v'}, {'w','x','y','z'}};
class Solution {
public:
    int childSize(char c) {
        switch (c) {
            case '2': case '3': case '4': case '5': case '6': case '8': return 3;
            case '7': case '9': return 4;
        }
        return 1;
    }
    void makeNode(ChrNode* node, char d) {
        node->size = childSize(d);
    }
    vector<string> letterCombinations(string digits) {
        vector<ChrNode> nodes;
        //Build tree
        int digiSize = digits.size();
        int solutionSz = 1;
        for(int i=0; i<digiSize; i++){
            ChrNode node;
            makeNode(&node, digits[i]);
            nodes.push_back(node);
            solutionSz *= childSize(digits[i]);
        }
        vector<string> solutions;
        if(solutionSz <= 1)
            return solutions;
        for(int row=0; row<solutionSz; row++)
            solutions.push_back("");
        char c;
        int jmp = solutionSz;
        for(int i=0; i<digiSize; i++) {
            jmp /= nodes[i].size;
            int jmp_diff;
            for(int j=0; j<solutionSz; j++) {
                jmp_diff = j / jmp;
                c = chrs[digits[i] - '0'][jmp_diff % nodes[i].size];
                solutions[j] += c;
            }
        }
        return solutions;
    }
};