Find the Difference

User Accepted: 812

User Tried: 861Total Accepted: 1362Total Submissions: 1552Difficulty: Easy

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:

s = "abcd"t = "abcde"

Output:

e

Explanation:

'e' is the letter that was added.

Solution

public class Solution {    public char findTheDifference(String s, String t) {        Map
    
      map = new HashMap<>();        char[] schar = s.toCharArray();        char[] tchar = t.toCharArray();        for (int i = 0; i < s.length(); i++) {            if (map.containsKey(schar[i])) map.put(schar[i], map.get(schar[i])+1);            else map.put(schar[i], 1);        }        for (int i = 0; i < t.length(); i++) {            if (map.containsKey(tchar[i]) && map.get(tchar[i]) > 0) map.put(tchar[i], map.get(tchar[i])-1);            else return tchar[i];        }        return 'a';    }}
    

Elimination Game

User Accepted: 6

User Tried: 26Total Accepted: 8Total Submissions: 40Difficulty: Medium

There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

Input:

n = 9,1 2 3 4 5 6 7 8 92 4 6 82 66

Output:

6

Solution

public class Solution {    public int lastRemaining(int n) {        int rest = n, start = 1, step = 2;        boolean left = true;        while (rest > 1) {            rest /= 2;            if (left) start = start + step * rest - step / 2;            else start = start - step * rest + step / 2;            step *= 2;            left = !left;        }        return start;    }}

Perfect Rectangle

User Accepted: 7

User Tried: 136Total Accepted: 8Total Submissions: 338Difficulty: HardGiven N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example

Example 1:

rectangles = [  [1,1,3,3],  [3,1,4,2],  [3,2,4,4],  [1,3,2,4],  [2,3,3,4]]

Return true. All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

rectangles = [  [1,1,2,3],  [1,3,2,4],  [3,1,4,2],  [3,2,4,4]]

Return false. Because there is a gap between the two rectangular regions.

Example 3:

rectangles = [  [1,1,3,3],  [3,1,4,2],  [1,3,2,4],  [3,2,4,4]]

Return false. Because there is a gap in the top center.

Example 4:

rectangles = [  [1,1,3,3],  [3,1,4,2],  [1,3,2,4],  [2,2,4,4]]

Return false. Because two of the rectangles overlap with each other.

Solution (26/27 passed)

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]);    }}