6.10号刷题

第一题 49. Group Anagrams

题目描述

给定一个字符串数组，返回所有互为字谜（anagram，变位词）的字符串的分组。

注意：所有输入只包含小写字母

算法

利用HashMap存储每个单词所包含的字母(进行排序)及所有同素异形的单词。

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (int i = 0; i < strs.length; i++) {
            String str = strs[i];
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String strsorted = String.valueOf(chars);
            
            List<String> list = map.getOrDefault(strsorted, new ArrayList<>());
            list.add(str);
            map.put(strsorted, list);
        }
        return new ArrayList<List<String>>(map.values());    
    }
}

第二题 36. Valid Sudoku

题目描述

给定一个9 * 9的矩阵，查看此矩阵形成的数独游戏是否成立。

算法

对于此题，我们分析题目后，发现我们需要验证的有三个：

• 对于9行，每行不含有相同的数字
• 对于9列，每列不含有相同的数字
• 对于9个小正方形，每个正方形不含有相同的数字

至此，我们可以进行解题。但是仍需要注意一点：对于[0,8]的循环，如果将其装换成一个二维坐标[0,2][0,2] 我们可以进行这样一个对应： x = i / 3, 纵坐标为 y = i % 3。这样就可以正确的转换为小方块的二维坐标

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board.length != 9 || board[0].length != 9) return false;

        for (int i = 0; i < 9; i++) {
            Set<Character> row = new HashSet<>();
            Set<Character> colunmn = new HashSet<>();
            Set<Character> subox = new HashSet<>();

            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.' && !row.add(board[i][j])) return false;
                if (board[j][i] != '.' && !colunmn.add(board[j][i])) return false;
                
                int rowoffset = 3 * (i / 3), coloffset = 3 * (i % 3);
                int boxRowIndex = j / 3, boxColIndex = j % 3;
                if (board[rowoffset + boxRowIndex][coloffset + boxColIndex] != '.' && !subox.add(board[rowoffset + boxRowIndex][coloffset + boxColIndex])) return false;
            }
        }
        return true;        
    }
}

第三题 37. Sudoku Solver

第四题 525. Contiguous Array

题目描述

给定一个二进制数组，求其中满足0的个数与1的个数相等的最长子数组

注意：给定二进制数组的长度不超过50,000

算法

将0变为-1，我们将[0,i]的sum及index都放入map中，如果0 和 1的数目是平衡的话。那么他们的和为0，即以前出现过这个sum的和，取出index，计算距离即可

public class findMaxLength525 {
    public int findMaxLength(int[] nums) {
        if (nums.length <= 1) return 0;

        //Key : presum, value : index
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 0);

        int sum = 0, max = 0;
        for (int i = 1; i < nums.length + 1; i++) {
            int index = i - 1, number = nums[index];
            if (number == 0) number = -1;
            sum += number;
            if (map.containsKey(sum)) max = Math.max(max, i - map.get(sum));
            else map.put(sum, i);
        }
        return max;
    }
}

第五题 299. Bulls and Cows

题目描述

你和朋友在玩下面的猜数字游戏（Bulls and Cows）：你写下一个4位数的神秘数字然后让朋友来猜，你的朋友每次猜一个数字，你给一个提示，告诉他有多少个数字处在正确的位置上（称为”bulls” 公牛），以及有多少个数字处在错误的位置上（称为”cows” 奶牛），你的朋友使用这些提示找出那个神秘数字。

例如：

神秘数字：  1807
朋友猜测：  7810
提示信息：  1公牛 3奶牛。（公牛是8， 奶牛是0, 1和7）

根据维基百科：“公牛和奶牛（也称为奶牛和公牛，或者猪和公牛， 或者公牛和Cleots）” 是一歀古老的两人或多人参与的密码破解智力游戏或纸笔游戏，早于与之类似的市售棋牌游戏Mastermind。这款游戏的数字版本通常包含4位数，但也可以是3位或者其他任何位数。”

编写函数，根据神秘数字与朋友的猜测，返回一个提示信息，使用A表示公牛，B表示母牛，在上例中，你的函数应当返回1A3B。

你可以假设神秘数字和你朋友的猜测只包含数字，并且长度一定相等。

算法

利用int[] 数组进行处理

由于每一位的数字只能是0 - 9，因此我们可以创建一个int [10]的数组存储两个String中出现的字母。如果是在Secret中出现，则+1，反之在Guess中出现，则-1。每次我们查看Secret中的数字是否小于0，如果小于0说明已经在Guess中出现过了。反之同样，如果Guess的数字大于0，则说明在Secret中出现过了。

public class Solution {
    public String getHint(String secret, String guess) {
        if (secret.length() != guess.length()) return "";
        int[] numbers = new int[10];

        int A = 0, B = 0;
        for (int i = 0; i < secret.length(); i++) {
            int sec = secret.charAt(i) - '0';
            int gus = guess.charAt(i) - '0';

            if (sec == gus) A++;
            else {
                if (numbers[sec] < 0) B++;
                if (numbers[gus] > 0) B++;
                numbers[sec]++; numbers[gus]--;
            }
        }
        StringBuilder result = new StringBuilder(A + "A" + B + "B");
        return result.toString();      
    }
}

HashMap

利用HashMap存储出现的数字和其对应的位置

public class getHint299 {
    public String getHint(String secret, String guess) {
        if (secret.length() != guess.length()) return "";
        Map<Character, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < secret.length(); i++) {
            char c = secret.charAt(i);
            Set<Integer> set= map.getOrDefault(c, new HashSet<>());
            set.add(i);
            map.put(c, set);
        }

        //First Loop, find A
        int A = 0, B = 0;
        for (int i = 0; i < guess.length(); i++) {
            char c = guess.charAt(i);
            if (map.containsKey(c)) {
                Set<Integer> set = map.get(c);
                if (set.contains(i)) {
                    A++;
                    set.remove(i);
                }
                if (set.isEmpty()) map.remove(c);
            }
        }
        //Second Lood, find B
        for (int i = 0; i < guess.length(); i++) {
            char c = guess.charAt(i);
            if (map.containsKey(c) && c != secret.charAt(i)) {
                Set<Integer> set = map.get(c);
                B++;
                int temp = set.iterator().next();
                set.remove(temp);
                if (set.isEmpty()) map.remove(c);
            }
        }

        StringBuilder result = new StringBuilder(A + "A" + B + "B");
        return result.toString();
    }
}

第六题 290. Word Pattern

题目描述

给定一个模式pattern和一个字符串str，判断str是否满足相同的pattern。

测试用例如题目描述。

注意：

pattern和str都只包含小写字母。
pattern和str不包含前导或者后缀空格。
str中的每一个单词之间都由一个空格分开。
pattern中的每一个字母都对应一个长度至少为1的单词

算法

利用HashMap进行对应

public class wordPattern290 {
    public boolean wordPattern(String pattern, String str) {
        if (pattern.isEmpty() || str.isEmpty()) return false;
        String[] words = str.split("\\s+");
        if (pattern.length() != words.length) return false;

        Map<Character, String > map = new HashMap<>();
        for(int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (map.containsKey(c)) {
                if (!map.get(c).equals(words[i])) return false;
            } else {
                if (map.containsValue(words[i])) return false;
                String a = map.put(c, words[i]);
            }
        }
        return true;
    }

    public boolean wordPattern2(String pattern, String str) {
        if (pattern.isEmpty() || str.isEmpty()) return false;
        String[] words = str.split("\\s+");
        if (pattern.length() != words.length) return false;

        Map map = new HashMap();
        for (Integer i = 0; i < pattern.length(); i++){
            if (map.put(pattern.charAt(i), i) != (map.put(words[i], i))) return false;
        }
        return true;
    }
}

学到的东西

在使用put方法的时候，put会有返回值，返回的是put之前的map中value的大小

第七题 274. H-Index

题目描述

给定研究人员的文章引用次数的数组（每一篇文章的引用次数都是非负整数），编写函数计算该研究人员的h指数。

根据维基百科对h指数的定义：“一名科学家的h指数是指其发表的N篇论文中，有h篇论文分别被引用了至少h次，其余N-h篇的引用次数均不超过h次”。

例如，给定引用次数数组 = [3, 0, 6, 1, 5]，这意味着研究人员总共有5篇论文，每篇分别获得了3, 0, 6, 1, 5次引用。由于研究人员有3篇论文分别至少获得了3次引用，且其余两篇的引用次数不超过3次，因而其h指数是3。

注意：如果存在多个可能的h值，取最大值作为h指数。

算法

利用自带的Array排序

我们需要保证的有两点

• 对于h篇文章，其中每一篇都大于等于h
• 对于剩余N - h篇，每篇都小于等于h

由于是排序，当我们找到满足第一点的最大值时，第二点自然成立

public class Solution {
    public int hIndex(int[] citations) {
        if (citations.length == 0) return 0;
        int n = citations.length;
        int[] num = new int[n + 1];
        for (int i = 0; i < n; i++) {
            if (citations[i] >= n ) num[n]++;
            else num[citations[i]]++;
        }
        int count = 0;
        for (int i = n; i >= 0; i--) {
            count += num[i];
            if (count >= i) return i;
        }
        return 0;   
    }
}

利用数组进行排序

由于我们想要求出h篇文章，每篇都大于等于h。

我们可以将引用次数作为角标，将他们出现的频率放入一个数组中。数组的角标就是引用的次数，记出现次数为0，当出现次数恰好大于等于角标i的时候，说明我们已经有了h篇文章，使得他们的引用次数大于i。由于 h >= i，所以此时是最大值

public class Solution {
    public int hIndex(int[] citations) {
        if (citations.length == 0) return 0;
        int n = citations.length;
        int[] num = new int[n + 1];
        for (int i = 0; i < n; i++) {
            if (citations[i] >= n ) num[n]++;
            else num[citations[i]]++;
        }
        int count = 0;
        for (int i = n; i >= 0; i--) {
            count += num[i];
            if (count >= i) return i;
        }
        return 0;   
    }
}

第八题 314. Binary Tree Vertical Order Traversal

题目描述

将一个二叉树，按照从左到右，从上到下的形状，通过List进行输出。

算法

利用BFS + 两个HashMap分别存储所有垂直线上的点，以及本身的垂直线

public class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        if (root == null) return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        Map<Integer, List<Integer>> store = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        HashMap<TreeNode, Integer> weight = new HashMap<TreeNode, Integer>();
        queue.offer(root);
        weight.put(root, 0);
        int min = 0;
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            int w = weight.get(cur);
            List<Integer> list = store.getOrDefault(w, new ArrayList<>());
            list.add(cur.val);
            store.put(w, list);
            if (cur.left != null) {
                queue.add(cur.left);
                weight.put(cur.left, w - 1);
            }

            if (cur.right != null) {
                queue.add(cur.right);
                weight.put(cur.right, w + 1);
            }
            min = Math.min(min, w);
        }
        while (store.containsKey(min)) {
            res.add(store.get(min++));
        }
        return res;        
    }
}