w4irdo / leetcode_practice Goto Github PK

View Code? Open in Web Editor NEW

1.0 1.0 0.0 8 KB

Step by step!

leetcode_practice's People

Contributors

Stargazers

leetcode_practice's Issues

206. Reverse Linked List

# 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:
        """
        :type head: ListNode
        :rtype: ListNode
        """
        prev_node = None
        curr_node = head
        while curr_node:
            next_node = curr_node.next
            curr_node.next = prev_node
            prev_node = curr_node
            curr_node = next_node
        head = prev_node
        return head

91. Decode Ways

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0' ? 0 : 1;
        
        for (int i = 2; i <= n; ++i) {
            int first = Integer.valueOf(s.substring(i - 1, i));
            if (first != 0) {
                dp[i] += dp[i - 1];
            }
            if (s.charAt(i - 2) == '0') {
                continue;
            }
            
            int second = Integer.valueOf(s.substring(i - 2, i));
            if (second >= 10 && second <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        
        return dp[n];
    }
}

378. Kth Smallest Element in a Sorted Matrix

# Java 二分查找法
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        int lo = matrix[0][0], hi = matrix[m-1][n-1];
        
        while (lo <= hi){
            int mid = lo + (hi - lo) / 2;
            int cnt = 0;
            for (int i = 0;i < m; i++){
                for (int j = 0; j < n && matrix[i][j] <= mid; j++){
                    cnt++;
                }
            }
            if (cnt < k) lo = mid + 1; 
            else hi = mid - 1;
        }
        return lo;
    }
}

# Java 堆解法

566. Reshape the Matrix

# Python 1
import numpy as np
class Solution:
    def matrixReshape(self, nums: List[List[int]], r: int, c: int) -> List[List[int]]:
        try:
            return np.reshape(nums, [r, c]).tolist()
        except:
            return nums

# Python 2
class Solution:
    def matrixReshape(self, nums: List[List[int]], r: int, c: int) -> List[List[int]]:
        """
        :type nums: List[List[int]]
        :type r: int
        :type c: int
        :rtype: List[List[int]]
        """
        if nums is None:
            return None
        i = len(nums)
        j = len(nums[0])
        if r * c != i * j:
            return nums
        
        tem = []
        re = []
        for row in range(i):
            for col in range(j):
                tem.append(nums[row][col])
        
        for ind in range(0, r*c, c):
            re.append(tem[ind:ind+c])
        
        return re

# Java
class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        int m = nums.length;
        int n = nums[0].length;
        if (m * n != r * c){
            return nums;
        }
        
        int index = 0;
        int [][] reshapedNums = new int[r][c];
        
        for(int i = 0; i < r; i++){
            for(int j = 0;j < c; j++){
                reshapedNums[i][j] = nums[index / n][index % n];
                index++;
            }
        }
        
        return reshapedNums;
    }
}

Python 版，用到矩阵，Numpy 直接解决不在话下；Python 2 版本要快很多。
Java 版：reshapedNums[i][j] = nums[index / n][index % n]理解透蛮关键的。

226. Invert Binary Tree

# 1. recursively

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root:
            invert = self.invertTree
            root.left, root.right = invert(root.right), invert(root.left)
        return root

# 2. DFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                node.left, node.right = node.right, node.left
                stack.extend([node.right, node.left])
        return root

# 3. BFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        queue = collections.deque([(root)])
        while queue:
            node = queue.popleft()
            if node:
                node.left, node.right = node.right, node.left
                queue.append(node.left)
                queue.append(node.right)
        return root

递归易懂，但实在是太慢。深度优先算法达到超过 99% 的提交。广度优先比深度优先慢点儿，也比递归好。

136. Single Number

# 1
from functools import reduce


class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        """
        Ltype nums: List[int]
        :rtype: int
        """
        return reduce(lambda x,y: x ^ y, nums)

# 2
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        """
        Ltype nums: List[int]
        :rtype: int
        """
        return 2 * sum(set(nums)) - sum(nums)

reduce() 是 Python 的内置函数，但在 Python3 开始，需要调包。在 lambda 函数里面，运用了异或运算符进行计算。
方法 2 是数学方法，有些讨巧。

283. Move Zeroes

# Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

# Python 1

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        type nums: List[int]
        Do not return anything, modify nums in-place instead.
        """
        count = nums.count(0)
        nums[:] = [i for i in nums if i != 0]
        nums += [0] * count

# Python 2

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        type nums: List[int]
        Do not return anything, modify nums in-place instead.
        """
        j = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[i], nums[j] = nums[j], nums[i]
                j += 1

nums[:] 属于浅拷贝。列表内的元素内存地址并未发生改变。

645. Set Mismatch

class Solution {
    public int[] findErrorNums(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            while(nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]){
                swap(nums, i, nums[i] - 1);
            }
        }
        
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != i + 1){
                return new int[]{nums[i], i + 1};
            }
        }
        
        return null;
    }
    
    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        for i, num in enumerate(nums):
            while nums[i] != i + 1 and nums[nums[i] - 1] != nums[i]:
                tmp = nums[i]
                nums[i] = nums[tmp - 1]
                nums [tmp - 1] = tmp
                
        for i, num in enumerate(nums):
            if num == i + 1:
                continue
            return [num, i+1]

485. Max Consecutive Ones

# Java
class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int max = 0, cur = 0;
        for(int x: nums){
            cur = x == 0 ? 0 : cur + 1;
            max = Math.max(max, cur);
        }
        return max;
    }
}

# Python 1
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        """
        :type nums: List[int]
        :rtype: int
        """
        
        count = 0
        maxCount = 0
        for num in nums:
            if num == 1:
                count += 1
            else:
                maxCount = max(count, maxCount)
                count = 0
                
        return max(count, maxCount)

# Python 2
class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        """
        :type nums: List[int]
        :rtype: int
        """
        
        count = 0
        ans = []
        
        for num in nums:
            if num == 1:
                count += 1
            else:
                ans.append(count)
                count = 0
                
        ans.append(count)
        return max(ans)

Python 2 优于 Python 1。

617. Merge Two Binary Trees

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode
        """
        if t1 and t2:
            t1.val += t2.val
            t1.left = self.mergeTrees(t1.left, t2.left)
            t1.right = self.mergeTrees(t1.right, t2.right)
            return t1
        else:
            return t1 or t2

递归

240. Search a 2D Matrix II

# Java

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        int row = 0, col = n - 1;
        while(row <= m-1 && col >= 0){
            if(target == matrix[row][col]) return true;
            else if(target < matrix[row][col]) col--;
            else row++;
        }
        return false;
    }
}

# Python

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        m = len(matrix)
        n = len(matrix[0]) 
        row, col = 0, n-1
        while row <= m-1 and col >= 0:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                col -= 1
            else:
                row += 1
        return False

771. Jewels and Stones

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        setJ = set(J)
        return sum(s in setJ for s in S)

343. Integer Break

# 动态规划
class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j < i; j++)
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)));
        return dp[n];
    }
}

# 贪心
class Solution {
    public int integerBreak(int n) {
        if (n < 2)
            return 0;
        if (n == 2)
            return 1;
        if (n == 3)
            return 2;
        int timeOf3 = n / 3;
        if (n - timeOf3 * 3 == 1)
            timeOf3--;
        int timeOf2 = (n - timeOf3 * 3) / 2;
        return (int) (Math.pow(3, timeOf3)) * (int) (Math.pow(2, timeOf2));
    }
}

104. Maximum Depth of Binary Tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

递归

1. Two Sum

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}
        for i,n in enumerate(nums):
            m = target - n
            if m in dict:
                return [dict[m], i]
            else:
                dict[n] = i

遍历数组，然后用字典建立值和键的映射。

w4irdo / leetcode_practice Goto Github PK

leetcode_practice's People

Contributors

Stargazers

leetcode_practice's Issues

Recommend Projects

Recommend Topics

Recommend Org