LeetCode 专题：查找表

作者: 李威威 | 来源:发表于2019-05-26 05:06 被阅读0次

LeetCode 专题：查找表

LeetCode 第 349 题：计算两个数组的交集

LeetCode 第 350 题：计算两个数组的交集

虽然是一个简单的问题，但还是有陷阱。

class Solution:
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """

        return [x for x in nums2 if x in nums1]

这样写是不对的，测试用例如下：

[4,9,5]
[9,4,9,8,4]

Python 代码：

class Solution:
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort()
        nums2.sort()
        len1 = len(nums1)
        len2 = len(nums2)
        result = []
        i = 0
        j = 0
        while i < len1 and j < len2:
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] == nums2[j]:
                result.append(nums1[i])
                i += 1
                j += 1
            else:
                j += 1
        return result


# 使用 HashMap 的写法
# https://gist.github.com/liweiwei1419/74ee4bc1d1443425ff6cc17df271a700

if __name__ == '__main__':
    nums1 = [4, 9, 5]
    nums2 = [9, 4, 9, 8, 4]

    solution = Solution()
    result = solution.intersect(nums1, nums2)
    print(result)

LeetCode 第 242 题：Valid Anagram

思路1：把两个字符串都转换成字符数组以后，进行排序，然后逐位进行比较。

Java 代码：

public class Solution {
    public boolean isAnagram(String s, String t) {
        boolean isAnagram = true;
        if (s.length() != t.length()) {
            isAnagram = false;
        } else {
            char[] sArray = s.toCharArray();
            Arrays.sort(sArray);
            char[] tArray = t.toCharArray();
            Arrays.sort(tArray);
            for (int i = 0; i < sArray.length; i++) {
                if (sArray[i] != tArray[i]) {
                    isAnagram = false;
                    break;
                }
            }
        }
        return isAnagram;
    }
}

思路2：放入一个 Map 中，只要后面有一个元素不出现在 Map 中，就退出，最后应该使得这个 Map 里所有元素的 value 值都为 0。

Java 代码：

public class Solution2 {
    public boolean isAnagram(String s, String t) {
        boolean isAnagram = true;
        if (s.length() != t.length()) {
            isAnagram = false;
        } else {
            char[] sArray = s.toCharArray();
            Map<Character, Integer> map1 = new HashMap<>();
            for (char c : sArray) {
                if (map1.containsKey(c)) {
                    map1.put(c, map1.get(c) + 1);
                } else {
                    map1.put(c, 1);
                }
            }
    
            char[] tArray = t.toCharArray();
            for (char c : tArray) {
                if (map1.containsKey(c) && map1.get(c) >= 1) {
                    map1.put(c, map1.get(c) - 1);
                } else {
                    isAnagram = false;
                    break;
                }
            }
        }
        return isAnagram;
    }
}

LeetCode 第 202 题：快乐数

Java 代码：

class Solution {
    public boolean isHappy(int n) {
        boolean isHappy = false;
        Set<Integer> set1 = new HashSet<>();
        String numberStr = String.valueOf(n);
        while (true) {
            int sum = 0;
            for (int i = 0; i < numberStr.length(); i++) {
                sum += Math.pow(Integer.valueOf(String.valueOf(numberStr.charAt(i))), 2);
            }
            if (sum == 1) {
                isHappy = true;
                break;
            } else if (set1.contains(sum)) {
                break;
            } else {
                set1.add(sum);
                numberStr = String.valueOf(sum);
            }
        }
        return isHappy;
    }
}

LeetCode 第 290 题：Word Pattern

思路：这里有一个小小的坑，就是当测试用例是：String pattern = "abba";String str = "dog dog dog dog";的时候，我们须要判断出结果是 false。

Java 代码：

public class Solution {
    public boolean wordPattern(String pattern, String str) {
        boolean wordPattern = false;
        int patternLength = pattern.length();
        String[] strArray = str.split(" ");
        if (patternLength == strArray.length) {

            Map<Character, String> map1 = new HashMap<>();
            Set<String> uniqueValue = new HashSet<>();
            char[] patternArray = pattern.toCharArray();
            for (int i = 0; i < patternLength; i++) {
                if (map1.containsKey(patternArray[i])) {
                    if (!map1.get(patternArray[i]).equals(strArray[i])) {
                        return wordPattern;
                    }
                } else {
                    if (uniqueValue.contains(strArray[i])) {
                        return wordPattern;
                    }
                    uniqueValue.add(strArray[i]);
                    map1.put(patternArray[i], strArray[i]);
                }
            }
            wordPattern = true;
        }
        return wordPattern;
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        String pattern = "abba";
        String str = "dog dog dog dog";
        boolean wordPattern = solution.wordPattern(pattern, str);
        System.out.println(wordPattern);
    }
}

LeetCode 第 205 题：Isomorphic Strings 判断是否同构

LeetCode 第 451 题：Sort Characters By Frequency

LeetCode 第 1 题：两数之和

传送门：1. 两数之和。

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:
给定 nums = [2, 7, 11, 15], target = 9

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

思路：用集合 Set 做差补来完成（推荐）

Python 代码：

class Solution(object):
    def findNumbersWithSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        s = set()
        for num in nums:
            if target - num not in s:
                s.add(num)
            else:
                return [num, target - num]

LeetCode 第 15 题：三数之和

用 set 把最后一层循环给省掉了。

image-20190120152934792

上面是在 set 里直接判重，下面是排好序以后判重。

image-20190120153003611

image-20190111135711219

Python 代码1：使用指针对撞，首先要排序

class Solution(object):
    def threeSum(self, nums):
        res = []
        nums.sort()
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 用指针对撞的方式
            l = i + 1
            r = len(nums) - 1
            # 不能等于，等于就变成取一样的数了
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s > 0:
                    r -= 1
                elif s < 0:
                    l += 1
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    # 注意：这一步在去重，是第一种解法 set 做不到的
                    # 看一看右边是不是和自己相等，如果相等，就向右边移动一格
                    while l < r and nums[l] == nums[l + 1]:
                        l += 1
                    # 看一看左边是不是和自己相等，如果相等，就向右边移动一格
                    while l < r and nums[r] == nums[r - 1]:
                        r -= 1
                    l += 1
                    r -= 1
        return res

Python 代码2：使用哈希表，首先要排序

class Solution(object):
    # 排序可以去掉 -4 但是不能把后面重复的 2 去掉
    # [-4,-4, 2, 2]
    def threeSum(self, nums):
        if len(nums) < 3:
            return []
        nums.sort()

        # 特判
        if nums[0] == nums[-1] == 0:
            return [[0, 0, 0]]

        res = set()
        # 最后两个数就没有必要作为遍历的起点了
        for index, one in enumerate(nums[:-2]):
            # 因为题目要求，答案中不可以包含重复的三元组。
            if index >= 1 and nums[index] == nums[index - 1]:
                continue
            s = set()
            for two in nums[index + 1:]:
                if two not in s:
                    s.add(-one - two)
                else:
                    # 找到了一个解
                    res.add((one, two, -one - two))
        return list(map(list, res))

LeetCode 第 18 题：4Sum

提示：采用了“三数之和”的解法，在外面多套了一层。

LeetCode 第 16 题：3Sum Closest

Python 代码：还是首先要排序

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """

        if len(nums) < 3:
            return []
        # 初始化
        diff = float('inf')
        nums.sort()
        for index in range(len(nums) - 2):
            if index > 0 and nums[index] == nums[index - 1]:
                continue
            l = index + 1
            r = len(nums) - 1
            while l < r:
                s = nums[index] + nums[l] + nums[r]
                if abs(s - target) < diff:
                    diff = abs(s - target)
                    res = s
                if s > target:
                    r -= 1
                elif s < target:
                    l += 1
                else:
                    # 如果已经等于 target 的话, 肯定是最接近的，根据题目要求，返回这三个数的和
                    return target
        return res

LeetCode 第 454 题：4 个数之和

Python 代码：

class Solution:
    def fourSumCount(self, A, B, C, D):
        """
        :type A: List[int]
        :type B: List[int]
        :type C: List[int]
        :type D: List[int]
        :rtype: int
        """

        map1 = self.get_map(A, B)
        map2 = self.get_map(C, D)
        res = 0

        for key1 in map1:
            if -key1 in map2:
                res += map1[key1] * map2[-key1]
        return res

    def get_map(self, tuple1, tuple2):
        map = dict()
        for num1 in tuple1:
            for num2 in tuple2:
                map[num1 + num2] = (map.setdefault(num1 + num2, 0) + 1)
        return map

LeetCode 第 49 题：字母异位词分组

LeetCode 第 447 题：Number of Boomerangs

LeetCode 第 149 题：直线上最多的点数

查找表和滑动窗口

查找表和滑动窗口问题（三题）可以整理一下。

LeetCode 第 217 题：Contains Duplicate

给定一个整数数组，判断是否存在重复元素。如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

提示：思路1：哈希表；思路2：排序以后判断重复。

LeetCode 第 219 题：Contains Duplicate ||

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。

提示：用哈希 map，其中 key 是遍历到的数，value 是索引，遍历到重复的时候，检查一下当前索引和之前索引的差值就可以了。

LeetCode 第 220 题：Contains Duplicate |||

提示：滑动窗口 + 查找表，这里的查找表是能查询上界和下界的 BST。

Java 代码：滑动窗口 + 查找表，这里的查找表是能查询上界和下界的 BST。

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        // 特判
        int len = nums.length;
        if (len == 0 || k <= 0 || t < 0) {
            return false;
        }
        TreeSet<Integer> treeSet = new TreeSet<>();
        for (int i = 0; i < len; i++) {
            // 大于等于 nums[i] 的最小数
            Integer ceiling = treeSet.ceiling(nums[i]);
            if (ceiling != null && (long) ceiling - (long) nums[i] <= t) {
                return true;
            }
            // 小于等于 nums[i] 的最大数
            Integer floor = treeSet.floor(nums[i]);
            if (floor != null && (long) nums[i] - (long) floor <= t) {
                return true;
            }
            treeSet.add(nums[i]);
            if (i >= k) {
                treeSet.remove(nums[i - k]);
            }
        }
        return false;
    }
}

（本节完）

LeetCode 专题：查找表