代码随想录刷题记录 Day6

发表于 更新于 本文字数： 2k 阅读时长 ≈ 7 分钟

To Do List

  • DAY 4 回顾
  • 对哈希表结构的理解
  • LeetCode 242. 有效的字母异位词 / Remove Linked List Elements
  • LeetCode 349. 两个数组的交集 / Intersection of Two Arrays
  • LeetCode 202. 快乐数 / Happy Number
  • LeetCode 1. 两数之和 / Two Sums
  • 总结 / Summary

对哈希表结构的理解

哈希表（Hash Table）也是一个基础的数据结构。

根据官方的定义：

1
哈希表是根据关键码的值而直接进行访问的数据结构。

立马就能想到数组，因为数组是根据下标索引来访问数据的。可以把哈希表的关键码比作数组的下标索引，然后通过哈希表所谓的 “下标” 直接访问其元素。立马就可以得知哈希表访问数据的时间复杂度为 O(1).

由这个特性可知，哈希表更适合用来判断一个元素是否出现在一个集合里。

举个栗子：要查询一个名字是否在学校里，直接把所有人的名字存在哈希表里，需要查找的时候只需查找下标就可以知道这个名字在不在学校了。

要将所有人的名字存到哈希表里，想必要通过某种方式存取，哈希表就是通过哈希函数 (Hash Function) 来存取的。

哈希函数，是一种将任意长度的数据映射到固定长度输出的算法。通过哈希值 ***(Hashcode)***，来把学生的姓名转化为数值。这个数值就是学生姓名在哈希表上的索引了。

如果学生的数量远大于哈希表的大小，就会不可避免地出现有多个名字映射到同一下标的情况。这就叫做哈希碰撞。这种情况如果哈希表真的没有空位，那么可以将多个映射到同一下标的名字存储到一个链表中，这样就可以通过一个下标查找到多个名字了。

用哈希表法解决问题的数据结构

除了可以用映射 (Map) 和数组 (Array) 外，还可以用集合 (Set).

（带补充）

LeetCode 242. 有效的字母异位词 / Valid Anagram

1
Difficulty: Easy

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Translated by zh-CN 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

Example 1:

1
2
Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

1
2
Input: s = "rat", t = "car"
Output: false

Constraints:

  • 1 <= s.length, t.length <= 5 * 104
  • s and t consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Translated by zh-CN 1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

解法：

(JavaScript)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isAnagram = function(s, t) {
    let hash = new Array(26).fill(0)
    const a = "a".charCodeAt()
    for (let i = 0; i < s.length; i++){
        hash[s[i].charCodeAt() - a]++
    }
    for (let i = 0; i < t.length; i++) {
        hash[t[i].charCodeAt() - a]--
    }
    for (let i = 0; i < hash.length; i++){
        if(hash[i] != 0) return false
    }
    return true
};

只需要注意，获取字符的 ASCII 码值，要用到字符串当中的 charCodeAt() 的方法，然后再跟着卡哥的思路写代码就容易多了。

LeetCode 349. 两个数组的交集 / Intersection of Two Arrays

1
Difficulty: Easy

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Translated by zh-CN 给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

Example 1:

1
2
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

1
2
3
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

Constraints:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

解法：

(JavaScript)

Part.1 数组方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    let hash = new Array(1001).fill(0)
    let result = new Set()
    for (let i = 0; i < nums1.length; i++){
        hash[nums1[i]] = true
    }
    for (let i = 0; i < nums2.length; i++){
        if(hash[nums2[i]]){
            result.add(nums2[i])
        }
    }
    return Array.from(result)
};

Part.II Set 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    let result = new Set()
    let numSet = new Set()
    for (let i = 0; i < nums1.length; i++){
        numSet.add(nums1[i])
    }
    for (let i = 0; i < nums2.length; i++){
        if(numSet.has(nums2[i])){
            result.add(nums2[i])
        }
    }
    return Array.from(result)
};

这两种方法都使用到了 Set 这个数据结构，笔者做题的时候也顺便补了一下有关 Set 和 Array 的方法：

1
2
3
4
set.add() //向集合中添加元素
set.has() //查找指定元素是否在集合中
Array.from(...) // 在 Set 当中将 Set 结构转为数组。
Array().fill(...) // 用指定字符串填充指定长度的数组，一般填 0 或填 1

LeetCode 202. 快乐数 / Happy Number

1
Difficulty: Easy

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

  • Starting with any positive integer, replace the number by the sum of the squares of its digits.
  • Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
  • Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Translated by zh-CN 编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

Example 1:

1
2
3
4
5
6
7
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2:

1
2
Input: n = 2
Output: false

Constraints:

  • 1 <= n <= 2^31 - 1

解法：

(JavaScript)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number} n
 * @return {boolean}
 */
var getSum = function(n) {
    let sum = 0
    while (n) {
        sum += (n % 10) ** 2
        n = Math.floor(n / 10)
    }
    return sum
}
var isHappy = function(n) {
    let res = new Set()
    while (n != 1 && !res.has(n)){
        res.add(n)
        n = getSum(n)
    }
    return n === 1
};

LeetCode 1. 两数之和 / Two Sum

1
Difficulty: Easy

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Translated by zh-CN 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

Example 1:

1
2
3
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

1
2
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

1
2
Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • 只会存在一个有效答案

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Translated by zh-CN 你可以想出一个时间复杂度小于 O(n^2) 的算法吗？

解法：

(JavaScript)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = new Map()
    for(let i = 0; i < nums.length; i++) {
        if (map.has(target - nums[i])){
            return [map.get(target - nums[i]), i]
        } else {
            map.set(nums[i], i)
        }
    }
    return null
};

总结

这次学习了哈希表及其原理，尝试使用了不同的数据结构来解决了有关数字和字符串的问题。需要注意 JavaScript 中的 Set 和 Map 结构都采用了 unordered 结构，原理也相当于映射。其他细节还在慢慢完善中…