This is the 14th day of my participation in the First Challenge 2022

First, write first

I heard you’re still writing a two-layer for loop to solve the sum of two numbers?

LeetCode 2: Sum of two numbers transfer gate: the median of two sorted arrays, “most” technical solution!

LeetCode 第 3 题 : Longest loop transport gate: Horse-and-cart algorithm to solve longest loop! Manacher

LeetCode 4 题 conversion of string to integer (ATOI) : Solve ATOI with “foolish old man removing mountains” method, think clever!

Continue solving LeetCode, the longest public prefix

One of LeetCode’s “most classic” algorithm problems: the sum of three numbers

The sum of the nearest three numbers, wonderful

LeetCode: Valid parentheses

Delete duplicates in LeetCode: delete duplicates in LeetCode

Question 10: The container with the most water, for the interview, looking forward to your participation.

Today’s topic

Given n non-negative integers A1, A2… Each number represents a point in the coordinates (I, ai). Draw n vertical lines in the coordinates, and the two endpoints of vertical line I are (I, AI) and (I, 0). Find the two lines that together with the X-axis will hold the most water.

Description:You can’t tilt the container, and n is at least 2. Example:

Input:1.8.6.2.5.4.8.3.7] output:49
Copy the code

Three, the analysis

The first time I saw this picture, I thought, this topic should be interesting, beautiful.

Just watching the topic, the first idea is to directly traversal, the elements of the composition of each pair of value area, and then take out a maximum, the time complexity of O (n ^ 2), think about all complicated, “stupid”, so to give up this thinking, clamp force criterion, on a topic to have the reader to ask can use clamp force criterion, my answer is no, this topic, we can, The basic idea is shown in the figure below:

Fourth, the problem solving

  • My approach:

Squeeze. We’ve used it more than once. Time complexity control Again: O(n) Space complexity: O(1)

  • Submit the results

Test data: 50 groups running time: 36-64ms beat percentage :15.52-95.79%

Code optimization:In the above optimization, I simply reduced the number of code. Here I used some Python knowledge. I am also consolidating the basic knowledge of Python.

While the code gets cleaner, our time efficiency is reduced by the simplicity of calling Python’s library.

  • Submit the results

Test data: 50 groups running time: 48-88ms Beat percentage :5.64-37.70%

Five, doubt

A brief introduction to the squeeze criterion

Squeeze Theorem is a Theorem called Squeeze Theorem. Also known as the two sides of the squeeze theorem, squeeze criterion, squeeze theorem, squeeze theorem, sandwich theorem, is one of the two criteria to determine the existence of the limit, is the limit of the function of the theorem.

Can be seen from the above, the rule of clamp force is one of the mathematical method, so the algorithm is better, head and flexible, mathematics is indispensable, we find the maximum, minimum, is actually a process of looking for extremum, and usually we come into contact with the junior middle school high school mathematics, the data are discrete, so we have to point analysis.

Squeeze criterion theorem

1. If the sequence {Xn},{Yn} and {Zn} satisfy the following conditions: (1) when n>N0, where N0∈N*, Yn≤Xn≤Zn,

(2) {Yn}, {Zn} have the same limit a, let -∞< A <+∞; Then, the limit of the sequence {Xn} exists and limXn =a as n→+∞.

2. If the limit of A is X and the limit of C is X, then the limit of B must be X. This is the squeeze theorem.

Squeeze criterion application

1. Let {Xn}, {Zn} be convergent sequence, and: when n tends to infinity, the limit of {Xn}, {Zn} are: a. If N exists such that Xn≤Yn≤Zn exists when N >N, the sequence {Yn} converges and the limit is A.

2. The squeezing criterion is suitable for solving the limit of functions that cannot be solved directly by the limit algorithm, and to determine the limit of F(x) indirectly by obtaining the limit of F(x) and G(x).

The above part of the content is from Baidu encyclopedia, hard sea is endless, good study.

Six, the concluding

Persistence and hard work: results.

Like to see the message forwarding, four support, the original is not easy. Ok, see you next time, I love the cat love technology, more love si si’s old cousin Da Mian ଘ(˙꒳˙)ଓ Di Di