面试经典150题——算法(数组/字符串)第一篇

发布于:2025-08-20 ⋅ 阅读:(17) ⋅ 点赞:(0)

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    var left = n-1;
    if(n==0){
        return nums1;
    }
    for(let i = m+n-1; i>=0; i--){
        if(nums1[i]!=0||left < 0){
            break;
        }else{
            nums1[i] = nums2[left];
            left = left-1;
        }
    }
    nums1.sort((a,b)=>a-b)
    return nums1;
};

注意:这里的突破点就是nums1[i]!=0||left < 0这个条件

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    var left = 0;
    while(left<nums.length){
        if(nums[left]==val){
            nums.splice(left,1);
        }else{
            left++;
        }
    }
    return nums.length;
};

注意:这里是考察数组中元素删除知识点,元素删除有以下几种方式:

(1)splice(起始索引,删除数量)
(2)pop()删除最后一个元素
(3)shift()删除第一个元素
(4)使用filter()返回新数组,不修改原数组

splice()、pop()、shift()都会修改原数组,而filter()会返回新数组,原数组保持不变。

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    var length = nums.length;
    if(length==0||length==1){
        return length;
    }
    var slow = 0;
    for(let fast = 1; fast<length; fast++){
        if(nums[slow]!=nums[fast]){
            slow++;
            nums[slow]=nums[fast]
        }
    }
    return slow+1;
};

注意:我原本是使用splice进行删除虽然也能得到正确答案,但是时间消耗还是比较大的。仔细读题题目中说

  • 更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。

所以我们只需要使前k个元素包含唯一元素就好了,就得到以上解法。

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    if(nums.length<=2){
        return nums.length;
    }
    var slow = 0;
    var num = 1;
    for(let fast = 1;fast<nums.length; fast++){
        if(nums[slow]==nums[fast]&&num<2){
            slow++;
            nums[slow]=nums[fast]
            num++;
        }else if(nums[slow]!=nums[fast]){
            slow++;
            nums[slow] = nums[fast];
            num = 1;
        }
    }
    return slow+1;
};

注意:跟上一题一样思路只是需要一个数计算此时数组中出现的数在数组中是第几次出现,而且要注意赋值就算是一样的数也要赋值,这样能确保逻辑正确,如果不进行赋值在某些情况下就会出现错误,比如输入[0,0,1,1,1,1,2,3,3],如果不赋值出现结果是[0,0,1,1,2,3,2]因为你在发现第二个3时没有把它赋值给第一个3后面那个数而后面那个数将继续保持2。

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    var length = (nums.length)/2
    nums.sort((a,b)=>a-b);
    var slow = 0;
    var num = 1;
    for(let fast = 1; fast<nums.length; fast++){
        if(nums[slow]==nums[fast]){
            num++;
            slow++;
        }else{
            num = 1;
            slow++;
        }
        if(num>length){
            return nums[slow];
        }
    }
    return nums[slow];
};

注意:我的思路是先进行排序,排序以后相同的数会在一起然后在通过遍历计数计算这个相同的数有几个,然后返回满足条件的数就好了。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function(nums, k) {
    if(nums.length<=1){
      return nums;
    }
    var length = nums.length
    if(length<=k){
      k = k%length
    }
      for(let i = length-k; i<length; i++){
        nums.push(nums[i]);
      }
      for(let i = 0;i<length-k;i++){
        nums.push(nums[i])
      }
      nums.splice(0,length);
    return nums;
};

注意:这里在if(length<=k)的条件下,使用k = k%length来计算新的滚动值,不能使用k = k-(k/length)*length来求因为这里的k/length并不会取得整数,而是会保留小数部分,我们想保留整数部分需要使用下列方法:

  • Math.floor(k / length):向下取整(7/2=3.5 → 3)
  • Math.ceil(k / length):向上取整(7/2=3.5 → 4)
  • Math.round(k / length):四舍五入(7/2=3.5 → 4)
  • parseInt(k / length):直接截断小数部分(7/2=3.5 → 3)

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let min = prices[0];
    let max = 0;
    let result = 0;
    for(let i = 1; i<prices.length; i++){
      if(prices[i]<min){
        min = prices[i];
      }
      result = prices[i]-min;
      if(result>max){
        max = result;
      }
    }
    return max;
};

注意:这一题主要就是想清楚像[2,8,1,5]的情况和[2,1,8,5]的情况。在[2,8,1,5]情况下如果是后面最小值可能会被替换成1,但是最终计算结果的最大值不会发生变化。在[2,1,8,5]的情况下,8在1后面就更好理解了最大值将会是8-1。所以通过一次循环就可以计算出最大值。

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let result = 0;
    let left = prices[0]
    let right = prices[0];
    let middle = 0;
    for(let i = 1; i<prices.length; i++){
      if(prices[i]<right){
        middle = right-left;
        result = result+middle;
        left = prices[i];
        right = prices[i];
      }else{
        right = prices[i];
      }
    }
    middle = right-left;
    result = result+middle;
    return result;
};

注意:代码通过追踪每一段连续上涨的区间(从 left 到 right),在区间结束时(价格开始下跌)卖出,赚取这段区间的利润。这样即使有多次涨跌,也能把所有上涨的利润都收入囊中,最终得到最大利润。

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {
    if(nums.length<=1){
        return true;
    }
    for(let i = 0; i<nums.length-1; i++){
        if(nums[i]==0){
            let sum = 0;
            for(let j = i-1;j>=0;j--){
                if(nums[j]>(i-j)){
                    sum++;
                    break;
                }
            }
            if(sum==0){
                return false;
            }
        }
    }
    return true;
};

注意:这里首先如果数组中每一个元素都不为0那么肯定能跳到最后一格。如果是最后一个元素为0其它元素不为0也能跳到最后一格。如果第一个元素就是0肯定不能跳到最后一格。还有一种情况就是中间元素有为0的,那就需要考虑0前面元素有没有使得能直接跨过这个0的,只要能跨过0就能跳到最后一格。还有就是数组只要一格元素直接就是最后一格直接返回true。

/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    if(nums.length<=1){
        return 0;
    }
    var position = nums.length-1;
    var step = 0;
    while(position>0){
        for(let i = 0; i<nums.length-1; i++){
            if(i+nums[i]>=position){
                step++;
                position = i;
                break;
            }
        }
    }
    return step;
};

注意:这一题是使用贪心算法,我利用的是反向查找出发位置,先定位到最后一个位置,然后正向查找能到达这个位置的数,最先查找到的也就是跳跃次数最少的。

/**
 * @param {number[]} citations
 * @return {number}
 */
var hIndex = function(citations) {
    var length = citations.length;
    var result = 0;
    citations.sort((a,b)=>a-b)
    for(let i = length; i>=0; i--){
        for(let j = 0; j<=length-i; j++){
            if(citations[j]>=i){
                result = i;
                return result;
            }
        }
    }
    return result;
};

注意:这一题首先就要搞清楚什么是h指数

  1. 这个研究者至少发表了 h 篇论文(比如 h=3,就意味着他发的论文总数≥3);
  2. 这 h 篇论文里,每篇的被引用次数都至少是 h 次(比如 h=3,就需要至少有 3 篇论文每篇被引都≥3 次)。

然后从而得知h指数需要的三个条件,如上面标红地方就是需要的条件。然后根据需要的条件编写代码,首先就是要得到数组的总长度,因为这个代表论文总数,由条件可知这个h指数肯定小于等于论文总篇数,而且有多个h指数时候取最大值,所以我们从大到小进行遍历。由于我们是要求有大于等于h篇论文的引用大于等于h所以我们需要先把论文引用从小到大排序,然后遍历前面(总篇数-h+1)篇有没有引用大于h的就好了,如果前面(总篇数-h+1)篇没有就不会满足条件大于等于h篇论文的引用大于等于h


var RandomizedSet = function() {
    this.values = [];
    this.map = new Map();
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if(this.map.has(val)){
        return false;
    }
    this.values.push(val);
    this.map.set(val,this.values.length-1)
    return true
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    if(!this.map.has(val)){
        return false;
    }
    var index = this.map.get(val);
    this.values[index] = this.values[this.values.length-1];
    this.map.set(this.values[this.values.length-1],index)
    this.values.pop();
    this.map.delete(val);
    return true;
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    var random = Math.floor(Math.random()*this.values.length);
    return this.values[random];
};

/** 
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */

注意:prototype的作用是为该构造函数创建的所有实例对象共享方法和属性。这题重点是掌握数组和Map集合中的一些方法,然后数组变化时候记得Map集合也要发生相应变化。其实获取随机数使用代码var random = Math.floor(Math.random()*this.values.length);这一行代码意思是

  1. Math.random()
    这是 JavaScript 内置的随机数生成函数,返回一个大于等于 0 且小于 1 的浮点数(即范围是 [0, 1))。例如可能返回 0.3450.999 等。

  2. * this.values.length
    将随机数乘以数组的长度(this.values 是存储元素的数组)。假设数组长度为 5,那么这一步会把随机数范围从 [0, 1) 扩展到 [0, 5),可能得到 1.234.99 等结果。

  3. Math.floor(...)
    对结果进行向下取整(取小于等于该数的最大整数)。例如:

    • 如果上一步结果是 1.23,取整后为 1
    • 如果是 4.99,取整后为 4

网站公告

今日签到

点亮在社区的每一天
去签到