基础数据结构
- 数组、链表、跳表的原理和实现
| 类型 | 链接 |
|---|---|
| 数组 | https://blog.csdn.net/qq_30257149/article/details/99588189 |
| 链表 | http |
| 跳表 | http |
代码：
- 三者的空间复杂度、时间复杂度
- 工程运用
- 跳表：升维思想+空间换时间
实战
盛水最多的容器
def maxArea(height):
l,r = 0,len(higth)-1
ans = 0
while l < r:
area = min(height[l],height[r]) * (r-l)
ans = max(area,ans)
if height[l] < height[r]:
l += 1
else:
r -= 1
return ans
爬楼梯
def climbStairs(n):
a = b = 1
for _ in range(n):
a,b = b,(a+b)
return a
移动零
def moveZeros(nums):
j = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[j] = nums[i]
if i != j:
nums[i] = 0
j += 1
链表：
reverse-linked-list
swap-nodes-in-pairs
linked-list-cycle
linked-list-cycle-ii
revese-nodes-in-k-group
Homework
remove-duplicates-from-sorted-array
rotate-array
merge-sorted-array
two-sum
move-zeroes
plus-one
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
leftindex = self.binary(nums,target,True)
rightindex = self.binary(nums,target,False)-1
if leftindex <= rightindex and rightindex < len(nums) and nums[leftindex] == target and nums[rightindex] == target:
return [leftindex,rightindex]
return [-1,-1]
def binary(self,nums,target,lower):
left = 0
right = len(nums)-1
ans = len(nums)
while left <= right:
mid =(left + right) // 2
if (nums[mid] > target) or (lower and nums[mid] >= target):
right = mid - 1
ans = mid
else:
left = mid + 1
return ans
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
f = [[0] * n for _ in range(n)]
f[0][0] = triangle[0][0]
for i in range(1,n):
f[i][0] = triangle[i][0] + f[i-1][0]
for j in range(1,i):
f[i][j] = min(f[i-1][j],f[i-1][j-1]) + triangle[i][j]
f[i][i] = triangle[i][i] + f[i-1][i-1]
return min(f[n-1])
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
res = []
path = []
def dfs(root,targetSum):
if not root:
return
path.append(root.val)
targetSum -= root.val
if not root.left and not root.right and targetSum == 0:
res.append(path[:])
dfs(root.left,targetSum)
dfs(root.right,targetSum)
path.pop()
dfs(root,targetSum)
return res
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
count,pre = 0,0
mp = {}
mp[0] = 1
for i in range(len(nums)):
pre += nums[i]
if pre-k in mp:
count += mp.get(pre - k)
mp[pre] = mp.get(pre,0) + 1
return count
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
if head.val == val:return head.next
tmp = head
while tmp.next :
if tmp.next.val == val:
tmp.next = tmp.next.next
return head
tmp = tmp.next
return head
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
slow,fast = head,head
t = 0
while fast:
if t >= k: slow = slow.next
fast = fast.next
t += 1
return slow
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
preNode = None
curNode = head
while curNode:
nextNode = curNode.next
curNode.next = preNode
preNode = curNode
curNode = nextNode
return preNode
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
cur = dum = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
cur.next,l1 = l1,l1.next
else:
cur.next,l2 = l2,l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dum.next
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
def recur(A,B):
if not B: return True
if not A or A.val != B.val:return False
return recur(A.left,B.left) and recur(A.right,B.right)
return bool(A and B) and (recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def mirrorTree(self, root: TreeNode) -> TreeNode:
if not root: return
stack = [root]
while stack:
node = stack.pop()
if node.left:stack.append(node.left)
if node.right:stack.append(node.right)
node.left,node.right = node.right,node.left
return root
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
def recur(L,R):
if not L and not R:return True
if not L or not R or L.val != R.val:return False
return recur(L.left,R.right) and recur(L.right,R.left)
return recur(root.left,root.right) if root else True
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix : return []
l,r,t,b,res = 0,len(matrix[0])-1,0,len(matrix)-1,[]
while True:
for i in range(l,r+1):res.append(matrix[t][i])
t += 1
if t > b:break
for i in range(t,b+1):res.append(matrix[i][r])
r -= 1
if l > r:break
for i in range(r,l-1,-1):res.append(matrix[b][i])
b -= 1
if t > b:break
for i in range(b,t-1,-1):res.append(matrix[i][l])
l += 1
if l > r:break
return res
class Solution:
def verifyPostorder(self, postorder: List[int]) -> bool:
def recur(i,j):
if i >= j:return True
p = i
while postorder[p] < postorder[j]: p += 1
m = p
while postorder[p] > postorder[j]: p += 1
return p == j and recur(i,m-1) and recur(m,j-1)
return recur(0,len(postorder)-1)
class Solution:
def permutation(self, s: str) -> List[str]:
c = list(s)
res = []
def dfs(x):
if x == len(c)-1:
res.append(''.join(c))
setc = set()
for i in range(x,len(c)):
if c[i] in setc: continue
setc.add(c[i])
c[x],c[i] = c[i],c[x]
dfs(x+1)
c[i],c[x] = c[x],c[i]
dfs(0)
return res
class Solution:
def majorityElement(self, nums: List[int]) -> int:
votes = 0
for num in nums:
if votes == 0:x = num
if x == num : votes += 1
else : votes -= 1
return x
import heapq
class Solution:
def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
if k == 0: return []
hq = [-x for x in arr[:k]]
heapq.heapify(hq)
for i in range(k,len(arr)):
if -hq[0] > arr[i]:
heapq.heappop(hq)
heapq.heappush(hq,-arr[i])
ans = [-x for x in hq]
return ans
class MedianFinder:
def __init__(self):
"""
initialize your data structure here.
"""
self.A = []
self.B = []
def addNum(self, num: int) -> None:
if len(self.A) != len(self.B):
heapq.heappush(self.A,num)
heapq.heappush(self.B,-heapq.heappop(self.A))
else:
heapq.heappush(self.B,-num)
heapq.heappush(self.A,-heapq.heappop(self.B))
def findMedian(self) -> float:
return self.A[0] if len(self.A) != len(self.B) else (self.A[0] - self.B[0]) / 2
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0] * len(nums)
dp[0] = nums[0]
for i in range(1,len(nums)):
if dp[i-1] > 0:
dp[i] = dp[i-1] + nums[i]
else:
dp[i] = nums[i]
return max(dp)
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1,len(nums)):
nums[i] += max(nums[i-1],0)
return max(nums)
class Solution:
def minNumber(self, nums: List[int]) -> str:
def quick_sort(l,r):
if l >= r :return
i,j = l,r
while i < j:
while strs[j] + strs[l] >= strs[l] + strs[j] and i < j : j -= 1
while strs[i] + strs[l] <= strs[l] + strs[i] and i < j : i += 1
strs[i],strs[j] = strs[j],strs[i]
strs[i],strs[l] = strs[l],strs[i]
quick_sort(l,i-1)
quick_sort(i+1,r)
strs = [str(num) for num in nums]
quick_sort(0,len(nums)-1)
return "".join(strs)
class Solution:
def maxValue(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
for j in range(1,n):
grid[0][j] += grid[0][j-1]
for i in range(1,m):
grid[i][0] += grid[i-1][0]
for i in range(1,m):
for j in range(1,n):
grid[i][j] += max(grid[i-1][j],grid[i][j-1])
return grid[-1][-1]
