LeetCode Records

Posted on Edited on Views: Word count in article: 2.7k Reading time ≈ 10 mins.

[1] Two Sum

Problem

https://leetcode.com/problems/two-sum/description/

Solution

  • Use enumeration or hash table.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashtable=dict()

        for i,a in enumerate(nums):
            if target-a in hashtable:
                return [hashtable[target-a],i]
            hashtable[a]=i
        
        return []

[20] Valid Parentheses

Problem

https://leetcode.com/problems/valid-parentheses/description/

Solution

  • If the stack is empty or the current character is the left half of a bracket ('(', '[', '{'), add the current character to the stack.
  • If the current bracket matches the top bracket on the stack, pop the top element of the stack.
  • If the stack is not empty and the current bracket does not match the top element of the stack, return False.
  • When the string traversal ends, if the stack is not empty, which means that there are unmatched brackets, returns False.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack=[]

        for i in s:
            if len(stack)==0 or i=='(' or i=='[' or i=='{':
                stack.append(i)
            elif stack[-1]=='(' and i==')':
                stack.pop()
            elif stack[-1]=='[' and i==']':
                stack.pop()
            elif stack[-1]=='{' and i=='}':
                stack.pop()
            else:
                return False
        
        return True if len(stack)==0 else False

[27] Remove Element

Problem

https://leetcode.com/problems/remove-element/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        a=0
        b=0

        while a<len(nums):
            if nums[a]!=val:
                nums[b]=nums[a]
                b+=1
            a+=1
        
        return b

[70] Climbing Stairs

Problem

https://leetcode.com/problems/climbing-stairs/description/

Solution

  • Fibonacci sequence: f(n)=f(n−1)+f(n−2)f(n)=f(n-1)+f(n-2). In order to save memory, f(n-1) and f(n-2) are saved by continuously updating a and b during the calculation process.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        a=1
        b=2

        # When n is 1 or 2, returns directly
        if n<=2:
            return n
        
        # Use a and b before the update to save the values ​​of f(n-2) and f(n-1) respectively
        for i in range(3,n+1):
            temp=b
            # After update, b=a+b, that is, f(n)=f(n-2)+f(n-1)
            b=a+b
            a=temp

[88] Merge Sorted Array

Problem

https://leetcode.com/problems/merge-sorted-array/description/

Solution

directly merge and sort
1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        nums1[m:]=nums2
        nums1.sort()
two pointers
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
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        final_list=[]
        p1,p2=0,0

        while p1<m or p2<n:
            # All elements in nums1 have been added, and only elements in nums2 need to be added
            if p1==m:
                final_list.append(nums2[p2])
                p2+=1
            # All elements in nums2 have been added, and only elements in nums1 need to be added
            elif p2==n:
                final_list.append(nums1[p1])
                p1+=1
            # Add elements with smaller values ​​first
            elif nums1[p1]<nums2[p2]:
                final_list.append(nums1[p1])
                p1+=1
            else:
                final_list.append(nums2[p2])
                p2+=1
        
        nums1[:]=final_list

[94] Binary Tree Inorder Traversal

Problem

https://leetcode.com/problems/binary-tree-inorder-traversal/description/

Solution

  • Left->root->right.
recursion solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        node_list=[]

        def inorder(root):
            if (not root):
                return None
                
            inorder(root.left)
            node_list.append(root.val)
            inorder(root.right)
        
        inorder(root)
        return node_list
stack solution
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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        node_list=[]
        stack=[root]

        while stack:
            if not root:
                return node_list

            while root.left:
                stack.append(root.left)
                root=root.left
            
            curr=stack.pop()
            node_list.append(curr.val)

            if curr.right:
                stack.append(curr.right)
                root=curr.right

        return node_list

[100] Same Tree

Problem

https://leetcode.com/problems/same-tree/description/

Solution

recursion solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: Optional[TreeNode]
        :type q: Optional[TreeNode]
        :rtype: bool
        """
        if p==None and q==None:
            return True
        elif p==None or q==None:
            return False
        elif p.val!=q.val:
            return False
        
        # When executing this step, the current nodes of the two binary trees must be the same, and continue to judge their child nodes
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

[112] Path Sum

Problem

https://leetcode.com/problems/path-sum/description/

Solution

recursion solution

While traversing the binary tree, calculate the sum of the node values for each path (from the root node to the leaf node).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def hasPathSum(self, root, targetSum):
        """
        :type root: Optional[TreeNode]
        :type targetSum: int
        :rtype: bool
        """
        if root==None:
            return False
        
        if root.left==None and root.right==None and root.val==targetSum:
            return True
        
        left_subtree=self.hasPathSum(root.left,targetSum-root.val)
        right_subtree=self.hasPathSum(root.right,targetSum-root.val)

        return left_subtree or right_subtree

[118] Pascal's Triangle

Problem

https://leetcode.com/problems/pascals-triangle/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        result=[]

        for i in range(numRows):
            curr_row=[]

            for j in range(0,i+1):
                # Generate ones at the beginning and end of the current row
                if j==0 or j==i:
                    curr_row.append(1)
                # Generate numbers in the middle of the current row
                else:
                    curr_row.append(result[i-1][j]+result[i-1][j-1])
            
            result.append(curr_row)
        
        return result

[145] Binary Tree Postorder Traversal

Problem

https://leetcode.com/problems/binary-tree-postorder-traversal/description/

Solution

  • Left->right->root.
recursion solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        node_list=[]

        def postorder(root):
            if (not root):
                return None

            postorder(root.left)
            postorder(root.right)
            node_list.append(root.val)
            
        postorder(root)
        return node_list
stack solution
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
35
36
37
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        node_list=[]
        stack=[]
        # When backtracking to the parent node, use prev to determine whether the last visited node is the right subtree
        prev=None

        while root or stack:
            while root:
                stack.append(root)
                root=root.left
            
            # The left subtree of the element popped from the stack must have been visited
            root=stack.pop()

            # Whether there is a right subtree, or whether the right subtree has been visited
            if not root.right or root.right==prev:
                node_list.append(root.val)
                # Update the access record
                prev=root
                root=None
            # Put the current node on the stack and visit its right subtree first
            else:
                stack.append(root)
                root=root.right

        return node_list

[169] Majority Element

Problem

https://leetcode.com/problems/majority-element/description/

Solution

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()

        # Round down
        return nums[len(nums)//2]

[181] Employees Earning More Than Their Managers

Problem

https://leetcode.com/problems/employees-earning-more-than-their-managers/description/

Solution

1
2
3
4
5
6
7
# Write your MySQL query statement below
SELECT
    a.Name AS 'Employee'
FROM 
    Employee AS a, Employee AS b
WHERE
    a.ManagerId=b.Id AND a.Salary>b.Salary;

[203] Remove Linked List Elements

Problem

https://leetcode.com/problems/remove-linked-list-elements/description/

Solution

  • Add a virtual head node so that you can unify the operation when deleting nodes, , and there is no need to do special processing when deleting the head node.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: Optional[ListNode]
        :type val: int
        :rtype: Optional[ListNode]
        """
        # Add a virtual head node
        virtual_head=ListNode(next=head)
        curr=virtual_head

        while(curr.next!=None):
            # Delete the cur.next node
            if (curr.next.val==val):
                curr.next=curr.next.next
            else:
                curr=curr.next
        
        return virtual_head.next

[206] Reverse Linked List

Problem

https://leetcode.com/problems/reverse-linked-list/description/

Solution

two pointers
  • One pointer (prevprev) indicates the previous node of the current node, and the other pointer (currcurr) indicates the current node.
  • Each time, the two pointers move back one step at the same time, and then reverse the link direction of the two adjacent nodes.
  • When moving to the end, prevprev is the head node of the reversed linked list, and currcurr is an empty node.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        prev,curr=None,head

        while curr!=None:
            # Save the next node of the current node in advance to avoid losing the next node
            next=curr.next
            # Reverse two adjacent nodes
            curr.next=prev

            # Update two pointers
            prev=curr
            curr=next
        
        return prev

[226] Invert Binary Tree

Problem

https://leetcode.com/problems/invert-binary-tree/description/

Solution

recursion solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: Optional[TreeNode]
        """
        if root==None:
            return root
        
        left_node=self.invertTree(root.left)
        right_node=self.invertTree(root.right)

        root.left,root.right=right_node,left_node

        return root

[234] Palindrome Linked List

Problem

https://leetcode.com/problems/palindrome-linked-list/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: bool
        """
        temp_list=[]

        if head==None:
            return True
        
        # Convert linked list to list
        while head.next!=None:
            temp_list.append(head.val)
            head=head.next
        temp_list.append(head.val)

        # Compare with the reversed list
        return temp_list==temp_list[::-1]

[283] Move Zeroes

Problem

https://leetcode.com/problems/move-zeroes/description/

Solution

Traverse the array from left to right. After finding the number that is zero, continue to find the first non-zero number behind it and exchange its position with it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums)-1):
           if nums[i]==0:
               for j in range(i+1,len(nums)):
                   # Find the first number that is not 0 and swap it
                   if nums[j]!=0:
                       nums[i]=nums[j]
                       nums[j]=0
                       break

[349] Intersection of Two Arrays

Problem

https://leetcode.com/problems/intersection-of-two-arrays/description/

Solution

solution 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        num_set=set(nums1)
        result=[]

        for x in nums2:
            if x in num_set:
                result.append(x)
                num_set.remove(x)
        
        return result
solution 2
1
2
3
4
5
6
7
8
class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        return list(set(nums1) & set(nums2))

[409] Longest Palindrome

Problem

https://leetcode.com/problems/longest-palindrome/description/

Solution

  • Letters that appear an even number of times can be added directly to the palindrome string.
  • Letters that are counted an odd number of times can only be added to the middle of the palindrome string, like the xx in aabbxbbaaaabbxbbaa.
  • If there are multiple letters that are counted an odd number of times, only one letter can be used in the palindrome string.
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
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        length=0
        odd_flag=False
        hash_count={}

        # Count the number of occurrences of all letters in the string
        for i in s:
            hash_count[i]=hash_count.get(i,0)+1
        
        # If the number of occurrences of the letter is even, just add it up, otherwise add (the number of occurrences - 1)
        for key in hash_count.keys():
            if hash_count[key]%2==0:
                length+=hash_count[key]
            else:
                length+=hash_count[key]-1
                odd_flag=True
        
        # If there is a letter that appears an odd number of times, it should be in the middle of the palindrome
        if odd_flag:
            length+=1
        
        return length

[414] Third Maximum Number

Problem

https://leetcode.com/problems/third-maximum-number/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def thirdMax(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # Sort the array in descending order
        nums.sort(reverse=True)
        count=1

        for i in range(1,len(nums)):
            if nums[i]!=nums[i-1]:
                count+=1

                if count==3:
                    return nums[i]
        
        # If there is no third largest number, return the largest number.
        return nums[0]

[485] Max Consecutive Ones

Problem

https://leetcode.com/problems/max-consecutive-ones/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count=0
        max_count=0

        for i,num in enumerate(nums):
            if num==1:
                count+=1
            else:
                max_count=max(max_count,count)
                count=0
        
        # The longest subarray of consecutive ones may appear at the end of the array
        max_count=max(max_count,count)
        return max_count

[617] Merge Two Binary Trees

Problem

https://leetcode.com/problems/merge-two-binary-trees/description/

Solution

  • If the corresponding nodes of the two binary trees are empty, the corresponding nodes of the merged binary tree are also empty.
  • If only one of the corresponding nodes of the two binary trees is empty, the corresponding node of the merged binary tree is the non-empty node.
  • If the corresponding nodes of both binary trees are not empty, the value of the corresponding node of the merged binary tree is the sum of the values of the corresponding nodes of the two binary trees.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def mergeTrees(self, root1, root2):
        """
        :type root1: Optional[TreeNode]
        :type root2: Optional[TreeNode]
        :rtype: Optional[TreeNode]
        """
        if not root1:
            return root2
        if not root2:
            return root1
        
        merged_node=TreeNode(root1.val+root2.val)
        merged_node.left=self.mergeTrees(root1.left,root2.left)
        merged_node.right=self.mergeTrees(root1.right,root2.right)

        return merged_node

Problem

https://leetcode.com/problems/binary-search/description/

Solution

  • This is the basic framework of binary search, and all other variants are based on this framework.

  • This algorithm can only find the index of the corresponding number. If there are repeated numbers in the array and you need to find the leftmost or rightmost index of the number, this algorithm is not applicable and some improvements need to be made based on this framework.

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):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left_index=0
        right_index=len(nums)-1

        while (left_index<=right_index):
            mid=left_index+(right_index-left_index)/2

            if (nums[mid]==target):
                return mid
            elif nums[mid]>target:
                right_index=mid-1
            elif nums[mid]<target:
                left_index=mid+1

[1013] Partition Array Into Three Parts With Equal Sum

Problem

https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum/description/

Solution

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
class Solution(object):
    def canThreePartsEqualSum(self, arr):
        """
        :type arr: List[int]
        :rtype: bool
        """
        arr_sum=sum(arr)

        # If the sum of the array is not divisible by 3, return False
        if arr_sum%3!=0:
            return False
        
        # After dividing the array into three equal parts, the sum of each part
        average=arr_sum//3

        temp_sum=0
        sum_list=[]

        for i in range(len(arr)):
            temp_sum+=arr[i]

            if temp_sum==average:
                # Record the sum of the first two parts
                sum_list.append(temp_sum)
                temp_sum=0

                # The remaining numbers in the array are counted in the third part
                if len(sum_list)==2 and i<len(arr)-1:
                    sum_3=sum(arr[i+1:])
                    sum_list.append(sum_3)

                    return sum_list[0]==sum_list[1] and sum_list[1]==sum_list[2]
        
        return False