Leetcode Tags（5）Hash Table

　　一、500. Keyboard Row

给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。

输入: ["Hello", "Alaska", "Dad", "Peace"]

输出: ["Alaska", "Dad"]

可以重复使用键盘上同一字符。

可以假设输入的字符串将只包含字母。

　　思路:将键盘上每一行的字母映射到所在的行数，如果单词的所有字母中存在和第一个单词所在的行数不相同的字母，则这个单词将不是符合需求的单词。

　　需要注意的地方：

　　1.whichRow = -1;以及 if (whichRow != -1) list.add(s);这种表示，可以少使用一个boolean类型的标识位，同样可以实现效果。

　　2.List<String> list = new ArrayList<>();以及return list.toArray(new String[0]);的表达，由于collection.toArray(T[] a)方法转换过来是Object类型的数组，使用new String[0]可以在转换之前提前说明转换之后的类型，就是开辟了一块长度为0的内存用来做标记的作用。

    public String[] findWords(String[] words) {

        String[] rows = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};

        Map<Character, Integer> map = new HashMap<>();

        for (int i = 0; i < rows.length; i++) {

            for (char c : rows[i].toCharArray()) {

                map.put(c, i);

            }

        }

        List<String> list = new ArrayList<>();

        for (String s : words) {

            int whichRow = map.get(s.toLowerCase().charAt(0));

            for (int i = 1; i < s.length(); i++) {

                if (map.get(s.toLowerCase().charAt(i)) != whichRow) {

                    whichRow = -1;

                    break;

                }

            }

            if (whichRow != -1) list.add(s);

        }

        return list.toArray(new String[0]);

    }

　　二、690. Employee Importance

给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。

比如，员工1是员工2的领导，员工2是员工3的领导。
他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5, []]。
注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。

现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。

输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1

输出: 11

员工1自身的重要度是5，他有两个直系下属2和3，而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11。

一个员工最多有一个直系领导，但是可以有多个直系下属。员工数量不超过2000。

　　1.类似于[[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1这种情况，可以使用下面的代码，只计算了当前的员工和其直系下属的重要值之和。

    public int getImportance(List<Employee> employees, int id) {

        int res = 0;

        int boss = -1;

        for (int i = 0; i < employees.size(); i++) {

            if (employees.get(i).id == id) {

                boss = i;

                res += employees.get(i).importance;

            }

        }

        if (boss == -1) return 0;

        for (int i = 0; i < employees.size(); i++) {

            if (employees.get(boss).subordinates.contains(employees.get(i).id)) {

                res += employees.get(i).importance;

            }

        }

        return res;

    }

　　而如果是[[1, 5, [2, 3]]，[2, 3, [4]],，[3, 3, []]， 4,1,[]], 1这种情况就无法计算了。但是如果画图来看，它就是一个二叉树，因此考虑深度优先遍历。（DFS）

　　2.思路：使用Map：e.id -> e，然后再使用DFS遍历即可。

　　需要注意的地方：使用Map是为了在DFS的时候可以很方便地用id来表示对象，注意DFS的表达ans += dfs(subid);

    private Map<Integer, Employee> map;

    public int getImportance(List<Employee> employees, int id) {

        map = new HashMap<>();

        for (Employee employee : employees) map.put(employee.id, employee);

        return dfs(id);

    }

    private int dfs(int id) {

        Employee employee = map.get(id);

        int ans = employee.importance;

        for (Integer subid : employee.subordinates) {

            ans += dfs(subid);

        }

        return ans;

    }

　　三、447. Number of Boomerangs

给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。

输入:

[[0,0],[1,0],[2,0]]

输出:

2

两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

　　1.思路：首先使用暴力法遍历出每一个点到除了它本身的其他点的距离，例如，假设遍历到了[0,0]这个点，对于其他每个点到[0,0]的距离做为key，出现的次数作为value，也就是说，如果[0,0]对应的map为{1=1,2=3,3=4}，就说明到[0,0]的距离为1的点有1个，为2的点有2个，为3的点有4个，那么表示回旋镖的时候，[0,0]为第一个，剩下两个数排列，即A²_{1 +}A₂² + A₃2 = 1*0 + 2*1+3*2=8;

　　2.代码（时间复杂度N^2，空间复杂度N）：需要注意的表达是：for (int value : map.values()) count += value * (value-1);和 map.clear();，前者不用通过map.keyset()来遍历，这样可以更加快捷，直接使用map里面的value也可以满足想要的需求；后者每次clear可以再次重复使用，这样只需要新建一个Map对象就可以重复使用。

    public int numberOfBoomerangs(int[][] points) {

        int count = 0;

        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < points.length; i++) {

            for (int j = 0; j < points.length; j++) {

                if (i == j) continue;

                int d = getDistance(points[i], points[j]);

                map.put(d, map.getOrDefault(d, 0)+1);

            }

            for (int value : map.values()) count += value * (value-1);

            map.clear();

        }

        return count;

    }

    private int getDistance(int[] a, int[] b) {

        int dx = a[0] - b[0];

        int dy = a[1] - b[1];

        return dx*dx + dy*dy;

    }

　　四、720. Longest Word in Dictionary（TODO）

输入:

words = ["w","wo","wor","worl", "world"]

输出: "world"

解释:

单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。

输入:

words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]

输出: "apple"

解释:

"apply"和"apple"都能由词典中的单词组成。但是"apple"得字典序小于"apply"。

　　1.思路：（1）Brute Force （2）Trie + DFS

　　2.代码：

　　五、438. Find All Anagrams in a String

输入:

s: "cbaebabacd" p: "abc"

输出:

[0, 6]

解释:

起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。

起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

输入:

s: "abab" p: "ab"

输出:

[0, 1, 2]

起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。

起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。

起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

　　1.思路：（1）Brute Force[Time Limit Exceeded] （2）Sliding Window（TODO）

　　2.代码：

　　（1）Brute Force[Time Limit Exceeded]

    public List<Integer> findAnagrams(String s, String p) {

        List<Integer> list = new ArrayList<>();

        Map<Character, Integer> map = new HashMap<>();

        for (char c : p.toCharArray()) map.put(c, map.getOrDefault(c, 0)+1);

        Map<Character, Integer> tmp = new HashMap<>();

        for (int i = 0; i <= s.length() - p.length(); i++) {

            for (int j = i; j < i + p.length(); j++) {

                tmp.put(s.charAt(j), tmp.getOrDefault(s.charAt(j), 0)+1);

            }

            if (tmp.equals(map)) list.add(i);

            tmp.clear();

        }

        return list;

    }

　　（2）Sliding Window

　　2.代码：

巴特西

Leetcode Tags（5）Hash Table

最新文章

热门文章