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

线代 范数

在机器学习中,经常使用范数函数衡量向量。

表示为||x||(略去了下标)。直观理解是点x到原点的距离。

其中,L2范数又可以称为欧几里得距离。

当下标为无穷时,表示向量中具有最大增幅的元素的值。

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