python常见面试题

leetcode算法

2020-05-12  本文已影响0人  苦海飘摇

前言

*最近在做一些leetcode的算法题，我会将自己做过的算法题记录下来以供大家参考，如果查找不方便请看油猴插件实现简书网站左侧目录生成。

Ⅰ.数组

一、删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例：

给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

解答：

def removeDuplicates(nums) -> int:
    if len(nums) <= 1:
        return len(nums)
    s = 0
    for i in range(1, len(nums)):
        if nums[s] != nums[i]:
            s += 1
            nums[s] = nums[i]
    return s + 1

nums = [1, 2, 2, 3]
s = removeDuplicates(nums)
print(s, nums)

     

二、买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例：

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

提示：

解答：

def maxProfit(prices) -> int:
    e = 0
    for i in range(len(prices) - 1):
        if prices[i] < prices[i + 1]:
            e += prices[i + 1] - prices[i]
    return e

prices = [7, 1, 5, 3, 6, 4]
print(maxProfit(prices))

     

三、旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例：

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

说明:

解答：

def rotate(nums, k: int) -> None:
    length = len(nums)
    k = k % length
    if k <= 0 or length <= 1:
        return
    nums[:] = nums[length - k:] + nums[:length - k]

nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
rotate(nums, k)
print(nums)

     

四、存在重复元素

给定一个整数数组，判断是否存在重复元素。
如果任意一值在数组中出现至少两次，函数返回true。如果数组中每个元素都不相同，则返回false。

示例：

输入: [1,2,3,1]
输出: true

输入: [1,2,3,4]
输出: false

解答：

def containsDuplicate(nums):
    if len(nums) <= 1:
        return False
    return len(nums) != len(set(nums))

nums = [1,2,3,1]
print(containsDuplicate(nums))

     

五、只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例：

输入: [2,2,1]
输出: 1

解答：

def singleNumber(nums) -> int:
    c = 0
    for i in nums:
        c ^= i
    return c

nums = [2, 3, 3]
print(singleNumber(nums))

     

六、两个数组的交集 II

给定两个数组，编写一个函数来计算它们的交集。

示例：

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]

说明：

进阶:

解答：

def intersect(nums1, nums2):
    r1 = {}
    r2 = {}

    for i in nums1:
        r1[i] = 1 if i not in r1.keys() else r1[i] + 1

    for i in nums2:
        r2[i] = 1 if i not in r2.keys() else r2[i] + 1

    k = set([i for i in r1.keys()]) & set([i for i in r2.keys()])
    r = []
    for i in k:
        r.extend([i] * min(r1[i], r2[i]))
    return r

nums1 = [1, 2, 2, 1]
nums2 = [2, 2]
print(intersect(nums1, nums2))

     

七、加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

示例：

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

解答：

def plusOne(digits) -> List:
    l = len(digits)
        for i in range(l):
            digits[l - i - 1] += 1
            if digits[l - i - 1] != 10:
                return digits
            elif i == l - 1:
                digits[l - i - 1] = 0
                digits.insert(0, 1)
                return digits
            else:
                digits[l - i - 1] = 0

nums = [1, 2, 3]
print(plusOne(nums))

     

八、移动零

给定一个数组 nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

  1. 必须在原数组上操作，不能拷贝额外的数组。
  2. 尽量减少操作次数。
def moveZeroes(nums):
    count = nums.count(0)
    if count == 0:
        return
    for i in range(count):
        nums.remove(0)
    nums.extend([0] * count)

nums = [0, 1, 0, 3, 12]
moveZeroes(nums)
print(nums)

     

九、两数之和

给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例：

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解答：

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

nums = [2, 7, 11, 15]
target = 9
print(twoSum(nums, target))

     

十、有效的数独

判断一个9x9的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

  1. 数字1-9在每一行只能出现一次。
  2. 数字1-9在每一列只能出现一次。
  3. 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
    上图是一个部分填充的有效的数独

数独部分空格内已填入了数字，空白格用'.'表示。

示例：

输入:
[
  ["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"]
]
输出: true

输入:
[
  ["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"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:

解答：

def isValidSudoku(board) -> bool:
    map1 = [{} for i in range(9)]  # 保存行中的数字
    map2 = [{} for i in range(9)]  # 保存列中的数字
    map3 = [{} for i in range(9)]  # 保存块中的数字
    for i in range(9):
        for j in range(9):
            if board[i][j] != '.':
                data = int(board[i][j])
                smallBoardi = (i // 3) * 3 + (j // 3)  # 每块的脚标，横向划分。

                # 当前单元格的值
                map1[i][data] = map1[i].get(data, 0) + 1
                map2[j][data] = map2[j].get(data, 0) + 1
                map3[smallBoardi][data] = map3[smallBoardi].get(data, 0) + 1

                # 检查这个值以前是否出现过
                if map1[i][data] > 1 or map2[j][data] > 1 or map3[smallBoardi][data] > 1:
                    return False
    return True

board = [["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"]]
print(isValidSudoku(board))

     

十一、旋转图像

给定一个*n *× *n*的二维矩阵表示一个图像。
将图像顺时针旋转90度。

说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例：

给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

解答：

def rotate(matrix):
    n = len(matrix)
    # 对角调换
    for i in range(n):
        for j in range(n - i):
            matrix[i][j], matrix[n - 1 - j][n - 1 - i] = matrix[n - 1 - j][n - 1 - i], matrix[i][j]
    # 列倒置
    for i in range(n):
        for j in range(n // 2):
            matrix[j][i], matrix[n - 1 - j][i] = matrix[n - 1 - j][i], matrix[j][i]

matrix = [
    [5, 1, 9, 11],
    [2, 4, 8, 10],
    [13, 3, 6, 7],
    [15, 14, 12, 16]
]
rotate(matrix)
print(matrix)

     

II、字符串

一、反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例：

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

解答：

def reverseString(s):
    s[:] = s[::-1]

s = ["h", "e", "l", "l", "o"]
reverseString(s)
print(s)

     

二、整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例：

输入: 123
输出: 321

输入: -123
输出: -321

输入: 120
输出: 21

注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

解答：

def reverse(x: int) -> int:
    # 个位数直接返回
    if abs(x) < 9:
        return x
    # 超过范围返回0
    elif not -2 ** 31 < x < 2 ** 31 - 1:
        return 0
    # 记录符号，将其转为无符号数
    elif x > 0:
        n = 1
    else:
        x = -x
        n = 0

    # 变成列表
    x = list(str(x))
    # 反转
    x[:] = x[::-1]
    # 去掉开头的0
    while x[0] == '0':
        x = x[1:]
    # 变成整数
    x = list(map(int, x))
    a = 0
    l = len(x)
    for i in range(l):
        a += x[i] * 10 ** (l - i - 1)
    # 反转后超过范围返回0，否则判断正负并返回
    return 0 if not -2 ** 31 < a < 2 ** 31 - 1 else a if n else -a

x = -1230
print(reverse(x))

     

三、字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例：

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

解答：

# 这个是我一开始的想法，测试后超时，怀疑count方法耗时大
'''
def firstUniqChar(s: str) -> int:
    s = list(s)
    for i in range(len(s)):
        if s.count(s[i]) > 1:
            continue
        else:
            return i
    return -1
'''

# 因此弃用count方法，需用in方法
def firstUniqChar(s: str) -> int:
    for i in range(len(s)):
        if s[i] not in s[i + 1:] and s[i] not in s[:i]:
            return i
    return -1

s = "leetcode"
print(firstUniqChar(s))

     

四、有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
长度一样，包含的字母都一样，每个字符出现的频率也一样，只是顺序不同而已，这就属于异位词，

示例：

输入: s = "anagram", t = "nagaram"
输出: true

说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

解答：

def isAnagram(s: str, t: str) -> bool:
    return sorted(s) == sorted(t)  

s = "anagram"
t = "nagaram"
print(isAnagram(s, t))

     

五、验证回文字符串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。

示例：

输入: "A man, a plan, a canal: Panama"
输出: true

解答：

# 这个是我一开始的想法，测试后超时。怀疑是测试的字符串贼长，导致for判断耗时特长，之前用的while方法耗时更长。
"""
def isPalindrome(s: str) -> bool:
    s = list(s.lower())
    s1 = set(s)
    for i in s1:
        if not i.isalpha() and not i.isalnum():
            for j in range(s.count(i)):
                s.remove(i)
    return s == s[::-1]
"""

# 因此弃用for方法，选用replace方法
def isPalindrome(s: str) -> bool:
    s1 = set(s)
    for i in s1:
        if not i.isalpha() and not i.isalnum():
            s = s.replace(i, '')
    s = list(s.lower())
    return s == s[::-1]

s = "A man, a plan, a canal: Panama"
print(isPalindrome(s))

     

六、字符串转换整数 (atoi)

请你来实现一个atoi函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0 。

提示：

示例：

输入: "42"
输出: 42

输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−231) 。

解答：

def myAtoi(s: str) -> int:
    s = s.strip()
    if len(s) == 0 or len(s.replace('-', '')) == 0 or len(s.replace('+', '')) == 0:
        return 0
    if s[0] == '-':
        n = 1
        s = s[1:]
    elif s[0] == '+':
        n = 0
        s = s[1:]
    else:
        n = 0
    for i in range(len(s)):
        if not '0' <= s[i] <= '9':
            if i == 0:
                return 0
            else:
                result = int(s[:i])
                break
        if i == len(s) - 1:
            result = int(s)
    if n == 0:
        if result > 2 ** 31 - 1:
            return 2 ** 31 - 1
        else:
            return result
    else:
        if result > 2 ** 31:
            return -2 ** 31
        else:
            return - result

s = "++1"
print(myAtoi(s))

     

七、实现 strStr()

实现 strStr() 函数。
给定一个haystack字符串和一个needle字符串，在haystack字符串中找出needle字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1。

示例：

输入: haystack = "hello", needle = "ll"
输出: 2

输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的strstr() 以及 Java的 indexOf()定义相符

解答：

def strStr(haystack: str, needle: str) -> int:
    if needle == '':
        return 0
    elif needle not in haystack:
        return -1
    else:
        return haystack.index(needle)

h = "hello"
n = 'll'
print(strStr(h, n))

     

八、外观数列

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

1.1
2.11
3.21
4.1211
5.111221

1被读作"one 1" ("一个一"), 即11。
11被读作"two 1s" ("两个一"), 即21。
21被读作"one 2", "one 1" ("一个二" , "一个一"), 即1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。

注意：整数序列中的每一项将表示为一个字符串。

示例：

输入: 1
输出: "1"
解释：这是一个基本样例。

输入: 4
输出: "1211"
解释：当 n = 3 时，序列是 "21"，其中我们有 "2" 和 "1" 两组，"2" 可以读作 "12"，也就是出现频次 = 1 而 值 = 2；类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起，也就是 "1211"。

解答：

def countAndSay(n: int) -> str:
    s = '1'
    for i in range(1, n):
        flag = 1
        rts = ''
        for j, char in enumerate(s):
            if not flag:
                count -= 1
                if count == 1:
                    flag = 1
                continue
            count = s[j: j + 2].count(char)
            if j < len(s) - 1:
                count2 = s[j + 1: j + 3].count(char)
            if count == 2 and count2 == 2:
                count = 3
            if count > 1:
                flag = 0
            rts += str(count) + char
        s = rts
    return s

n = 4
print(countAndSay(n))

# 方法二
def countAndSay(self, n: int) -> str:
    res = '1'
    for i in range(1, n):
        list_res = list(res)
        res = ''
        count = 1
        for j in range(1, len(list_res)):
            if list_res[j] == list_res[j - 1]:
                count += 1
            else:
                res += str(count) + list_res[j - 1]
                count = 1
        res += str(count) + list_res[-1]
    return res

     

九、最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串""。

示例：

输入: ["flower","flow","flight"]
输出: "fl"

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:
所有输入只包含小写字母a-z。

解答：

def longestCommonPrefix(strs) -> str:
    if strs == []:
        return ''
    strs.sort()
    s1 = strs[0]
    result = len(s1)
    for i in range(1, len(strs)):
        for j in range(len(s1)):
            if s1[j] == strs[i][j]:
                continue
            else:
                result = min(result, j)
                break
    return s1[:result]

strs = ["flower", "flow", "flight"]
print(longestCommonPrefix(strs))

     

III、链表

一、删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:

示例：

输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

解答：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        if not node:
            return 
        node.val = node.next.val
        node.next = node.next.next

     

二、删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：
给定的 n 保证是有效的。

进阶：
你能尝试使用一趟扫描实现吗？

解答：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        if head == None or head.next == None:
            return None
        l1 = head
        l2 = head
        while n != 0:
            l1 = l1.next
            n -= 1
        if l1 == None:
            head = head.next
            return head
        while l1.next != None:
            l1 = l1.next
            l2 = l2.next
        l2.next = l2.next.next
        return head

     

三、反转链表

反转一个单链表。

示例：

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

解答：

# 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:
        index, index_before = head, None
        while index:
            index.next, index_before, index = index_before, index, index.next
        return index_before

     

四、合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

解答：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        new = ListNode(-1)
        tail = new
        while l1 != None and l2 != None:
            if l1.val <= l2.val:
                tail.next = l1
                tail = tail.next
                l1 = l1.next
            else:
                tail.next = l2
                tail = tail.next
                l2 = l2.next
        if l1 != None:
            tail.next = l1
        if l2 != None:
            tail.next = l2
        return new.next

     

五、回文链表

请判断一个链表是否为回文链表。

示例：

输入: 1->2
输出: false

输入: 1->2->2->1
输出: true

解答：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        l = []
        while head != None:
            l.append(head.val)
            head = head.next
        return l[::-1] == l

     

六、环形链表

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果pos是-1，则在该链表中没有环。

示例：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

解答：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 快慢指针 
        h1 = h2 = head
        while h2 and h2.next:
            h1 = h1.next
            h2 = h2.next.next
            if h1 == h2:
                return True
        return False

     

IV、树

一、二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树[3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

解答：

# 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:
        if root == None:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left, right) + 1

     

二、验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：

示例：

输入:
    2
   / \
  1   3
输出: true

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

解答：

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

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        if not root:
            return True
        minOrderTree = []
        self.MinOrder(root,minOrderTree);
        for i in range(len(minOrderTree)-1):
            if minOrderTree[i] >= minOrderTree[i+1]:
                return False 
        return True
    
    def MinOrder(self,root,res):
        if not root:
            return None
        self.MinOrder(root.left,res)
        res.append(root.val)
        self.MinOrder(root.right,res)

     

三、对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树[1,2,2,3,4,4,3]是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个[1,2,2,null,3,null,3]则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

解答：

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

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        return True if root == None else self.inn(root.left, root.right)
    
    def inn(self, l1, l2):
        if l1 == None and l2 == None:
            return True
        if l1 == None or l2 == None:
            return False
        return l1.val == l2.val and self.inn(l1.left, l2.right) and self.inn(l1.right, l2.left)

     

四、二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

解答：

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

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        result = []
        current_level = [root]
        while current_level:
            auxiliary = []
            next_level = []
            for node in current_level:
                auxiliary.append(node.val)
                if node.left:
                    next_level.append(node.left)
                if node.right:
                    next_level.append(node.right)
            result.append(auxiliary)
            current_level = next_level
        return result

     

五、将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例：
给定有序数组:[-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / \
   -3   9
   /   /
 -10  5

解答：

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

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if not nums:
            return None
        middle = len(nums) // 2
        tn = TreeNode(nums[middle])
        tn.left = self.sortedArrayToBST(nums[:middle])
        tn.right = self.sortedArrayToBST(nums[middle + 1:])
        return tn

     

V、排序和搜索

一、合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明:

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

解答：

def merge(nums1, m: int, nums2, n: int) -> None:
    """
    Do not return anything, modify nums1 in-place instead.
    """
    if not n:
        return nums1
    nums1[:] = nums1[:m] + nums2
    nums1.sort()


n1 = [1, 2, 3, 0, 0, 0]
n2 = [2, 5, 6]
merge(n1, 3, n2, 3)
print(n1)

     

二、第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有n个版本[1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用bool isBadVersion(version)接口来判断版本号version是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例：

给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。

解答：

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return n if isBadVersion(n) else 0
        st = 1
        while st <= n:
            mid = st + (n - st) // 2
            if isBadVersion(mid):
                n = mid - 1 
            else:
                st = mid + 1
        return st

     

VI、动态规划

一、爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

示例：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

解答：

def climbStairs(n: int) -> int:
    if n <= 3:
        return n
    temp = [1, 1]
    result = 0
    while (n > 1):
        result = temp[-1] + temp[-2]
        temp[-1] = temp[-2]
        temp[-2] = result
        n = n - 1
    return result

print(climbStairs(5))

     

二、买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。

示例：

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

解答：

def maxProfit(prices) -> int:
    if len(prices) <= 1:
        return 0
    buy = prices[0]
    sell = 0
    for i in range(len(prices)):
        buy = min(buy, prices[i])
        sell = max(sell, prices[i] - buy)
    return sell

prices = [7, 1, 5, 3, 6, 4]
print(maxProfit(prices))

     

三、最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解答：

def maxSubArray(nums) -> int:
    l = len(nums)
    if l == 0:
        return 0
    elif l == 1:
        return nums[0]
    else:
        dp = [0 for _ in range(l)]
        dp[0] = nums[0]
        for i in range(1, l):
            dp[i] = max(dp[i - 1] + nums[i], nums[i])
        return max(dp)


nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums))

     

四、打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例：

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

解答：

def rob(nums) -> int:
    l = len(nums)
    if l == 0:
        return 0
    elif l <= 2:
        return max(nums)
    else:
        a = [-1] * (l + 1)
        a[0], a[1] = 0, nums[0]
        for i in range(1, l):
            a[i + 1] = max(a[i], a[i - 1] + nums[i])
        return a[-1]


nums = [2, 7, 9, 3, 1]
print(rob(nums))

     

VII、设计问题

一、打乱数组

打乱一个没有重复元素的数组。

示例：

// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();

// 重设数组到它的初始状态[1,2,3]。
solution.reset();

// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();

解答：

class Solution:
    def __init__(self, nums: List[int]):
        self.nums = nums

    def reset(self) -> List[int]:
        """
        Resets the array to its original configuration and return it.
        """
        return self.nums

    def shuffle(self) -> List[int]:
        """
        Returns a random shuffling of the array.
        """
        nums2 = self.nums[:]
        l = len(nums2)
        for i in range(l):
            n = random.randrange(i, l)
            nums2[i], nums2[n] = nums2[n], nums2[i]
        return nums2


# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()

     

二、最小栈

设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。

示例：

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

解答：

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []

    def push(self, x: int) -> None:
        self.stack.append(x)

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return min(self.stack)

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

     

VIII、数学

一、Fizz Buzz

写一个程序，输出从 1 到 n 数字的字符串表示。

  1. 如果 n 是3的倍数，输出“Fizz”；
  2. 如果 n 是5的倍数，输出“Buzz”；
  3. 如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

示例：

n = 15,

返回:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

解答：

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        result = []
        for i in range(1, n + 1):
            if i % 3 == 0:
                if i % 5 == 0:
                    result.append("FizzBuzz")
                else:
                    result.append("Fizz")
            elif i % 5 == 0:
                result.append("Buzz")
            else:
                result.append(str(i))
        return result

     

二、计数质数

统计所有小于非负整数 n 的质数的数量。

示例：

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

解答：

# 一开始用的暴力循环超时了
"""
def countPrimes(n: int) -> int:
    result = 0
    if n < 3:
        return result
    result += 1
    for i in range(3, n):
        for j in range(2, i):
            if i % j == 0:
                break
            if j == i - 1:
                result += 1
    return result
"""

# 初始化一个长度为n的列表，将坐标为质数的标1，非质数标0。

def countPrimes(n: int) -> int:
    result = [1] * max(2, n)
    result[0], result[1] = 0, 0
    x = 2
    while x * x < n:
        if result[x]:
            p = x * x
            while p < n:
                result[p] = 0
                p += x
        x += 1
    return sum(result)

n = 10
print(countPrimes(n))

     

三、3的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。

示例：

输入: 27
输出: true

输入: 0
输出: false

解答：

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n == 1:
            return True
        elif n == 0:
            return False
        else:
            while n != 1:
                if n % 3 == 0:
                    n //= 3
                else:
                    return False
            return True

# 方法二
def isPowerOfThree(self, n: int) -> bool:
    return n > 0 and pow(3, 19) % n == 0

     

四、罗马数字转整数

罗马数字包含以下七种字符:I，V，X，L，C，D和M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如，罗马数字2写做II，即为两个并列的1。12写做XII，即为X + II。 27写做XXVII, 即为XX + V + II。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如4不写做IIII，而是IV。数字1在数字5的左边，所表示的数等于大数5减小数1得到的数值4。同样地，数字9表示为IX。这个特殊的规则只适用于以下六种情况：

示例：

输入: "III"
输出: 3

输入: "IV"
输出: 4

输入: "IX"
输出: 9

输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

解答：

def romanToInt(s: str) -> int:
    nums = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
        '1': 4,
        '2': 9,
        '3': 40,
        '4': 90,
        '5': 400,
        '6': 900
    }
    s = s.replace('IV', '1').replace('IX', '2').replace('XL', '3').replace('XC', '4').replace('CD', '5').replace('CM', '6')
    result = 0
    for i in s:
        result += nums[i]
    return result

s = 'MCMXCIV'
print(romanToInt(s))

     

IX、其他

一、位1的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

示例：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

解答：

class Solution:
    def hammingWeight(self, n: int) -> int:
        return str(bin(n)).count('1')

     

二、汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：
0 ≤ x, y < 231.

示例：

输入: x = 1, y = 4
输出: 2

解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

解答：

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        if not 0 <= x <= 2 ** 31 and not 0 <= y <= 2 ** 31:
            return None
        return str(bin(x ^ y)).count('1')

     

三、颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

示例：

输入: 00000010100101000001111010011100
输出: 00111001011110000010100101000000
解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

输入：11111111111111111111111111111101
输出：10111111111111111111111111111111
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

提示：

解答：

class Solution:
    def reverseBits(self, n: int) -> int:
        b = list(bin(n))[2:][::-1]
        b.extend('0' * (32 - len(b)))
        b.insert(0, '0b')
        b = ''.join(b)
        return int(b, 2)

     

四、帕斯卡三角形

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例：

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

解答：

def generate(numRows: int):
    result = []
    if numRows == 0:
        return []
    elif numRows == 1:
        result.append([1])
        return result
    else:
        result.append([1])
        for i in range(1, numRows):
            flag = []
            for j in range(i + 1):
                if j == 0 or j == i:
                    flag.append(1)
                else:
                    flag.append(result[i - 1][j - 1] + result[i - 1][j])
            result.append(flag)
        return result

numRows = 5
print(generate(numRows))

# 方法二
def generate(numRows: int) -> List[List[int]]:
    if numRows == 0:
        return []
    res = [[1]]
    if numRows != 1:
        for i in range(1, numRows):
            l = [1]
            for j in range(1, i):
                l.append(res[i - 1][j - 1] + res[i - 1][j])
            l.append(1)
            res.append(l)
    return res

     

五、有效的括号

给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意：空字符串可被认为是有效字符串。

示例：

输入: "()"
输出: true

输入: "()[]{}"
输出: true

输入: "(]"
输出: false

输入: "([)]"
输出: false

输入: "{[]}"
输出: true

解答：

class Solution:
    def isValid(self, s: str) -> bool:
        for i in range(len(s) // 2):
            s = s.replace('{}', '').replace('()', '').replace('[]', '')
        if not s:
            return True
        else:
            return False

     

六、缺失数字

给定一个包含0, 1, 2, ..., n中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例：

输入: [3,0,1]
输出: 2

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

说明：
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

解答：

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums) - 1
        s1 = n * (n + 1) // 2
        s2 = sum(nums)
        return n - (s2 - s1) + 1
上一篇下一篇

猜你喜欢

热点阅读