This is the 25th day of my participation in the August Challenge

⚽ digression

Yesterday, some friends came to me and asked me how I could not do many questions. After understanding, I found that I did not know much about the data structure. I did not know how to build linked lists and stacks. I suggest you look at the data structure to make up the problem and we will brush it slowly. As for how to make up the problem, if your partner does not have a good plan, you can also chat with me privately. I will find resources for you.

⚽ algorithm problem

Given an array of non-negative integers, nums, you start at the first position in the array.

Each element in the array represents the maximum length you can jump at that location.

Your goal is to get to the last position in the array with the fewest hops.

Suppose you can always get to the last place in the array.

The sample1: Input: nums = [2.3.1.1.4] output:2Explanation: The minimum number of jumps to the last position is2. From the subscript for0Skip to subscript1The position of jump1Step, then jump3Step to the last position in the array.Copy the code

The sample2: Input: nums = [2.3.0.1.4] output:2
Copy the code

Tip:1 <= nums.length <= 104
0 <= nums[i] <= 1000
Copy the code

⚽ A little thought

In this case, you need to pay attention to the position where the number is your maximum jump length rather than your required length. For example, nums = [2,3,1,1,4] and the value is two when the subscript is zero. You can jump to a length less than or equal to 2. I don’t know why I suddenly remembered the prim algorithm in graph theory. Ha ha ha, of course I’m imagining this. The solution we use today is known as the greedy algorithm because it requires finding the best of many outcomes.

⚽ source code and detailed explanation

class Solution {
    public int jump(int[] nums) {
        int length = nums.length;
        int end = 0;
        // Record the largest position in order to get the so-called greedy best value, because we are looking for
        // The shortest jump is, of course, the larger the better
        int maxPosition = 0; 
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
        // Here we go through each element of the array to find the one with the largest value
            maxPosition = Math.max(maxPosition, i + nums[i]); 
            // Record the number of jumps if the position traversed is equal to the position of the previous jump
            if(i == end) { end = maxPosition; steps++; }}returnsteps; }}Copy the code

⚽ interview questions

Mybatis

1. What is Mybatis? Mybatis is a semi-ORM (Object relational Mapping) framework, which encapsulates JDBC internally. When developing, you only need to pay attention to THE SQL statement itself, and do not need to spend energy to deal with the complex process of loading drivers, creating connections, creating statements and so on. Programmers directly write the original SQL, SQL execution performance can be strictly controlled, high flexibility.

MyBatis can configure and map native information using XML or annotations to map POJOs to records in the database, eliminating almost all of the JDBC code and manual setting of parameters and fetching result sets.

Statements to be executed are configured through XML files or annotations, and SQL statements are generated by mapping Java objects and dynamic parameters of SQL in statements. Finally, MyBatis framework executes SQL, maps the results to Java objects and returns them. (The process from executing SQL to returning result).

2, The advantages of Mybaits: based on SQL statement programming, quite flexible, will not cause any impact on the existing design of the application program or database, SQL written in XML, remove the COUPLING of SQL and program code, easy to unified management; Provides XML tags that support writing dynamic SQL statements and can be reused.

Compared with JDBC, reduce the amount of code by more than 50%, eliminate a lot of JDBC redundant code, do not need to manually switch the connection;

MyBatis uses JDBC to connect to the database, so as long as JDBC support database MyBatis all support

Good integration with Spring;

Provide mapping labels to support ORM field relational mapping between objects and databases; Provides object-relational mapping labels to support object-relational component maintenance.

3. Disadvantages of MyBatis framework: it takes a lot of work to write SQL statements, especially when there are many fields and associated tables, which requires certain skills of developers to write SQL statements.

SQL statements depend on databases, which leads to poor database portability. Therefore, databases cannot be replaced at will.