Share my solutions for Contest 2


  • 6
    L

    Problem 1 is trivial:

        public char findTheDifference(String s, String t) {
            int[] count = new int[128];
    		for (char ch : t.toCharArray())
    			count[ch] += 1;
    
    		for (char ch : s.toCharArray())
    			count[ch] -= 1;
    
    		char ans = 'a';
    		for (int i = 0; i < 128; i++) {
    			if (count[i] != 0)
    				ans = (char) i;
    		}
    
    		return ans;
        }
    

    Problem 2:
    We can get rid of half of the number for each round, the key idea is to find the starting number of the next round.

        public int lastRemaining(int n) {
    		int remaining = n;
    		int start = 1;
    		int step = 2;
    		boolean left = true;
    		while (remaining > 1) {
    			remaining = remaining / 2;
    			if (left)
    				start = start + step * remaining - step / 2;
    			else
    				start = start - step * remaining + step / 2;
    
    			step *= 2;
    			left = left ? false : true;
    		}
    
    		return start;
        }
    

    Problem 3:
    This is not a correct solution see @stachenov counter example below.
    We need to check both vertically and horizontally if the accumulated heights and width can form a rectangle. Overral running time is O(m + n).

    The OJ has a missing test case: { 1, 1, 4, 4 }, { 1, 3, 4, 5 }, { 1, 6, 4, 7 }. These 3 rectangles can not form a rectangle, some buggy code can still pass all test cases.
    Another missing test case: {{1, 1, 2, 2}, {2, 1, 3, 2}, {2, 1, 3, 2}, {2, 1, 3, 2}, {3, 1, 4, 2}}


  • 1

    @lzb700m said in Share my solutions for Contest 2:

    if (left)
    start = start + step * remaining - step / 2;
    else
    start = start - step * remaining + step / 2;

    would you mind explaining why these work? (how do you come out the idea, so great)


  • 4
    L

    The original array is formed by [1, 2, 3, 4, ..., N], one observation is that:
    if at the start of each round: we have n numbers and the distance between the remaining numbers is d,
    then at the end of each round: we have n / 2 numbers left, and the distance between the remaining numbers is 2d.
    For example,

    Original: [1, 2, 3, 4, 5, 6, 7, 8, 9], n = 9, d = 1;
    Round 1: [ , 2, , 4, , 6, , 8, ], n = 4, d = 2;
    Round 2: [ , 2, , , , 6, , , ], n = 2, d = 4;
    Round 3: [ , , , , , 6, , , ], n = 1, d = 8;
    Round 4: because n == 1, end of iteration

    Next observation is that you can calculate the start number of next round in constant time. How?
    You know how many numbers you are going to skip, which is n / 2, and you know the starting number, and you know the step size.

    Original: [1, 2, 3, 4, 5, 6, 7, 8, 9], start = 1, step = 2, skipped = n / 2 = 4;
    Round 1: [ , 2, , 4, , 6, , 8, ], start = 1 + step * skipped - step / 2 = 8, step = 4, skipped = 2;
    Round 2: [ , 2, , , , 6, , , ], start = 8 - step * skipped + step / 2 = 2, step = 8, skipped = 1;
    Round 3: [ , , , , , 6, , , ], start = 2 + step * skipped - step / 2 = 6, step = 16, skipped = 0;
    Round 4: because skipped == 0, end of iteration, return start, which is 6.

    Hope this helps.


  • 0
    L

    For problem 3, can we just compare the total area? Or we have to accumulate width and height?

    I can pass 26/27 cases, can you tell where is wrong? Thanks.

    public class Solution {
        public boolean isRectangleCover(int[][] A) {
            int m = A.length;
            int minlbrow = Integer.MAX_VALUE, minlbcol = Integer.MAX_VALUE, maxrurow = 0, maxrucol = 0;
            for (int i = 0; i < m; i++) {
                minlbrow = Math.min(minlbrow, A[i][1]);
                minlbcol = Math.min(minlbcol, A[i][0]);
                maxrurow = Math.max(maxrurow, A[i][3]);
                maxrucol = Math.max(maxrucol, A[i][2]);
            }
            int[] largest = {minlbrow, minlbcol, maxrurow, maxrucol};
            int alarge = area(largest);
            int asum = 0;
            for (int i = 0; i < m; i++) {
                asum += area(A[i]);
            }
            return asum == alarge;
        }
        public int area(int[] a) {
            if (a.length != 4) return 0;
            return (a[2]-a[0]) * (a[3]-a[1]);
        }
    }
    

  • 0

    @lin40
    It isn't tagged hard for nothing. By comparing area, you are not considering overlaps. Width and height won't help you much with it, either. Comparing areas and checking that there are no overlaps will give you the right answer, but it's easier said than done.


  • 0
    L

    @lin40 try the test case I listed in my original post

    { 1, 1, 4, 4 }, { 1, 3, 4, 5 }, { 1, 6, 4, 7 }
    

  • 2

    @lzb700m
    I felt like your problem 3 solution is not entirely correct, and after playing around with some tests, I was able to prove it. Try

    [[0, 1, 2, 3],[0, 1, 1, 2],[2, 2, 3, 3],[1, 0, 3, 1],[2, 0, 3, 1]]

    2 x x x
    1 2 x  
    0   x 2
      0 1 2
    

    It fails because there are overlaps, and yet total heights and widths add up nicely. See the picture: each x is occupied by one rectangle, 2 means two rectangles overlap there.


  • 0
    Y

    @stachenov Nice test case! It fails my accepted code too.


  • 0
    L

    @stachenov Thank you for spotting the bug. Great test case! Then I guess this approach may not work in general. We have to solve the problem from a different perspective.


  • 0

    @lzb700m Thanks for highlighting these missing test cases. I have added your test case and @stachenov test case. Thanks.


Log in to reply
 

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