[LC] Perfect Rectangle / Find the Difference / Eli

mingde 发布于2019-08-14 14:33 / 1172人阅读

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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