算法题002

January 11, 2020

链表

成对翻转

1->2->3->4 ==> 2->1->4->3

public Node swapNodePair(Node head){
    Node newHead = new Node(0);
    newHead.next = head;
    Node pre = newHead;

    while(pre.next != null && pre.next.next != null){
        Node n1 = pre.next;
        Node n2 = pre.next.next;
        Node n3 = pre.next.next.next;

        pre.next = n2;
        pre.next.next = n1;
        pre.next.next.next = n3;
        pre = pre.next.next;
    }

    return newHead.next;
}

LeetCode 141. Linked List Cycle

def hasCycle(self, head: ListNode) -> bool:
    p1, p2 = head, head

    while p2 and p2.next:
        p1 = p1.next
        p2 = p2.next.next
        if p1 == p2:
            return True
    return False

栈和队列

LeetCode 20. Valid Parentheses

def isValid(self, s: str) -> bool:
    stack = []
    
    for c in s:
        if c == '(' or c == '[' or c == '{':
            stack.append(c)
        if c == ')' and (len(stack) == 0 or stack.pop() != '('):
            return False
        if c == ']' and (len(stack) == 0 or stack.pop() != '['):
            return False
        if c == '}' and (len(stack) == 0 or stack.pop() != '{'):
            return False
            
    return len(stack) == 0

def isValid2(self, s: str) -> bool:
    stack = []
    param_map = {')':'(', ']':'[', '}':'{'}

    for c in s:
        if c not in param_map:
            stack.append(c)
        elif not stack or stack.pop() != param_map[c]:
            return False
    return not stack

优先队列

LeetCode 703. Kth Largest Element in a Stream

class KthLargest {
    private int k;
    private PriorityQueue<Integer> minHead;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.minHead = new PriorityQueue<>(k);
        for (int i : nums) {
            add(i);
        }
    }

    public int add(int val) {
        if (minHead.size() < k) {
        minHead.offer(val);
        } else if (minHead.peek() < val) {
        minHead.poll();
        minHead.offer(val);
        }

        return minHead.peek();
    }
}

Map 和 Set

LeetCode 242. Valid Anagram

def isAnagram(self, s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    
    map1 = {}
    for c in s:
        if c in map1:
            map1[c] = map1[c] + 1
        else:
            map1[c] = 1
            
    for c in t:
        if c in map1 and map1[c] > 0:
            map1[c] = map1[c] - 1
            if map1[c] == 0:
                map1.pop(c)
        else:
            return False
    
    return len(map1) == 0

LeetCode 1. two sum

def twoSum(self, nums: List[int], target: int) -> List[int]:
    hashmap = {}
    
    for i, v in enumerate(nums):
        n = target - v
        if n in hashmap:
            return [i, hashmap[n]]
        hashmap[v] = i

Tree

LeetCode 103. Binary Tree Zigzag Level Order Traversal

def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
    q = []
    q.append(root)
    need_reverse = False
    
    res = []
    
    while True:
        t = []
        q2 = []
        
        while q:
            n = q.pop(0)
            if n:
                t.append(n.val)
                q2.append(n.left)
                q2.append(n.right)
            
        q = q2
        
        if t:
            if need_reverse:
                t.reverse()
                res.append(t)
            else:
                res.append(t)
            need_reverse = not need_reverse
        else:
            break
    
    return res

LeetCode 98. Validate Binary Search Tree

def isValidBST(self, root: TreeNode) -> bool:
    def isValid(n, l, h):
        if not n:
            return True
        if h != None and (n.val > h or n.val == h):
            return False
        if l != None and (n.val < l or n.val == l):
            return False

        return isValid(n.left, l, n.val) and isValid(n.right, n.val, h)
    return isValid(root, None, None)

LeetCode 235. Lowest Common Ancestor of a Binary Search Tree

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if root == None or root == p or root == q:
        return root
    
    n1 = self.lowestCommonAncestor(root.left, p, q)
    n2 = self.lowestCommonAncestor(root.right, p, q)
    
    if n1 == None:
        return n2
    if n2 == None:
        return n1
    return root

LeetCode 50. Pow(x, n)

def myPow(self, x: float, n: int) -> float:
    if not n:
        return 1
    if n < 0:
        return 1 / self.myPow(x, -n)
    if n % 2:
        return x * self.myPow(x, n-1)
    return self.myPow(x*x, n/2)

LeetCode 169. Majority Element

def majorityElement(self, nums: List[int]) -> int:
    m = {}
    for n in nums:
        if n not in m:
            m[n] = 1
        else:
            m[n] = m[n] + 1
    max_v = None
    for v in m:
        if max_v == None or m[max_v] < m[v]:
            max_v = v
    
    return max_v

贪心

122. Best Time to Buy and Sell Stock II

def maxProfit(self, prices: List[int]) -> int:
    pre = -1
    sum = 0
    
    for cur in prices:
        if pre != -1 and cur > pre:
            sum += cur - pre
        pre = cur
    
    return sum

广度优先搜索（BFS）

LeetCode 102. Binary Tree Level Order Traversal

def levelOrder(self, root: TreeNode) -> List[List[int]]:
    if not root: return []
    res = []
    
    q = []
    q.append(root)
    while q:
        l = len(q)
        t = []
        
        for _ in range(l):
            n = q.pop(0)
            t.append(n.val)
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
        
        res.append(t)
    
    return res

# dfs

def levelOrder(self, root: TreeNode) -> List[List[int]]:
    def _dfs(n, level):
        if not n: return
        
        if len(res) < level + 1:
            res.append([])
            
        res[level].append(n.val)
        
        _dfs(n.left, level + 1)
        _dfs(n.right, level + 1)
    
    if not root: return []
    res = []
    _dfs(root, 0)
    
    return res

LeetCode 127. Word Ladder

LeetCode 104. Maximum Depth of Binary Tree

def maxDepth(self, root: TreeNode) -> int:
    if not root:
        return 0
    
    return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

LeetCode 22. Generate Parentheses

def generateParenthesis(self, n: int) -> List[str]:
    def _gen(l, r, s):
        if l == n and r == n:
            res.append(s)
            return
        if l < n:
            _gen(l + 1, r, s + '(')
        if r < n and l > r:
            _gen(l, r + 1, s + ')')
    
    res = []
    _gen(0, 0, '')
    return res

剪支

LeetCode 51, 52 N Queens

LeetCode 36, 37 Sudoku

二分查找

要求：

有序
存在上界、下界
能够通过索引访问

LeetCode 69. Sqrt(x)

def mySqrt(self, x: int) -> int:
    h, l = x, 1

    while l <= h:
        m = (l + h)  // 2
        if m*m < x:
            l = m + 1
        elif m*m > x:
            h = m - 1
        else:
            return m
    
    return h

字典数

动态规划

递归 + 记忆化 -> 递推
状态方程
状态转移方程
最优子结构

LeetCode 120. Triangle

def minimumTotal(self, t: List[List[int]]) -> int:
    for i in range(len(t)-1, 0, -1):
        for j in range(len(t[i])-1):
            t[i-1][j] = t[i-1][j] + min(t[i][j], t[i][j+1])
    return t[0][0]

def minimumTotal(self, t: List[List[int]]) -> int:
    res = t[-1]
    for i in range(len(t)-2, -1, -1):
        for j in range(len(t[i])):
            res[j] = t[i][j] + min(res[j], res[j+1])
    return res[0] 

LeetCode 152. Maximum Product Subarray

def maxProduct(self, nums: List[int]) -> int:
    if nums is None: return 0
    
    dp = [[0 for _ in range(2)] for _ in range(2)]
    
    dp[0][0], dp[0][1], res = nums[0], nums[0], nums[0]
    
    for i in range(1, len(nums)):
        x, y = i % 2, (i-1) % 2
        dp[x][0] = max(dp[y][0]*nums[i], dp[y][1]*nums[i], nums[i])
        dp[x][1] = min(dp[y][0]*nums[i], dp[y][1]*nums[i], nums[i])
        res = max(res, dp[x][0])
    
    return res