代码随想录刷题记录 Day7

发表于 更新于 本文字数： 750 阅读时长 ≈ 3 分钟

To Do List

  • DAY 5 回顾
  • LeetCode 454. 四数相加II
  • LeetCode 383. 赎金信
  • LeetCode 15. 三数之和
  • LeetCode 18. 四数之和
  • 哈希表总结 / Summary

DAY 5 回顾

（）

LeetCode 454. 四数相加II / 4Sum II

1
Difficulty: Medium

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
Translated by zh-CN 给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Example 1:

1
2
3
4
5
6
Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
两个元组如下:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

Example 2:

1
2
Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

Constraints:

  • n == nums1.length
  • n == nums2.length
  • n == nums3.length
  • n == nums4.length
  • 1 <= n <= 200
  • -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

解法：

(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
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[]} nums3
 * @param {number[]} nums4
 * @return {number}
 */
var fourSumCount = function(nums1, nums2, nums3, nums4) {
    let map = new Map()
    let count = 0
    for (let i = 0; i < nums1.length; i++) {
        for (let j = 0; j < nums2.length; j++){
            let sum = nums1[i] + nums2[j]
            map.set(sum, (map.get(sum) || 0) + 1)

        }
    }
    for (let k = 0; k < nums3.length; k++) {
        for (let l = 0; l < nums4.length; l++) {
            let target = 0 - (nums3[k] + nums4[l])
            if (map.has(target)){
                count += map.get(target)
            }
        }
    }
    return count
};

PS: 需要注意 map.get(sum) 的值并不是一个数字，而是 NaN (可以在第一大段循环 j 代码块里的最后一行添加 return map.get(sum) 看看具体的值是什么)，需要将 NaN 转化为 0. 其他的跟着卡哥的思路写代码就好。

LeetCode 383. 赎金信 / Ransom Note

1
Difficulty: Easy

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Translated by zh-CN 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。

Example 1:

1
2
Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

1
2
Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

1
2
Input: ransomNote = "aa", magazine = "aab"
Output: true

Constraints:

  • 1 <= ransomNote.length, magazine.length <= 105
  • ransomNote and magazine consist of lowercase English letters.
Translated by zh-CN ransomNote 和 magazine 由小写英文字母组成

解法：

(JavaScript)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var canConstruct = function(ransomNote, magazine) {
    let hash = new Array(26).fill(0)
    const a = "a".charCodeAt()
    for (let i = 0; i < magazine.length; i++){
        hash[magazine[i].charCodeAt() - a]++
    }
    for (let i = 0; i < ransomNote.length; i++){
        hash[ransomNote[i].charCodeAt() - a]--
        if (hash[ransomNote[i].charCodeAt() - a] < 0) {
            return false
        }
    }
    return true
};

PS: 和第 242 题哈希法的解题思路很相似，242 题要求的是两个字符串中各个字符都能相互组成，而这题只需要满足 ransomNote 这个字符串能在 magazine 字符串上找到这个要求就好了。一样采用数组作为哈希表的数据结构，如果哈希表中有任意一个元素的值小于 0 则直接不满足要求。