替换空格
题目
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy。则经过替换之后的字符串为We%20Are%20Happy。
代码
情况一（只能转换一个空格）
直接用空格将字符串切割成数组，再用20%进行连接。
function replaceSpace(str){return str.split(' ').join('%20')}let str="We Are Happy"console.log(replaceSpace(str));//We%20Are%20Happy
正则解决
function replaceSpace(str)
{
let reg=/\s/g;
let newStr=str.replace(reg,"%20");
return newStr
}
let str="We Are Happy"
console.log(replaceSpace(str));//We%20Are%20Happy
双指针解决（快慢指针）
function replaceSpace(str) {
let intNum = 0, emptyNum = 0;
for (let i = 0; i < str.length; ++i) {
if (str[i] === " ") {
emptyNum++
} else {
intNum++
}
}
let newStrlength = intNum + emptyNum;
let newArr = new Array(newStrlength)
for (let j = 0, i = 0; j < str.length; ++j) {
if (str[j] === ' ') {
newArr[i++] = "%";
newArr[i++] = "2";
newArr[i++] = '0'
} else {
newArr[i++] = str[j]
}
}
return newArr.join('')
}
情况二（一个或多个空格）
正则解决
function replaceSpace(str)
{
let reg=/\s+/g;
let newStr=str.replace(reg,"%20");
return newStr
}
let str="We Are Happy"//每个字符串相隔两个字符
console.log(replaceSpace(str));//We%20Are%20Happy
字符串的排列
题目
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba
思路
给定一个字符串，求该字符串的全排列
function Permutation(str) {
var res = [];//存放结果
if (str.length <= 1) {
return str;
}
var map = {};
for (var i = 0; i < str.length; i++) {
var s = str[i];
if (!map[s]) {
var newStr = str.slice(0, i) + str.slice(i + 1, str.length);
var list = Permutation(newStr);
for (var j = 0; j < list.length; j++) {
res.push(s + list[j]);
}
map[s] = true;
}
}
// console.log(res);
return res;
}
字符串中的第一个唯一字符
题目
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
思路
- 使用map来储存字符和字符出现的次数，若遍历时为出现次数为1，并停止运行
- 使用hash表来储存字符和出现次数，和以上同理
- 用indexOf和lastIndexOf的api来处理（思路有点类似左右指针）
Map
var firstUniqChar = function(s) {
if(s.length===0) return -1
let map=new Map()
for(let i=0;i<s.length;i++){
let count=map.get(s[i])||0;
map.set(s[i],count+1)
}
for(let j=0;j<s.length;j++){
if(map.get(s[j])==1) return j
}
return -1
};
Hash
var firstUniqChar = function(s) {
if(s.length===0) return -1
let hash={}
for(let i=0;i<s.length;i++){
if(!hash[s[i]]){
hash[s[i]]=1
}else{
hash[s[i]]++
}
}
for(let i=0;i<s.length;i++){
if(hash[s[i]]===1) return i
}
return -1
};
JS的骚操作
var firstUniqChar = function(s) {
if(s.length===0) return -1
for(let i=0;i<s.length;i++){
let preIndex=s.indexOf(s[i])
let lastIndex=s.lastIndexOf(s[i])
if(preIndex==lastIndex){
return i
}
}
return -1
};
左旋转字符串
题目
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。
思路
- 使用队列的方法解决
- 直接调用api进行字符串的拼接
队列
if(!s) return ""
let queue=[]
for (const item of s) {
queue.push(item)
}
for(let i=0;i<n;i++){
queue.push(queue.shift())
}
return queue.join("")
字符串拼接
let st=s.split("")
let ds=st.concat(str).join('')
return ds.slice(n,n+s.length)
//return s.substring(n) + s.substring(0,n)
翻转单词顺序列
题目
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”
思路
- 通过revese来直接翻转数组
- 双指针
JS骚操作
let reg=/\s+/g;
let queue=s.split(" ").reverse()
return queue.join(" ").trim('').replace(reg," ")
左右指针
**
var reverseWords = function(s) {
if(!s) return ""
let res = '';
let n = s.length;
if(n===0) return res;
let right = n - 1;
while(right >=0) {
// 从后往前寻找第一字符
while(right >=0 && s[right] === ' ') right--;
if(right < 0) break;
// 从后往前寻找第一字符
let left = right;
while(left >=0 && s[left] !== ' ') left--;
// 将结果添加到单词
console.log(left,right);
res += s.substr(left+1,right-left);
res += " ";
right = left;
}
if(res) res = res.trim();
return res;
};
扑克牌中的顺子
题目
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
限制：
数组长度为 5
数组的数取值为 [0, 13] .
思路
- 0代表万能牌，所以需要先把数组进行升序排序，然后计算出数值为零的牌的张数a，然后是对剩余的牌进行判断，如果后一张牌比前一张大且大于1，则计算两者间的差值-1保存为一个值b，如果相等则不满足，最后对两个保存的数据进行比较，如果a超过b，则满足
var isStraight = function(nums) {
let a=0,b=0;
nums.sort((a,b)=>a-b)
let newNums=nums.filter((item)=>item!=0)
a=nums.length-newNums.length
for(let i=0;i<newNums.length;i++){
if(newNums[i+1]-newNums[i]>1){
b+=newNums[i+1]-newNums[i]-1
}else if(newNums[i+1]===newNums[i]){
return false
}
}
return a>=b?true:false
};
正则表达式匹配
题目
请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。
思路
- 回溯
- “.”代表万能字符，”“代表前一个字符的重复次数（0-无穷，但前面必须有字符），故此我们可以分为第二个字符为”“或不是的两种情况（然后进行回溯，一个个字符进行判断），起初我想的是，一个，多个，0个情况进行匹配，但时间复杂度太高，到了O（n2）
原因是我对一个和多个字符的匹配进行了重复判断，只需判断多个即可（一个包含在里面），故此我的优化是（当然模仿了下题解）if (!p) return !s; if (p[1] === '*') { if (s && (s[0] == p[0] || p[0] == '.')) { return isMatch(s.substr(1), p) || isMatch(s.substr(1), p.substr(2)) || isMatch(s, p.substr(2)) } else { return isMatch(s, p.substr(2)) } } else { return s && (s[0] == p[0] || p[0] == '.') && (isMatch(s.substr(1), p.substr(1))) }
这样时间复杂度就到了O（N）var isMatch = function (s, p) { if(!p) return !s; if(p[1] == '*'){ return isMatch(s, p.substr(2)) || (s && (s[0] == p[0] || p[0] == '.')) && isMatch(s.substr(1), p); } else { return s && (s[0] == p[0] || p[0] == '.') && (isMatch(s.substr(1), p.substr(1))); } };
把字符串转化成整数
题目
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
说明：
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
思路
- 会用一些API就行
var strToInt = function(str) { if(!str) return 0; let min=Math.pow(-2,31) let max=Math.pow(2,31)-1 let num=parseInt(str) if(isNaN(num)) return 0; if(num<min){ return min }else if(num>max){ return max } return num };
表示数值的字符串
题目
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”、”5e2”、”-123”、”3.1416”、”-1E-16”、”0123”都表示数值，但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。
思路
var isNumber = function(s) {
return s.trim()?!isNaN(s):false;
};
若有收获，就点个赞吧
0 人点赞
