interview code

[scarcoco]

问题描述

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]
输出: 2

示例 2:

输入: [3,1,3,4,2]
输出: 3

说明：

• 不能更改原数组（假设数组是只读的）。
• 时间复杂度小于 O(n*n) 。
• 数组中只有一个重复的数字，但它可能不止重复出现一次。

解法

不考虑空间复杂度：O(n)，Array 或者 Map 缓存访问过的值

暴力方法（时间复杂度不满足）

function getRepeat(arr) {
    const len = arr.length
    let result
    for (let i = 0; i < len-1; i ++) {
        for (let j = i+1; j < len; j ++) {
            if (arr[i] === arr[j]) {
                result = arr[i]
            }
        }
        if (result !== undefined) {
            break
        }
    }
    return result
}

Map 缓存（可用数组）

function getRepeat(arr) {
    const ret = {}, len = arr.length
    let i
    for (i = 0; i < len; i++) {
        if (ret[arr[i]]) {
            break
        }
        ret[arr[i]] = 1
    }
    return i === len ? undefined : arr[i]
}

其他想法

如果确认只有一个元素重复，可以结合鸽笼原理和 N 个数求和相减即可。

面试官想要的解法

二分法猜元素，遍历查找，比如刚开始猜测试 M = Math.floor(N / 2)，那么遍历小于 M 的元素个数，和大于 M 的元素个数，根据结果推断是在那边，然后继续，直到找到元素。

function getRepeat(arr) {
    const len = arr.length
    // n+1 => [1, n]
    let min = 1, max = len - 1
    let guess
    do {
        guess = Math.floor((min + max) / 2)
        let smallCount = 0, bigCount = 0

        for (let i = 0; i < len; i++) {
            if (arr[i] > guess) {
                bigCount ++ 
            } else if (arr[i] < guess) {
                smallCount ++
            }
        }
        if (smallCount > (guess - min)) {
            max = guess - 1
        } else if (bigCount > (max - guess)) {
            min = guess + 1
        } else {
            break
        }
    } while (min <= max)
    
    return guess
}

[scarcoco]

回文判断

给定一个字符串，可能包含大小写字母、数字和空格，判断这个字符串是否是回文：

• 忽略空字符和大小写；
• 正序和逆序字符串相同；

/**
 * 是否是回文判断
 * @param {string} s
 * @return {boolean}
 */
function isPalindrome(s) {
    const len = s.length
    let flag = true
    let i = 0, j = len-1;
    
    while(i <= j) {
        while(!isValidChar(s[i])) {
            i ++ 
        }
        while(!isValidChar(s[j])) {
            j --
        }
        
        if(i === j) {
            break
        }
        if(s[i].toLowerCase() === s[j].toLowerCase()) {
            i ++, j --
        }
    }
    return flag
};

function isValidChar(s) {
    return s >= 'a' && s <= 'z' || s >= 'A' && s <= 'Z' || s >= '0' && s <='9'
}

[scarcoco]

压缩字符串

给定递增整数数组，现在要求把连续三个或者三个以上的整数表示为 x-y，其他情况不改变，输出都好分割的字符串。

比如：

[1, 2, 3, 4] => '1-4'
[1, 2, 5, 6, 7, 8, 9, 10, 11] => '1,2,5-11'
[1, 3, 5, 7, 8, 10, 11] => '1,3,5,7,8,10,11'

注意问题：边界条件

代码实现

function convert(nums) {
    const ret = []
    const len = nums.length
    if (len <= 2) {
        return nums.join(',')
    }

    function compress(start, end) {
        const delta = end - start + 1
        if (delta > 2) {
            ret.push(`${nums[start]}-${nums[end]}`)
        } else if (delta === 2) {
            ret.push(nums[start])
            ret.push(nums[start + 1])
        } else if (delta === 1) {
            ret.push(nums[start])
        }
    }

    let index = 0
    for (let i = 1; i < len;) {
        while (i - index === nums[i] - nums[index] && i < len) {
            i++
        }
        if(i >= len) {
            break
        }

        compress(index, i-1)

        index = i
        i = index + 1
    }
    compress(index, len-1)
    return ret.join(',')
}

[scarcoco]

wechat

1.设定如下的对应关系(A=1,B=2,C=3,...,Z=26,AA=27,AB=28,....AZ=, BA=, .....AAA=, ...)，编写一个转换函数，根据上面的规则把一个字符串: "WECHAT" 转换为数字

之前代码问题直接用字符相减，而不是 charCodeAt 。

function convert26to10(str) {
    const len = str.length
    let sum = 0
    let factor = 1
    const acode = 64 // 'A'.charCodeAt(0) - 1

    for(let i = len-1; i>=0; i--) {
        sum += (str[i].charCodeAt(0) - acode) * factor 
        factor *= 26
    }
    return sum
}

2.在二叉排序树{value:Number, left:Object, right:Object}上面找出第3大的节点。注意：不能把二叉树全量存储到另外的存储空间，比如存储到数组中，然后取出数组的第三个元素。

当时自己的解法如下，但是没有认真审题，二叉排序树这个条件没有利用上。

function getThirdElement(root, maxList = [], N = 3) {
    if (!root) {
        return null
    }

    // 插入排序思想
    let i = maxList.length - 1
    while (root.value > maxList[i] && i >= 0) {
        if (i + 1 < N) {
            maxList[i + 1] = maxList[i]
        }
        i--
    }
    maxList[i + 1] = root.value

    getThirdElement(root.left, maxList, N)
    getThirdElement(root.right, maxList, N)

    return maxList.length < N ? null : maxList[N - 1]
}

考虑有序数组的处理方法：

function getThirdElement(root) {

}

3.从一个整数数组中，找出连续递增的最长序列。

function getLongestAscSeq(arr) {
    if (arr.length <= 1) {
        return arr
    }
    let lastStart = 0, lastEnd = 1

    let i = 0, j = 0

    for (; j < arr.length - 1; j++) {
        while (arr[j + 1] >= arr[j] && j < arr.length - 1) {
            j++
        }

        if (j + 1 >= arr.length) {
            break
        }

        if (j + 1 - i > lastEnd - lastStart) {
            lastStart = i
            lastEnd = j + 1
        }
        i = j + 1
        j = i
    }
    if (j + 1 - i > lastEnd - lastStart) {
        lastStart = i
        lastEnd = j + 1
    }

    return arr.slice(lastStart, lastEnd)
}

4.从单链表{value:Number, next:Object}中找出中间位置的节点。

这个应该是一个经典的面试题，我直接暴力处理，实际上应该用快慢双指针处理。

function getMiddleNode(root) {
    let count = 0
    iif(!root || !root.next) {
        return root
    }

    let temp = root
    while (temp) {
        count++
        temp = temp.next
    }

    let temp = root

    const isOdd = count % 2 === 0
    let middle = (count >> 1) + (isOdd ? 0 : 1)

    let middleNode = null

    let i = 0
    while (temp) {
        i++
        if (i == middle) {
            middleNode = temp
            break
        }
        temp = temp.next
    }

    return middleNode
}

快慢指针方式

function getMiddleNode(root) {
    if(!root || !root.next) {
        return root
    }
    let slow = root
    let fast = root.next
    while(fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }

    return slow
}

5.两个有序（从小到大）单链表{value:Number, next:Object}，构造一条新有序链表，包含同时出现在两个链表的节点

这个题的思想和合并两个有序数组的思想类似。

function getCommonElementLink(a, b) {
    let atemp = a
    let btemp = b
    let ret = null, retHead = null

    while (atemp && btemp) {
        if (atemp.value === btemp.value) {
            const node = {
                value: atemp.value,
                next: null
            }
            // 第一个节点
            if (ret === null) {
                retHead = ret = node
            } else {
                // 后续节点
                ret.next = node
                ret = node
            }
        } else if (atemp.value > btemp.value) {
            btemp = btemp.next
        } else if (atemp.value < btemp.value) {
            atemp = atemp.next
        }
    }

    return retHead
}

6.反转数组，在原数组反转（不能使用arr.reverse方法）

之前代码写错了，swap 应该是箭头函数，笔试的时候写成普通函数。。

Array.prototype.reverse = Array.prototype.reverse || function () {
    const swap = (i, j) => {
        const temp = this[i]
        this[i] = this[j]
        this[j] = temp
    }
    let len = this.length
    let half = len >> 1;
    for (let i = 0; i < half; i++) {
        swap(i, len - 1 - i)
    }
    return this
}

[scarcoco]

wechat

给定数组 A，判断是否可以把数组拆分为三个子数组，三个子数组的和相同。

最初的想法是把这个问题转化为：

给定数组 A 和整数 S，找出子元素构成的新数组，使得其和为 S。

解决思路：递归方式，和为 N 的情况包括：假设数组的长度为 N，那么要么前 N-1 个数的和为 S，或者前 N-1 个数的和为 S - last。

// 0 可以不参与
function filterZero(arr) {
    return arr.filter(Boolean)
}

// 返回所有和为 sum 的情况列表，否则返回 false
function getSubArrayOfN(arr, sum, len) {
    if (len === undefined) {
        len = arr.length
    }
    // 终止条件
    if (len <= 0) {
        return false
    }

    const last = arr[len - 1]
    if (len <= 1) {
        if (last === sum) {
            return [[last]]
        }
        return false
    }

    const case1 = getSubArrayOfN(arr, sum, len - 1)
    const case2 = getSubArrayOfN(arr, sum - last, len - 1)

    if (case1 === false && case2 === false) {
        return false
    }
    let ret = []

    if (case1 !== false) {
        ret = ret.concat(case1)
    }

    if (case2 !== false) {
        ret = ret.concat(case2.map(item => item.concat(last)))
    }
    return ret
}

第二个函数返回的元素个数可能大于3，也可能等于3，也可能小于3，小于3肯定是不行的，那么大于等于3也有可能不行，有可能每个元素被多次使用，比如：

arr = [1, 5, 3, -2, 9, 5]
S = 4

[1, 3]
[1, 5, -2]
[1, -2, 5]

虽然结果返回 3 个数组，但是还是不符合条件，因为 1 和 -2被使用了多次，所以还需要继续后面的问题。

已知多个子数组和一个原始数组，选择 3 个数组，使得其拼接的数组为原始数组。