Skip to content

Instantly share code, notes, and snippets.

View pdu's full-sized avatar

Peng Du pdu

34 followers · 12 following
  • Singapore
View GitHub Profile
@pdu
pdu / leetcode_next_permutation.cpp
Created February 20, 2013 14:09
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. Here are some examples. Inputs are in the left…
class Solution {
public:
void nextPermutation(vector<int> &num) {
if (!next_permutation(num.begin(), num.end()))
sort(num.begin(), num.end());
}
};
@pdu
pdu / leetcode_longest_valid_parentheses.cpp
Created February 20, 2013 14:04
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", which has length = 2. Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4. http://leetcode.com/onli…
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.length();
int ans = 0;
int sum = 0;
for (int i = 0; i < n; ++i) {
sum = 0;
if (ans >= n - i)
break;
@pdu
pdu / leetcode_search_in_rotated_sorted_array.cpp
Created February 19, 2013 14:46
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
class Solution {
public:
int search(int A[], int n, int target) {
int ans = -1;
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) >> 1;
if (A[mid] == target) {
ans = mid;
break;
@pdu
pdu / leetcode_search_for_a_range.cpp
Created February 19, 2013 14:32
Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. http://leetcode.com/onlinejudge#question_34
class Solution {
public:
vector<int> searchRange(int A[], int n, int target) {
int left = 0, right = n - 1;
int ans1 = n;
while (left <= right) {
int mid = (left + right) >> 1;
if (A[mid] == target) {
ans1 = min(ans1, mid);
right = mid - 1;
@pdu
pdu / leetcode_search_insert_position.cpp
Created February 19, 2013 14:26
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0 http://leetcode.com/onlinejudge#question_35
class Solution {
public:
int searchInsert(int A[], int n, int target) {
int ans = n;
int left = 0, right = n - 1;
while (left <= right) {
int mid = (left + right) >> 1;
if (A[mid] >= target) {
ans = min(ans, mid);
right = mid - 1;
@pdu
pdu / leetcode_count_and_say.cpp
Created February 19, 2013 14:18
The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ... 1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211. Given an integer n, generate the nth sequence. Note: The sequence of integers will be represented as a string. http://leetcode.c…
class Solution {
public:
string countAndSay(int n) {
string ans = "1";
while (--n) {
string tmp = ans;
ans.clear();
int cnt;
char num;
char buf[1024];
@pdu
pdu / leetcode_combination_sums.cpp
Created February 19, 2013 14:10
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 orde…
class Solution {
public:
vector<vector<int> > combinationSum(vector<int> &num, int target) {
vector<vector<int> > ans;
map<vector<int>, bool> hash;
if (target == 0 || num.empty())
return ans;
vector<int> tmp;
sort(num.begin(), num.end());
for (int i = 0; i < num.size(); ++i) {
@pdu
pdu / leetcode_combination_sums_2.cpp
Created February 19, 2013 14:07
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,…
class Solution {
public:
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
vector<vector<int> > ans;
map<vector<int>, bool> hash;
if (target == 0 || num.empty())
return ans;
vector<int> tmp;
sort(num.begin(), num.end());
for (int i = 0; i < num.size(); ++i) {
@pdu
pdu / leetcode_first_missing_positive.cpp
Created February 19, 2013 12:58
Given an unsorted integer array, find the first missing positive integer. For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2. Your algorithm should run in O(n) time and uses constant space. http://leetcode.com/onlinejudge#question_41
class Solution {
public:
int firstMissingPositive(int A[], int n) {
for (int i = 0; i < n; ++i) {
int id = i;
while (A[id] != id + 1 && A[id] >= 1 && A[id] <= n && A[id] != A[A[id] - 1])
swap(A[id], A[A[id] - 1]);
}
for (int i = 0; i < n; ++i)
if (A[i] != i + 1)
@pdu
pdu / leetcode_trapping_rain_water.cpp
Created February 19, 2013 12:52
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining. For example, Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6. The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trap…
#define MAXN 100000
int _left[MAXN];
int _right[MAXN];
class Solution {
public:
int trap(int A[], int n) {
for (int i = 0; i < n; ++i) {
if (i == 0)
_left[i] = A[i];