面试算法题二

本文主要是介绍面试算法题二，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

我们知道在javascript中 可以在数组中保存不同类型的值 并且数组可以动态增长，不像其他语言 例如
C 创建的时候要决定数组的大小 如果数组满了 ，就要重新申请内存，这是为什么呢?
可从四个方面回答这个问题
数组基础入门
javascript中 数组为什么可以保存不同类型的值
javascript中 数组是如何存储的
javascript中 数组的动态扩容与减容
Javascript中JSArray继承自JSObject,或者说它是一个特殊的对象,内部是以key-value形式存储数据
所以javascript中的数组可以存放不同类型的值。
它有两种存储方式,快数组与慢数组,初始化数组时 使用快数组，快数组使用连续的内存空间
当数组长度达到最大时 JSArray会进行动态扩容 以储存更多的元素，相对于慢数组 性能要好很多
当数组hole太多时(数组长度太长时) 会转变成慢数组,即以哈希表的方式(key-value的形式)存储数据 以节省内存空间

最后附赠一道前端面试题（腾讯）：数组扁平化、去重、排序

已知如下数组：var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];
编写一个程序将数组扁平化去除其中重复的部分  最终得到一个升序且不重复的数组
var arr = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];
// 扁平化
let flatArray = arr.flat(4)
// 去重
let disArr = Array.from(new Set(floatArray))
// 排序
let result = disArr.sort((a,b)=>a-b)
console.log(result);



const getArray = (arr, dep) => Array.from(new Set(arr.flat(dep))).sort()
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

给你两个有序整数数组nums1和nums2 请你将nums2合并到nums1中 使num1成为一个有序数组
说明:nums1和nums2的元素数量分别为m和n。
你可以假设nums1有足够的空间 (空间大于或等于m + n) 来保存nums2中的元素
示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

nums1 、 nums2 有序，若把 nums2 全部合并到 nums1 ，则合并后的 nums1 长度为 m+n
我们可以从下标 m+n-1 的位置填充 nums1 ，比较 nums1[len1] 与 nums2[len2] 的大小，将最大值写入 nums1[len]，即
nums1[len1]>=nums2[len2] ，nums1[len–] = nums1[len1–] ,这里 – 是因为写入成功后，下标自动建议，继续往前比较
否则 nums1[len–] = nums2[len2–]
边界条件：
若 len1 < 0 ，即 len2 >= 0 ，此时 nums1 已重写入， nums2 还未合并完，仅仅需要将 nums2 的剩余元素（0…len）写入 nums2 即可，写入后，合并完成
若 len2 < 0，此时 nums2 已全部合并到 nums1 ，合并完成
时间复杂度为 O(m+n)
代码实现:

const merge = function(nums1,m,nums2,n){
    let len1 = m-1;
    let len2 = n-1;
    len = m + n -1;
    while(len2>=0){
        if(len1<0){
         nums1[len--] = nums2[len2--]
         continue
        }
        nums1[len--] = nums1[len1]>=nums2[len2]?nums1[len1--]:nums2[len2--]
    }
}

给定一个整数数组nums和一个目标值target 请你在该数组中找到和为目标值的那两个整数，并返回他们的数组下标
你可以假设每种输入只会对应一个答案。但是 你不能重复利用这个数组中同样的元素
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解题思路:
初始化一个map= new Map()
从第一个元素开始遍历nums
获取目标值与nums[i]的差值 即k = target - nums[i]
判断差值在map中是否存在
不存在(map.has(k)为false),则将nums[i]加入到map中(key为nums[i],value为i,方便查找map中是否存在某值)
并可以通过get方法直接拿到下标
存在(map.has(k)) 返回[map.get(k),i],求解结束
遍历结束 则nums中没有符合条件的两个数 返回[]
时间复杂度 O(n)

const twoSum = function(nums,target){
    let map = new Map()
    for(let i =0;i<nums.length;i++){
        let k = target-nums[1]
        if(map.has(k)){
            return [map.get(k),i]
        }
        map.set(nums[i],i)
    }
    return []
}

这篇关于面试算法题二的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！