Mock Interview: Amazon #4

4628 ワード

Rectangle Overlap

class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        //bottom left, top right
        // x1, x2 사이에 x1 or x2가 있음
        // y1, y2 사이에 y1 or y2가 있음
        // 둘 다 충족해야함...!!
        
        boolean veranswer = isBetween(rec1[0], rec1[2], rec2[0]) || isBetween(rec1[0], rec1[2], rec2[2]);
        boolean horanswer = isBetween(rec1[1], rec1[3], rec2[1]) || isBetween(rec1[1], rec1[3], rec2[3]);
        
        return veranswer && horanswer;
    }
    
    
    private boolean isBetween(int x1, int x2, int x3) {
        if (x3 > x1 && x3 < x2) {
            return true;
        } else {
            return false; 
        }
    }
}
46/54 test cases passed.
class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        //bottom left, top right
        // x1, x2 사이에 x1 or x2가 있음
        // y1, y2 사이에 y1 or y2가 있음
        // 둘 다 충족해야함...!!
        
        boolean veranswer = isBetweenSmall(rec1[0], rec1[2], rec2[0], rec1[1], rec1[3], rec2[1]);
            //|| isBetween2(rec1[0], rec1[2], rec2[0]) || isBetween2(rec1[0], rec1[2], rec2[2]);
        boolean horanswer = isBetweenLarge(rec1[0], rec1[2], rec2[2], rec1[1], rec2[3], rec1[3]);
            //|| isBetween2(rec1[1], rec1[3], rec2[1]) || isBetween2(rec1[1], rec1[3], rec2[3]);
        
        return veranswer || horanswer;
    }
    
    
    private boolean isBetweenSmall(int x1, int x2, int x, int y1, int y2, int y) {
        if (x >= x1 && x < x2 && y >= y1 && y < y2) {
            return true;
        } else {
            return false; 
        }
    }
    
    private boolean isBetweenLarge(int x1, int x2, int x, int y1, int y2, int y) {
        if (y > y1 && y <= y2 && x > x1 && x <= x2) {
            return true;
        } else {
            return false; 
        }
    }
}
39/54 test cases passed.
class Solution {
    public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
        if (rec1[0] == rec1[2] || rec1[1] == rec1[3] ||
            rec2[0] == rec2[2] || rec2[1] == rec2[3]) {
            return false;
        }
        
        if (rec1[0] >= rec2[2] || rec2[0] >= rec1[2]) {
            return false;
        }
        
        if (rec1[1] >= rec2[3] || rec2[1] >= rec1[3]) {
            return false;
        }
        
        return true; 
    }
}
Runtime: 0 ms, faster than 100.00% of Java online submissions for Rectangle Overlap.
Memory Usage: 35.9 MB, less than 95.38% of Java online submissions for Rectangle Overlap.
^^...

Partiton Labels


和弦又...
class Solution {
    public List<Integer> partitionLabels(String S) {
        //at most one part
        
        int[] count = new int[26];
        
        for (int i = 0; i < S.length(); i++) {
            count[S.charAt(i) - 'a']++;
        }
        
        List<Integer> result = new ArrayList<Integer>();
        
        int start = 0;
        int end = 0;
        Set<Character> find = new HashSet<Character>();
        
        while (end < S.length()) {
            char c = S.charAt(start);
            if (count[c - 'a'] == 1 && find.isEmpty()) {
                result.add(end - start + 1);
                start = end + 1;
            } else if (find.contains(c) && count[c-'a'] == 1) {
                find.remove(c);
            } else if (! find.contains(c) && count[c-'a'] > 1) {
                find.add(c);
            }
            
            count[c - 'a']--; 
            
            end++;
        }
        
        return result;
    }
}