Tag: LeetCode OJ

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.

思路

多数投票嘛，这个题目当年NB哄哄的数据库老师在课堂上提到过，至今印象深刻，跟我们说选班长的时候画正字就是在浪费空间（当然要保证半数通过的前提）。
假设当前候选人A唱了三票，那么小黑板上A的“正”字记了三笔；这时候有了B的一票，由于我们只要统计排名第一的人，此时可以把A的正字划去一票，而不是重新记一个“B，一票”。因为照这样计算，如果B再唱了两票，那两个人的票刚好抵消，小黑板被擦干净，这时候不管是谁得了一票就写在小黑板上重新计数啦

思路2

设想一下排序后的数列，如果有个元素占了超过半数的位置，那么它肯定也是这个数列的中位数。参考快速排序的思想，可以在O(n)的复杂度找到这个中位数，它也就是要得到的结果。（参考数组第k大数的那个递归方法）

代码（思路1）

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int majNum = -1;
        int majCount = 0;
        int numSz = nums.size();
        for(int i=0; i<numSz; i++){
            if(majNum != nums[i]){
                if(majCount == 0){
                    majNum = nums[i];
                    majCount = 1;
                } else {
                    majCount--;
                }
            } else {
                majCount++;
            }
        }
        return majNum;
    }
};

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

思路：

二叉搜索树的中序遍历（LNR）就是按照从小到大顺序排的，所以遍历到N节点的时候就记个数，计数到k的时候就返回了。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        if(root == NULL)
            return -1;
        int retVal = -1;
        int count = 0;
        kthSmallest1(root, k, count, retVal);
        return retVal;
    }
    void kthSmallest1(TreeNode* root, int k, int& count, int& retVal){
        if(count >= k)
            return;
        if(root->left != NULL)
            kthSmallest1(root->left, k, count, retVal);
        count ++;
        if(count == k){
            retVal = root->val;
            return;
        }
        if(root->right != NULL)
            kthSmallest1(root->right, k, count, retVal);
    }
};

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

思路

这个是剑指Offer还是什么程序员面试经典或者是编程珠玑上的一道题，反正已经广为流传了。
O(n)复杂度的想法是，假定我有之前能得到的最大和子串的和sum[i-1]和当前值a[i]，如何得到当前的最大和sum[i]呢？分两个情况：

• 如果sum[i-1]+a[i]<a[i]，比如上面那个数列的前两项-2+1 = -1 < 1，那意思就是前面那么好的加起来还不如从我这边重新开始来的好，则sum[1]就是a[i]
• 否则，更新sum[i]=sum[i-1]+a[i]

概括成一句话就是，既然之前的人加在一起都不如我，那就我带头上吧！

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if(nums.empty())
            return -1;
        int max = nums[0];
        for(int i = 1; i<nums.size(); i++){
            if(nums[i-1] + nums[i] > nums[i]){
                nums[i] += nums[i-1];
            }
            if(nums[i] > max)
                max = nums[i];
        }
        return max;
    }
};

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;
    }
};