[leetcode]第七部分

33-Search in Rotated Sorted Array

问题描述

假设一个升序数组在某个我们不知道的轴点被交换了。(例如:[0,1,2,4,5,6,7]变成了[4,5,6,7,0,1,2])。

给定一个待搜索的目标数。如果存在于数组中,则返回其索引,否则返回-1

可以假定数组中没有重复值。

算法的时间复杂度必须限制在O(log n)以内。

示例1

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

示例2

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

解题思路

算法的时间复杂度控制在O(log n),不难想到应该使用二分法。本题应该考虑是:有序数组的二分查找。分两种情况:

  • 如果轴点已经找到,那么直接使用二分法
  • 否则,继续向两端使用二分法

代码

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        return self.binarySearch(nums, target, 0, len(nums)-1, False)

    def binarySearch(self, nums, target, l, r, isPivot):
        if r < l:
            return -1
        mid = (l+r)/2
        if nums[mid] == target:
            return mid
        else:
            if isPivot:
                if nums[mid] < target:
                    return self.binarySearch(nums, target, mid+1, r, isPivot)
                else:
                    return self.binarySearch(nums, target, l, mid-1, isPivot)
            else:
                isPivot = self.checkPivot(nums, mid)
                lIdx = self.binarySearch(nums, target, l, mid-1, isPivot)
                if lIdx >= 0:
                    return lIdx
                else:
                    rIdx = self.binarySearch(nums, target, mid+1, r, isPivot)
                    return rIdx

    def checkPivot(self, nums, mid):
        if mid == 0 or mid == len(nums)-1:
            return False
        if nums[mid-1] < nums[mid] < nums[mid+1]:
            return False
        else:
            return True

34-Find First and Last Position of Element in Sorted Array

问题描述

给定一个升序排列的整数数组nums,找到给定target值的起始位置和终止位置。

算法的时间复杂度必须在O(log n)内。

如果目标数值没有在数组中出现,返回[-1,-1]

示例1

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

示例2

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

解题思路

算法复杂度限制在O(log n),首先想到使用二分查找。使用三个指针:leftrightmid=(left+right)/2

  • 如果nums[mid] > target,那么right=mid-1,继续遍历
  • 如果nums[mid] < target,那么left=mid+1,继续遍历
  • 否则,分别往前后找到第一个不等于target的值即可

代码

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = (l+r)/2
            if nums[mid] > target:
                r = mid - 1
            elif nums[mid] < target:
                l = mid + 1
            else:
                lIdx = self.searchLRRange(nums, target, l, mid, True)
                rIdx = self.searchLRRange(nums, target, mid, r, False)
                return [lIdx, rIdx]
        return [-1, -1]


    def searchLRRange(self, nums, target, l, r, isLeft=True):
        mid = (l+r)/2
        if r < l:
            return -1
        tmp = r
        if isLeft:
            tmp = l
        if mid == tmp:
            if nums[mid] == target:
                return mid
        if nums[mid] > target:
            return self.searchLRRange(nums, target, l, mid-1, isLeft)
        elif nums[mid] < target:
            return self.searchLRRange(nums, target, mid+1, r, isLeft)
        else:
            if isLeft:
                tmpIdx = self.searchLRRange(nums, target, l, mid-1, isLeft)
            else:
                tmpIdx = self.searchLRRange(nums, target, mid+1, r, isLeft)
            if tmpIdx == -1:
                return mid
            else:
                return tmpIdx**

35-Search Insert Position

问题描述

给定一个排好序的数组和一个目标值,如果发现目标值的话就返回其索引;如果没有发现,则返回如果其要插入需要插入的索引位置。

可以假设数组中无重复值。

示例1

Input: [1,3,5,6], 5
Output: 2

示例2

Input: [1,3,5,6], 2
Output: 1

示例3

Input: [1,3,5,6], 7
Output: 4

示例4

Input: [1,3,5,6], 0
Output: 0

解题思路

最简单的做法是:从前往后遍历,遇到第一个大于或等于target的值就停止计算。此时,算法复杂度为O(n)

如果想要将时间复杂度缩短到O(log n),可以考虑二分法求解,其实是希望找到有序数组中第一个大于或等于target的值。

  • 取中间的数,如果等于target,直接返回
  • 如果小于target,则左指针移动到mid+1
  • 如果大于target,那么得根据mid的值进行判断:
    • 如果mid小于1,那么直接返回0
    • 如果mid-1也大于target,则直接将右指针移动到mid-1
    • 如果mid-1等于target,直接返回mid-1
    • 如果mid-1小于targer,直接返回mid

时间复杂度为O(log n)

代码

解法1

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        for i in range(len(nums)):
            val = nums[i]
            if val == target:
                return i
            elif val > target:
                return i - 1
        return len(nums)

解法2

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        return self.searchRange(nums, target, 0, len(nums)-1)

    def searchRange(self, nums, target, l, r):
        if l > r:
            return l
        mid = (l+r)/2
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            if mid > 0:
                if nums[mid-1] == target:
                    return mid - 1
                elif nums[mid-1] > target:
                    return self.searchRange(nums, target, l, mid-1)
                else:
                    return mid
            else:
                return mid
        else:
            return self.searchRange(nums, target, mid+1, r)

36-Valid Sudoku

问题描述

判断9X9的数独是否有效。只有满足以下条件才能说明该数独为有效:

  • 每一行必须包含1-9的数字
  • 每一列必须包含1-9的数字
  • 每个3*3的子格必须包含1-9的数字


数独板可能只有部分填充,空格子使用字符.表示。

示例1

Input:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true

示例2

[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: false
解析: 与示例1相同, 除了第一列的第四行修改为了8,同一列中有两个8,因此为无效数独。

注意
– 数独(部分填充)也有可能是有效的,尽管不一定全部解出来
– 根据提到的规则,只有填充了的空格需要为有效
– 给定的数独只包含1-9.字符
– 给定的数独大小一般为9*9

解题思路

针对二维数组,分别检查三个条件是否均满足即可:
– 行
– 列
– 子块

此时,时间复杂度为O(n*n)

代码

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        num = len(board[0])
        for i in range(num):
            row = self.getRow(board, i)
            isValid = self.checkList(row)
            if not isValid:
                return False
        for j in range(num):
            column = self.getColumn(board, j)
            isValid = self.checkList(column)
            if not isValid:
                return False
        for i in range(0, num, num/3):
            for j in range(0, num, num/3):
                sub = self.getSubCub(board, i, j)
                isValid = self.checkList(sub)
                if not isValid:
                    return False
        return True

    def getRow(self, board, idx):
        if idx < len(board):
            return board[idx]
        return None

    def getColumn(self, board, idx):
        retList = list()
        for dataList in board:
            if idx >= len(dataList):
                return None
            else:
                retList.append(dataList[idx])
        return retList

    def getSubCub(self, board, rIdx, cIdx):
        retList = list()
        if rIdx + 2 >= len(board):
            return None
        retList = board[rIdx][cIdx: cIdx+3]
        retList += board[rIdx+1][cIdx: cIdx+3]
        retList += board[rIdx+2][cIdx: cIdx+3]
        return retList


    def checkList(self, dataList):
        tmpDict = dict()
        if len(dataList) != 9:
            return False
        for data in dataList:
            if data != ".":
                if data in tmpDict:
                    return False
                else:
                    tmpDict[data] = 1
        return True

37-Sudoku Solver

问题描述

编写一分代码通过填充空格字符来完成数独。

一个数独的解决方案必须满足下面的条件:
1-9中的每个字符每行必须只能出现一次
1-9中的每个字符每列必须只能出现异常
– 在每个3*3的子空格中1-9中的每个字符只能出现一次

使用字符.表示空格


答案

注意

  • 给定的数独只包含1-9.字符
  • 可以假设给定的数独只有唯一的一种解法
  • 给定的数独大小一般为9*9

解题思路

使用回溯法进行求解。针对未知的空格,找到所有满足 条件的元素,进行尝试,如果遇到不满足条件的,回溯;否则,继续执行,直到遇到满足条件的w

代码

class Solution(object):
    r3, r9, poss_dict = range(3), range(9), {str(i) for i in range(1,10)}

    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        self.solve(board)

    def solve(self, board):
        for i, row in enumerate(board):
            for j, char in enumerate(row):
                if char == ".":
                    for x in self.poss_dict - {row[k] for k in self.r9} - {board[k][j] for k in self.r9} \
                            - {board[i / 3 * 3 + m][j / 3 * 3 + n] for m in self.r3 for n in self.r3}:
                        board[i][j] = x
                        if self.solve(board):
                            return True
                        board[i][j] = "."
                    return False
        return True

38-Count and Say

问题描述

count-and-say序列是一个整数的序列,前5个序列如下:

1.     1
2.     11
3.     21
4.     1211
5.     111221

首先,第1个数:1,读作11,因此得到第二个序列11
而第三个数基于第二个数:21,因此,读作21
第四个数基于第三个数:1211,因此读作:1211

给定一个整数n,返回count-and-say序列的第n个数。

注意:该数表示为字符创形式

示例1

Input: 1
Output: "1"

示例2

Input: 4
Output: "1211"

输入限制:

1 <= n <= 30

解题思路

由于是个序列,因此只需要从1遍历到n即可,而针对前一个数:我们只需要统计出每个数出现的次数然后拼接起来即可。

代码

class Solution(object):

    seq_dict = dict()

    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        now_seq = "1"
        if n == 1:
            self.seq_dict[n] = now_seq
        if n in self.seq_dict:
            return self.seq_dict[n]
        pre_seq = now_seq
        for i in range(1, n):
            now_seq = self.countAndSayNext(pre_seq)
            self.seq_dict[i+1] = now_seq
            pre_seq = now_seq
        return now_seq

    def countAndSayNext(self, pre_seq):
        cur_num = 0
        seq_len = len(pre_seq)
        now_seq = ""
        i = 0
        while i < seq_len:
            tmp_num = pre_seq[i]
            while i < seq_len and tmp_num == pre_seq[i]:
                i += 1
                cur_num += 1
            now_seq += str(cur_num) + tmp_num
            cur_num = 0
        return now_seq

39-Combination Sum

问题描述

给定一个候选数的集合candidates)(没有重复数)和一个目标数target。找到candidates中所有和为target的唯一组合。

candidates中的同一个数字可以被使用无限次数。

注意

  • 所有数字(包括target)都为正整数
  • 答案集不要包括重复组合

示例1

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

示例2

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

解题思路

使用回溯法进行求解,从前到后进行遍历,直到和大于或等于target为止,向前回溯。

代码

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        total_com = list()
        self.backtrack(total_com, list(), candidates, target, 0)
        return total_com



    def backtrack(self, total_com, tmp_list, candidates, remain, start):
        if remain < 0:
            return False
        elif remain == 0:
            total_com.append(tmp_list[:len(tmp_list)])
            return False
        else:
            for i in range(start, len(candidates)):
                tmp_list.append(candidates[i])
                flag = self.backtrack(total_com, tmp_list, candidates, remain - candidates[i], i)
                tmp_list.pop()
                #remain = remain + candidates[i]
                if not flag:
                    break
            return True

mickey

记录生活,写给几十年后的自己。

发表评论

电子邮件地址不会被公开。 必填项已用*标注