[公开]北京市地理信息公共服务平台（天地图·北京）数据建设与应用中标公告

121212/Python-Algorithm

/leetcode/73. Set Matrix Zeroes.py
# leetcode
# 73. Set Matrix Zeroes

class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
row = len(matrix)
col = len(matrix[0])
zero_row = []
zero_col = []
for i in range(row):
for j in range(col):
if matrix[i][j] == 0:
zero_row.append(i)
zero_col.append(j)
for i in zero_row:
for j in range(col):
matrix[i][j] = 0
for j in zero_col:
for i in range(row):
matrix[i][j] = 0

/leetcode/225. Implement Stack using Queues.py
# leetcode
# 225. Implement Stack using Queues

class MyStack:

def __init__(self):
"""
Initialize your data structure here.
"""
self.stack = []

def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.stack.append(x)

def pop(self) -> int:
"""
Removes the element on top of the stack.
"""
return self.stack.pop()

def top(self) -> int:
"""
Get the top element.
"""
return self.stack[-1]

def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return len(self.stack) == 0

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

/leetcode/209. Minimum Size Subarray Sum.py
# leetcode
# 209. Minimum Size Subarray Sum

class Solution:
def minSubArrayLen(self, s: int, nums: List[int]) -> int:
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
length = len(nums)
if length == 0:
return 0
pre = 0
start = 0
length = float('inf')
for i in range(length):
pre += nums[i]
while pre >= s:
length = min(length, i-start+1)
pre -= nums[start]
start += 1
return length if length != float('inf') else 0

/leetcode/148. Sort List.py
# leetcode
# 148. Sort List

class Solution:
def sortList(self, head: ListNode) -> ListNode:
"""
:type head: ListNode
:rtype: ListNode
"""
dummy = ListNode(0)
dummy.next = head
length = 0
while head:
length += 1
head = head.next
head = dummy
while length > 1:
cur = head.next
pre = dummy
length = 0
while length < length//2:
pre = pre.next
cur = cur.next
length += 1
pre.next = None
first = self.sortList(head.next)
second = self.sortList(cur)
head.next = self.merge(first, second)
while head.next:
head = head.next
return dummy.next

def merge(self, first, second):
if not first:
return second
if not second:
return first
dummy = ListNode(0)
head = dummy
while first and second:
if first.val < second.val:
head.next = first
head = head.next
first = first.next
else:
head.next = second
head = head.next
second = second.next
if first:
head.next = first
if second:
head.next = second
return dummy.next

/leetcode/674. Longest Continuous Increasing Subsequence.py
# leetcode
# 674. Longest Continuous Increasing Subsequence

class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
"""
:type nums: List[int]
:rtype: int
"""
length = len(nums)
if length == 0:
return 0
pre = nums[0]
max_length = 1
current_length = 1
for i in range(1, length):
if pre < nums[i]:
current_length += 1
max_length = max(max_length, current_length)
else:
current_length = 1
pre = nums[i]
return max_length

/leetcode/344. Reverse String.py
# leetcode
# 344. Reverse String

class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
length = len(s)
for i in range(length//2):
s[i], s[length - i - 1] = s[length - i - 1], s[i]

/leetcode/253. Meeting Rooms II.py
# leetcode
# 253. Meeting Rooms II

class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
"""
:type intervals: List