Peng Du pdu
pdu
/ leetcode_remove_duplicates_from_sorted_list.cpp
Created
January 21, 2013 13:40
Given a sorted linked list, delete all duplicates such that each element appear only once. For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3. http://leetcode.com/onlinejudge#question_83
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Definition for singly-linked list. | |
| * struct ListNode { | |
| * int val; | |
| * ListNode *next; | |
| * ListNode(int x) : val(x), next(NULL) {} | |
| * }; | |
| */ | |
| class Solution { | |
| public: |
pdu
/ leetcode_search_in_rotated_sorted_array.cpp
Created
January 21, 2013 13:53
Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. http://leetcode.com/onlinejudge#question_33
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| int get_biggest(int A[], int n) { | |
| int ret = 0; | |
| int left = 0; | |
| int right = n - 1; | |
| while (left <= right) { | |
| int mid = (left + right) >> 1; | |
| if (A[mid] >= A[0]) { | |
| ret = max(ret, mid); | |
| left = mid + 1; | |
| } |
pdu
/ leetcode_search_in_rotated_sorted_array_2.cpp
Created
January 21, 2013 14:21
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the array. http://leetcode.com/onlinejudge#question_33
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| bool bsearch(int A[], int left, int right, int target) { | |
| while (left <= right) { | |
| int mid = (left + right) >> 1; | |
| if (A[mid] > target) | |
| right = mid - 1; | |
| else if (A[mid] < target) | |
| left = mid + 1; | |
| else | |
| return true; | |
| } |
pdu
/ leetcode_remove_duplicates_from_sorted_arrsy_2.cpp
Created
January 21, 2013 14:30
Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice? For example,
Given sorted array A = [1,1,1,2,2,3], Your function should return length = 5, and A is now [1,1,2,2,3]. http://leetcode.com/onlinejudge#question_80
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int removeDuplicates(int A[], int n) { | |
| int id = 0; | |
| int cur = 0; | |
| while (cur < n) { | |
| int cnt = 0; | |
| int val = A[cur]; | |
| while (cur < n && val == A[cur]) { | |
| cur++; |
pdu
/ leetcode_word_search.cpp
Created
January 22, 2013 14:24
Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. For example,
Given board = [ ["ABCE"], ["SFCS"], ["ADEE"]
] word = "ABCCED", -> re…
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #define MAXN 1000 | |
| bool used[MAXN][MAXN]; | |
| int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; | |
| bool valid(int i, int j, int n, int m) { | |
| return i >= 0 && i < n && j >= 0 && j < m; | |
| } | |
| bool find(vector<vector<char> >& board, bool used[MAXN][MAXN], int n, int m, |
pdu
/ leetcode_subsets.cpp
Created
January 22, 2013 14:31
Given a set of distinct integers, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example,
If S = [1,2,3], a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []
] http://leetcode.com/onlinejudge#question_78
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| void dfs(vector<int>& S, vector<vector<int> >& ret, vector<int>& cur, int kth) { | |
| if (kth == S.size()) { | |
| ret.push_back(cur); | |
| return; | |
| } | |
| dfs(S, ret, cur, kth + 1); | |
| cur.push_back(S[kth]); | |
| dfs(S, ret, cur, kth + 1); | |
| cur.pop_back(); | |
| } |
pdu
/ leetcode_combinations.cpp
Created
January 22, 2013 14:38
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example,
If n = 4 and k = 2, a solution is: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],
] http://leetcode.com/onlinejudge#question_77
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| void dfs(int n, int k, int kth, vector<vector<int> >& ret, vector<int>& cur) { | |
| if (k == cur.size()) { | |
| ret.push_back(cur); | |
| return; | |
| } | |
| if (kth == n + 1) | |
| return; | |
| if (k - cur.size() > n - kth + 1) | |
| return; | |
| dfs(n, k, kth + 1, ret, cur); |
pdu
/ leetcode_sort_colors.cpp
Created
January 23, 2013 15:12
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note:
You are not suppose to use the library's sort function for this problem. h…
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| void sortColors(int A[], int n) { | |
| int pos0 = 0; | |
| int pos1 = n - 1; | |
| int pos2 = n - 1; | |
| while (pos0 < pos2) { | |
| if (A[pos0] == 0) | |
| pos0++; | |
| else if (A[pos0] == 1) { |
pdu
/ leetcode_minimum_window_substring.cpp
Created
January 23, 2013 15:48
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC". Note:
If there is no such window in S that covers all characters in T, return the emtpy string "". If there are multiple such windows, you are guaranteed…
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| string minWindow(string S, string T) { | |
| if (S.empty() || T.empty()) | |
| return ""; | |
| tr1::unordered_map<char, int>::iterator iter; | |
| tr1::unordered_map<char, int> MT; | |
| for (int i = 0; i < T.length(); ++i) { | |
| iter = MT.find(T[i]); | |
| if (iter == MT.end()) |
pdu
/ leetcode_search_a_2d_matrix.cpp
Created
January 24, 2013 15:58
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
For example, Consider the following matrix: [ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]…
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| bool big(vector<vector<int> > &matrix, int leftr, int leftc, int rightr, int rightc) { | |
| return (leftr > rightr) || (leftr == rightr && leftc > rightc); | |
| } | |
| void getmid(vector<vector<int> > &matrix, int leftr, int leftc, int rightr, int rightc, int& midr, int& midc) { | |
| int n = matrix.size(); | |
| int m = matrix[0].size(); | |
| int len = (rightr * m + rightc - leftr * m - leftc) / 2; | |
| int pos = leftr * m + leftc + len; | |
| midr = pos / m; |