本文收集了一些LeetCode的一些较难的题目。
找出两个正序数组的中位数
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 (归并、快速排序 n.log(n))。假设 nums1 和 nums2 不会同时为空。
示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0
示例 2: nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| public static double problem1(int[] nums1, int[] nums2){
int i = 0,j = 0,count = 0;
int left = 0, right = 0;
if((nums1.length + nums2.length) % 2 == 0 ){
while(i < nums1.length && j < nums2.length && count < (nums1.length + nums2.length) / 2 + 1){
if(nums1[i] <= nums2[j]){
count++;
if(count == (nums1.length + nums2.length) / 2){
left = nums1[i];
}
if(count == (nums1.length + nums2.length) / 2 + 1){
right = nums1[i];
}
System.out.print(nums1[i] +" ( 第"+ count +"个 )" + " ->");
i++;
}else{
count++;
if(count == (nums1.length + nums2.length) / 2){
left = nums2[j];
}
if(count == (nums1.length + nums2.length) / 2 + 1){
right = nums2[j];
}
System.out.print(nums2[j] +" ( 第"+ count +"个 )" + "->");
j++;
}
}
while(i < nums1.length && count < (nums1.length + nums2.length) / 2 + 1){
count++;
if(count == (nums1.length + nums2.length) / 2){
left = nums1[i];
}
if(count == (nums1.length + nums2.length) / 2 + 1){
right = nums1[i];
}
System.out.print(nums1[i] +" ( 第"+ count +"个 )" + "->");
i++;
}
while(j < nums2.length && count < (nums1.length + nums2.length) / 2 + 1){
count++;
if(count == (nums1.length + nums2.length) / 2){
left = nums2[j];
}
if(count == (nums1.length + nums2.length) / 2 + 1){
right = nums2[j];
}
System.out.print(nums2[j] +" ( 第"+ count +"个 )" + "->");
j++;
}
return (left + right) 1.0 / 2;
}else{
while(i < nums1.length && j < nums2.length && count < (nums1.length + nums2.length) / 2 + 1){
if(nums1[i] <= nums2[j]){
count++;
if(count == (nums1.length + nums2.length) / 2 + 1){
left = nums1[i];
}
System.out.print(nums1[i] +" ( 第"+ count +"个 )" + "->");
i++;
}else{
count++;
if(count == (nums1.length + nums2.length) / 2 + 1){
left = nums2[j];
}
System.out.print(nums2[j] +" ( 第"+ count +"个 )" + "->");
j++;
}
}
while(i < nums1.length && count < (nums1.length + nums2.length) / 2 + 1){
count++;
if(count == (nums1.length + nums2.length) / 2 + 1){
left = nums1[i];
}
System.out.print(nums1[i] +" ( 第"+ count +"个 )" + "->");
i++;
}
while(j < nums2.length && count < (nums1.length + nums2.length) / 2 + 1){
count++;
if(count == (nums1.length + nums2.length) / 2 + 1){
left = nums2[j];
}
System.out.print(nums2[j] +" ( 第"+ count +"个 )" + "->");
j++;
}
return left;
}
}
|
支持’.‘和’*'的正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。'.' 匹配任意单个字符；'*' 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。
说明：s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 。
示例 1：输入: s = “aa” p = “a” 输出: false。解释: “a” 无法匹配 “aa” 整个字符串。
示例 2：输入: s = “aa” p = "a" 输出: true。
解释: ‘’ 代表可匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此，字符串 “aa” 可被视为 ‘a’ 重复了一次。
示例 3：输入: s = “ab” p = "." 输出: true。解释: "." 表示可匹配零个或多个（'’）任意字符（‘.’）。
示例 4：输入: s = “aab” p = “cab” 输出: true。
解释: 因为 '’ 表示零个或多个，这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。
示例 5：输入:s = “mississippi” p = "misisp." 输出: false。
1
2
3
4
5
6
7
8
9
| public static boolean problem2(String s, String p){
if((s.length() == 0 || s == null) && (p.length() == 0 || p == null)){
return true;
}if((p == null && s != null) || (p != null && s == null)){
return false;
}
return false;
}
|
