leetCode之算法笔记

  |  
 阅读次数

前言

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

一、整数转罗马数字(难度:中等)


题目描述:
罗马数字包含以下七种字符: IVXLCDM


字符 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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
* @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;
};

二、罗马数值转整数(难度:中等)

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

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
/**
* @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这种方法不就行了,其实题主的意思肯定是不想你用这种方法

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

1
2
3
4
5
6
7
8
9
10
11
12
13

/*
* @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
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

方法一:数组先排序,然后比较,优点省内存,执行速度慢
/**
* @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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @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;
};