leetCode之算法笔记

前言

经常在V2EX、掘金、知乎上面看到这样的话题：前端工程师应该掌握数据结构和算法吗？我也在想需不需要，貌似在平时的工作中处理业务代码的时候也不经常用是不是，有人说码农不需要掌握算法，一个好的工程师一定会掌握算法的，有过BAT面试经验的人肯定知道一定是会考算法的，算法能考验一个人的大脑思路是否清晰活跃。这对以开发者来说至关重要，LeetCode是一个刷题的网站，知道的人都说好，附上国内官网LeetCode，从今天开始不定期的更新leetCode的算法笔记。

一、整数转罗马数字（难度：中等）

题目描述：
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符	I	V	X	L	C	D	M
数值	1	5	10	50	100	500	1000

例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例1：输入: 3 、输出: “III”
示例2：输入: 4、输出: “IV”
示例3：输入: 9、输出: “IX”
示例4：输入: 58、输出: “LVIII”、解释: L = 50, V = 5, III = 3.
示例5：输入: 1994、输出: “MCMXCIV”、解释: M = 1000, CM = 900, XC = 90, IV = 4.


/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
    // 1. 直接读数组法 （最佳 264 ms）
    const fixedArr = [
        ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX'], // 0-9
        ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC'], // 10-90
        ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM'], // 100-900
        ['', 'M', 'MM', 'MMM']
    ];
    let result = '';
    let i = 0;
    while (num!==0) {
        result = fixedArr[i][num%10] + result;
        num = Math.floor(num/10);
        i++;
    }
    return result;
};

二、罗马数值转整数（难度：中等）

描述就不写了跟👆上面的相反，直接上代码，下面的代码是别人的思路，感觉很妙

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    var m = {
        I: 1,
        V: 5,
        X: 10,
        L: 50,
        C: 100,
        D: 500,
        M: 1000,
    };
    var temp = 0;
    return s.split('').reduce(function(sum, c){
        var cn = m[c];
        sum += cn;
        if(cn > temp) {
            sum -= temp * 2;
        }
        temp = cn;
        return sum;
    }, 0);
};

三、反转字符串（难度：简单）

题目描述：
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组char[]的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例1：输入：[“h”,”e”,”l”,”l”,”o”]、输出：[“o”,”l”,”l”,”e”,”h”]
示例2：输入: [“H”,”a”,”n”,”n”,”a”,”h”]、[“h”,”a”,”n”,”n”,”a”,”H”]

看到这道题很多人肯定回想直接用reverse这种方法不就行了，其实题主的意思肯定是不想你用这种方法

关键点：必须原地修改输入数组


/*
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function(s) {
  const l = s.length;
  for (let i = 0; i < l / 2; i++) {
    let temp = s[i];
    s[i] = s[l - i - 1];
    s[l - i - 1] = temp;
  }
};

四、重复数组判断(难度：简单)

题目描述：
给定一个整数数组，判断是否存在重复元素。如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例1：输入: [1,2,3,1]、输出: true
示例2：输入: [1,2,3,4]、输出: false
示例2：输入: [1,1,1,3,3,4,3,2,4,2]、输出: true


方法一：数组先排序，然后比较，优点省内存，执行速度慢
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function(nums) {
    nums.sort();
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === nums[i+1]) {
          return true;
        }
    }
    return false;
};

方法二:利用对象，缺点显而易见开辟了额外的内存空间，但是执行速度提升了。

var containsDuplicate = function(nums) {
    const has = {};
    for (let i = 0; i < nums.length; i++) {
        if (has[nums[i]]) {
          return true;
        }
        has[nums[i]] = true;
    }
    return false;
}

五、只出现一次的数字（难度：简单）

题目描述：
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例1：输入: [2,2,1]、输出: 1
示例2：输入: [4,1,2,1,2]、输出: 4

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    // 交换律：a ^ b ^ c  <=> a ^ c ^ b,俩两相同的移到一起
    // 相同的数异或为0: n ^ n => 0,只剩下单个的了
    // 任何数于0异或为任何数 0 ^ n => n
    
    var s = 0;
    for(var i=0;i<nums.length;i++){
        s = s^nums[i];
    }
    return s;
};

木子李先生

一只前端汪