Tag: LeetCode OJ

题目：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;
    }
};

原题：https://leetcode.com/problems/3sum/
思路：
3Sum的问题其实是2Sum问题的晋级版，可我当年投机取巧用hashmap过了2sum问题（有兴趣可以搜下我的解法^-^），导致这个3sum卡壳了很久。所以经验教训是，不管自己AC了没有，要看看别人怎么做的，歪门邪道不一定次次通用。
因此先来解决下2sum的问题，也就是给定一个数组，找到两个元素a[i],a[j]使得a[i]+a[j]=X的问题，简单点，假设X=0；这个问题可以用两个指针来解决，当然前提是要先把数组排序好，时间复杂度是O(nlogn). 排序后，假设两个指针一开始指向数组的头、末元素(i=0, j=size-1)，然后就有三种可能性：

• 刚好碰巧这两个值的和就是0 ，那么下一步i,j就要各自朝向内部移动一格(i++, j–)。这里不会产生分支情况，即不可能存在a[i]+a[j] == a[i+1]+a[j] 或==a[i]+a[j-1]，除非前项、后项的值是同一个元素；
• 如果两个值的和<0了，那说明负能量太大了，因此i明显太小了，要把i向右移动让它变大才有可能，因此i++；
• 与上一条同理，j–;

所以，2sum问题在排序后，内部查找的时间复杂度是线性复杂度O(n).
那么3sum问题呢，可以先简化一下，假设不用考虑数组内有重复元素的情况，那么可以把3Sum问题这样简化，固定一个位置的元素a[pos]，在数组内寻找另外两个元素，其值a[i]+a[j]==-a[pos]，这就变成2Sum问题了，其中之前提到的X=-a[pos]。整个算法需要先排序一遍，时间复杂度O(nlogn)，然后需要遍历每个pos再在循环里做2Sum问题，复杂度为O(n^2)，所以两个连在一起，复杂度在O(n^2)范围内（暴力解法复杂度为O(n^3)）。
代码（记得处理重复问题）：

bool sortFunc (int i,int j) { return (i<j); }
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end(), sortFunc);
        vector<vector<int>> results;
        for(int pos=0; pos<nums.size(); pos++){
            threeSumSub(nums, pos, results);
            while(pos+1 < nums.size() && nums[pos+1] == nums[pos])
                pos++;
        };
        return results;
    }
    void threeSumSub(vector<int>& nums, int pos, vector<vector<int>> &results) {
        //Find two elements which add up equals -nums[pos]
        int i = pos+1;
        int j = nums.size() - 1;
        int val;
        while(i < j) {
            val = nums[pos] + nums[i] + nums[j];
            if(val == 0){
                vector<int> solution;
                solution.push_back(nums[pos]);
                solution.push_back(nums[i]);
                solution.push_back(nums[j]);
                results.push_back(solution);
                while(nums[i+1] == nums[i] && i < j) i++;
                while(nums[j-1] == nums[j] && i < j) j--;
                i++;
                j--;
            } else if (val < 0) {
                //Too big, move right
                while(nums[i+1] == nums[i] && i < j) i++;
                i++;
            } else {
                while(nums[j-1] == nums[j] && i < j) j--;
                j--;
            }
        }
    }
};

原题：https://leetcode.com/problems/container-with-most-water/
思路：
最简单的方法当然是嵌套两层的循环i,j，时间复杂度是O(n^2)，但是撸了一发超时了，说明还有更简单的方法。
可以这么理解，要让长方形的面积最大，可以先从底边长度最大开始试，假设左端高度是h_i，右端高度是h_j，那么面积就是(j-i)*min(h_i, h_j).
此时可以移动左边或右边的柱子将底边长度缩小一点，但是有个问题，假设当前的瓶颈在左侧i这里，如果保持i的位置不变移动右侧，最好情况也只会把面积缩小，因为底边长度缩水了，高最高也就是i的高度，所以其实若要缩小宽度，只能把瓶颈去除掉，只能移动当前的瓶颈位置i，这样如果碰到个更大的i’，高度会上升至min(h_i’,h_j)，肯定比i要大了，这样才有可能增加面积。由于这种方法只用扫一遍数组，所以时间复杂度是O(n)
代码：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0;
        int j = height.size() - 1;
        int area;
        int maxArea = 0;
        while(i != j){
            if(height[i] < height[j]){
                area = height[i] * (j - i);
                i ++; //Bottle neck at i, move forward
            } else {
                area = height[j] * (j - i);
                j --; //Bottle neck at j, move backward
            }
            if (area > maxArea)
                maxArea = area;
        }
        return maxArea;
    }
};

原题：https://leetcode.com/problems/valid-anagram/
思路：Anagram就是指两个单词（一说句子也行）里面字符的种类、数量一样，但是能拼出不同的词。所以思路就是统计里面的字符频率就行。
代码：

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size())
            return false;
        int stable[26] = {0};
        int ttable[26] = {0};
        for(int i=0; i<s.size(); i++){
            stable[s[i] - 'a'] ++;
            ttable[t[i] - 'a'] ++;
        }
        for(int i=0; i<26; i++){
            if (stable[i] != ttable[i])
                return false;
        }
        return true;
    }
};

题目：https://leetcode.com/problems/move-zeroes/
思路：
说是把0 挪到后面去，其实等同于把非0值往前挪。挪到什么地方呢？就得找个东西记录可以往前挪的“坑”。而这个“坑”有两种情况：
1.原来的值就是0的；
2.如果把当前的非0值往前面挪过了，那当前的位置也就空缺；
从一开始记录一下找到的0的个数，把非0值挪完了以后，最后几位写成0就行。
这一切的时间复杂度为O(n)
代码（用到了队列来存储坑的位置）：

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int size = nums.size();
        int zeroCount = 0;
        queue<int> availIndices;
        for(int i=0; i < size; i++){
            if(nums[i] == 0){
                zeroCount ++;
                availIndices.push(i);
            } else {
                if(!availIndices.empty()) {
                    //Move forward
                    int index =availIndices.front();
                    availIndices.pop();
                    nums[index] = nums[i];
                    //Mark i as empty
                    availIndices.push(i);
                }
            }
        }
        for(int i = size - zeroCount; i < size; i++) {
            nums[i] = 0;
        }
    }
};