每日算法
Kotori Y 27 Posts
 2021-04-19 20:56      

这三年也没正儿八经学过算法，每次都是无脑for循环，实在不够elegant。于是我拿出来积灰已久的LeetCode，每天没事玩玩算法。还没想好怎么分，就先按类型写吧。

TOC

…

0. 空间复杂度与时间复杂度

…

1. 哈希表 (Hash Table)

两数之和

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

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]
1
2
输入：nums = [3,3], target = 6
输出：[0,1]

解答

Python
1
2
3
4
5
6
7
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashTable = {}
        for idx, num in enumerate(nums):
            if (target - num) in hashed:
                return [hashTable[target - num], idx]
            hashed[num] = idx
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let hashTable = new Map()
    for (let idx = 0; idx <= nums.length-1; idx++) {
        const num = nums[idx]
        if (hashTable.has(target - num)) {
            return [hashTable.get(target - num), idx]
        }
        hashTable.set(num, idx)
    }
};

无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1
2
输入: s = ""
输出: 0

解答

1
2
3
4
5
6
7
8
9
10
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        hashTable = {}
        leftIdx = maxLen = 0
        for rightIdx, c in enumerate(s):
            if c in hashTable:
                leftIdx = max(hashTable[c]+1, leftIdx)
            hashTable[c] = rightIdx
            maxLen = max(maxLen, rightIdx- leftIdx + 1)
        return maxLen
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = (s) => {
    let hashMap = new Map();
    let leftIdx = 0, maxLen = 0

    for (let rightIdx=0; rightIdx<=s.length-1; rightIdx++) {
        const c = s[rightIdx]
        if (hashMap.has(c)) {
            leftIdx = Math.max(leftIdx, hashMap.get(c)+1)
        }
        hashMap.set(c, rightIdx)
        maxLen = Math.max(maxLen, rightIdx - leftIdx + 1)
    }
    return maxLen
};

2. 链表 (Linked List)

两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储 一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
1
2
输入：l1 = [0], l2 = [0]
输出：[0]
1
2
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

解答

Python
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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        head, tail = [None, None]
        carry = 0

        while (l1 or l2):

            n1 = l1.val if l1 else 0
            n2 = l2.val if l2 else 0

            sum_ = n1 + n2 + carry
            carry = sum_ // 10

            if not head:
                head = tail = ListNode(sum_ % 10)
            else:
                tail.next = ListNode(sum_ % 10)
                tail = tail.next

            if l1:
                l1 = l1.next
            
            if l2:
                l2 = l2.next

        if (carry > 0): 
            tail.next = ListNode(carry)
        return head
JavaScript
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
46
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let head = null, tail = null;
    let carry = 0;

    while (l1 || l2) {

        const n1 = l1 ? l1.val : 0;
        const n2 = l2 ? l2.val : 0;
        const sum = ( n1 + n2 + carry );

        if (!head) {
            head = tail = new ListNode(sum % 10)
        } else {
            tail.next = new ListNode(Math.floor(sum % 10))
            tail = tail.next
        }

        carry = Math.floor(sum / 10)

        if (l1) {
            l1 = l1.next
        }

        if (l2) {
            l2 = l2.next
        }
    }

    if (carry > 0) {
        tail.next = new ListNode(carry);
    }

    return head
};

寻找两个正序数组的中位数

给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的中位数。

要求：时间复杂度为（或优于）O(log(m + n))

1
2
3
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
1
2
3
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
1
2
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
1
2
输入：nums1 = [], nums2 = [1]
输出：1.00000
1
2
输入：nums1 = [2], nums2 = []
输出：2.00000

解答

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
46
47
48
49
50
51
52
53
'''
Description:
Author: Kotori Y
Date: 2021-04-21 11:54:00
LastEditors: Kotori Y
LastEditTime: 2021-04-21 11:56:24
FilePath: \LeetCode-Code\codes\BinarySearch\Median-of-Two-Sorted-Arrays\script.py
AuthorMail: kotori@cbdd.me
'''

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            return self.findMedianSortedArrays(nums2, nums1)
        length1, length2 = len(nums1), len(nums2)

        if nums1:
            # the number of elements at left part
            leftLength = (length1 + length2 + 1) // 2

            left = 0
            right = length1

            while True:
                i = left + (right - left + 1) // 2
                j = leftLength - i

                if (i > 0) and nums1[i - 1] > nums2[j]:
                    right = i - 1
                elif (i < length1) and (nums2[j - 1] > nums1[i]):
                    right = i + 1
                    left = i
                else:
                    break

            leftOne = nums1[i-1] if i > 0 else min(nums2)
            leftTwo = nums2[j-1] if j > 0 else min(nums1)

            if (length1 + length2) % 2 == 1:
                return max([leftOne, leftTwo])

            rightOne = nums1[i] if i < length1 else max(nums2)
            rightTwo = nums2[j] if j < length2 else max(nums1)

            n1 = max([leftOne, leftTwo])
            n2 = min([rightOne, rightTwo])
            return (n1 + n2) / 2

        if length2 % 2 == 1:
            return nums2[(length2 - 1)//2]

        return (nums2[(length2-1)//2] + nums2[length2//2]) / 2

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/*
 * @Description:
 * @Author: Kotori Y
 * @Date: 2021-04-21 11:59:15
 * @LastEditors: Kotori Y
 * @LastEditTime: 2021-04-21 15:20:28
 * @FilePath: \LeetCode-Code\codes\BinarySearch\Median-of-Two-Sorted-Arrays\script.js
 * @AuthorMail: kotori@cbdd.me
 */

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  if (nums1.length > nums2.length) {
    return findMedianSortedArrays(nums2, nums1);
  }

  if (nums1.length) {
    let right = 0;
    let left = nums1.length;
    const leftLength = Math.floor((nums1.length + nums2.length + 1) / 2);

    let flag = true;
    var i, j;

    while (flag) {
      i = left + Math.floor((right - left + 1) / 2);
      j = leftLength - i;
      switch (true) {
        case i > 0 && nums1[i - 1] > nums2[j]:
          left = i - 1;
          break;
        case i < nums1.length && nums2[j - 1] > nums1[i]:
          right = i + 1;
          left = i;
          break;
        default:
          flag = false;
          break;
      }
    }

    const leftOne = i > 0 ? nums1[i - 1] : Math.min(...nums2);
    const leftTwo = j > 0 ? nums2[j - 1] : Math.min(...nums1);
    const rightOne = i < nums1.length ? nums1[i] : Math.max(...nums2);
    const rightTwo = j < nums2.length ? nums2[j] : Math.max(...nums1);

    if ((nums1.length + nums2.length) % 2 === 1) {
      return Math.max(leftOne, leftTwo);
    }

    const n1 = Math.max(leftOne, leftTwo);
    const n2 = Math.min(rightOne, rightTwo);
    return (n1 + n2) / 2;
  }

  if (nums2.length % 2 == 1) {
    return nums2[Math.floor((nums2.length - 1) / 2)];
  }

  return (
    (nums2[Math.floor((nums2.length - 1) / 2)] + nums2[nums2.length / 2]) / 2
  );
};

  • Post title：每日算法
  • Post author：Kotori Y
  • Create time：2021-04-19 20:56
  • Post link：https://blog.iamkotori.com/2021/04/19/每日算法/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments