Skip to content

Instantly share code, notes, and snippets.

View luoxiaoxun's full-sized avatar

luoxiaoxun

7 followers · 0 following
View GitHub Profile
@luoxiaoxun
luoxiaoxun / LeetCode-Search in Rotated Sorted Array
Created June 17, 2013 01:22
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.
C++:
class Solution {
public:
int search(int A[], int n, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int low=0;
int high=n-1;
int mid;
while(low<=high){
@luoxiaoxun
luoxiaoxun / LeetCode-Remove Duplicates from Sorted Array II
Last active December 18, 2015 14:29
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].
C++:
class Solution {
public:
bool search(int A[], int n, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int low=0;
int high=n-1;
int mid;
while(low<=high){
@luoxiaoxun
luoxiaoxun / LeetCode-Maximal Rectangle
Last active December 18, 2015 15:09
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
C++:
class Solution {
public:
int maximalRectangle(vector<vector<char> > &matrix) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int m=matrix.size();
if(m==0) return 0;
int n=matrix[0].size();
if(n==0) return 0;
@luoxiaoxun
luoxiaoxun / LeetCode-Remove Duplicates from Sorted Array
Created June 18, 2013 01:46
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example, Given input array A = [1,1,2], Your function should return length = 2, and A is now [1,2].
C++:
class Solution {
public:
int removeDuplicates(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n==0||n==1) return n;
int min=A[0]-1;
for(int i=n;i>0;i--)
if(A[i]==A[i-1])
@luoxiaoxun
luoxiaoxun / LeetCode-Remove Duplicates from Sorted Array II
Created June 18, 2013 02:03
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].
C++:
class Solution {
public:
int removeDuplicates(int A[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n==0||n==1) return n;
int min=A[0]-1;
int cur=A[0];
int count=0;
@luoxiaoxun
luoxiaoxun / LeetCode-Remove Duplicates from Sorted List
Created June 18, 2013 02:21
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.
C++:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
@luoxiaoxun
luoxiaoxun / LeetCode-Remove Duplicates from Sorted List II
Created June 18, 2013 03:20
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.
C++:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
@luoxiaoxun
luoxiaoxun / LeetCode-Combinations
Created June 19, 2013 01:03
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], ]
C++:
class Solution {
public:
vector<vector<int> > combine(int n, int k) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int>> results;
vector<int> result;
if(n<=0||k<=0||n<k) return results;
comb(n,k,results,result,1,0);
@luoxiaoxun
luoxiaoxun / LeetCode-Combination Sum
Created June 19, 2013 01:43
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times. Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, � , ak) must be in non-descending order.…
C++:
class Solution {
public:
vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int>> results;
if(candidates.size()==0) return results;
sort(candidates.begin(),candidates.end());
vector<int> result;
@luoxiaoxun
luoxiaoxun / LeetCode-Combination Sum II
Created June 19, 2013 01:50
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: All numbers (including target) will be positive integers. Elements in a combination (a1, a2, � , ak) must be in non-descending order. (ie, a…
C++:
class Solution {
public:
vector<vector<int> > combinationSum2(vector<int> &candidates, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<vector<int>> results;
if(candidates.size()==0) return results;
sort(candidates.begin(),candidates.end());
vector<int> result;