leedcode Combination Sum

Given a set of candidate numbers (C) (without duplicates) 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.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

1
2
3
4
[
[7],
[2, 2, 3]
]

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def DFS(self, candidates, target, start, valuelist):
length = len(candidates)
if target == 0:
return Solution.ret.append(valuelist)
for i in range(start, length):
if target < candidates[i]:
return
self.DFS(candidates, target - candidates[i], i, valuelist + [candidates[i]])
def combinationSum(self, candidates, target):
candidates.sort()
Solution.ret = []
self.DFS(candidates, target, 0, [])
return Solution.ret

leedcode Count and Say

Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1
2
3
4
5
1. 1
2. 11
3. 21
4. 1211
5. 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 term of the count-and-say sequence.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
# @return a string
def count(self,s):
t=''; count=0; curr='#'
for i in s:
if i!=curr:
if curr!='#':
t+=str(count)+curr
curr=i
count=1
else:
count+=1
t+=str(count)+curr
return t
def countAndSay(self, n):
s='1'
for i in range(2,n+1):
s=self.count(s)
return s

leedcode Regular Expression Matching

Search Insert Position

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

code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def searchInsert(self, A, target):
left = 0; right = len(A) - 1
while left <= right:
mid = ( left + right ) / 2
if A[mid] < target:
left = mid + 1
elif A[mid] > target:
right = mid - 1
else:
return mid
return left

leedcode Search for a Range

Search for a Range

Given an array of integers sorted in ascending order, 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].

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
def findLeft(self,nums,first,mid):
if nums[first] == nums[mid]:
return first
nmid = (first + mid) // 2
if nums[nmid] == nums[mid]:
return self.findLeft(nums,first,nmid)
return self.findLeft(nums,nmid + 1,mid)
def findRight(self,nums,mid,last):
if nums[last] == nums[mid]:
return last
nmid = (mid + last + 1) // 2
if nums[nmid] == nums[mid]:
return self.findRight(nums,nmid,last)
return self.findRight(nums,mid,nmid - 1)
def searchRange(self, nums, target):
last = len(nums);first = 0
while first != last:
mid = (first + last) // 2
if nums[mid] == target:
return [self.findLeft(nums,first,mid),self.findRight(nums,mid,last - 1)]
elif nums[mid] < target:
first = mid + 1
else:
last = mid
return [-1,-1]

leedcode Search in Rotated Sorted Array

Search in Rotated Sorted Array

Suppose an array sorted in ascending order 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.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def search(self, nums, target):
start=0
end=len(nums)-1
while start<=end:
mid=(start+end)/2
if nums[mid]==target:
return mid
if nums[mid]>=nums[start]:
if target>=nums[start] and target<nums[mid]:
end=mid-1
else:
start=mid+1
if nums[mid]<nums[end]:
if target>nums[mid] and target<=nums[end]:
start=mid+1
else:
end=mid-1
return -1

leedcode Next Permutation

Next Permutation

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-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def nextPermutation(self, nums):
if len(nums)<=1:
return
for i in range(len(nums)-2,-1,-1):
if nums[i]<nums[i+1]:
for k in range(len(nums)-1,i,-1):
if nums[k]>nums[i]:
nums[i],nums[k]=nums[k],nums[i]
nums[i+1:]=sorted(nums[i+1:])
break
break
else:
if i==0:
nums.sort()

leedcode Longest Valid Parentheses

Longest Valid Parentheses

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.

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def longestValidParentheses(self, s):
maxlen = 0
stack = []
last = -1
for i in range(len(s)):
if s[i]=='(':
stack.append(i)
else:
if stack == []:
last = i
else:
stack.pop()
if stack == []:
maxlen = max(maxlen, i-last)
else:
maxlen = max(maxlen, i-stack[len(stack)-1])
return maxlen