Leetcode 汇总

面试题 17.10

数组中占比超过一半的元素称之为主要元素。给一个整数数组，找出其中的主要元素。若没有，返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。

解法

• 边界条件：当输入数组为空，返回 -1 。输入数组仅一个数则返回此数。
• 存在数组占比超过一半的元素则为主要元素 => nums[i] 获得超过 nums.length/2 的数字重复。
• 由于键的唯一性，不存在重复的键值对，考虑哈希表。

var majorityElement = function(nums) {
    if(!nums.length) return -1;
    if(nums.length === 1) return nums[0];
    let map = new Map(),num = Number.MIN_SAFE_INTEGER;
    for(let i = 0; i < nums.length; i++){
        if(!map.get(nums[i])){
            map.set(nums[i],1)
        } else {
            map.set(nums[i],map.get(nums[i])+1)
        }
        max = Math.max(num, map.get(nums[i]))
        if(max > nums.length/2) return nums[i]
    }
    return -1
};

回顾

1. 算法的时间与空间复杂度

常数阶O(1)-消耗并不随着某个变量的增长而增长；线性阶O(n)-消耗的时间是随着n的变化而变化；对数阶O(logN)-循环 logx^n 次以后，代码结束；线性对数阶O(nlogN)

O(1)-算法执行所需要的临时空间不随着某个变量n的大小而变化；O(n)-算法执行所需要的临时空间随着某个变量n的大小而变化

2. Map 与 Object

两者都允许将 key 设置、检索、删除以及检测某个键存储的 value。
Map 的键可以是任何值（函数、对象或任何原始值），而 Object 必须是 String 或 Symbol 。
Map 可以从 size 属性中检索出项目数，而 Object 必须手动检索。
Map 不支持 JSON 序列化与解析，而 Object 支持序列化：JSON.stringify() 与 JSON.parse()

leetcode 14

最长公共前缀：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串""。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""

解法

• 边界条件：当字符串数组长度为 0 时则公共前缀为空，直接返回。
• 初始化最长公共前缀 ans 的值为第一个字符串。
• 遍历字符串，依次将其与 ans 比较，循环找出公共前缀，最终结果即为最长公共前缀。

// JavaScript
var longestCommonPrefix = function(strs) {
    if(strs.length === 0) {
        return '';
    }
    var ans = strs[0];
    for(let i = 1; i < strs.length; i++){
        for(let j = 0; j<ans.length; j++){
            if(ans[j]!==strs[i][j]){
                ans = ans.slice(0,j);
                if (ans === 0){
                    return ''
                }
                break;
            }

        }
    }
    return ans
};

回顾

1. 反向假设默认公共前缀最长字符串为输入字符串数组第一项：

惯性思考方向是建立空字符串 ans，根据输入字符串数组的项中的元素逐一两两比较，再于 ans 中加入相同的字符串。但是这种模式在输入字符串数组存在项的情况下，会导致时间复杂度很高，光是确定 ans[0]就需要循环 strs.length 次。

2. 区分 slice、splice、substring、substr：

⭕️ slice 可操作数组和字符串，splice 只能操作数组，substring 和 substr 只能操作字符串。

slice(start,stop) 截取从下标 start 到下标 stop（不包括该元素）的之间的元素，返回新数组/新字符串，并不修改原数组/原字符串。

var str = "012345";
console.log(str.slice(1,4)) // 123

splice(start,length,items) 从下标 start 处截取 length 长度的元素后，在 start 处为原数组添加 items，并返回 被截取的新数组，splice会直接修改原数组。

var arr = [0,1,2,3,4,5];
console.log(arr.splice(1,0,2,3,4)); // []
console.log(arr); // [0,2,3,4,1,2,3,4,5] 

substring(start,stop) 返回从 start 开始到 stop 处之间的新字符串。包含 start，但不包含 stop，不修改原字符串。

var str = "012345";
console.log(str.substring(2,5)); // 234

substr(start,length) 返回从 start 开始直到 length 长度的新字符串，包含 start，不修改原字符串。

var str = "012345";
console.log(str.substr(2,2)) // 23

3. 区分 break、return、continue：

break: 直接跳出当前的循环，从当前循环外面开始执行。忽略且仅忽略当前循环体，只能跳出一层回圈。如果循环逐个嵌套，那么需要按照循环圈的层次，逐步使用 break 跳出。
return: 从当前的方法中退出，返回到使用该的方法的语句处继续执行。
continue: 终止当前的一次循环过程，不跳出循环，而是继续往下循环判断条件执行语句。只能结束循环中的一次过程，但不能终止循环继续进行。

function myBreak() {
    for(var i = 0; i < 5; i++) {
        if(i == 3) {
            break;
        }
    console.log(i);
    }
    console.log("out");
}
myBreak(); // 0 1 2 out

function myReturn () {
    for(var i = 0; i < 5; i++) {
        if(i == 3) {
            return;
        }
    console.log(i);
    }
    console.log("out");
}
myReturn(); // 0 1 2

function myContinue() {
    for(var i = 0; i < 5; i++) {
        if(i == 3) {
            continue;
        }
    console.log(i);
    }
    console.log("out");
}
myContinue(); // 0 1 2 4 out

• 58.最后一个单词的长度

一个字符串 s 由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。单词是指仅由字母组成、不包含任何空格字符的最大子字符串。
输入 s = "Hello World" 输出：5
输入 s = " fly me to the moon " 输出：4
输入 s = "luffy is still joyboy" 输出：6

var lengthOfLastWord = function(s) {
  // trim() 方法移除字符串起始及结尾的空白
  s = s.trim(); // the moon | m
  let end = s.length - 1; //  7 | 0
  let start = end;
  while (start >= 0 && s.charAt(start) !== ' ') {
    start--;
  }
  return end - start
}

• 171.Excel 表列序 => 给定 Excel 表格中的列名称，返回其相应的列序

charCodeAt() 方法返回 0 到 65535 之间的整数，表示给定索引处的 UTF-16 代码单元

/*
  A -> 1、B -> 2、C -> 3 ... Z -> 26、AA -> 27、AB -> 28 
  输入 "A" 输出 1 ... 输入 "AB" 输出 28
*/
var titleToNumber = function(columnTitle) {
    let number = 0;
    let multiple = 1;
    for (let i = columnTitle.length - 1; i >= 0; i--) {
        const k = columnTitle[i].charCodeAt() - 'A'.charCodeAt() + 1;
        number += k * multiple;
        multiple *= 26;
    }
    return number;
}
class Solution {
    public int titleToNumber(String columnTitle) {
        int number = 0;
        int multiple = 1;
        for (int i = columnTitle.length() - 1; i >= 0; i--) {
            int k = columnTitle.charAt(i) - 'A' + 1;
            number += k * multiple;
            multiple *= 26;
        }
        return number;
    }
}

结束

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！