LeetCode-初级算法-数组

发表于   |     |   阅读次数

数组

从排序数组中删除重复项

关键词：排序 原地修改输入数组

思路：将重复元素与第一个非重复的元素值交换，保存当前最后一个非重复值的 index。该 index 即数组的长度。

  • Swift5

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    func removeDuplicates(_ nums: inout [Int]) -> Int {
        if nums.count <= 1 {
            return nums.count
        }
        
        var cIndex = 1
        var cIndexValue = nums[0]
        
        for index in 1..<nums.count {
            if nums[index] != cIndexValue {
                (nums[cIndex], nums[index]) = (nums[index], nums[cIndex])
                cIndexValue = nums[cIndex]
                cIndex += 1
            }
        }
        
        return cIndex
    }

  • Python3 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def removeDuplicates(self, nums: [int]) -> int:
        if len(nums) <= 1:
            return len(nums)
        
        cIndex = 1
        cIndexValue = nums[0]
        
        for index in range(1, len(nums)):
            if nums[index] != cIndexValue:
                nums[index], nums[cIndex] = nums[cIndex], nums[index]
                cIndexValue = nums[cIndex]
                cIndex += 1
        return cIndex

买卖股票的最佳时机 II

关键词：最大利润 不能同时参与多笔交易

思路：计算每个峰值，将峰值累加即为最大利润

  • Swift5

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    func maxProfit(_ prices: [Int]) -> Int {
        if prices.count <= 1 {
            return 0
        }
        
        var maxProfit = 0
        
        for index in 1..<prices.count {
            if prices[index] > prices[index - 1] {
                maxProfit += prices[index] - prices[index - 1]
            }
        }
        return maxProfit
    }

  • Python3

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def maxProfit(self, prices: [int]) -> int:
        if len(prices) <= 1:
            return 0
        
        max_profit = 0
        for index in range(1, len(prices)):
            if prices[index] > prices[index - 1]:
                max_profit += prices[index] - prices[index - 1]
        
        return max_profit

旋转数组

思路：依次将最后一个元素插入到数组当做第一个元素，再将最后一个元素移除

  • Swift5

    1
    2
    3
    4
    5
    6
    7
    8
    func rotate(_ nums: inout [Int], _ k: Int) {
        var count = k % nums.count
        while count > 0 {
            nums.insert(nums.last!, at: 0)
            nums.removeLast()
            count -= 1
        }
    }

  • Python3

    1
    2
    3
    4
    5
    6
    def rotate(self, nums: [int], k: int):
        count = k % len(nums)
        
        while count > 0:
            nums.insert(0, nums.pop())
            count -= 1

存在重复

思路：利用 Set 数据结构

  • Swift5

    1
    2
    3
    func containsDuplicate(_ nums: [Int]) -> Bool {
        return Set(nums).count != nums.count
    }

  • Python3

    1
    2
    def containsDuplicate(self, nums: [int]) -> bool:
        return len(set(nums)) != len(nums)

只出现一次的数字

思路：利用异或操作符: ^

  • Swift5

    1
    2
    3
    4
    5
    6
    7
    func singleNumber(_ nums: [Int]) -> Int {
        var result = 0
        for num in nums {
            result = result ^ num
        }
        return result
    }

  • Python3

    1
    2
    3
    4
    5
    def singleNumber(nums: [int]) -> int:
        result = 0
        for num in nums:
            result = result ^ num
        return result

两个数组的交集 II

思路：先排序，再用快慢指针法

  • Swift5

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
        var result = [Int]()
        var tNum1 = nums1.sorted()
        var tNum2 = nums2.sorted()
        
        var i = 0
        var j = 0
        
        while i < tNum1.count && j < tNum2.count {
            if tNum1[i] > tNum2[j] {
                j += 1
            } else if tNum1[i] < tNum2[j] {
                i += 1
            } else {
                result.append(tNum1[i])
                
                i += 1
                j += 1
            }
        }
        
        return result
    }

  • Python3

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def intersect(nums1: [int], nums2: [int]) -> [int]:
        l1 = sorted(nums1)
        l2 = sorted(nums2)
        res = []
        i = 0
        j = 0
        while i < len(l1) and j < len(l2):
        if l1[i] > l2[j]:
            j += 1
        elif l1[i] < l2[j]:
            i += 1
        else:
            res.append(l1[i])
            i += 1
            j += 1
        return res

加一

思路：遍历

  • Swift5

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    func plusOne(_ digits: [Int]) -> [Int] {
        var result = [Int]()
        var carry = 1
        
        for i in 0..<digits.count {
            let num = digits[digits.count - i - 1]
            
            if num + carry == 10 {
                result.insert(0, at: 0)
                if i == digits.count - 1 {
                    result.insert(1, at: 0)
                }
            } else {
                result.insert(num + carry, at: 0)
                carry = 0
            }
        }
        
        return result
    }

  • Python3

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def plusOne(digits: [int]) -> [int]:
        res = []
        carry = 1
        for i in range(len(digits)):
            num = digits[len(digits) - i - 1]
            if num + carry == 10:
                res.insert(0, 0)
                if i == len(digits) - 1:
                    res.insert(0, 1)
            else:
                res.insert(0, num + carry)
                carry = 0
        return res

移动零

思路：快慢指针

  • Swift5

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    func moveZeroes(_ nums: inout [Int]) {
        var fast = 0
        var slow = 0
        while fast < nums.count && slow < nums.count {
            if nums[fast] == 0 {
                fast += 1
            } else {
                if slow != fast {
                    (nums[slow], nums[fast]) = (nums[fast], nums[slow])
                }
                slow += 1
                fast += 1
            }
        }
    }

  • Python3

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def moveZeroes(nums: [int]):
        fast = 0
        slow = 0
        length = len(nums)
        while fast < length and slow < length:
        if nums[fast] == 0:
            fast += 1
        else:
            if slow != fast:
                nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1
            fast += 1

两数之和

思路：利用字典的数据结构

  • Swift5

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var dict = [Int : Int]()
        for (i, num) in nums.enumerated() {
            if let value = dict[target - num] {
                return [value, i]
            } else {
                dict[num] = i
            }
        }
        
        return []
    }

  • Python3

    1
    2
    3
    4
    5
    6
    7
    8
    def twoSum(nums: [int], target: int) -> [int]:
        kv = {}
        for i, v in enumerate(nums):
            if target - v in kv:
                return [kv[target - v], i]
            else:
                kv[v] = i
        return []

有效的数独

思路：按每行、每列、每个3x3判断 (Swift 版)。Python3为官方解题思路

  • Swift5

    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
    38
    39
    40
    41
    42
    43
    44
    45
    func isValidSudoku(_ board: [[Character]]) -> Bool {
        // 每一行
        for chars in board {
            var tChars = chars
            tChars.removeAll(where: { $0 == "."})
            if tChars.count != Set(tChars).count {
            return false
            }
        }
        //每一列
        for i in 0..<9 {
            var column = [Character]()
            for j in 0..<9 {
                if board[j][i] != "." {
                    column.append(board[j][i])
                }
            }
            if column.count != Set(column).count {
                return false
            }
        }
        //每个3x3
        var t = [Character]()
        var count = 0
        
        for i in 0..<9 {
            for j in 0..<9 {
                let x = 3 * (i/3) + j/3
                let y = 3 * (i%3) + j%3
                if board[x][y] != "." {
                    t.append(board[x][y])
                }
                count += 1
                if count == 9 {
                    if t.count != Set(t).count {
                        t.removeAll()
                        return false
                    }
                    t.removeAll()
                    count = 0
                }
            }
        }
        return true
    }

  • Python3

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # init data
        rows = [{} for i in range(9)]
        columns = [{} for i in range(9)]
        boxes = [{} for i in range(9)]
        # validate a board
        for i in range(9):
            for j in range(9):
                num = board[i][j]
                if num != '.':
                    num = int(num)
                    box_index = (i // 3 ) * 3 + j // 3
                        
                    # keep the current cell value
                    rows[i][num] = rows[i].get(num, 0) + 1
                    columns[j][num] = columns[j].get(num, 0) + 1
                    boxes[box_index][num] = boxes[box_index].get(num, 0) + 1
                        
                    # check if this value has been already seen before
                    if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
                        return False         
        return True

旋转图像

思路：官方题解

  • Swift5

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    func rotate(_ matrix: inout [[Int]]) {
        let n = matrix[0].count
        for i in 0..<(n / 2 + n % 2) {
            for j in 0..<(n / 2) {
                let tmp = matrix[n - 1 - j][i]
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1]
                matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 - i]
                matrix[j][n - 1 - i] = matrix[i][j]
                matrix[i][j] = tmp
            }
        }
    }

  • Python3

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix[0])
        for i in range(n // 2 + n % 2):
            for j in range(n // 2):
                tmp = [0] * 4
                row, col = i, j
                # store 4 elements in tmp
                for k in range(4):
                    tmp[k] = matrix[row][col]
                    row, col = col, n - 1 - row
                # rotate 4 elements   
                for k in range(4):
                    matrix[row][col] = tmp[(k - 1) % 4]
                    row, col = col, n - 1 - row