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

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
Instead of partial strings.

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

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

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

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

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){ result.add(queue.poll()); } 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
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

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