数组及数学

7、整数反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def reverse(self, x: int) -> int:
        ans = 0
        flag = False
        if x < 0:
            flag = True
            x = -1 * x
        a = 0   # 除法余数
        while x != 0:
            a = x % 10
            x = x // 10
            ans = ans * 10 + a
        if flag:
            ans = -1 * ans
        if ans > 2 ** 31 - 1 or ans < -(2 ** 31):
            return 0
        else:
            return ans

9、回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        a = self.reverse(x) # 整数反转
        if a == x:
            return True
        else:
            return False

    def reverse(self, x: int) -> int:
        ans = 0
        a = 0   # 除法余数
        while x != 0:
            a = x % 10
            x = x // 10
            ans = ans * 10 + a
        return ans

11、盛水最多的容器

我们使用双指针的思想，两个指针分别为数组的头尾结点，每轮都进行面积的计算，并且每轮只移动较小结点的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        left = 0    # 左指针
        right = n - 1   # 右指针
        max_s = 0   # 面积最大值
        s = 0   # 面积
        l = 0   # 边长
        while right > left:
            if height[left] > height[right]:
                l = height[right]
            else:
                l = height[left]
            s = (right - left) * l
            if s > max_s:
                max_s = s
            if height[left] > height[right]:
                right = right - 1
            else:
                left = left + 1
        return max_s

12、整数转罗马数字

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
class Solution:
    A = [
        (1000, "M"),
        (900, "CM"),
        (500, "D"),
        (400, "CD"),
        (100, "C"),
        (90, "XC"),
        (50, "L"),
        (40, "XL"),
        (10, "X"),
        (9, "IX"),
        (5, "V"),
        (4, "IV"),
        (1, "I"),
    ]
    
    def intToRoman(self, num: int) -> str:
        ans = ""
        for value, s in self.A:
            while num >= value:
                num = num - value
                ans = ans + s
            if num == 0:
                break
        
        return ans

13、罗马数字转整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    A = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
    }

    def romanToInt(self, s: str) -> int:
        ans = 0
        n = len(s)
        for i, ch in enumerate(s):
            if i < n - 1 and self.A[ch] < self.A[s[i+1]]:
                ans = ans - self.A[ch]
            else:
                ans = ans + self.A[ch]
        return ans

15、三数之和

采用双指针的思想，为了不使三元组重复，先对数组进行排序。当确定了第一个元素，只需要对剩下元素进行设置左指针和右指针，如果三元组大与0，右指针就左移一位，反之亦然。如果三元组之和刚好等于0，就需要左指针和右指针都移动一位。这时候还会出现重复问题，所以需要判断此时遍历的元素和之前的是否相同，如果相同就要跳过。

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
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        ans = list()
        for i in range(n):	# 固定其中一个元素
            if i == 0 or nums[i] != nums[i - 1]:
                k = n - 1
                j = i + 1
                while k > j:	# 进行双指针遍历
                    if k != n - 1 and nums[k] == nums[k + 1]:	# 如果右指针之前出现过就跳过
                        k = k - 1
                        continue
                    if j != i + 1 and nums[j] == nums[j - 1]:	# 如果左指针之前出现过就跳过
                        j = j + 1
                        continue
                    s = nums[i] + nums[j] + nums[k]
                    if s == 0:
                        ans.append([nums[i], nums[j], nums[k]])
                        k = k - 1
                        j = j + 1
                    elif s > 0:
                        k = k - 1
                    elif s < 0:
                        j = j + 1
        return ans

16、最接近的三数之和

采用双指针的思想，先对数组进行排序。当确定了第一个元素，只需要对剩下元素进行设置左指针和右指针，如果三元组之和大于target，我们只需要将右节点左移一位，相反亦然。

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
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        n = len(nums)
        nums.sort()
        min_num = 10**9
        ans = 0
        for i in range(n):
            if i != 0 and nums[i] == nums[i - 1]:
                continue
            k = n - 1
            j = i + 1
            while k > j:
                s = nums[i] + nums[j] + nums[k]
                if s == target:
                    return s
                if s > target:
                    if s - target < min_num:
                        min_num = s - target
                        ans = s
                    k = k - 1
                elif s < target:
                    if target - s < min_num:
                        min_num = target - s
                        ans = s
                    j = j + 1
        return ans

18、四数之和

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
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        if nums == [] or n < 4:
            return []
        nums.sort()
        ans = list()
        for i in range(n - 3):
            if i != 0 and nums[i] == nums[i - 1]:
                continue
            if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
                break
            if nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target:
                continue
            for j in range(i + 1, n - 2):
                if j != i + 1 and nums[j] == nums[j - 1]:
                    continue
                if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
                    break
                if nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target:
                    continue
                k = j + 1
                l = n - 1
                while k < l:
                    sum = nums[i] + nums[j] + nums[k] + nums[l]
                    if sum < target:
                        k = k + 1
                    elif sum > target:
                        l = l - 1
                    elif sum == target:
                        ans.append([nums[i], nums[j], nums[k], nums[l]])
                        while k < l and nums[k] == nums[k + 1]:
                            k = k + 1
                        k = k + 1
                        while k < l and nums[l] == nums[l - 1]:
                            l = l - 1
                        l = l - 1 

        return ans

26、删除有序数组中的重复项

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if nums == []:
            return 0
        n = len(nums)
        left, right = 1, 1
        while right < n:
            if nums[right] != nums[right - 1]:
                nums[left] = nums[right]
                left = left + 1
            right = right + 1
        return left

31、下一个排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        j = len(nums) - 1
        if i >= 0:
            while j >= 0 and nums[i] >= nums[j]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        left, right = i + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

33、搜索旋转排序数组

看到有序的数组，然后对其查找，一般最先要想到的是二分查找

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
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        i = 0
        if nums[0] > nums[len(nums) - 1]:
            while i < len(nums) - 1 and nums[i] < nums[i + 1]:
             i += 1
            if target > nums[len(nums) - 1]:
                left = 0
                right = i
            elif target < nums[len(nums) - 1]:
                left = i + 1
                right = len(nums) - 1
            elif target == nums[len(nums) -1]:
                return len(nums) - 1
        else:
            left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = (left + right) // 2
            if target == nums[mid]:
                return mid
            elif target < nums[mid]:
                right = mid - 1
            elif target > nums[mid]:
                left = mid + 1
        return -1

34、在排序数组中查找元素的第一个和最后一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return [-1, -1]
        def binarySearch(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] >= target:
                    right = mid - 1
                elif nums[mid] < target:
                    left = mid + 1
            return left
        a = binarySearch(nums, target)
        b = binarySearch(nums, target + 1)
        if a == len(nums) or nums[a] != target:
            return[-1, -1]
        else:
            return[a, b - 1]

50、Pow(x, n)

使用递归的思想，直接循环会导致运行时间过长

1
2
3
4
5
6
7
8
class Solution:
    def myPow(self, x: float, n: int) -> float:
        def quickPow(N):
            if N == 0:
                return 1.0
            y = quickPow(N // 2)
            return y * y if N % 2 == 0 else y * y * x
        return quickPow(n) if n >= 0 else 1.0 / quickPow(-n)

53、最大子数组和

看到这种区间的，可以想到动态规划

1
2
3
4
5
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] += max(nums[i - 1], 0)
        return max(nums)
LeetCode

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！