scenario

  • A lot of people will say it’s for the interview and it’s results-oriented and that’s fine.
  • More often than not, why do we do algorithms, what are the core points?
  • I’m going to ask myself as an interviewer what the test points are for algorithms
  1. Consideration of corresponding anomaly and boundary value
  2. The execution efficiency of an algorithm, the reason why an algorithm is called an algorithm, is a summary of the previous efficient execution of the program
  3. Divergent creativity goes beyond the present and comes up with more creative ideas about things
  4. The most important thing is to solve this problem first, and then to optimize the solution, regardless of work and life are a certain degree of result-oriented, first solve the immediate problems, and then optimize must be the best way at this stage, rather than give up!!
  • These qualities are valuable in the development process, and they are essential for a requirement development and an architecture design

Is the front end worth learning?

  • First of all, it is possible on the scene, before I have done a requirement: maximum matching scene, in fact, the last abstraction is a maximum common string algorithm.
  • A multi-terminal scenario or a server-side implementation would be more appropriate
  • Learning is endless. Continuous learning is the most important thing for developers and life. Embrace changes and imagine the future.

Methods and algorithm index

  • Use one loop or reduce loops to improve execution efficiency, for example: sum of two numbers, the oldest string without repeating characters
  • The cache mechanism can greatly improve the execution efficiency and reduce the memory. For example, the sum of two numbers and the oldest string without repeating characters

Get to the point

1. The sum of two Numbers

Given an integer array nums and an integer target value target, you find the two integers in the array and the target value target and return their array subscripts.

You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer. You can return the answers in any order.

The sample

Enter: nums = [2.7.11.15], target = 9Output:0.1Because nums[0] + nums[1] = =9To return to the [0.1].Copy the code

Compared with the target value, the two-layer loop sum is obviously not efficient
O ( n 2 ) O(n^2)

  1. The following code
/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(nums, target) {
     for(let i = 0; i<nums.length; i++){let child1 = nums[i];
         for(let k = i+1; k<nums.length; k++){let child2 = nums[k];
            if(child1+child2 === target){
                return [i,k]
            }
        }

     }
     return[]}.Copy the code

  1. Execution result: Execution time: 132 ms; Memory consumption: 38.6 MB

  2. The illustration

A cycle of slow, save valid data, compare the difference, the effect is better

  1. We all know that when we loop through, we know that the current index value, the current value, the target value minus the current value is in the data that we cached before, and if it’s not, we cache the current value

  2. The following code

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(nums, target) {
    var map = {};
    for (let i = 0; i < nums.length; i++) {
      var child1 = nums[i];
      var key = target - child1;
      if(map[key] ! = =undefined) {
        return [map[key], i];
      }
      map[child1] = i;
    }
    return [];
};
Copy the code

  1. Execution result: Execution time: 80 ms; Memory consumption: 39.6 MB

  2. The illustration

3. The oldest string without repeating characters

Given a string, find the length of the smallest string that does not contain repeating characters.

The sample

Enter: s ="abcabcbb"Output:3Because the oldest string without repeating characters is"abc", so its length is3.Copy the code

Solution idea 1: Two-layer loop, the first layer of the loop string and the second string splicing, the second layer to determine whether the string has been included in the previous splicing data, compare the length of each non-repeating string, the complexity is
O ( n 2 ) O(n^2)

  1. The following code
/ * * *@param {string} s
 * @return {number}* /
var lengthOfLongestSubstring = function(s) {
 if(s.length ==0) {return 0
 }else{
     var array = s.split("")
     var num = 0
     if(array.length == 1) {return 1
     }
     for(let i=0; i<array.length; i++){var map = array[i]
        var cn = 1
        for(let k=i+1; k<array.length; k++){var child1 = array[k]
            if(! map.includes(child1)){ map = map+child1 cn++ }else{
                break; } } num = num > cn? num:cn }return num
 }
};
Copy the code

  1. Execution result: Execution time: 352 ms; Memory consumption: 44.2 MB

  2. The illustration

In the first layer, string concatenation is performed, and the string behind the previous concatenation is found in the cache. Then, the string behind the previous concatenation is cut off, and the string behind the previous concatenation is added to the current string. Then, the cache string is updated and the loop continues.

  1. The following code
/ * * *@param {string} s
 * @return {number}* /
var lengthOfLongestSubstring = function (s) {
    if (s.length == 0) {
      return 0;
    } else {
      var array = s.split("");
      var num = 0;
      var cn = 0;
      var map = "";
      for (let i = 0; i < array.length; i++) {
        var str = array[i];
        if(! map.includes(str)) { map = map + str; cn++; }else {
          var index = map.indexOf(str);
          map = map.substring(index + 1) + str;
          cn = map.length;
        }
        num = num > cn ? num : cn;
      }
      returnnum; }};Copy the code

  1. Execution result: Execution time: 128 ms; Memory consumption: 43.7 MB

  2. The illustration

conclusion

  • Continuous learning, every day to have a driving force, not intermittently smug, continuous sitting eating and waiting for death!
  • Algorithm applet adds animation mode to its own todo
  • After 35 years old, learning to share is a choice direction of my life