狐七的面试题库

数组

3/23/2022 算法

# 数组里面有 10 万个数据，取第一个元素和第 10 万个 元素的时间相差多少？

查看答案

数组可以直接根据索引取的对应的元素，所以不管取哪个位置的元素的时间复杂度都是 O(1)
得出结论：消耗时间几乎一致，差异可以忽略不计

# 旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1：
输入: [1, 2, 3, 4, 5, 6, 7] 和 k = 3
输出: [5, 6, 7, 1, 2, 3, 4]
解释:
向右旋转 1 步: [7, 1, 2, 3, 4, 5, 6]
向右旋转 2 步: [6, 7, 1, 2, 3, 4, 5]
向右旋转 3 步: [5, 6, 7, 1, 2, 3, 4]

示例 2：
输入: [-1, -100, 3, 99] 和 k = 2
输出: [3, 99, -1, -100]
解释:
向右旋转 1 步: [99, -1, -100, 3]
向右旋转 2 步: [3, 99, -1, -100]

查看答案 
function rotate(arr, k) {
    const len = arr.length
    // 超出数组长度取模
    const step = k % len
    return arr.slice(-step).concat(arr.slice(0, len - step))
}
// rotate([1, 2, 3, 4, 5, 6], 7) => [6, 1, 2, 3, 4, 5]
1
2
3
4
5
6
7

# 找出 1 - 10000 之间的所有对称数

查看答案 
// [...Array(10000).keys()] 也可以
[...new Array(10000).keys()].filter((x) => {
    return x.toString().length > 1 && x === Number(x.toString().split('').reverse().join(''))
})
1
2
3
4

# 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
复制代码说明: 必须在原数组上操作，不能拷贝额外的数组，尽量减少操作次数。

查看答案 
function zeroMove(array) {
    let len = array.length;
    let j = 0;
    for (let i = 0; i < len - j; i++) {
        if (array[i] === 0) {
            array.push(0);
            array.splice(i, 1);
            i--;
            j++;
        }
    }
    return array;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

# 数组中找出重复元素

var arr = ["a", "c", "a", {"a": 2}, 112, {"a": 2}, 112, 234, {"b": 1}] // [ 'a', { a: 2 }, 112 ]

查看答案 
// map + 计数器，时间复杂度O(n ^ 2)
function findRepeat(arr) {
	let map = new Map()
	let result = []
	arr.forEach((val) => {
		const str = (typeof val === 'object' && val !== null) ? JSON.stringify(val) : val
		map.set(str, map.get(str) ? map.get(str) + 1 : 1)
	})
	map.forEach((val, key) => {
		if (val > 1) {
			try {
				result.push(JSON.parse(key))
			} catch (error) {
				result.push(key)
			}
		}
	})
	return result
}

// map的遍历还可以
for(let [k, v] of map.entries()) {
    if(v > 1) {
        try {
            result.push(JSON.parse(k))
        } catch (error) {
            result.push(k)
        }
    }
}

// [ 'a', { a: 2 }, 112 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 接雨水问题

LeetCode上面有这道题，题号42
给定n个非负整数表示每个宽度为1的柱子的高度图，计算彼此排列的柱子，下雨之后能接多少雨水。
示例1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

实例2：
输入：height = [4,2,0,3,2,5]
输出：9

接雨水问题详细解释 (opens new window)

查看答案 
// 暴力解法，时间复杂度O(n)，空间复杂度O(n)
function trap(height) {
    if(!height.length) return 0;
    let left = []
    let right = []
    let lmax = rmax = 0
    let len = height.length
    let result = 0
    // 把左右最大出水量求出来
    for(let i = 0; i < len; i++) {
        lmax = Math.max(height[i], lmax)
        rmax = Math.max(height[len-i-1], rmax)
        left[i] = lmax
        right[len- i - 1] = rmax
    }
    // 算出最小的然后累加
    for(let i = 0; i < len; i++) {
        result += Math.min(left[i],right[i]) - height[i]
    }
    return result
};

// 最后的累加可以使用reduce
return height.reduce((prev, item, index) => {
    return prev + Math.min(left[index],right[index]) - item
}, 0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# LeetCode No.1 两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

查看答案 
// 暴力解法，时间复杂度O(n ^ 2)
function twoSum(nums, target) {
    for(var i = 0 ; i <= nums.length -1 ; i++){
        for(var j = i+1 ; j <= nums.length-1 ; j++){
            if(nums[j] + nums[i] == target){
                return [i,j]
            }
        }
    }
};
1
2
3
4
5
6
7
8
9

# 请找出这两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2
要求算法的时间复杂度为 O(log(m+n))

示例 1： nums1 = [1, 3] nums2 = [2] 中位数是 2.0
示例 2： nums1 = [1, 2] nums2 = [3, 4] 中位数是(2 + 3) / 2 = 2.5

查看答案 
const findMedianSortedArrays = function (nums1: number[], nums2: number[]) {
    const lenN1 = nums1.length;
    const lenN2 = nums2.length;
    const median = Math.ceil((lenN1 + lenN2 + 1) / 2);
    const isOddLen = (lenN1 + lenN2) % 2 === 0;
    const result = new Array < number > (median);
    let i = 0; // pointer for nums1 
    let j = 0; // pointer for nums2 
    for (let k = 0; k < median; k++) {
        if (i < lenN1 && j < lenN2) { // tslint:disable-next-line:prefer-conditional-expression 
            if (nums1[i] < nums2[j]) {
                result[i + j] = nums1[i++];
            } else {
                result[i + j] = nums2[j++];
            }
        } else if (i < lenN1) {
            result[i + j] = nums1[i++];
        } else if (j < lenN2) {
            result[i + j] = nums2[j++];
        }
    }
    if (isOddLen) {
        return (result[median - 1] + result[median - 2]) / 2;
    } else {
        return result[median - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 合并两个有序数组

查看答案

合并两个有序数组是归并排序的原理。从头比较两个数组，小的那个先进入结果数组中，继续比较。

写法一：

function merge(l,r) {
    let len = l.length + r.length
    let lindex = 0
    let rindex = 0
    let result = []
    for(let i = 0; i < len; i++) {
        if (lindex < l.length && rindex < r.length) {
            if (l[lindex] <= r[rindex]) {
                result.push(l[lindex++])
            } else {
                result.push(r[rindex++])
            }
        } else if (lindex < l.length) {
            result.push(l[lindex++])
        } else {
            result.push(r[rindex++])
        }
    }
    return result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

写法二：

function merge(arrA, arrB) {
    const result = [];
    let i = 0; 
    let j = 0;
    while (i < arrA.length && j < arrB.length) {
        if (arrA[i] < arrB[j]) {
            result.push(arrA[i]);
            i++;
        } else {
            result.push(arrB[j]);
            j++;
        }
    }
    while (i < arrA.length) {
        result.push(arrA[i]);
        i++;
    }
    while (j < arrB.length) {
        result.push(arrB[j]);
        j++;
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
更新时间: 2024-06-12 11:00

树