Leetcode 0223: Rectangle Area

题目描述:

Given an input string s and a pattern p, implement regular expression matching with support for ’ . ’ and ‘ * ‘ where:
‘.’ Matches any single character.​​​​
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

Example 1:
Leetcode 0223: Rectangle Area

Input: A = -3, B = 0, C = 3, D = 4, E = 0, F = -1, G = 9, H = 2
Output: 45

Notes:

Assume that the total area is never beyond the maximum possible value of int.

Time complexity:
根据容斥原理
两个矩形重叠后形成的总面积 = 矩形面积S1 + 矩形面积S2 - 两个矩形相交的面积. 求两个线段线段1: A ______B 和线段2 C_____D 的相交线段长的长度 = Math
max(0, min(B,D) - max(A,C)) 线段尾的最小值减去线段头的最大值。

class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        long l = Math.max(0,  (long)Math.min(C,G) - Math.max(A,E));
        long w = Math.max(0,  (long)Math.min(D,H) - Math.max(B,F));
        return (int)((long)(C-A)*(D-B) + (H-F)*(G-E) - l*w);
    }
}
上一篇:每天shell之批量重命名


下一篇:使用sh-x调试shell脚本