Tag: LeetCode OJ

Categories
木有技术

LeetCode 23. Merge k Sorted Lists

https://leetcode.com/problems/merge-k-sorted-lists/description/
Use max heap, the time complexity is O( log(k) * N )

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.empty())
            return nullptr;
        auto comparor = [](ListNode* lhs, ListNode* rhs) {
            return lhs->val > rhs->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(comparor)> pri_queue(comparor);
        // perpare queue with K items
        for(auto& list : lists)
        {
            if (list != nullptr)
                pri_queue.push(list);
        }
        ListNode* head = new ListNode(-1);
        ListNode* prev = head;
        ListNode* current = nullptr;
        while (!pri_queue.empty())
        {
            current = pri_queue.top();
            prev->next = current;
            ListNode* next = current->next;
            pri_queue.pop();
            if (next != nullptr)
                pri_queue.push(next);
            prev = current;
        }
        return head->next;
    }
};

 

Categories
木有技术

LeetCode 222. Count Complete Tree Nodes

https://leetcode.com/problems/count-complete-tree-nodes/description/
简单的二分法分治，探测（子）树的左右侧是否相等即可。
（下面代码没实现）想要更快的话，其实自从第一次算出左侧的深度后，后面的左测深度直接可以通过减法求出，不用再去探测一次了。

/**
 * 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 countLevel(TreeNode* root, bool to_left) {
        int count = 0;
        while (root != nullptr)
        {
            count++;
            root = to_left ? root->left : root->right;
        }
        return count;
    }
    int countNodes(TreeNode* root) {
        if (root == nullptr)
            return 0;
        int lvl_left = countLevel(root, true);
        int lvl_right = countLevel(root, false);
        if (lvl_left == lvl_right)
        {
            // finally
            return (1 << lvl_left) - 1; // 2^n - 1
        }
        else
        {
            return 1 + countNodes(root->left) + countNodes(root->right);
        }
    }
};

 

Categories
不学无术

LeetCode 76. Minimum Window Substring

76. Minimum Window Substring
思路:
构造一个哈希表结构统计我们的需求，也就是字符串t中每个字符的数量，方便起见如果有需求则哈希表的对应值-1。另外存储一下当前解的起始位置START以及最优解的位置。
扫描字符串s，在位置s[i]时如果能够满足需求（即哈希表中没有负值），则从START开始清除无用的字符直至无法满足需求位置。比如需求是A:1, B:2，START开始的字符是DEFBAB，则清除DEF。清除完成后更新START值并跟当前已知的最优解比较，更新最优解。
啰嗦一句，似乎相当一部分substring类型的题目都能用hash table + two pointers的方式解决。

class Solution {
public:
    static string minWindow(string s, string t) {
        int count_map[128] = {0};
        set<char> req_set;
        int start_index = -1, min_start_index = 0;
        int min_end_index = INT_MAX;
        for (const char& c : t)
        {
            count_map[c] --;
            req_set.insert(c);
        }
        for (int i = 0; i < s.size(); ++i)
        {
            const char c = s[i];
            count_map[c] ++;
            bool require_sufficed = true;
            for (const char& c : req_set)
            {
                if (count_map[c] < 0)
                {
                    require_sufficed = false;
                    break;
                }
            }
            if (!require_sufficed) continue;
            // clear left
            for (int j = start_index + 1; j <= i; ++j)
            {
                if (--count_map[s[j]] < 0)
                {
                    start_index = j;
                    break;
                }
                start_index = j;
            }
            if (i - start_index < min_end_index - min_start_index)
            {
                min_start_index = start_index;
                min_end_index = i;
            }
        }
        if (min_end_index == INT_MAX)
            return "";
        else
            return s.substr(min_start_index, min_end_index - min_start_index + 1);
    }
};

 

Categories
不学无术

LeetCode 47. Permutations II

用回溯法完成，跟普通排列问题不同的是，需要排除掉一些重复“路径”。
可以这样做，先把输入数组排个序，这样重复的数就在相邻位置了。随后在回溯探求的过程中，我们要保证相同值的两个数nums[i], nums[j]，如果i<j，那遍历只能有一种次序：nums[i]先，nums[j]后。
换句话说，就是判断这种情况是需要提前终止的：两个数nums[i]==nums[j] && i<j，但是nums[i]还没有被遍历。所以找个东西记录一下访问就行了。
时间复杂度是O(N!)，空间复杂度是O(N)

class Solution {
public:
    void permSub(vector<int>& nums, vector<int>& sub, vector<vector<int>>& results, vector<bool>& used){
        if(sub.size() == nums.size()){
            results.push_back(sub);
            return;
        } else {
            for(int i=0; i<nums.size(); i++){
                if(used[i])
                    continue;
                if(i>0 && nums[i]==nums[i-1] && !used[i-1])
                    continue;
                sub.push_back(nums[i]);
                used[i] = true;
                permSub(nums, sub, results, used);
                sub.pop_back();
                used[i] = false;
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> results;
        vector<bool> used(nums.size(), false);
        vector<int> sub;
        permSub(nums, sub, results, used);
        return results;
    }
};

 

Categories
不学无术

LeetCode 368. Largest Divisible Subset

思路：
想到一个词叫“传递性”，在这边应该也适用。就是如果b%a==0，然后c%b==0，那么肯定有c%a==0. 按照这个方法来构造一个集合就可以了，应该是动态规划的思想，results[i]保存包含数组元素nums[i]的最佳集合，构建集合的时候，首先从之前的results[j] (j=0…i-1)里面找到能够“传递”过来的集合(nums[i]%nums[i]==0)选作最佳（相当于找到c%b==0，当然这里的b是之前results[j]里面的最大元素，即nums[j]）然后加上本身的nums[i]就构成了到第i个元素为止的最佳集合，如此继续…
时间复杂度应该是O(n^2)

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        if(nums.empty())
            return nums;
        sort(nums.begin(), nums.end());
        int bestIndex = 0;
        vector<vector<int>> results(nums.size());
        for(int i=0; i<nums.size(); i++){
            for(int j=0; j<i; j++){
                //nums[j] < nums[i]
                if(nums[i]%nums[j]==0 &&
                    results[i].size() < results[j].size())
                    results[i] = results[j];
            }
            results[i].push_back(nums[i]);
            if(results[bestIndex].size() < results[i].size())
                bestIndex = i;
        }
        return results[bestIndex];
    }
};

 

Categories
不学无术

LeetCode 424. Longest Repeating Character Replacement

思路很重要。
给定一个长度n的字符串s和限制k，将s中的部分字符替换(替换次数<=k)后，能得到连续字符（如AAAA）的长度最大为多少？
使用滑动窗口的思路可以在O(n)时间复杂度的情况下解决这个问题。需要记录当前窗口内各个字符的计数值（可以看做分布情况）以及当前窗口的起始点，窗口内最多字符的计数best。我们知道，最多字符的计数best+修改数量k如果还是不能使得当前窗口内的字符都统一的话，就得把窗口缩小（起始点后挪）。窗口缩小时记得把窗口计数更新一下。
这里有一个tricky的地方，best值本来在滑动窗口的时候是要更新的，因为可能窗口过了这个best会变小。但是由于我们要找的只是个最优的值，所以这个情况并不需要考虑对best进行更新，反正它也成不了最优。

代码

class Solution {
public:
    int characterReplacement(string s, int k) {
        //sliding window solution
        int charCount[26] = {0};
        int w_start = 0, best = 0;
        for(int w_end = 0; w_end < s.size(); w_end++){
            charCount[s[w_end]-'A']++;
            best = max(best, charCount[s[w_end]-'A']);
            if(best+k <= w_end-w_start){
                //replace k chars in current window,
                // if we still can't have the optimal
                // we will shrink the left border of window
                charCount[s[w_start]-'A']--;
                w_start++;
            }
        }
        return s.size()-w_start;
    }
};

 

Categories
不学无术

LeetCode 295. Find Median from Data Stream

题目大意是给定一个int数据流，判断当前整个数组的中位数值。由于数据流是可以不断增加的，因此采用两个堆（最大堆*1+最小堆*1）来实现。
这东西思路网上都有，每次新进一个数，维护堆就行了。维护一次的复杂度是O(logN)，对应整个数组的复杂度是O(N logN)

STL 堆相关的三个函数 make_heap(), push_heap(), pop_heap()

STL是个好东西，在<algorithm>库里面就有三个与堆有关的函数，利用vector存储堆元素就可以调用这些函数来建立、更新堆。
make_heap(first, last, comp)是建立堆的函数，输入的first, last对应begin()和end()的iterator，comp函数可选，与库中sort()用到的方法相同，自定义的时候比较两个元素x, y的偏序关系，返回true说明x应该排在前面。相关的有两个仿函数叫less<T>() 和greater<T>()，直接用来比较<和>关系的。
push_heap(first, last, comp)使用时，将新元素放在数组末尾(代表堆的末叶节点)，然后调用这个函数更新堆，是一个sift-up的过程。
pop_heap(first, last, comp)会将堆顶元素调整到数组末尾用于pop，同时调整更新堆。

代码

class MedianFinder {
private:
    vector<int> maxHeap; // store values less than median
    vector<int> minHeap; // store values greater than median
public:
    // Adds a number into the data structure.
    void addNum(int num) {
        int minSize = minHeap.size();
        int maxSize = maxHeap.size();
        if(maxSize == 0){
            maxHeap.push_back(num);
            return;
        }
        if(num < maxHeap[0]){
            maxHeap.push_back(num);
            push_heap(maxHeap.begin(), maxHeap.end());
            if(maxSize > minSize) {
                pop_heap(maxHeap.begin(), maxHeap.end());
                int popVal = maxHeap[maxHeap.size()-1];
                maxHeap.pop_back();
                minHeap.push_back(popVal);
                push_heap(minHeap.begin(), minHeap.end(), greater<int>());
            }
        } else {
            minHeap.push_back(num);
            push_heap(minHeap.begin(), minHeap.end(), greater<int>());
            if(minSize >= maxSize) {
                pop_heap(minHeap.begin(), minHeap.end(), greater<int>());
                int popVal = minHeap[minHeap.size()-1];
                minHeap.pop_back();
                maxHeap.push_back(popVal);
                push_heap(maxHeap.begin(), maxHeap.end());
            }
        }
    }
    // Returns the median of current data stream
    double findMedian() {
        if((maxHeap.size() + minHeap.size())%2 == 0){
            //even num.
            if(maxHeap.empty() && minHeap.empty())
                return 0.0;
            double sum = maxHeap[0] + minHeap[0];
            return sum/2.0;
        } else {
            if(maxHeap.empty())
                return 0.0;
            return (double)maxHeap[0];
        }
    }
};
// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();

 

Categories
不学无术

LeetCode 51. N-Queens

八皇后问题的延伸版，回溯实现。

class Solution {
public:
bool checkQueen(int** mat, int N, int r, int c) {
	for (int row = 0; row < N; row++) {
		if (row == r)
			continue;
		if (mat[row][c] == 1)
			return false;
	}
	//
	int row = r-1, col = c-1;
	while (row >= 0 && col >= 0) {
		if (mat[row][col] == 1)
			return false;
		row--; col--;
	}
	row = r + 1, col = c + 1;
	while (row < N && col < N) {
		if (mat[row][col] == 1)
			return false;
		row++; col++;
	}
	//
	//
	row = r - 1, col = c + 1;
	while (row >= 0 && col < N) {
		if (mat[row][col] == 1)
			return false;
		row--; col++;
	}
	row = r + 1, col = c - 1;
	while (row < N && col >= 0) {
		if (mat[row][col] == 1)
			return false;
		row++; col--;
	}
	//
	return true;
}
void nQueensSub(int** mat, int N, int row, int col, vector<vector<string>>& results) {
	if (row == N) {
		//print
		vector<string> result;
		for (int i = 0; i < N; i++) {
			string row;
			for (int j = 0; j < N; j++) {
				if (mat[i][j] == 0)
					row += '.';
				else
					row += 'Q';
			}
			result.push_back(row);
		}
		results.push_back(result);
	}
	else {
		if (checkQueen(mat, N, row, col)) {
			//put queen here
			mat[row][col] = 1;
			//try next row
			nQueensSub(mat, N, row + 1, 0, results);
			mat[row][col] = 0;
		}
		//try next col
		if (col+1 < N) {
			nQueensSub(mat, N, row, col + 1, results);
		}
	}
}
    vector<vector<string>> solveNQueens(int n) {
	    int** mat = new int*[n];
	    for (int i = 0; i < n; i++) {
	    	mat[i] = new int[n];
	    	for (int j = 0; j < n; j++) {
	    		mat[i][j] = 0;
    		}
    	}
    	vector<vector<string>> results;
    	nQueensSub(mat, n, 0, 0, results);
    	for (int i = 0; i < n; i++) {
    		delete[]mat[i];
    	}
    	delete[] mat;
    	return results;
    }
};

 

Categories
不学无术

LeetCode 220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

思路

基本思路是，假设当前运行到nums[i]的位置，则需要往前看k个数，并且找到其中任意一个数x满足 nums[i]-t <= x <=nums[i]+t。可以利用一个大小为k的二叉搜索树解决搜索范围的问题（问题就转变为：找到第一个>=nums[i]-t的数，判断他是否<=nums[i]+t）。整个算法的时间复杂度是O(N * logk)，N为数组长度。
下面代码中用set实现，set是用红黑树实现的。

代码

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(nums.empty() || k<1 || t<0)
            return false;
        k++;
        set<int> kNumSet;
        for (int i=0; i<nums.size(); i++){
            if(i >= k){
                int oldVal = nums[i-k];
                kNumSet.erase(oldVal);
            }
            auto l_bound = kNumSet.lower_bound(nums[i] - t);
            if(l_bound != kNumSet.end()){
                if(*l_bound - t <= nums[i])
                    return true;
            }
            kNumSet.insert(nums[i]);
        }
        return false;
    }
};

 

Categories
不学无术

LeetCode 223. Rectangle Area

题目

题目大意是给定两个长方形的坐标，计算他们一起覆盖的面积。
总的思路很简单，Area_A + Area_B – Overlap，具体求重合的面积则需要计算重合区域的两个坐标点。
那么就要分情况讨论，以重合区左下角点的横坐标为例，需要判断点E与横坐标AC的位置关系，即三种：E<A; A<E<C; C<E。

代码

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int pt_M[2], pt_N[2];
        int area_A_or_B = (C-A)*(D-B) + (G-E)*(H-F);
        //pt_M[0]
        if(E<A)
            pt_M[0] = A;
        else if(E<=C)
            pt_M[0] = E;
        else
            return area_A_or_B;
        //pt_N[0]
        if(G<=A)
            return area_A_or_B;
        else if(G<=C)
            pt_N[0] = G;
        else
            pt_N[0] = C;
        //pt_M[1]
        if(F<B)
            pt_M[1] = B;
        else if(F <= D)
            pt_M[1] = F;
        else
            return area_A_or_B;
        //pt_N[1]
        if(H<=B)
            return area_A_or_B;
        else if(H<=D)
            pt_N[1] = H;
        else
            pt_N[1] = D;
        return area_A_or_B - (pt_N[0]-pt_M[0]) * (pt_N[1]-pt_M[1]);
    }
};