share my easy way to approach P1. Including P3 explanation


  • 1

    Problem 1
    My solution is calculating their sum of ascII, and do the subtraction to get the additional character, For example, there are two strings: s = "abc" and t = "abcd", the sum1 of s will be 97+98+99, the sum2 of t will be 97 + 98 + 99 + 100.
    If we do the subtraction sum2 - sum1, we'll get the additional character.

    public class Solution {
        public char findTheDifference(String s, String t) {
            if (s == null || t == null) return (char)0;
            int ascII1 = 0, ascII2 = 0;
            for (int i = 0; i < s.length(); i++) {
                ascII1 += (int)s.charAt(i);
            }
            for (int j = 0; j < t.length(); j++) {
                ascII2 += (int)t.charAt(j);
            }
            return (char)(ascII2 - ascII1);
        }
    }
    

    Problem 3
    There is a rule in P3, see the pic bellow:
    0_1472368324914_upload-82503da3-df36-43f7-be5f-8e6e31830a20
    you'll find red points appear 2 times, while green points only 1 time.
    Every rectangle's four points coordinate are (x,y), (i,j), (i, y), (x, j).
    For example:
    rectangle a -> (1,1), (2,3), (2,1), (1,3)
    rectangle b -> (2,1), (5,3), (5,1), (2,3)
    rectangle c -> (1,3), (4,4), (4,3), (1,4)
    rectangle d -> (4,3), (5,4), (5,3), (4,4)
    And then ELIMINATE duplicate coordinates:
    0_1472368933779_upload-f4773aa0-d67d-4237-beb7-8e0502c84361
    You get four corner now (1,1),(5,1),(5,4),(1,4)
    Therefore what we need to do is get all nodes and eliminate duplicate ones, if the remaining nodes amount is 4, then return true.

    The code is:

    public class Solution {
        public boolean isRectangleCover(int[][] rectangles) {
            if (rectangles == null || rectangles.length == 0 || rectangles[0].length == 0) return false;
            
            HashMap<Node, Integer> map = new HashMap<>();
            for (int i = 0; i < rectangles.length; i++) {
                Node n1 = new Node(rectangles[i][0], rectangles[i][1]);
                if (map.containsKey(n1)) 
                    map.put(n1, map.get(n1)+1);
                else 
                    map.put(n1, 1);
                
                Node n2 = new Node(rectangles[i][2], rectangles[i][3]);
                if (map.containsKey(n2)) 
                    map.put(n2, map.get(n2)+1);
                else 
                    map.put(n2, 1);
                
                Node n3 = new Node(rectangles[i][2], rectangles[i][1]);
                if (map.containsKey(n3)) 
                    map.put(n3, map.get(n3)+1);
                else 
                    map.put(n3, 1);
                
                Node n4 = new Node(rectangles[i][0], rectangles[i][3]);
                if (map.containsKey(n4)) 
                    map.put(n4, map.get(n4)+1);
                else
                    map.put(n4, 1);
            }
            int flag = 0;
            for (Map.Entry<Node, Integer> entry : map.entrySet()) {
                if (entry.getValue() == 1) flag++;
            }
            return flag == 4;
        }
    }
    
    class Node {
        int x;
        int y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public boolean equals(Object o) {
            Node n = (Node)o;
            if (this.x == n.x && this.y == n.y) return true;
            return false;
        }
        @Override
        public int hashCode() {
            return (x + "" + y).hashCode();
        }
    }
    

  • 0

    @lusoul your P3 solution doesn't work for the following input [[0, 0, 3, 3], [1, 1, 2, 2], [1, 1, 2, 2]]


  • 0

    @dettier Thanks, I have added your test case.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.