题目描述:
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:
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);
}
}