Leetcode Contest 8/25/2018

892. Surface Area of 3D Shapes

On a N * N grid, we place some 1 * 1 * 1 cubes.

Each value v = grid[j] represents a tower of v cubes placed on top of grid cell (i, j).

Return the total surface area of the resulting shapes.

1. class Solution {
   
2.     public int surfaceArea(int[][] grid) {
   
3.         if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
   
4.         int R = grid.length;
   
5.         int C = grid[0].length;
   
6.         int area = 0;
   
7.         for (int r = 0; r < R; r++) {
   
8.             for (int c = 0; c < C; c++) {
   
9.                 int h = grid[r][c];
   
10.                 if (h > 0) {
    
11.                     area += (h * 4 + 2);
    
12.                     area -= overlapped(r, c, R, C, grid);
    
13.                 }
    
14.             }
    
15.         }
    
16.         return area;
    
17.     }
    
18.    
    
19.     public int height(int r, int c, int R, int C, int[][] grid) {
    
20.         if (r >= 0 && r < R && c >= 0 && c < C) {
    
21.             return grid[r][c];
    
22.         } else {
    
23.             return 0;
    
24.         }
    
25.     }
    
26.    
    
27.     public int overlapped(int r, int c, int R, int C, int[][] grid) {
    
28.         int h = grid[r][c];
    
29.         return Math.min(h, height(r + 1, c, R, C, grid)) +
    
30.             Math.min(h, height(r -1, c, R, C, grid)) +
    
31.             Math.min(h, height(r, c + 1, R, C, grid)) +
    
32.             Math.min(h, height(r, c - 1, R, C, grid));
    
33.     }
    
34. }

复制代码

893. Groups of Special-Equivalent Strings

You are given an array A of strings.

Two strings S and T are [i]special-equivalent if after any number of moves, S == T.

A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S with S[j].

Now, a [i]group of special-equivalent strings from A is a non-empty subset of A such that any string not in A is not special-equivalent with any string in A.

Return the number of groups of special-equivalent strings from A.

1. import java.util.Arrays;
   
2. 
   
3. class Solution {
   
4.     public int numSpecialEquivGroups(String[] A) {
   
5.         if (A == null || A.length == 0) return 0;
   
6.         Set<String> set = new HashSet<String>();
   
7.         for (String s: A) {
   
8.             set.add(min(s));
   
9.         }
   
10.         return set.size();
    
11.     }
    
12.    
    
13.     public String min(String s) {
    
14.         if (s == null) return null;
    
15.         if (s.length() == 0) return "";
    
16.         int len = s.length();
    
17.         char[] even = new char[(len +1) / 2];
    
18.         for (int i = 0; i < len; i += 2) even[i / 2] = s.charAt(i);
    
19.         char[] odd = new char[len / 2];
    
20.         for (int i = 1; i < len; i += 2) odd[i / 2] = s.charAt(i);
    
21.         Arrays.sort(even);
    
22.         Arrays.sort(odd);
    
23.         char[] result = new char[len];
    
24.         for (int i = 0; i < len; i += 2) result[i] = even[i / 2];
    
25.         for (int i = 1; i < len; i += 2) result[i] = odd[i / 2];
    
26.         return new String(result);
    
27.     }
    
28. }

复制代码

894. All Possible Full Binary Trees

A full binary tree is a binary tree where each node has exactly 0 or 2 children.

Return a list of all possible full binary trees with N nodes.  Each element of the answer is the root node of one possible tree.

Each node of each tree in the answer must have node.val = 0.

You may return the final list of trees in any order.

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.     static Map<Integer, List<TreeNode>> dic = new HashMap<>();
    
12.    
    
13.    
    
14.     static private  void buildDic(int N) {
    
15.         List<TreeNode> one = new ArrayList<TreeNode>();
    
16.         one.add(newTreeNode());
    
17.         dic.put(1, one);
    
18.         for (int n = 1; n <= N; n += 2) {
    
19.             if (dic.containsKey(n)) continue;
    
20.             List<TreeNode> list = new ArrayList<>();
    
21.             for (int l = 1; l <= n - 2; l += 2) {
    
22.                 int r = n - l - 1;
    
23.                 // System.out.println("" + l + ", " + r);
    
24.                 for (TreeNode left : dic.get(l)) {
    
25.                     for (TreeNode right: dic.get(r)) {
    
26.                         TreeNode root = newTreeNode();
    
27.                         root.left = copy(left);
    
28.                         root.right = copy(right);
    
29.                         list.add(root);
    
30.                     }
    
31.                 }
    
32.             }
    
33.             dic.put(n, list);
    
34.         }
    
35.     }
    
36.    
    
37.     static private TreeNode newTreeNode() { return new TreeNode(0); }
    
38.    
    
39.     public List<TreeNode> allPossibleFBT(int N) {
    
40.         if (N <= 0 || N % 2 == 0) return new ArrayList<TreeNode>();
    
41.         buildDic(N);
    
42.         return dic.get(N);
    
43.     }
    
44.    
    
45.     static public TreeNode copy(TreeNode origin) {
    
46.         if (origin == null) return null;
    
47.         TreeNode copied = new TreeNode(origin.val);
    
48.         copied.left = copy(origin.left);
    
49.         copied.right = copy(origin.right);
    
50.         return copied;
    
51.     }
    
52. }

复制代码

895. Maximum Frequency Stack

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

• push(int x), which pushes an integer x onto the stack.
• pop(), which removes and returns the most frequent element in the stack.
  • If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.
    
  
  

1. class FreqStack {
   
2.    
   
3.     static class Node implements Comparable {
   
4.         int val;
   
5.         int freq;
   
6.         int order;
   
7.         public Node(int val, int freq, int order) {
   
8.             this.val = val;
   
9.             this.freq = freq;
   
10.             this.order = order;
    
11.         }
    
12.         @Override
    
13.         public int compareTo(Object o) {
    
14.             Node that = (Node) o;
    
15.             if (this.freq != that.freq) return that.freq - this.freq;
    
16.             return that.order - this.order;
    
17.         }
    
18.     }
    
19.    
    
20.     Map<Integer, Integer> freqs;
    
21.     PriorityQueue<Node> pq;
    
22.     int order = 0;
    
23.    
    
24.     public FreqStack() {
    
25.         freqs = new HashMap<>();
    
26.         pq = new PriorityQueue<>();
    
27.     }
    
28.    
    
29.     public void push(int x) {
    
30.         order += 1;
    
31.         int freq = freqs.getOrDefault(x, 0) + 1;
    
32.         freqs.put(x, freq);
    
33.         pq.offer(new Node(x, freq, order));
    
34.     }
    
35.    
    
36.     public int pop() {
    
37.         Node node = pq.poll();
    
38.         if (node.freq == 1) {
    
39.             freqs.remove(node.val);
    
40.         } else {
    
41.             freqs.put(node.val, node.freq - 1);
    
42.         }
    
43.         return node.val;
    
44.     }
    
45. }
    
46. 
    
47. /**
    
48. * Your FreqStack object will be instantiated and called as such:
    
49. * FreqStack obj = new FreqStack();
    
50. * obj.push(x);
    
51. * int param_2 = obj.pop();
    
52. */

复制代码