6.7号刷题

发表于 | 分类于 | 0 comments

第一题 508. Most Frequent Subtree Sum

题目描述

给定一棵二叉树，求其最频繁子树和。即所有子树的和中，出现次数最多的数字。如果存在多个次数一样的子树和，则全部返回。

注意：你可以假设任意子树和均为32位带符号整数。

算法

利用hashmap将相同的sum值进行存储和记录，然后利用前序遍历对整个树进行一遍遍历，存储下所有的字数的sum值。最后再进行统计

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class findFrequentTreeSum508 {
    Map<Integer, Integer> store;
    int maxnum;
    public int[] findFrequentTreeSum(TreeNode root) {
        if (root == null) return new int[0];
        store = new HashMap<Integer, Integer>();
        maxnum = 0;
        int sum = preOrder(root);
        List<Integer> res = new ArrayList<>();
        for (int key : store.keySet()) {
            if (store.get(key) == maxnum) res.add(key);
        }
        int[] result = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }
    public int preOrder(TreeNode root) {
        if (root == null) return 0;
        int left = preOrder(root.left);
        int right = preOrder(root.right);
        int sum = left + right + root.val;
        int count = store.getOrDefault(sum, 0) + 1;
        store.put(sum, count);
        maxnum = Math.max(count, maxnum);
        return sum;
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}

学到的东西

  • 注意下树的前序中序后序遍历是怎么遍历的。
  • 另外List 转为Array 的 int[] result = list.toArray(new int[list.size()])是无法对int形使用的，只能对Integer型

第二题 389. Find the Difference

题目描述

给定两个字符串s和t，都只包含小写字母。

字符串t由字符串s打乱顺序并且额外在随机位置添加一个字母组成。

寻找t中新增的那个字母。

测试用例如题目描述。

算法

与在一个Array中找出不重复的数字算法相同, 利用亦或运算，相同的最后亦或之后最终会变为0，只会留下不同的那一个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public char findTheDifference(String s, String t) {
        if (t.length() <= s.length()) return 0;
        int result = 0;
        for (char c : s.toCharArray()) {
            result = result ^ c;
        }
        
        for (char c : t.toCharArray()) {
            result = result ^ c;
        }
        
        char re = (char) result;
        return re;       
    }
}

第三题 451. Sort Characters By Frequency

题目描述

给定一个字符串，将字符按照出现次数从高到低排序。

算法

用HashMap记录下每个字母和起出现次数，然后最后排序后打印出来。

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
28
29
30
31
public class Solution {
    public String frequencySort(String s) {
        if (s.length() <= 1) return s;
        //Each character and its frequency
        Map<Character, Integer> store = new HashMap<>();
        for (char c : s.toCharArray()) {
            int count = store.getOrDefault(c, 0) + 1;
            store.put(c, count);
        }
        List<Map.Entry<Character, Integer>> list = new LinkedList<Map.Entry<Character, Integer>>(store.entrySet());
        Collections.sort(list, new Comparator <Map.Entry<Character, Integer>>() {
            public int compare(Map.Entry<Character, Integer> o1,
                               Map.Entry<Character, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });
        StringBuilder re = new StringBuilder();
        for (Map.Entry<Character, Integer> entry : list) {
            for (int i = 0; i < entry.getValue(); i++) {
                re.append(entry.getKey());
            }
        }
        return re.toString();        
    }
}

学到的东西

如何对一个HashMap根据其Value排序

第四题 311. Sparse Matrix Multiplication

算法

对应每个位置相乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int rowA = A.length, colA = A[0].length, colB = B[0].length;
        int[][] C = new int[rowA][colB]; // [n * m] * [m * n] = [n * n]
        
        for (int i = 0; i < rowA; i++) {
            for (int j = 0; j < colA; j++) {
                if (A[i][j] != 0) {
                    for (int k = 0; k < colB; k++) {
                        C[i][k] += A[i][j] * B[j][k];
                    }
                }
            }
        }
        
        return C;        
    }
}

第五题 599. Minimum Index Sum of Two Lists

题目描述

求两个字符串列表中索引之和最小的公共串

注意：

列表长度范围[1, 1000]

字符串长度[1, 30]

下标范围[0, len - 1]

列表内无重复

算法

利用HashMap存储出现过的数， 然后之后用List存储所有的结果。

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
public class findRestaurant599 {
        public String[] findRestaurantRefc(String[] list1, String[] list2) {
            if (list1 == null || list2 == null) return new String[0];
    
            Map<String, Integer> store = new HashMap<>();
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < list1.length; i++) {
                store.put(list1[i], i);
            }
            List<String> res = new ArrayList<>();
            for (int i = 0; i < list2.length; i++) {
                if (store.containsKey(list2[i])) {
                    int temp = store.get(list2[i]);
                    if (i + temp < min) {
                        res = new ArrayList<>();
                        min = i + temp;
                        res.add(list2[i]);
                    } else if (i + temp == min) {
                        res.add(list2[i]);
                    }
                }
            }
            return res.toArray(new String[res.size()]);
        }
}

第六题 347. Top K Frequent Elements

题目描述

给定一个非空整数数组，返回其前k个出现次数最多的元素。

测试用例如题目描述。

注意：

你可以假设k总是有效的，1 ≤ k ≤ 独立元素的个数。

你的算法时间复杂度必须优于O(n log n)，其中n是数组的长度。

算法

利用HashMap存储频率，但是有个很巧妙的解决排序问题。可以利用一个数组长度的List数组来存储频率，由于需要输出前k个，那么最后从list数组从后向前输出即可。

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
28
29
30
31
32
33
34
public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        if (nums == null) return new ArrayList<>();
        
        // Key : Number, Value: Frequency
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer>[] bucket = new List[nums.length + 1];
        
        for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
        
        for (int key : map.keySet()) {
            int frequency = map.get(key);
            if (bucket[frequency] == null) {
                bucket[frequency] = new ArrayList<>();
            }
            bucket[frequency].add(key);
        }
        
        List<Integer> res = new ArrayList<>();
        for (int i = nums.length; i >= 0 && res.size() < k; i--) {
            if (bucket[i] != null) {
                res.addAll(bucket[i]);
            }
        }
        
        if (res.size() > k) {
            for (int i = 0; i < res.size() - k; i++) {
                res.remove(res.size() - i - 1);
            }
        }
        
        return res;        
    }
}

第七题 349. Intersection of Two Arrays

题目描述

给定两个数组，编写函数计算它们的交集。

测试用例如题目描述。

注意：

结果中的每个元素一定是唯一的。

结果可以采用任意顺序。

算法

三种算法:

  • 可以使用Set用数据进行存储
  • 如果两个Array都是有序的，可以利用两个指针进行推进
  • 如果有一个有序，可以利用二分查找
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    public class Solution {
        public int[] intersection(int[] nums1, int[] nums2) {
            if (nums1 == null || nums2 == null) return new int[0];
            Set<Integer> set = new HashSet<>();
            for (int num : nums1) set.add(num);
            List<Integer> res = new ArrayList<>();
            for (int num : nums2) {
                if (set.contains(num) && !res.contains(num)) res.add(num);
            }
            int[] result = new int[res.size()];
            for (int i = 0; i < result.length; i++) {
                result[i] = res.get(i);
            }
            return result;      
        }
    }

第八题 359. Intersection of Two Arrays II

算法

与之前类似，只不过现在使用一个Hashmap对数字进行存储

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
public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) return new int[0];
        
        //Key: number Value: frequency
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int num : nums1) map.put(num, map.getOrDefault(num, 0) + 1);
        
        List<Integer> store = new ArrayList<>();
        for (int num : nums2) {
            if (map.containsKey(num)) {
                if (map.get(num) > 0) {
                    store.add(num);
                    map.put(num, map.get(num) - 1);
                } 
            }
        }
        
        int[] res = new int[store.size()];
        for (int i = 0; i < store.size(); i++) {
            res[i] = store.get(i);
        }
        
        return res;        
    }
}

第九题 237. Delete Node in a Linked List

题目描述

编写一个函数删除单链表中（除末尾节点外）的一个节点，只提供待删除节点。

假如链表是1 -> 2 -> 3 -> 4 给你第3个节点，值为3，则调用你的函数后链表为1 -> 2 -> 4

算法

忽然想起来这道题在很久以前找实习的时候遇到过，当时没有做出来，希望经过自己的努力，会有慢慢的提高吧。

1
2
3
4
5
6
public class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

第十题 206. Reverse Linked List

题目描述

单链表逆置

提示：
用递归和迭代方式分别实现。

算法

iterative
1
2
3
4
5
6
7
8
9
10
11
12
public class reverseList206 {
    public ListNode reverseList(ListNode head) {
        ListNode newhead = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = newhead;
            newhead = head;
            head = next;
        }
        return newhead;
    }
}
recursive
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public ListNode reverseList(ListNode head) {
        return helper(head, null);
    }
    
    public ListNode helper(ListNode head, ListNode newhead) {
        if (head == null) return newhead;
        ListNode next = head.next;
        head.next = newhead;
        return helper(next, head);
    }
    
}

学到的东西

LinkedList的入门知识，自己多梳理一遍，回忆一下。