编程题

树

94. 二叉树的中序遍历

var inorderTraversal = function(root) {
    return Array.from(fn(root))
};

function* fn(root) {
    if (root) {
        yield* fn(root.left)
        yield root.val
        yield* fn(root.right)
    }
}

98. 验证二叉搜索树

var isValidBST = function(root) {
    return helper(root)
};

function helper(root, min = -Infinity, max = Infinity) {
    if (!root) return true;
    const { val, left, right } = root    
    if (val <= min || val >= max) return false;

    return helper(left, min, val) && helper(right, val, max);
}

var isValidBST = function(root) {
    try {
        helper(root)
        return true;
    } catch {
        return false;
    }
}

function helper(root, result = []) {
    if (root) {
        helper(root.left, result);
        if (result.length === 0 || root.val > result[result.length - 1]) {
            result.push(root.val)
        } else {
            throw new Error('')
        }
        helper(root.right, result);
    }

    return result;
}

101. 对称二叉树

var isSymmetric = function(root) {
    return check(root.left, root.right)
};

function check(root1, root2) {
    if (!root1 && !root2) return true;
    if (!root1 || !root2) return false;

    return root1.val === root2.val && check(root1.left, root2.right) && check(root1.right, root2.left);
}

102. 二叉树的层序遍历

var levelOrder = function(root) {
    return helper(root)
};

function helper(root, level = 0, result = []) {
    if (root) {
        result[level] = (result[level] || []).concat(root.val);
        helper(root.left, level + 1, result);
        helper(root.right, level + 1, result);
    }
    
    return result;
}

104. 二叉树的最大深度

var maxDepth = function(root) {
    return helper(root)
};

function helper(root, level = 0) {
    if (root) {
        return Math.max(helper(root.left, level + 1), helper(root.right, level + 1))
    }

    return level;
} 

226. 翻转二叉树

var invertTree = function(root) {
    if (!root) return null;
    const newRoot = {
        val: root.val,
        left: null,
        right: null
    }

    newRoot.left = invertTree(root.right);
    newRoot.right = invertTree(root.left);

    return newRoot;
};

其他

两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。（leetcode.1 easy）

// 使用Map而不是两个循环，空间换时间
function twoSum(arr, target) {
    const map = new Map()
    for (let i = 0; i < arr.length; i++) {
        let value = arr[i]
        let diff = target - value
        if (map.has(diff)) {
            return [map.get(diff), i]
        } else {
            map.set(value, i)
        }
    }
}

twoSum([1, 2, 3, 4], 7)

三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。(leetcode.15 medium)

注意 答案中不可以包含重复的三元组。

function threeSum(arr, sum = 0) {
    let res = []
    let n = arr.length
    arr.sort((a, b) => a - b) // 先排序
    for (let i = 0; i < n - 2; i++) {
        if (arr[i] === arr[i - 1]) continue // 去重
        // 两个指针不断向中间靠拢
        let l = i + 1
        let r = n - 1 
        while(l < r) {
            let m = arr[i] + arr[l] + arr[r]
            if (m === sum) {
                res.push([arr[i], arr[l], arr[r]])
                while(l < r && arr[l] === arr[l + 1]) l++ // 去重
                while(l < r && arr[r] === arr[r - 1]) r-- // 去重
                l++
                r--
            }
            if (m > sum) {
                r--
            }
            if (m < sum) {
                l++
            }
        }
    }
    return res
}

四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。(leetcode.18 medium)

类似三数之和，外面多套一层循环即可，另外要注意重复的情况。

function fourSum(arr, sum) {
    let res = []
    let n = arr.length
    arr.sort((a, b) => a - b) // 先排序
    for (let j = 0; j < n - 3; j++) {
        if (arr[j] === arr[j - 1]) continue // 去重
        for (let i = j + 1; i < n - 2; i++) {
            if (i > j + 1 && arr[i] === arr[i - 1]) continue // 去重，注意 i > j + 1
            // 两个指针不断向中间靠拢
            let l = i + 1
            let r = n - 1 
            while(l < r) {
                let m = arr[j] + arr[i] + arr[l] + arr[r]
                if (m === sum) {
                    res.push([arr[j], arr[i], arr[l], arr[r]])
                    while(l < r && arr[l] === arr[l + 1]) l++ // 去重
                    while(l < r && arr[r] === arr[r - 1]) r-- // 去重
                    l++
                    r--
                }
                if (m > sum) {
                    r--
                }
                if (m < sum) {
                    l++
                }
            }
        }       
    }

    return res
}

n数之和

给定数组，取出 n 个数，使其相加和为 sum

function getArr(arr, n, m, temp = []) {
    if (temp.length === n) {
        let sum = temp.reduce((a, b) => a + b)
        if (sum === m) {
            return temp
        } else {
            return
        }
    }
    
    for (let i = 0; i < arr.length; i++) {
        temp.push(arr.shift())
        let ret = getArr(arr, n, m, temp)
        if (ret) {
            return ret
        } else {
            arr.push(temp.pop())
        }
    }
}


let myArr = [1, 2, 3, 4]
getArr(myArr, 2, 7, [])

两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。(leetcode.2 medium)

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let carry = 0
    let res = new ListNode(-1)
    let cur = res
    while (l1 !== null || l2 !== null) {
        let v1 = l1 ? l1.val : 0
        let v2 = l2 ? l2.val : 0
        let sum = v1 + v2 + carry
        carry = sum >= 10 ? 1 : 0
        cur.next = new ListNode(sum % 10)
        
        cur = cur.next
        l1 = l1 ? l1.next : l1
        l2 = l2 ? l2.next : l2
    }
    if (carry === 1) {
        cur.next = new ListNode(1)
    }
    return res.next
};

// test
class ListNode {
    constructor(val) {
        this.val = val
        this.next = null
    }
}
const l1 = new ListNode(2)
l1.next = new ListNode(4)
l1.next.next = new ListNode(3)

const l2 = new ListNode(5)
l2.next = new ListNode(6)
l2.next.next = new ListNode(4)

addTwoNumbers(l1, l2) // 7 => 0 => 8

无重复字符的最长子串

给定一个字符串，找出其中不含有重复字符的 最长子串 的长度。(leetcode.3 medium)

1 暴力破解（效率很低）

function getLength(str) {
    let length = 0
    for (let i = 0; i < str.length; i++) {
        for (let j = i + 1; j <= str.length; j++) {
            if (isUnique(str, i, j)) {
                length = Math.max(length, j - i)
            }
        }
    }
    return length
}

function isUnique(str, i, j) {
    let set = new Set()
    while (i < j) {
        let char = str.charAt(i)
        if (set.has(char)) {
            return false
        } else {
            set.add(char)
        }
        i++
    }
    
    return true
}
getLength('aaabcdd')

2 滑动窗口

function getLength(str) {
    let n = str.length
    let set = new Set()
    let [len, i, j] = [0, 0, 0]

    while (i < n && j < n) {
        if (set.has(str.charAt(j))) {
            set.delete(str.charAt(i++))
        } else {
            set.add(str.charAt(j++))
            len = Math.max(len, j - i)
        }
    }
    return len
}

判断回文数

回文，即正序和逆序相等的数，如12321，1221等。(leetcode.9 easy)

简单粗暴法，翻转字符串看是否相等

function isHuiWen(num) {
    return num == num.toString().split('').reverse().join('')
}

高级版

function isHuiWen(num) {
    // 数小于0，如-121则不为回文数。
    // 1000这种末尾为0的也不会是回文数
    if (num < 0 || (num % 10 === 0 && num !==0 )) return false 
    let revertNum = 0
    while (num > revertNum) {
        revertNum = num % 10 + revertNum * 10
        num = Math.floor(num / 10)
    }
    
    return num === revertNum || num === Math.floor(revertNum / 10)
}

isHuiWen(12321)
// 1232 1
// 123 12
// 12 123
// 12 === ~~(123 / 10)

实现累加器(柯里化)

描述

// 实现一个add方法，使计算结果能够满足如下预期：
add(1)(2)(3) = 6;
add(1, 2, 3)(4) = 10;
add(1)(2)(3)(4)(5) = 15;

实现

function sum (...args) {
    function fn(...newArgs) {
        return sum(...args, ...newArgs)
    }

    // 重点是这个toString
    // 当最后返回函数的时候，自动调用toString函数进行累加
    fn.toString = () => {
        return args.reduce((a, b) => {
            return a + b
        })
    }

    return fn
}

实现repeat

描述

function repeat(func, times, wait) {
  // TODO
}
const repeatFunc = repeat(alert, 4, 3000);
repeatFunc("hellworld");
//会alert4次 helloworld，每次间隔3秒

实现

一：使用setInterval

function repeat(fn, times, wait) {
    let timer
    let count = 0
    return function (...args) {
        if (times > 0) {
            fn(...args)
        }
        timer = setInterval(() => {
            if (count < times - 1) {
                fn(...args)
                count++
            }
            else {
                clearInterval(timer)
            }
        }, wait)
    }
}

二：使用async/await + setTimeout

function repeat(fn, times, wait) {
    async function func(...args) {
        for (let i = 0; i < times; i++) {
            fn(...args)
            await new Promise((resolve, reject) => {
                setTimeout(resolve, wait)
            })
        }
    }
    return func
}

实现sleep函数

const sleep = (wait) => new Promise((resolve, reject) => {
    setTimeout(resolve, wait)
}) 

// 使用
async function test () {
    await sleep(1000)
    console.log('awake')
}

实现LazyMan

注：微信事业群笔试题

描述

HardMan(“jack”) 输出:
I am jack

HardMan(“jack”).rest(10).learn(“computer”) 输出
I am jack
//等待10秒
Start learning after 10 seconds
Learning computer

HardMan(“jack”).restFirst(5).learn(“chinese”) 输出
//等待5秒
Start learning after 5 seconds
I am jack
Learning chinese

实现

class _HardMan {
    constructor(name) {
        this.tasks = []

        setTimeout(async () => {
            for (let task of this.tasks) {
                await task()
            }
        })

        this.tasks.push(() =>
            new Promise(resolve => {
                console.log(`I am ${name}`)
                resolve()
            })
        )
    }

    wait(sec) {
        return new Promise(resolve => {
            console.log(`//等待${sec}秒..`)
            setTimeout(() => {
                console.log(`Start learning after ${sec} seconds`)
                resolve()
            }, sec * 1000);
        })
    }


    rest(sec) {
        this.tasks.push(() => this.wait(sec))
        return this
    }

    restFirst(sec) {
        this.tasks.unshift(() => this.wait(sec))
        return this
    }

    learn(params) {
        this.tasks.push(() =>
            new Promise(resolve => {
                console.log(`Learning ${params}`)
                resolve()
            })
        )
        return this
    }
}

function HardMan(name) {
    return new _HarnMan(name)
}

// 解答分析：
// 1. 链式调用，每一个方法都返回this
// 2. 并不直接执行代码，而是使用SetTimeout，这样就先把想要执行的任务先放进队列再执行
// 3. sleep/wait 的使用，使用setTimeout，如果不用Promise把setTimeout包住，就无法堵塞后面代码的执行
// 4. 除了用Promise，也可以在每个任务中指定的调用下一个任务，如：
    next() {
        let task = this.tasks.shift()
        task && task()
    }

    wait(sec) {
      setTimeout(() => {
        //do something
        this.next()
      }, sec)
    }