[LC] Perfect Rectangle / Find the Difference / Eli

mingde 發布于2019-08-14 14:33 / 1260人閱讀

Find the Difference

User Accepted: 812
User Tried: 861
Total Accepted: 1362
Total Submissions: 1552
Difficulty: 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:

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: 26
Total Accepted: 8
Total Submissions: 40
Difficulty: 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 9
2 4 6 8
2 6
6

Output:

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: 136
Total Accepted: 8
Total Submissions: 338
Difficulty: Hard
Given 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]);
    }
}

云服務器 GPU云服務器 Difference perfect the Rectangle

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/65078.html

leetcode391. Perfect Rectangle

摘要：題目要求用一個二維數組來表示一堆矩形，二維數組中的每一行分別記錄矩形左下角和右上角的坐標。該理想情況下矩形的面積應當等于所有矩形的面積之和。一旦不相等，則一定無法構成大的矩形。其次，光判斷面積并不足夠，可以這樣三個矩形構成的圖形。題目要求 Given N axis-aligned rectangles where N > 0, determine if they all togeth...

不知名網友 2019-08-16 15:40 評論0 收藏0
[LintCode] Largest Rectangle in Histogram

摘要：只要出現當前右邊界高度小于等于棧頂元素高度的情況，就取出棧頂元素當前遍歷過最高的并對這個元素進行取最大矩形的運算。 Problem Given n non-negative integers representing the histograms bar height where the width of each bar is 1, find the area of largest ...

alighters 2019-08-14 15:27 評論0 收藏0
Perfect Rectangle

摘要：首先確定上下的邊界，左右線段按照橫坐標排序。檢查填充滿上圖的情況就組成不了一個長方形。找重合和有空隙只需要把所有橫坐標在的線段排序之后檢查首位相連，且起點，終點。且最后成的面積等于小矩形的面積和。 Perfect Rectangle 題目鏈接：https://leetcode.com/problems... 掃描線，哪個方向都行。我是從左往右掃，矩陣按照左右的邊來存。showImg(h...

SolomonXie 2019-08-14 17:23 評論0 收藏0
[LeetCode/LintCode] Construct the Rectangle

Problem For a web developer, it is very important to know how to design a web pages size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose l...

sf_wangchong 2019-08-15 17:58 評論0 收藏0
[Leetcode] Shortest Word Distance 最短單詞間距

摘要：代碼第一次寫入就先不比較第一次寫入就先不比較哈希表法復雜度時間空間思路因為會多次調用，我們不能每次調用的時候再把這兩個單詞的下標找出來。我們可以用一個哈希表，在傳入字符串數組時，就把每個單詞的下標找出存入表中。 Shortest Word Distance Given a list of words and two words word1 and word2, return the ...

jsliang 2019-08-14 12:48 評論0 收藏0