算法简单题,吾辈重拳出击 - 判断子序列
2023-06-13 09:11:18 时间
题目:
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。 进阶: 如果有大量输入的 S,称作 S1, S2, ... , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?
示例 1:
输入:s = "abc", t = "ahbgdc"
输出:true
示例 2:
输入:s = "axc", t = "ahbgdc"
输出:false
解:
第一反应
把字符串变成数组,循环 s 数组,每一项去 t 数组里面找(find),如果不存在的,就 return false;
var isSubsequence = function(s, t) {
sArr = s.split("")
tArr = t.split("")
let res = true
tArr.map(i=>{
if(!sArr.find(s=>s===i)){res = false}
})
return res
};
解答错误,敲!原来是要按顺序的,这下就麻烦一点了。
第二反应
看一下解析,找一下关键词,噢,双指针,那懂了:
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isSubsequence = function(s, t) {
if(s==="") return true
let p0 = 0
let p1 = 0
while(p1<t.length){
if(s[p0]===t[p1]){
p0++
}
if(p0===s.length){
return true
}
p1++
}
return false
};
思路:设两个指针,初始位置都在字符串的第一位。
当两个指针所指数字相等,说明子字符在父字符中找到了对应的字符,并且是依次找的。此时,父子字符的指针都加一,向右移动。
如果不相等,仅移动父字符串的指针向右加一。
当父字符的指针指向了最后一位,而子字符的指针没有指向最后一位,说明没找到,返回 false;如果在这个过程中子字符就已经遍历完了,说明找到了,返回 true。
双指针!太强了!
(动图来自:Krahets)
第三反应
如果非要用数组呢?
var isSubsequence = function(s, t) {
if(s.length == 0) return true;
let sStack = s.split('');
let tStack = t.split('');
while(tStack.length>0){
let tItem = tStack.pop();
if(tItem == sStack[sStack.length-1]){
sStack.pop();
if(sStack.length == 0) return true;
}
}
return false;
};
思路和双指针相似,但具体操作有差异,要用到 pop() 剔除掉找到了的字符。
第四反应
复习一下 while 和 for 的区别:
- for循环是在序列穷尽时停止,while循环是在条件不成立时停止。
- for循环语句申明循环变量,while循环语句判断循环条件。
- 需要在读文本文件中有很多逻辑判断时,采用while比较好。 没有复杂的逻辑判断时用for比较好。
相关文章
- 日拱算法:双指针解“判断子序列”,除夕快乐~
- Python用KShape对时间序列进行聚类和肘方法确定最优聚类数k可视化|附代码数据
- BAT面试算法进阶- 最长的斐波那契子序列的长度(暴力法)
- Python电力负荷:ARIMA、LSTM神经网络时间序列预测分析
- 算法-栈的压入、弹出序列详解编程语言
- 算法-二叉搜索树的后序遍历序列详解编程语言
- 最长回文子序列算法详解编程语言
- Oracle序列设置缓存值优化性能(oracle序列缓存)
- Oracle导出序列的步骤分析(oracle导出序列)
- Oracle序列助您的数据更具唯一性(oracle关于序列说法)
- 化初探Oracle VM中的序列化功能(Oracle vm序列)
- Oracle Job序列助力企业数据管理(oracle job序列)
- PHP求最大子序列和的算法实现