1, clever array subscripts

For example, when counting the number of captions in A string, we can use these letters as array subscripts, and increment arr[‘ A ‘] by 1 if the letter A is traversed.

Method 1: use the key value of the object is not repeated

var str = 'hajshdjldjf';
function count(str){
    var obj = {};
    for(var i = 0; i < str.length; i++){
        if(obj[str[i]]){
            obj[str[i]]++;
        }else{
            obj[str[i]] = 1;
        }
    }
    console.log(obj);
    return obj;
}
count(str);Copy the code

Method 2: use array subscripts

var str = 'hajshdjldjf';
function count(str){
    var arr = [];
    for(var i = 0; i < str.length; i++){
        if(arr[str[i]]){
            arr[str[i]]++;
        }else{
            arr[str[i]] = 1;
        }
    }
}
count(str);Copy the code

In fact, the idea of the two methods is the same.

For example, you are given an array of n unordered ints arr, each of which ranges from 0 to 20, and are told to print the n numbers in order from smallest to largest in O(n) time.

For this problem, if you sort the n numbers first and then print them out, you can’t print them out in order n. But the values range from 0 to 20. So we can use array subscripts in a clever way. Take the corresponding number as the array subscript, and increment the array if the number is present.

Objects used:

Var arr =,2,3,4,5,4,5,6,6,7,6,9,17,16,15,14,12,11 [1]; // The conventional solution uses the key value of the object to count the number of timesfunction fn(arr){
    arr.sort(function(a,b){
        return a - b;
    });
    var res = [];
    var resdetail = [];
    for(var i = 0; i < arr.length; i++){
        if(res.length === 0 || res[res.length-1] ! == arr[i]){ res.push(arr[i]); var obj = { key:arr[i], value:1 }; resdetail.push(obj); }else{
            resdetail[resdetail.length-1].value++;
        }
    }
    console.log(resdetail);
    return resdetail;


}
fn(arr);Copy the code

Use array subscripts

Var arr =,2,3,4,5,4,5,6,6,7,6,9,17,16,15,14,12,11 [1]; // Use array subscript time complexity O(n)functionFn (arr) {var temp =,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 [0];for(var i = 0; i < arr.length; i++){
        temp[arr[i]]++;
    }
    for(var j = 0; j < 21; j++){
        for(var k = 0; k < temp[j]; k++){
            console.log(j);
        }
    }
}
fn(arr);Copy the code

2, skillfully use to take remainder

Sometimes when we’re going through a set of numbers, we do an out of bounds judgment, and if the index is almost out of bounds, we set it to 0 and we go through again. This is especially true in circular arrays, such as arrays. Code like this is often written:

for (int i = 0; i < N; i++)
{
    if(pos < N) {// Not out of bounds // arr[pos]else{ pos = 0; Arr [pos]} pos++; }}Copy the code

We can actually simplify our code by doing mod

for(int i = 0; i < N; I++) {// use the array arr[pos] (we assume pos < N at the beginning) pos = (pos + 1) % N; }Copy the code

3. Use double Pointers skillfully

For double Pointers, it is particularly useful in doing problems about single linked lists, such as “judging whether single linked lists have rings”, “how to find the middle node of the list in one traverse”, “the KTH node from the bottom of the single linked list” and so on. For this kind of problem, we can use double Pointers, which is much more convenient.

(1) Judge whether there are rings in the single linked list

We can set a fast pointer and a slow pointer, the slow pointer moves one node at a time, the fast pointer moves two nodes at a time. If a loop is present, the fast pointer meets the slow pointer on the second pass.

(2) How to find the middle node of the linked list in one traverse

Again, set a fast pointer and a slow pointer. Slow moves one node at a time, fast moves two at a time. When the fast pointer traversal is complete, the slow pointer just reaches the midpoint.

(3) the penultimate KTH node in a single linked list

Set two Pointers, one of which moves k-1 first, starting at step k, both Pointers move at the same speed. When the first pointer is traversed, the second pointer points to the KTH position from the bottom.

4. Skillfully use displacement

Sometimes when we’re doing divisor or multiplier operations, such as n / 2, n / 4, n / 8, we can do it by shifting, which is much faster.

Such as:

N over 2 is the same thing as n >> 1

N over 4 is the same thing as n >> 2

N over 8 is the same thing as n >> 3.

In this way, the operation of the shift will be faster in the execution speed, and you can also show the appearance of a very strong, ha ha.

There are also some & (and), | (or) operation, can also speed up the operation. For example, to determine whether a number is odd, you might do this

if(n % 2 == 1){
    dosomething();
}Copy the code

But it’s a lot faster if we use and or. For example, if it’s odd, we can sum n with 1, if it’s 1, it’s odd, otherwise it’s not. namely

if(n & 1 == 1){
    dosomething();
)Copy the code

5. Set up sentries

In linked list problems, we often set a header pointer, and the header pointer does not hold any valid data, just for ease of operation, this header pointer can be called a sentinel.

For example, if we want to delete the first node in the header, if we do not set a sentinel, it will operate differently from deleting the second node. But we set the sentry, so deleting the first node is the same as deleting the second node, so there’s no extra judgment. Of course, the same goes for inserting nodes.

Sometimes we can set a sentinel when we are manipulating arrays, and use arr[0] as the sentinel. Arr [I] == arr[i-1]? Arr [I] == arr[i-1]? . You don’t have to worry about crossing the boundary at I = 0.

6. Some optimizations related to recursion

(1) Consider state preservation for problems that can be recursed.

When we use recursion to solve a problem, it is easy to repeat the calculation of the same subproblem, and we should consider state saving to prevent double calculation.

Example: Fibonacci sequence

function fn(n){
    if(n <= 2){
        return 1;
    }else{
        return fn(n-1) + fn(n-2);
    }
}
console.log(fn(10));Copy the code

But for problems that can be solved recursively, it’s important to consider whether there’s a lot of double counting. Obviously, for f(n) = f(n-1) + f(n-2) recursion, there’s a lot of double counting. Such as



There’s a lot of double counting. At this point we have to think about state saving. And you can go from the bottom up.

function fn(n){
    var res = [];
    res[0] = 1;
    res[1] = 1;
    for(var i = 2; i < n; i++){
        res[i] = res[i-1] + res[i-2];
    }
    console.log(res[n-1]);
    return res[n-1];
}
fn(10);Copy the code

Further optimization: Use two variables.

function fn(n){
    var a = 1;
    var b = 1;
    for(var i = 3; i <= n; i++){
        a = a + b;
        b = a - b;
    }
    return a;
}
fn(10);Copy the code