This is the second day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

preface

This article is mainly used to sort out some algorithm problems often encountered in the front-end interview, the solution is to record my own writing method, but also convenient for me to check. A better way to write it is to go directly to Leetcode and see the solution.

The title

1. Climb the stairs

When you climb stairs, you can choose to climb 1 or 2 steps at a time.

You can see that the way to the NTH step is either through the n-1 step or the n-2 step. So fn(n) = fn(n-1) + FN (n-2)

var climbStairs = function(n) {
    let fn={};
    fn[1] =1;
    fn[2] =2;

    for(let i=3; i<=n; i++) {
        fn[i]=fn[i-1]+fn[i-2];
    }
    return fn[n];
};
Copy the code

See leetcode#70 for specific problems and other solutions

2. Valid brackets

Check whether the parentheses are closed correctly. There are three parentheses: (),{}, and [].

Consider using a stack. Check whether the top of the stack matches when the left parenthesis is added to the stack. If the top matches, the stack is removed. If the top does not match, false is returned

var isValid = function (s) {
    if (s.length % 2) {
        return false;
    }
    let arr = []
    let obj = {
        '(': ') '.'{': '} '.'[': '] '
    }
    for(let i=0; i<s.length; i++) {
        if(s[i] in obj) {
            arr.push(s[i]);
        }else {
            let ele = arr.pop();
            if(obj[ele] ! == s[i]) {return false; }}}if(arr.length === 0) {
        return true;
    }
    return false;
};
Copy the code

See leetcode#20 for solutions and other solutions

3. Integer representation in English

This problem, although marked as difficult in LeetCode, is a simple problem in itself, as long as you get the transformation rules right. It is not difficult to consider the special English expressions of numbers.


let oneMap = [""."One"."Two"."Three"."Four"."Five"."Six"."Seven"."Eight"."Nine"];
let teenMap = ["Ten"."Eleven"."Twelve"."Thirteen"."Fourteen"."Fifteen"."Sixteen"."Seventeen"."Eighteen"."Nineteen"];
let tenMap = [ "Twenty"."Thirty"."Forty"."Fifty"."Sixty"."Seventy"."Eighty"."Ninety"];
let threeDigits = ["Thousand"."Million"."Billion"];


var numberToWords = function(num) {
    if(num === 0) {
        return 'Zero';
    }
    if(num < 10) {
        return oneMap[num];
    }else if(num < 20) {
        return teenMap[num%10];
    }else if(num < 100) {
        let tensDigit = parseInt(num/10);
        let unitsDigit = num%10;
        if(unitsDigit) {  // Whitespace processing
            return tenMap[tensDigit-2] + ' ' +  oneMap[unitsDigit];
        }else {
            return tenMap[tensDigit-2]}}else if(num < 1000) {
        let hundredDigit = parseInt(num/100);
        if(num%100) {
            return oneMap[hundredDigit] + ' Hundred ' + numberToWords(num%100);
        }else {
            return oneMap[hundredDigit] + ' Hundred'; }}else {
        // The maximum number of digits is 4294967296
        let str = ' ';
        for(let i=3, unit = 1000000000; i>=0; unit/=1000, i--) {
            let digit = parseInt(num/unit);
            if(digit) {
                num -= digit*unit;
                if(str) {
                    str += ' ';
                }
                str += numberToWords(digit);

                if(i>0) {
                    str += ' ' + threeDigits[i-1]; }}}if(num) {
            return str += ' ' +numberToWords(num);
        }else{
            returnstr; }}};// console.log(numberToWords(1000000000))
// console.log(numberToWords(20))

Copy the code

See leetcode#273 for solutions and other solutions