leetcode python

Posted on   |   In   |  

Array

1. Two sum

1
2
3
4
5
6
def twoSum(nums, target):
    h = {}
    for i, num in enumerate(nums):
        if (target - num) in h and i != h[target - num]:
            return sorted([i,h[target - num]])
        h[num] = i

11. Container With Most Water

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def maxArea(height):
    lo = 0
    hi = len(height)-1
    max_lo = height[lo]
    max_hi = height[hi]
    max_1 = (hi - lo) * min(max_lo, max_hi)

    while lo < hi:
        if height[lo] > height[hi]:
            while height[hi] <= max_hi and lo < hi:
                hi -= 1
            max_hi = height[hi]
        else:
            while height[lo] <= max_lo and lo < hi:
                lo += 1
            max_lo = height[lo]
        max_temp = (hi - lo) * min(max_hi,max_lo)
        max_1 = max(max_temp, max_1)
    return max_1

15. 3Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def twoSum(target, nums):
    h={}
    result = set()
    for i,nums in enumerate(nums):
        if target-nums in h :
            result.add(tuple(sorted([-target,nums,target - nums])))
        h[nums] = i
    return result

def threeSum(nums):
    result = set()
    for i, n in enumerate(nums):

        result = result.union(twoSum(-n, nums[i+1:]))
    return list(result)

16. 3Sum Closest

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
27
28
29
30
31
32
33
34
def threeSumClosest(nums, target):
    nums = list(sorted(nums))
    dis = target - (nums[0] + nums[1] + nums[2])  # -103
    for i in range(len(nums)-2):
        target_temp = target - nums[i]   # -101
        dis = findNear(nums[i+1:], target_temp, dis)
        if dis == 0:
            return target

    return target - dis

def findNear(nums, target_temp, dis): # target_temp = nums2+nums3+near
    left = 0
    right = len(nums) - 1
    while left < right:
        if abs(dis) > abs(target_temp - nums[left] - nums[right]):
            dis = target_temp - nums[left] - nums[right]
        if dis == 0:
            return dis
        if target_temp - nums[left] - nums[right] > 0:
            left += 1
        else:
            right -= 1
    return dis

# def findNear(nums, target_temp, dis):
#     for i in range(len(nums)-1):
#         temp = target_temp - nums[i]  # temp = near + num_3   -8
#         while i < len(nums)-1:
#             if abs(dis) > abs(temp - nums[i+1]):
#                 dis = temp - nums[i+1]  # -9
#             i += 1
#
#     return dis

18. 4Sum

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
27
28
29
30
31
32
def fourSum(nums, target):
    h = {}
    sol = set()
    nums = sorted(nums)
    for i in range(len(nums)-3):
        if nums[i] not in h:
            target_3 = target - nums[i]
            # sol = sol + threeSum(nums[i+1:], target_3, nums[i])
            sol = sol.union(threeSum(nums[i+1:], target_3, nums[i]))
            h[nums[i]] = 1
    return list(sol)

def threeSum(nums, target,n):
    sol = set()
    h = {}
    for i in range(len(nums)-2):
        if nums[i] not in h:
            target_2 = target - nums[i]
            # sol = sol + twoSum(nums[i+1:], target_2, nums[i], n)
            sol = sol.union(twoSum(nums[i+1:], target_2, nums[i], n))

            h[nums[i]] = 1
    return sol

def twoSum(nums, target, m, n):
    sol = set()
    h = {}
    for i in range(len(nums)):
        if target - nums[i] in h:
            sol.add(tuple(sorted([m, n, nums[i], target-nums[i]])))
        h[nums[i]] = 1
    return sol

26. Remove Duplicates from Sorted Array

1
2
3
4
5
6
7
8
9
10
11
12
13
def removeDuplicates(self, nums):
	
    if len(nums) < 2:
            return len(nums)
            
    for i in nums:
        i,j=0,1
        while j < len(nums):
            if nums[i] != nums[j]:
                nums[i+1] = nums[j]
                i = i+1
            j = j+1
        return i+1

27. Remove Element

1
2
3
4
def removeElement(self, nums, val):
    while( val in nums):
        nums.remove(val)
    return len(nums)

next-permutation-algorithm.png

31. Next Permutation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def nextPermutation(nums):
	if len(nums) > 1:
		for i in range(len(nums)-1, 0, -1):
			if nums[i] > nums[i-1] and i > 0:
				a, b = nums[i-1], i-1
				while a < nums[b+1]:
					b += 1
					if b == len(nums)-1:
						break
				nums[i-1],nums[b] = nums[b], nums[i-1]
				nums[i:] = sorted(nums[i:])
				break
			elif i == 1:
				nums.sort()

34. Search for a Range

···python
def searchRange(nums, target):
lo, hi = 0, len(nums)-1
while lo <= hi:
mid = (hi + lo)//2
if nums[mid] == target:
while nums[lo] != target:
if nums[lo] < target:
lo += 1
while nums[hi] != target:
if nums[hi] > target:
hi -= 1
return [lo, hi]
elif nums[mid] < target:
lo = mid + 1
elif nums[mid] > target:
hi = mid - 1
return [-1, -1]

start = nums.index(target)

ncount = nums.count(target)

res = [start, start + ncount - 1]

return res

1
2
3
4
5
6
7
8
9
10
11
12
13
## 35. Search Insert Position
```python
def searchInsert(nums, target):
    lo, hi = 0, len(nums)-1
    while lo <= hi:
        mid = (lo + hi)//2
        if target == nums[mid]:
            return mid
        elif target < nums[mid]:
            hi = mid - 1
        elif target > nums[mid]:
            lo = mid + 1
    return lo

39. Combination Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def combinationSum(candidates, target):
    sol = []
    h = {}
    path = []
    index = 0
    findSol(nums,target,index,sol,path)
    return sol

def findSol(nums,target,index,sol,path):
    if target < 0:
        return
    if target == 0:
        sol.append(path)
    if target > 0:
        for i in range(index,len(nums)):
            findSol(nums,target - nums[i],i,sol,path+[nums[i]])

40. Combination Sum II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def combinationSum2(candidates, target):
    candidates.sort()
    sol = set()
    h = {}
    path = []
    for i in range(len(candidates)):
        if candidates[i] not in h:
            dfs(candidates[i:],target,path,sol)
            h[candidates[i]] = 1
    return list(sol)

def dfs(nums,target,path,sol):
    if target - nums[0] < 0:
        return
    if target - nums[0] == 0:
        sol.add(tuple(path + [nums[0]]))
        return
    if target - nums[0] > 0 and len(nums) > 1:
        for i in range(len(nums)-1):
            dfs(nums[i+1:],target - nums[0],path + [nums[0]],sol)
    return

48. Rotate Image

1
2
3
4
5
6
7
8
9
def rotate(matrix):
    for i in range(len(matrix)):
        for j in range(i,len(matrix)):
            if i != j:
                matrix[i][j], matrix[j][i] = matrix[j][i],matrix[i][j]

    for i in range(len(matrix)):
        for j in range(0,len(matrix)//2):
            matrix[i][j], matrix[i][len(matrix)-1-j]= matrix[i][len(matrix)-1-j],matrix[i][j]
1
2
3
4
5
6
7
8
9
10
def rotate(matrix):
    a = 0
    b = len(matrix) - 1
    while a < b:
        for i in range(b-a):
            matrix[a][a + i],matrix[a + i][b] = matrix[a + i][b],matrix[a][a + i]
            matrix[a][a + i],matrix[b][b - i] = matrix[b][b - i],matrix[a][a + i]
            matrix[a][a + i],matrix[b-i][a] = matrix[b-i][a],matrix[a][a + i]
        a += 1
        b -= 1

53. Maximum Subarray

1
2
3
4
5
6
7
8
9
10
11
def maxSubArray(nums):
    if not nums:
        return 0
    cur = nums[0]
    m = nums[0]

    for num in nums[1:]:
        cur = max(num,cur + num)
        m = max(cur,m)

    return m

54. Spiral Matrix

1
2
3
4
5
6
7
8
9
10
11
def spiralOrder(matrix):
    i, j, di, dj = 0, 0, 0, 1
    sol = []
    for k in range(len(matrix) * len(matrix[0])):
        sol.append(matrix[i][j])
        matrix[i][j] = ''
        if matrix[(i+di)%len(matrix)][(j+dj)%len(matrix[0])] == '':
            di, dj = dj, -di
        i += di
        j += dj
    return sol

55. Jump Game

1
2
3
4
5
6
7
8
9
10
11
12
13
def canJump( nums):
    # n = len(nums) - 1
    # jump = n
    # for i in range(n - 1, -1, -1):
    #     if i + nums[i] >= n or i + nums[i] >= jump:
    #         jump = i  # jump is the lowest index that has path(s) to last index
    # return jump == 0 or i + nums[i] >= n
    maxReach = -1
    for i in range(len(nums)-1):
        maxReach = max(maxReach,i + nums[i])
        if maxReach <= i: return False
        if maxReach >= len(nums)-1: return True
    return True

62. Unique Paths

1
2
3
4
5
6
7
8
# def uniquePaths(self, m, n):
#    return factorial(m+n-2)/factorial(n-1)/factorial(m-1)
def uniquePaths(m, n):
    temp = [1] + [0]*(n-1)
    for i in range(m):
        for j in range(1,n):
            temp[j] += temp[j-1]
    return temp[-1]

66. Plus One

1
2
3
4
5
def plusone(digits):
	num = 0
	for i in rang(len(digits):
		temp += digits[i] + pow(10, len(digits)-i-1)
	return [int(i) for i in str(temp+1)]

当数组为[0,8,9], 结果为[9,0]

1
2
3
4
5
6
7
8
9
10
11
def plusOne(digits):
    if len(digits) == 0 :
        return []
    i = len(digits)-1
    while(digits[i]+1 >=10 and i>0):
        digits[i-1] += 1
        digits[i]=0
        i -= 1
    if digits[0] >= 10:
        digits = digits.insert(0,1)
    return digits

88. Merge Sorted Array

1
2
3
4
5
6
7
8
def merge(self, nums1, m, nums2, n):
    while n > 0:
        if m <= 0 or nums2[n - 1] >= nums1[m - 1]:
            nums1[m + n - 1] = nums2[n - 1]
            n -= 1
        else:
            nums1[m + n - 1] = nums1[m - 1]
            m -= 1

118. Pascal’s Triangle

1
2
3
4
5
6
def generate(numRows):
    temp,a=[],[1]
    for i in range(numRows):
        temp.append(a)
        a = [1]+[a[j]+a[j+1] for j in range(len(a)-1)]+[1]
    return temp

119. Pascal’s Triangle II

1
2
3
4
5
def getRow(rowIndex):
    temp = [1]
    for i in range(rowIndex):
            temp = [1] + [temp[j]+temp[j+1] for j in range(len(temp)-1)] + [1]
    return temp

121. Best Time to Buy and Sell Stock

1
2
3
4
5
6
7
8
9
max = 0
for i in range(len(prices)-2):
	j = i + 1
	while (j<len(prices)):
		temp = prices[j]-prices[i]
		if  temp > max:
			max = temp
		j += 1
return max
1
2
3
4
5
6
7
8
9
10
output = 0
index = 0
for i in range(1,len(prices)):
	if prices[i] > prices[index]:
		temp = prices[i] - prices[index]
		if temp > output:
			output = temp
	else:
		index = i
return output

169. Majority Element

1
2
3
4
def majorityElement(self, nums):
	temp = list(nums)
	temp.sort()
	return temp[len(temp)/2]

189. Rotate Array

1
2
3
4
def rotate(self, nums, k):
	k = k % len(nums)
	if k != 0:
		nums[:k] , nums[k:]= nums[-k:],nums[:-k]

217. Contains Duplicate

1
2
3
4
5
6
7
def containsDuplicate( nums):
    h = {}
    for i in nums:
        if i in h :
            return True
        h[i] = 1
    return False
1
2
def containsDuplicate(self, nums):
	return len(set(nums)) < len(nums)

219. Contains Duplicate II

1
2
3
4
5
6
7
def containsNearbyDuplicate(nums, k):
    h = {}
    for i,temp in enumerate(nums):
        if temp in h and i - h[temp] <= k:
            return True
        h[temp] = i
    return False

283. Move Zeroes

1
2
3
4
5
6
def moveZeroes(nums):
    for i in range(len(nums)):
        if nums[i] == 0:
            nums.remove(0)
            nums.append(0)
    return nums