力扣经典清单1 初级算法

字数统计: 2.7k字   |   阅读时长: 12分

编程能力就像任何其他技能一样，也是一个可以通过刻意练习大大提高的。

初级算法 - 帮助入门

数组

删除排序数组中的重复项

给定一个排序数组，你需要在** 原地** 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        # i记录最后一个不同数的下标
        i = 0
        for j in range(1, len(nums)):
            if nums[j] != nums[i]:  # 遍历直到找到一个和当前最后不同数不一样的新数，新数作为当前最后的不同数的下标
                i = i + 1
                nums[i] = nums[j]
        return i + 1

时间复杂度：O(n)

空间复杂度：O(1)

买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

Python动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if prices == []:
            return 0
        # res[i]表示截止到第i天的最大利润
        res = [0] * len(prices)
        res[0] = 0
        for i in range(1, len(prices)):
            res[i] = max(res[i - 1], prices[i] - min(prices[0 : i]))
        return res[len(prices) - 1]

Python贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if prices == []:
            return 0
        import math
        temp_min = math.inf
        temp_max = -math.inf
        for i in range(0, len(prices)):
            temp_min = min(temp_min, prices[i])
            temp_max = max(temp_max, prices[i] - temp_min)
        return temp_max

买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

Python贪心

1
2
3
4
5
6
7
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        for i in range(0, len(prices) - 1):
            if prices[i] < prices[i + 1]:
                res = res + (prices[i + 1] - prices[i])
        return res

旋转数组

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

示例 1:

1
2
3
4
5
6
输入: [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]

Python暴力（超时）

1
2
3
4
5
6
7
8
9
10
class Solution:
    def rotate(self, nums, k):
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(0, k):
            temp = nums[-1]
            for j in range(len(nums) - 1, 0, -1):
                nums[j] = nums[j - 1]
            nums[0] = temp

Java暴力

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public void rotate(int[] nums, int k) {
        for (int i = 0; i < k; i++) {
            int temp = nums[nums.length - 1];
            for (int j = nums.length - 1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
            nums[0] = temp;
        }
    }
}

存在重复元素

给定一个整数数组，判断是否存在重复元素。

如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

java

1
2
3
4
5
6
7
8
9
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        if len(nums) <= 1:
            return False
        nums.sort()
        for i in range(0, len(nums) - 1):
            if nums[i] == nums[i + 1]:
                return True
        return False

只出现一次的数字

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

说明：

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

Python异或

1
2
3
4
5
class Solution:
    def singleNumber(self, nums):
        for i in range(1, len(nums)):
            nums[0] = nums[0] ^ nums[i]
        return nums[0]

两个数组的交集 II

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

示例 1:

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

示例 2:

1
2
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

说明：

  • 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
  • 我们可以不考虑输出结果的顺序。

\进阶:**

  • 如果给定的数组已经排好序呢？你将如何优化你的算法？
  • 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
  • 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

Python哈希映射

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums1) > len(nums2):
            temp = nums1
            nums1 = nums2
            nums2 = temp
        nums1_dict = {}
        for i in nums1:
            nums1_dict[i] = nums1_dict.get(i, 0) + 1
        res = []
        for j in nums2:
            if nums1_dict.get(j, 0) > 0:
                res.append(j)
                nums1_dict[j] = nums1_dict[j] - 1
        return res

加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

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

示例 2:

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

Python

1
2
3
4
5
6
7
8
9
10
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        d = 0
        for i in range(0, len(digits)):
            d = 10 * d + digits[i]
        d = d + 1
        res = []
        for j in str(d):
            res.append(int(j))
        return res

移动零

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

示例:

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

说明:

  1. 必须在原数组上操作，不能拷贝额外的数组。
  2. 尽量减少操作次数。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums)):
            if nums[i] == 0:
                for j in range(i + 1, len(nums)):
                    if nums[j] != 0:
                        nums[i], nums[j] = nums[j], nums[i]
                        break
        return nums

两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

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

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

Python哈希

1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}  # 元素 ： 序号
        for i, num in enumerate(nums):
            another_num = target - num
            if another_num in dict:
                return [dict[another_num], i]
            dict[num] = i

有效的数独

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

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

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

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入:
[
  ["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

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入:
[
  ["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 存在, 因此这个数独是无效的。

说明:

  • 一个有效的数独（部分已被填充）不一定是可解的。
  • 只需要根据以上规则，验证已经填入的数字是否有效即可。
  • 给定数独序列只包含数字 1-9 和字符 '.' 。
  • 给定数独永远是 9x9 形式的。

旋转图像

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明：

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

示例 1:

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

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

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

Python先转置再逆序

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if j > i:
                    matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for i in range(len(matrix)):
            matrix[i] = matrix[i][::-1]

        return matrix

字符串

链表

树

排序和搜索

动态规划

设计问题

数学

其他

本文作者： Yao Zhu
发布时间： 2020-05-02
最后更新： 2020-05-11
本文链接： https://juoyo.github.io/posts/c985b81e.html
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
知识共享许可协议
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

微信分享二维码
-->

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

日日行，不怕千万里； <br><br> 常常做，不怕千万事。 <br><br> INTJ <br><br> 天真认生，请多指教。