# Weekly Leetcode: 10, 11, 74, 692, 169

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

s
And a character rule
p
, Please come and implement a support
'.'
with
'*'
The regular expression matches.
'.'
Matches any single character,
'*'
Match zero or more of the preceding element. The so-called matching is to cover the  entire  string
s

• 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
• s
May be empty, and only contain from
az
Lowercase letters.
• p
May be empty, and only contain from
az
Lowercase letters, and characters
.
with
*
.
• Guarantee every occurrence of characters
*
When, the front is matched to a valid character

Source: LeetCode

## Solution-Dynamic Programming

use

dp[i][j]
Means
s
before
i
Characters and
p
before
j
Whether the characters match. We can perform iterative calculations from back to front.

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

This situation explains

s[i]
with
p[j]
Match a single character. At this time, you only need to compare whether the preceding parts match. The state transition equation is:

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

in case

s[i]
with
p[j]
Unable to match, indicating that the entire string cannot be matched.

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

due to

*
Is bound to the previous character, so we have to look at the previous character, namely
p[j-1]
.

in case

p[j-1] == s[i]
: It means that it can be matched at least once, then just look at
s
before
i-1
Characters and
p
match. The state transition equation is:

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

in case

p[j-1] =='.'
: The state transition equation is:

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

in case

p[j-1] != s[i]
: Explain at this time
p[j-1]*
The combination cannot match any character, that is, it matches 0 times. We can think that this combination has not appeared. The state transition equation is:

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:

dp[s.length][p.length]
.

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

dp[0][0] = true
That is, an empty string can be matched. due to
dp[0][0]
Represents an empty string, so our
dp
The array actually has one more row and one column,
dp[1][1]
Means
s[0]
with
p[0]
Whether it matches.

We can

p[j] =='*' && p[j-1] == s[i]
with
p[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 as
isMath()
.

//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

n
Non-negative integer
a1, a2,..., an
, Each number represents a point in the coordinates
(i, ai)
. Draw within the coordinates
n
A vertical line, the two end points of the vertical line i are
(i, ai)
with
(i, 0)
. Find two of the lines so that they are the same
x
The container formed by the shafts can hold the most water.

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

## Solution-Two Pointer Method

We use left and right pointers

left,right
Respectively indicate the positions of the two sides of the container. Initially,
left = 0,right = length-1
.

When the left and right pointers do not meet

left <right
When we always move the index of the shorter edge (
left++
or
right--
). This is because the height of the container is the length of the shorter side. If you move the index of the higher side, the height will not change, and the width (
right-left
) Is decreasing, so the area will only be smaller.

The calculation formula for the interview is:

$area = Math.min(height[left],height[right]) * (right-left)$

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

h
, In the future movement process, because the width is decreasing, if the area is to be larger, the height must be higher than the current height
h
Bigger. So we add a variable
h
, Used to dynamically express the height of the container during the movement, only
heigth[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

h
Initialized 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 move
left

• At this time, the smaller height is 7, which is higher than
h
Large, the area needs to be calculated as 49. mobile
right

• Due to height 3 ratio
h
Small, 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
h
Big, calculate the interview and compare updates, move
left
or
right
, Assuming mobile
left

• As you can see, moving to the middle, no matter which pointer is moved, the height is always
h
Small, so the area will not be updated. until
left >= right
At 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

mxn
In the matrix, whether there is a target value. The matrix has the following characteristics:

1. The integers in each row are arranged in ascending order from left to right.
2. 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

## 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

row,col
. From the first
row
Line, first
i(i=0)
Column start and
target
Compare:

• in case
target
Bigger, indicating that it should be found in this row, and
i++
,
row
constant
• in case
target
Smaller, indicating that the search should be continued from the previous line, at this time
row--
,
i
constant
• If and
target
Equal, return
true

The condition for the end of the loop is

row> 0 && i <col
. The code is implemented as follows:

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

k
The most frequently occurring words. The returned answers should be sorted by word frequency from highest to lowest. If different words have the same frequency, they are sorted alphabetically.

• 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

## Solution one hash table + sort

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

HashMap
To count the number of occurrences of each word. Then sort in descending order of the number of occurrences of each word, take the first
k
Just a word.

//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

HashMap
Count the number of occurrences of words. Sorting can be implemented by constructing a large top heap. The implementation of priority queue is provided in Java
PriorityQueue
, The default is an implementation of a small top heap. A comparator is passed in the constructor to specify the order of element insertion.

Then add the word to the queue, take the front

k
A word that goes out of the team is enough.

//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){
}
return result;
}
Copy code

# 169 Majority Elements

## Title description

Given a size

n
Array of, find most of the elements. Most is the number of elements present in the array 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

## Solution one hash table count

use

HashMap
Count the array elements, and when you find that the count value of an element is more than half, just return.

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