Algorithm

Title Description
leecode 22. bracket-generating
The number n represents the logarithm of the generated bracket. Please design a function to generate all possible and effective bracket combinations.
Example 1:
Input: n = 3
Output: ["(())", "(())", "(()) ()", "() () ()", "() () ()"]
Example 2:
Input: n = 1
Output: ["()"]
Tips:
1 <= n <= 8

Detailed explanation of the topic
1. Concept:
Backtracking algorithm is a priority search method, because there are many possibilities for some problems. If the exhaustive method is adopted, although the problem can be solved eventually, the time complexity and space complexity will become higher. In order to reduce the search scope, pruning search is carried out, that is, the depth priority search according to the requirements is met, and the traversal is stopped if the pruning conditions are met, If no satisfactory solution is found, go back and take a new branch. Backtracking is a kind of DFS. The main difference between backtracking and DFS is that backtracking does not retain the complete tree structure in the process of solving the problem, while depth first search records the complete search tree.

2,Reference to the thought and concept of backtracking method

3. Problem solving script:
1. Define solution space
Solution space includes solution organization and explicit constraints
Organization form of solution: the organization form of solution is normalized as an n-tuple {x1,x2,x3,x4..., xn}
Explicit constraint: it limits the value range of solution components. The size of solution space can be controlled by explicit constraint
2. Determine the organizational structure of the solution space:
The organizational structure of solution space is usually expressed in the image of solution space tree. According to different solution space trees, solution space is divided into subset trees
Permutation tree, m-ary tree.
3. Search solution space
Backtracking method is to search the feasible solution or optimal solution of the problem in the solution space according to the depth first search strategy and the hidden bundle (constraint function and bound function)
When it is found that the current node does not meet the solution conditions, backtrack and try other paths
To find the feasible solution, you only need to set the constraint function. If you find the optimal solution, you need to set the constraint function and limit function.
Explicit constraints can control the size of the solution space, the constraint function determines the pruning efficiency, and the bound function determines whether the optimal solution is obtained

4. Practical ideas for solving this problem

Solution space: a combination string of parentheses that satisfies left parenthesis = right parenthesis = n. according to the backtracking solution space tree, the tree usually has 2^n leaf nodes,
The total number of nodes is (2^(n+1))-1.
Explicit constraint: logarithm n, left represents the number of current left parentheses, right represents the number of current right parentheses, and N represents the logarithm of parentheses.
Recursive exit: when left=right=n, add a new bracket combination.
Pruning function (faint bundle): when left < n, the left bracket can be added; when right < left, the right bracket can be added.

code implementation

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> list = new ArrayList<String>();
        if(n==0){
            return list;
        }

        dfs("",0,0,n,list);
        return list;
    }
    private void dfs(String s, int left, int right, int n, List<String> list) {

        if(left==n && right==n){
            list.add(s);
        }
        if(left < n){
            dfs(s+"(",left+1,right,n,list);
        }
        if(right<left){
            dfs(s+")",left,right+1,n,list);
        }

    }
}

Review

Responsibility chain model of design model

In GoF's design pattern, it is defined as follows:
The sending and receiving of the request are decoupled, so that multiple receiving objects have the opportunity to process the request. All receiving processors are connected into a chain by remembering the reference of the next object through the previous object. These receiving objects are connected into a chain, and the request is passed along the chain until a receiving object on the chain can process it. Each processor on the chain undertakes its own processing responsibilities.

In real life, the purchase approval process, leave process and company employee leave process can be solved by using the responsibility chain.

Responsibility chain is a behavioral design pattern. Its advantage is that it can reduce the coupling between objects and decouple the sending and receiving of requests, so as to enhance the scalability of the system. New request processing classes can be added as needed to meet the opening and closing principle. The disadvantage is that it cannot guarantee that every request can be processed, because if your request has no clear receiver, it may not be processed at the end of the link. Therefore, the diversity of request processing schemes should be considered as much as possible in the design. Second, the processing of requests may involve multiple processing objects, and the system performance will be affected to a certain extent.

1. Pattern structure

• Abstract Handler role: define an interface for processing requests, including abstract processing methods and a subsequent connection.
• Concrete Handler role: implement the processing method of the abstract handler to judge whether the request can be processed. If the request can be processed, process it. Otherwise, transfer the request to its successor.
• Client role: create a processing chain and submit a request to the specific handler object of the chain head. It does not care about the processing details and the transmission process of the request.
  2. Example implementation

public interface IHandler {
  boolean handle();
}

public class HandlerA implements IHandler {
  @Override
  public boolean handle() {
    boolean handled = false;
    //...
    return handled;
  }
}

public class HandlerB implements IHandler {
  @Override
  public boolean handle() {
    boolean handled = false;
    //...
    return handled;
  }
}

public class HandlerChain {
  private List<IHandler> handlers = new ArrayList<>();

  public void addHandler(IHandler handler) {
    this.handlers.add(handler);
  }

  public void handle() {
    for (IHandler handler : handlers) {
      boolean handled = handler.handle();
      if (handled) {
        break;
      }
    }
  }
}

// Use examples
public class Application {
  public static void main(String[] args) {
    HandlerChain chain = new HandlerChain();
    chain.addHandler(new HandlerA());
    chain.addHandler(new HandlerB());
    chain.handle();
  }
}

3. Practical work application

Scenario 1. Implementation of login authentication interception pseudo responsibility chain

1) Requirement background: the system sets login authentication and permission interception to determine the system access of interfaces or users. The role permission design is mainly based on RBAC(Role-Base Access Control), that is, users are associated through roles and permissions. Simply put, a user has multiple roles, and a role has multiple permissions. The login authentication function is based on the authorization model of "user role permission".
2) Specific design

• The login interceptor of the system is implemented through the HandlerInterceptorAdapter adapter of SpringBoot to obtain the information of the login user
• Thirdly, the permission control interceptor is implemented through the HandlerInterceptorAdapter to judge what permissions the current logged in user has
• Through the WebMvcConfigurationSupport configuration class, register the above two interceptors and build the login and authentication link

3) The function of interceptor and configuration class is introduced and implemented
a. Interceptor
In spring boot, we can use the HandlerInterceptorAdapter adapter to implement our own interceptors. In this way, all requests can be intercepted and processed accordingly. The adapter needs to be implemented for the custom interceptor, as follows:

• preHandle: execute before the business method is called. Similar verification functions can be performed in this method. If true is returned, the next interceptor continues to be called. If false is returned, execution is interrupted.
• postHandle: executed after the business method (Controller) is executed
• After completion: call back after the entire request is processed, that is, the view data is rendered or the caller has received the response.

Execution order of multiple interceptors: (the order of normal execution, and the reverse order of exception interceptors)
preHandle of interceptor 1 (return true after execution) - > preHandle of interceptor 2 (return true after execution) - > posthandle of interceptor 2 - > posthandle of interceptor 1 - > afterCompletion of interceptor 2 - > afterCompletion of interceptor 1

@Configuration
public class MyInterceptor extends HandlerInterceptorAdapter {

    @Override
    public boolean preHandle(HttpServletRequest request, HttpServletResponse response,
            Object handler) throws Exception {
            //Login related logic
    }
 
    @Override
    public void postHandle(HttpServletRequest request, HttpServletResponse response, Object handler){
    }
 
    @Override
    public void afterCompletion(HttpServletRequest request, HttpServletResponse response,
            Object handler, Exception ex) throws Exception {
        System.out.println("afterCompletion.........");
    }
}

b. Configuration class WebMvcConfigurationSupport
WebMvcConfigurationSupport is the configuration class of webmvc. If a configuration class inherits WebMvcConfigurationSupport in the springboot project, the automatic configuration class webmvcconfiguration of webmvc will become invalid.

You can see the annotation @ ConditionalOnMissingBean(WebMvcConfigurationSupport.class) of webmvcconfiguration in the above map, which means that the automatic configuration class will take effect only when the bean inheriting WebMvcConfigurationSupport type is not loaded in the spring container.
Key points: There can only be one WebMvcConfigurationSupport configuration class in Spring Boot

The method to make the interceptor in a effective is to register the interceptor through the configuration class. Some methods of WebMvcConfigurationSupport to configure webmvc are:

@Configuration
public class Configurer extends WebMvcConfigurationSupport{
    
    //A custom interceptor
    @Autowired
    MyInterceptor MyInterceptor;
    
    //Define time format converter
    @Bean
    public MappingJackson2HttpMessageConverter jackson2HttpMessageConverter() {
        MappingJackson2HttpMessageConverter converter = new MappingJackson2HttpMessageConverter();
        ObjectMapper mapper = new ObjectMapper();
        mapper.configure(DeserializationFeature.FAIL_ON_UNKNOWN_PROPERTIES, false);
        mapper.setDateFormat(new SimpleDateFormat("yyyy-MM-dd hh:mm:ss"));
        converter.setObjectMapper(mapper);
        return converter;
    }

    //Add converter
    //Configure the format of output data when spring MVC returns data. Only the time output format is configured here
    @Override
    public void configureMessageConverters(List<HttpMessageConverter<?>> converters) {
        //Add the time format converter we defined to the converter list,
        //In this way, whenever jackson encounters Date type during formatting, it will be converted to the format defined by us
        converters.add(jackson2HttpMessageConverter());
    }

    @Override
    protected void addInterceptors(InterceptorRegistry registry) {
        // TODO Auto-generated method stub
        //Register our customized login interceptor into the configuration, which will intercept the / api / * * request path.
        registry.addInterceptor(MyInterceptor).addPathPatterns("/api/**");
        super.addInterceptors(registry);
    }   
	

	/**
     * Prevent @ EnableMvc from overwriting the default static resource path. Set it manually
     * Static resource access is configured
     * You can also configure view resolution to access resources on the server
     * @param registry
     */
    @Override
    protected void addResourceHandlers(ResourceHandlerRegistry registry) {
        // Resolve static resource inaccessibility
        registry.addResourceHandler("/**").addResourceLocations("classpath:/static/");
        //Configure view resolution and map the path with / image / * * * in the url to the resources in the photo file on disk c
       	registry.addResourceHandler("/image/**").addResourceLocations("file:C://photo/");
        super.addResourceHandlers(registry);
    }

    //Configuration server cross domain requests are allowed
    @Override
    public void addCorsMappings(CorsRegistry registry) {
        registry.addMapping("/**")
                .allowedOrigins("*")
                .allowedMethods("GET", "POST", "PUT", "OPTIONS", "DELETE", "PATCH")
                .allowCredentials(true).maxAge(3600);
    }
}

Scenario 2. Implementation of responsibility chain of exception handling notification module

1) Demand background
The failure rate of job execution can be reduced through exception handling (retry and recommendation notification), and the user can be notified in time to ensure the normal execution of the user's job, and reduce the operation and maintenance work of the operation and maintenance personnel of the head office.

• By configuring the exception configuration of automatic retry, some jobs due to connection problems or abnormal failure can be automatically retried, which can reduce the manual operation and maintenance cost and improve the success rate of job execution
• By configuring the processing recommendation method, when the job fails, you can match the log keyword or return code to detect whether the error type of the job has configuration processing recommendations. If configured, it will be displayed under the log and can be pushed to the user by means of recruitment.

2) Specific design
Build the links of exception retry processor, exception recommendation processor and exception notification processor, and determine whether the exception step is processed on each processor according to the user's configuration of the exception.
There are some modifications in the actual application and the implementation of the basic responsibility chain mentioned above. The basic responsibility chain refers to that if a request reaches a processor, it will not continue to pass down if it can handle the request; If it cannot be processed, it will be handled by the subsequent processor; In this actual requirement, there may be multiple processors that need to be processed. Therefore, it is not set to return after processing, but each request goes through the whole link.
Processor A: initializes the processor, which is used to persist the request step information to the database
Processor B: exception retry processor. Match according to the step retry keyword configured by the user. If the match is successful, handle the step retry
Processor C: exception recommendation processor, which matches according to the step recommendation keywords configured by the user, and processes the step recommendation information after successful matching
Processor D: exception notification processor, which determines whether to recommend the recommendation information of exception recommendation processor C to the user through SMS according to the notification information of the job configured by the user
Processor E: persistent the processing information of step information on this link to the database

Tips

The recommended map method for converting a class into attributes and attribute values is to obtain the fields and field values of the class through java reflection.

A brief introduction to java reflection: java reflection is very powerful. You can create objects and obtain class properties, methods, constructors, etc. through reflection.

public HashMap<String, Object> beanToMap(Object obj) throws IllegalAccessException {
        HashMap<String, Object> map = new HashMap<>();
        Class<?> clazz=obj.getClass();
        for (Field field:clazz.getDeclaredFields()){
            field.setAccessible(true);
            String fieldName=field.getName();
            Object fieldObj = field.get(obj);
            if (fieldObj!=null)
                map.put(fieldName,fieldObj.toString());
        }
        return map;
    }

Share

Performance interviews were conducted this week to share some work feelings:
1. In the process of work, actively help customers solve problems. In the process of solving problems, record the user's needs and think about whether the user's problems are the shortcomings of the product itself and how to improve if they want to improve

2. In the actual development process, we should not only think about the realization of functions from the perspective of developers, but also think about the realization of functions from the perspective of users, such as the basic realization of functions, how to meet the unified functions if the needs of multiple users are different, and consider concurrency. We should not only consolidate our own development strength, but also from the perspective of products or users, Make the function design more perfect

3. Everything has a response, everything has a place, and everything has an explanation. This sentence refers to the "closed-loop thinking" at work. If you take over a thing, no matter what degree it is finally done, you should have an explanation. If it's done, there should be an explanation. If it's not done, there should also be an explanation. It doesn't sound very difficult, but most people can't. Some people are unwilling to do it.

4. A person's ability to do things can be seen from every little thing. Only when you do the third point above, the leader will give you more important things

5. No matter in the demand discussion meeting or communicating with colleagues and leaders, you should think more and express your ideas. No matter whether the ideas are reasonable or not, the expression shows that you have thinking and there is the possibility of idea collision. This is the manufacturing experience mentioned in the powerful moment before.

6. We should express what we do more and let the leaders see that we should not do things quietly. We should not be transparent people or marginal people. We should participate in things and contribute our own strength.

7. Do you want to make products or technology?? This question is really worth thinking about (talk about it with classmates or others)

8. At present, we still need to improve our technical ability and customize learning in a modular way. Recently, we learned a way to list the learning plans for the next one to two months. For example, when writing a blog, we should roughly plan the name and content of the blog article and implement it every week as planned

9. Practical communication is the source of inspiration. Self learning is important, but practical experience is more important