The 5 Leetcodes this week are:

**10 Regular expression matching****11 Container with the most water****74 Search for a two-dimensional matrix****692 Top k high-frequency words****169 Majority Elements**

# 10 Regular expression matching

## Title description

Give you a string

**entire**string

- Example 1:

Input: s = "aa" p = "a" Output: false Explanation: "a" cannot match the entire string of "aa". Copy code

- Example 2:

```
Input: s = "aa" p = "a *"
Output: true
Explanation: Because'* ' means that it can match zero or more of the previous element, the previous element here is'a'. Therefore, the string "aa" can be regarded as'a' repeated once.
Copy code
```

- Example 3:

```
Input: s = "ab" p = ". *"
Output: true
Explanation: ".* " means that it can match zero or more (' *') arbitrary characters ('.').
Copy code
```

- Example 4:

```
Input: s = "aab" p = "c *a* b"
Output: true
Explanation: Because' *' means zero or more, here'c' is 0 and'a' is repeated once. So it can match the string "aab".
Copy code
```

- Example 5:

```
Input: s = "mississippi" p = "mis *is* p *."
Output: false
Copy code
```

- prompt:
- 0 <= s.length <= 20
- 0 <= p.length <= 30
- sMay be empty, and only contain fromazLowercase letters.
- pMay be empty, and only contain fromazLowercase letters, and characters.with*.
- Guarantee every occurrence of characters *When, the front is matched to a valid character

Source: LeetCode

Link: leetcode-cn.com/problems/re... The

copyright is owned by LeetCode . For commercial reprints, please contact the official authorization. For non-commercial reprints, please indicate the source.

## Solution-Dynamic Programming

use

**Situation 1**:s[i] == p[j] || p[j] =='.'

This situation explains

```
S//[I] == P [J] || P [J] == '.'
DP [I] [J] DP = [I- . 1 ] [J- . 1 ]
Copy the code
```

in case

**Situation 2**:p[j] =='*'

due to

in case

```
P//[J] == '*' && P [-J. 1] == S [I]
DP [I] [J] DP = [I- . 1 ] [J]
duplicated code
```

in case

```
P//[J] == '*' && P [-J. 1] == '.'
DP [I] [J] DP = [I] [J- 2 ]
Copy Code
```

in case

```
P//[J] == '*' && P [-J. 1]! = S [I]
DP [I] [J] DP = [I] [J- 2 ]
Copy Code
```

According to the above various situations, the final result can be obtained:

To calculate from back to front, the corresponding boundary conditions must be set:

We can

p[j] =='*' && p[j-1] == s[i]withp[j] =='*' && p[j-1] == s[i]Seen as a situation, they are all able to match successfully. The method to determine whether two characters match is encapsulated asisMath().

```
//Solution 1 dynamic programming
public boolean isMatch (String s, String p) {
int sl = s.length();
int pl = p.length();
boolean [][] dp = new boolean [sl + 1 ][ pl + 1 ];
dp[ 0 ][ 0 ] = true ;
for ( int i = 0 ; i <= sl; ++i){
for ( int j = 1 ; j <= pl; ++j){
if (p.charAt( j- 1 ) != '*' ){
if (isMatch(s,p,i,j)){
dp[i][j] = dp[i- 1 ][j- 1 ];
}
} else {
if (isMatch(s,p,i,j- 1 )){
dp[i][j] = dp[i- 1 ][j] || dp[i][j- 2 ];
} else {
dp[i][j] = dp[i][j- 2 ];
}
}
}
}
return dp[sl][pl];
}
public boolean isMatch (String s, String p, int si, int pj) {
if (si == 0 ){
return false ;
}
if (p.charAt(pj- 1 ) == '.' ){
return true ;
}
return s.charAt(si- 1 ) == p.charAt(pj- 1 );
}
Copy code
```

# 11 Container with the most water

## Title description

Give you

Note: You cannot tilt the container.

- Example 1:

Input: [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The vertical line in the figure represents the input array [1,8,6,2,5,4,8,3,7]. In this case, the maximum value that the container can hold water (shown as the blue part) is 49. Copy code

Source: LeetCode

Link: leetcode-cn.com/problems/co... The

copyright belongs to LeetCode . For commercial reprints, please contact the official authorization. For non-commercial reprints, please indicate the source.

## Solution-Two Pointer Method

We use left and right pointers

When the left and right pointers do not meet

The calculation formula for the interview is:

We also noticed that, assuming the height of the current container is

**onlyheigth[left],height[right] Smaller than h**When it is

**large**, the area is calculated and the maximum area is updated.

To facilitate calculations, we will

hInitialized to-1.

The following example 1 is used to show the whole process.

- In the beginning,left = 0, right = 8, The area at this time is 8 and the height of the container is 1. Since the left side is shorter, we moveleft

- At this time, the smaller height is 7, which is higher than hLarge, the area needs to be calculated as 49. mobileright

- Due to height 3 ratio hSmall, so there is no need to calculate the area, continue to move the right pointer

- The smaller height is equal to 8 and more than hBig, calculate the interview and compare updates, moveleftorright, Assuming mobileleft

- As you can see, moving to the middle, no matter which pointer is moved, the height is always hSmall, so the area will not be updated. untilleft >= rightAt the end, the final area is 49.

The code is implemented as follows:

```
//A pair of pointer method
public int maxArea ( int [] height) {
int left = 0 ;
int right = height.length- 1 ;
int result = 0 ;
int h = -1 ;
int min = 0 ; //used Represents a shorter height value
while (left <right) {
if (h <(min = Math.min(height[left],height[right]))){
h = min;
result = Math.max(result,h*(right-left));
}
if (height[left] <height[right]){
left++;
} else {
right--;
}
}
return result;
}
Copy code
```

# 74 Search for a two-dimensional matrix

## Title description

Write an efficient algorithm to judge

- The integers in each row are arranged in ascending order from left to right.
- The first integer in each line is greater than the last integer in the previous line.

- Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true Copy code

- Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13 Output: false Copy code

- prompt:

```
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= Matrix [ I ] [ J ], target <= 104
duplicated code
```

Source: LeetCode

Link: leetcode-cn.com/problems/se... The

copyright belongs to LeetCode Network. For commercial reprints, please contact the official authorization. For non-commercial reprints, please indicate the source.

## Solution one binary search

According to the meaning of the title, if each row of the matrix is concatenated into an array, the array is in ascending order. So you can use **binary search** .

But we want to map the linear index value to the corresponding element in the matrix. The mapping function is as follows:

```
/**
* Arrange each row of the matrix into a linear structure in order, the dimension of the matrix is m*n, then 0 <= index <= m*n-1
* Return the corresponding element in the matrix according to the given index
*/
private int mapMatrix ( int [][] matrix, int index) {
return matrix[index/matrix[ 0 ].length][index%matrix[ 0 ].length];
}
Copy code
```

The realization of binary search is as follows:

```
class Solution {
/** Method 1 Binary search method*/
public boolean searchMatrix ( int [][] matrix, int target) {
int left = 0 ;
int right = matrix.length * matrix[ 0 ].length- 1 ;
while (left <= right){
int mid = left + (right-left)/ 2 ;
int midValue = mapMatrix(matrix,mid);
if (midValue == target){
return true ;
} else if (midValue> target){
right = mid- 1 ;
} else {
left = mid + 1 ;
}
}
return false ;
}
}
Copy code
```

## Solution 2: Find by line

Define the number of rows and columns of the matrix as

- in case targetBigger, indicating that it should be found in this row, andi++,rowconstant
- in case targetSmaller, indicating that the search should be continued from the previous line, at this timerow--,iconstant
- If and targetEqual, returntrue

The condition for the end of the loop is

```
class Solution {
public boolean searchMatrix ( int [][] matrix, int target) {
int row = matrix.length, col = matrix[ 0 ].length;
int i = 0 ;
while (row> 0 && i <col) {
if (target> matrix[row- 1 ][i]) {
i++;
} else if (target <matrix[row- 1 ][i]) {
row--;
} else {
return true ;
}
}
return false ;
}
}
Copy code
```

# 692 Top k high-frequency words

## Title description

Give a non-empty word list, before returning

- Example 1:

Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2 Output: ["i", "love"] Analysis: "i" and "love" are the two most frequent words, both appearing twice. Note that "i" comes before "love" in alphabetical order. Copy code

- Example 2:

Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4 Output: ["the", "is", "sunny", "day"] Analysis: "the", "is", "sunny" and "day" are the four most frequently occurring words, with 4, 3, 2 and 1 occurrences in sequence. Copy code

- note:

Assuming that k is always a valid value, 1 k the number of set elements. The words entered are composed of lowercase letters. Copy code

Source: LeetCode

Link: leetcode-cn.com/problems/to... The

copyright is owned by LeetCode . For commercial reprints, please contact the official authorization. For non-commercial reprints, please indicate the source.

## Solution one hash table + sort

In order to get the frequency of each word, you should first use

```
//Solution one hash table sorting
public List<String> topKFrequent (String[] words, int k) {
HashMap<String,Integer> counts = new HashMap<>();
for ( int i = 0 ; i <words.length; i++){
counts.put(words[i],counts.getOrDefault(words[i], 0 ) + 1 );
}
List<String> list = new ArrayList<>(counts.keySet());
list.sort((a,b) -> {
//The number of occurrences of the word is the same, according to the default order of the word to achieve
if (counts.get(a) == counts.get(b)){
return a.compareTo(b);
} else {
return counts.get(b)-counts.get(a);
}
});
return list.subList( 0 ,k);
}
Copy code
```

## Solution two hash table + priority queue (heap)

Also use

Then add the word to the queue, take the front

```
//Solution two hash table + heap
public List<String> topKFrequent (String[] words, int k) {
HashMap<String,Integer> counts = new HashMap<>();
for ( int i = 0 ; i <words.length; i++){
counts.put(words[i],counts.getOrDefault(words[i], 0 ) + 1 );
}
PriorityQueue<String> queue = new PriorityQueue<>((a,b) -> {
if (counts.get(a) == counts.get(b)){
return a.compareTo(b);
}
return counts.get(b)-counts.get(a);
});
for (String s: counts.keySet()){
queue.offer(s);
}
List<String> result = new ArrayList<>();
for ( int i = 0 ; i <k; ++i){
result.add(queue.poll());
}
return result;
}
Copy code
```

# 169 Majority Elements

## Title description

Given a size

**is greater than n/2**elements.

You can assume that the array is non-empty, and there will always be a majority of elements in a given array.

- Example 1:

Input: [3,2,3] Output: 3 Copy code

- Example 2:

Input: [2,2,1,1,1,2,2] Output: 2 Copy code

Source: LeetCode

Link: leetcode-cn.com/problems/ma... The

copyright belongs to LeetCode . For commercial reprints, please contact the official authorization. For non-commercial reprints, please indicate the source.

## Solution one hash table count

use

While counting, we judge whether it is more than half, but we should pay attention to the fact that the array has only one element, so we take it out for judgment first.

```
//Solution one HashMap
public int majorityElement ( int [] nums) {
//If the array has only one element, return directly
if (nums.length == 1 ){
return nums[ 0 ];
}
int lower = nums.length/2 ;
HashMap<Integer,Integer> map = new HashMap<>();
for ( int num: nums){
if (!map.containsKey(num)){
map.put(num, 1 );
} else {
map.put(num,map.get(num)+ 1 );
if (map.get(num)> lower){
return num;
}
}
}
return 0 ;
}
Copy code
```

## Divide and conquer

Using the idea of dichotomy, divide the array into left and right parts, and calculate the majority of elements on the left and right sides respectively. If they are equal, the majority of elements are this element. If they are not equal, the majority element should be the majority element that appears more frequently.

```
//Two-division and rule of solution
public int majorityElement ( int [] nums) {
return majorityElement(nums, 0 ,nums.length- 1 );
}
//Return most elements in the range of left ~ right
public int majorityElement ( int [] nums, int left, int right) {
//Only one element, most elements are themselves
if (left == right){
return nums[left] ;
}
//dichotomy
int mid = left + (right-left)/2 ;
int leftMajorityEle = majorityElement(nums,left,mid);
int rightMajorityEle = majorityElement(nums,mid + 1 ,right);
if (leftMajorityEle == rightMajorityEle){
return leftMajorityEle;
}
//Most elements on the left and right are not equal, count the number of times they appear on the left and right sides respectively
int leftCounts = counts(nums,leftMajorityEle,left,mid);
int rightCounts = counts(nums,rightMajorityEle,mid + 1 ,right);
//return more occurrences
return leftCounts> rightCounts? LeftMajorityEle: rightMajorityEle;
}
//Count the number of occurrences of target within the range of left ~ right
private int counts ( int [] nums, int target, int left, int right) {
int counts = 0 ;
for ( int i = left; i <= right; i++ ){
if (nums[i] == target){
counts++;
}
}
return counts;
}
Copy code
```