输入: "A man, a plan, a canal: Panama"
输出: true
输入: "race a car"
输出: false
题目分析设想
这道题我有两个方向,一是改变原输入串,二是不改变原输入串。
改变原输入串,可以去掉非字母和数字的字符后,反转判断或者双指针判断或者单指针
不改变原输入串,直接双指针判断
主要作答方法就是反转判断,双指针法以及二分法。
编写代码验证
Ⅰ.反转判断
代码:
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
// 正则去除不满足条件的字符
let str = s.toLowerCase().replace(/[^0-9a-z]/g, '')
return str === str.split('').reverse().join('')
};
结果:
476/476 cases passed (72 ms)
Your runtime beats 95.33 % of javascript submissions
Your memory usage beats 47.7 % of javascript submissions (38.1 MB)
时间复杂度: O(1)
Ⅱ.双指针法(预处理字符)
代码:
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
// 正则去除不满足条件的字符
let str = s.toLowerCase().replace(/[^0-9a-z]/g, '')
let len = str.length
let l = 0
let r = len - 1
while(l < r) {
if (str.charAt(l) !== str.charAt(r)) {
return false
}
l++
r--
}
return true
};
结果:
476/476 cases passed (76 ms)
Your runtime beats 89.25 % of javascript submissions
Your memory usage beats 70.96 % of javascript submissions (37.4 MB)
时间复杂度: O(n)
Ⅲ.单指针法(预处理字符)
代码:
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
// 正则去除不满足条件的字符
let str = s.toLowerCase().replace(/[^0-9a-z]/g, '')
let len = str.length
// 最多需要判断的次数
let max = len >>> 1
let i = 0
while(i < max) {
if (len % 2) { // 奇数
if (str.charAt(max - i - 1) !== str.charAt(max + i + 1)) {
return false
}
} else { // 偶数
if (str.charAt(max - i - 1) !== str.charAt(max + i)) {
return false
}
}
i++
}
return true
};
结果:
476/476 cases passed (72 ms)
Your runtime beats 95.33 % of javascript submissions
Your memory usage beats 56.02 % of javascript submissions (38 MB)
时间复杂度: O(n)
Ⅳ.双指针法
代码:
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
let len = s.length
let l = 0
let r = len - 1
while (l < r) {
if (!/[0-9a-zA-Z]/.test(s.charAt(l))) {
l++
} else if (!/[0-9a-zA-Z]/.test(s.charAt(r))) {
r--
} else {
if(s.charAt(l).toLowerCase() !== s.charAt(r).toLowerCase()) {
return false
}
l++
r--
}
}
return true
};
结果:
476/476 cases passed (76 ms)
Your runtime beats 89.25 % of javascript submissions
Your memory usage beats 13.06 % of javascript submissions (42 MB)
时间复杂度: O(n)
查阅他人解法
这里看到一种利用栈的思路,先进后出,推一半入栈然后进行比较。
Ⅰ.利用栈
代码:
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
// 正则去除不满足条件的字符
let str = s.toLowerCase().replace(/[^0-9a-z]/g, '')
let mid = str.length >>> 1
let stack = str.substr(0, mid).split('')
// 起始位置如果字符个数为奇数则跳过中间位
for(let i = str.length % 2 ? mid + 1 : mid; i < str.length; i++) {
const last = stack.pop()
if (last !== str.charAt(i)) {
return false
}
}
return true
};
结果:
476/476 cases passed (84 ms)
Your runtime beats 65.67 % of javascript submissions
Your memory usage beats 71.81 % of javascript submissions (37.4 MB)
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
let hash = {}
for(let i = 0; i < nums.length; i++) {
if (hash[nums[i]]) {
hash[nums[i]] = false
} else if (hash[nums[i]] === undefined) {
hash[nums[i]] = true
}
}
for(let i in hash) {
if(hash[i]) {
return parseInt(i)
}
}
};
结果:
16/16 cases passed (72 ms)
Your runtime beats 68.39 % of javascript submissions
Your memory usage beats 5.49 % of javascript submissions (38.6 MB)
时间复杂度: O(n)
Ⅱ.异或运算
简单列一下几条运算规则,利用这规则,发现很容易作答这道题。
交换律: a^b^c = a^c^b
任何数和 0 异或为本身:a^0 = a
相同的数异或为 0:a^a = 0
代码:
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
let n = 0
for(let i = 0; i < nums.length; i++) {
n ^= nums[i]
}
return n
};
结果:
16/16 cases passed (60 ms)
Your runtime beats 95.77 % of javascript submissions
Your memory usage beats 74.07 % of javascript submissions (35.3 MB)
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
if (head === null || head.next === null) return false
if (head === head.next) return true
let p = head.next
let q = p.next
let x = head
head.next = null
// 相当于每遍历一个链表,就把后面的指向前面一项,这样当循环的时候,会反方向走出环形
while(q !== null) {
p.next = x
x = p
p = q
q = q.next
}
return p === head
};
结果:
17/17 cases passed (72 ms)
Your runtime beats 90.05 % of javascript submissions
Your memory usage beats 35.91 % of javascript submissions (36.8 MB)
背景
本文记录刷题过程中的整个思考过程,以供参考。主要内容涵盖:
目录
Easy
121.买卖股票的最佳时机
题目地址
题目描述
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
示例 2:
题目分析设想
这道题,我的第一反应有点像求最大子序和,只不过这里不是求连续,是求单个,转换为增益的思想来处理。当然也可以使用两次遍历的笨办法来求解。我们分别来验证一下。
编写代码验证
Ⅰ.两次遍历
代码:
结果:
O(n^2)
Ⅱ.增益思想
代码:
结果:
O(n)
查阅他人解法
这里看到两种不同的思考,一种是理解为波峰和波谷,找到波谷后的下一个波峰,判断每个波峰与波谷差值的大小。另外一种是基于状态机的动态规划,也就是说把可能性都前置运算后,再进行比较。
Ⅰ.波峰波谷
代码:
结果:
O(n)
Ⅱ.动态规划
代码:
结果:
O(n)
这个思路还有一系列的优化过程,可以点击这里查看
思考总结
很多问题都可以转换成动态规划的思想来解决,但是我这里还是更推荐使用增益思想,也可以理解为差分数组。但是如果题目允许多次买入卖出,我会更推荐使用动态规划来解决问题。
122.买卖股票的最佳时机Ⅱ
题目地址
题目描述
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
示例 2:
题目分析设想
上面刚刚做了算最大收益的,这题明显是算累计收益的,所以可以按以下几个方向:
编写代码验证
Ⅰ.一次遍历
代码:
结果:
O(n)
Ⅱ.波峰波谷
代码:
结果:
O(n)
Ⅲ.动态规划
代码:
结果:
O(n)
查阅他人解法
这里看到了动态规划的优化版,主要是降低空间复杂度。其他的思路都区别不大。
Ⅰ.动态规划优化版
代码:
结果:
O(n)
还可以进一步进行状态压缩
代码:
结果:
O(n)
思考总结
就这道题而言,我会推荐使用一次遍历的方式,也就是贪心算法,理解起来会十分清晰。当然,动态规划的解决范围更广,基本上可以解决这类型的所有题目。增益也是一个比较常见的手段。总体而言,这两道股票题还比较简单。
125.验证回文串
题目地址
题目描述
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
示例:
题目分析设想
这道题我有两个方向,一是改变原输入串,二是不改变原输入串。
主要作答方法就是反转判断,双指针法以及二分法。
编写代码验证
Ⅰ.反转判断
代码:
结果:
O(1)
Ⅱ.双指针法(预处理字符)
代码:
结果:
O(n)
Ⅲ.单指针法(预处理字符)
代码:
结果:
O(n)
Ⅳ.双指针法
代码:
结果:
O(n)
查阅他人解法
这里看到一种利用栈的思路,先进后出,推一半入栈然后进行比较。
Ⅰ.利用栈
代码:
结果:
O(n)
思考总结
总体而言,判断回文字符或者相关的题目,我更推荐采用双指针法,思路非常清晰。这里头尾递归比较也可以作答,就不在这里列举了。
136.只出现一次的数字
题目地址
题目描述
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
题目分析设想
这题说明了线性时间复杂度,所以最多一次遍历。很容易想到用 Hash 表或者其他方式对各数字出现次数做个统计来求解,但是需要考虑如何不适用额外空间。这里很明显就指向了离散数学中的异或运算。
O(n)
的空间编写代码验证
Ⅰ.Hash 法
代码:
结果:
O(n)
Ⅱ.异或运算
简单列一下几条运算规则,利用这规则,发现很容易作答这道题。
代码:
结果:
O(n)
查阅他人解法
没有发现其他不同方向的解法。
思考总结
这里的话第一想法大多都是借助哈希表来实现,但是由于有补充说明,所以更推荐使用异或算法。纯粹是数学公式的应用场景之一,没有什么太多好总结的地方。
141.环形链表
题目地址
题目描述
给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
进阶:
你能用 O(1)(即,常量)内存解决此问题吗?
题目分析设想
这道题的本质其实就是对象的比较,而对应的相等应当是引用同样的内存,可以想象成数组中找到同样的元素。所以第一个想法就是哈希表,当然也可以使用快慢指针来做处理。由于哈希表需要额外的内存,所以可以做优化,比如直接改变原对象,做特殊标识或者其他方式。
编写代码验证
Ⅰ.哈希表
代码:
结果:
O(n)
Ⅱ.特殊标识法
代码:
结果:
O(n)
Ⅲ.双指针法
代码:
结果:
O(n)
查阅他人解法
这里发现一个有意思的思路,通过链路导致。如果是环,那么倒置后的尾节点等于倒置前的头节点。如果不是环,那么就是正常的倒置不相等。
Ⅰ.倒置法
代码:
结果:
O(n)
思考总结
一般去重或者找到重复项用哈希的方式都能解决,但是在这题里,题目期望空间复杂度是
O(1)
,要么是改变原数据本身,要么是使用双指针法。这里我比较推荐双指针法,当然倒置法也比较巧妙。(完)