字符串算法题

操作字符串

• charAt() 返回索引位置字符
• charCodeAt()返回索引位置字符 UTF16 代码
• concat() 拼接
• indexOf(), lastIndexOf() 返回索引
• includes() 返回 Boolean
• match() 匹配正则
• replace() 替换
• split() 分割字符串
• slice() 截取返回新字符串，以索引
• substring() //截取返回新字符串，以长度
• trim() //删除空格
• toLowerCase(), toUpperCase()

最长公公前缀

// 输入: ["flower","flow","flight"]
// 输出: "fl"

var longestCommonPrefix = function (strs) {
	if (!strs.length || strs.length === 0) return "";
	let prefix = strs[0]; //  第一个字符串作为参考
	for (let i = 1; i < strs.length; i++) {
		// 后续和他比较
		let j = 0; // 从0索引开始，判断公共部分则j++
		for (; j < prefix.length && j < strs[i].length; j++) {
			if (prefix[j] !== strs[i][j]) break;
		}
		prefix = prefix.substring(0, j); // 和strs[i]比较完后重合的部分
	}
	return prefix;
};

连字符转为驼峰

const toCamelCase = (str: string) => str.replace(/-\w/g, ($) => $.slice(1).toUpperCase());

将字符串改为首字母大写

// -i-hate -_you_
// \b匹配单词边界
// 加上判断是否会有下划线
// \w 字母、数字、下划线

const firstUpper = (str: string) => str.replace(/\b_?\w/g, ($) => $.toUpperCase());

反转句子

//  正则
function reverseWords(str) {
	return str.trim().replace(/\s+/g, " ").split(" ").reverse().join(" ");
	// \s \s是指空白,包括空格、换行、tab缩进等所有的空白
	// 去除单词之间多余的空白
}

//
function reverseWords(str) {
	// 也可以使用string+ ' '
	// 这里使用数组
	let arr = [];
	str = srt.trim();
	let left = 0;
	let right = str.length - 1;
	let word = "";
	// 去除头尾多余空格
	while (left <= right) {
		let char = str.charAt(left);
		if (char === " " && word) {
			arr.unshift(word);
			word = "";
		} else if (char !== " ") {
			word += char;
		}
		left++;
	}
	arr.unshift(word);
	// 上面单词的添加是基于该位置字符是否为空
	// 则最后一个单词的末尾非空将不会被添加
	// 所以最后加上arr.unshift(word)
	return arr.join(" ");
}

检查回文

function reverseCheck(str) {
	let s = str.toLowerCase().replace(/[\W_]/g, "");
	// 格式掉不是字母的别的玩意
	// | `\W`   | 匹配任意不是字母，数字，下划线 |
	// `[]` 字符串用中括号括起来，表示匹配其中的任一字符
	return s === s.split("").reverse().join("");

	// 指针
	let l = 0;
	let r = str.length - 1;
	while (l < r) {
		if (str[l++] === str[r--]) {
			continue;
		} else {
			return false;
		}
	}
	return true;
}

最长不重复子串长度

// 滑动窗口
function longest1(str) {
	const window = [];
	let maxLen = 0;
	for (let + = 0; i < str.length; i++) {
		const repeatIndex = window.indexOf(str[i]);
		if (repeatIndex !== -1) {
			window.splice(0, repeatIndex + 1);
			// 有重复值时缩小窗口
		}
		window.push(str[i]);
		// 无重复扩大窗口
		maxLen = Math.max(maxLen, window.length);
	}
	return maxLen;
}

function longest2(str) {
	let maxLen = 0;
	for (let i = 0, j = 0; j < str.length; j++) {
		const _index = str.substring(i, j).indexOf(str[j]);
		if (_index !== -1) {
			// _index为重复项位置
			i += _index + 1;
		}
		maxLen = Math.max(maxLen, j - i + 1);
	}
	return maxLen;
}
// map + 双指针
function longest3(str) {
	const map = new Map();
	let maxLen = 0;
	let i = 0;
	// 设 i 位置右侧字符无重复
	for (let j = 0; j < str.length; j++) {
		if (map.has(str[j])) {
			i = Math.max(map.get(str[j]) + 1, i);
			// Math.max:检测到重复，更新i的位置，注意不一定是str[j]+1，str[j]+1不一定比上一个重复元素的查重位置更靠后
			// 3 => 0
			// 2 => 1
			// 1 => 2
			// 1 => has , i = 3 // 检测到重复移动左指针
			// 3 => has , i = Math.max((0+1),3) = 3
			// 2 => has , i = Math.max(3,1) = 3
			// [3,2,1,1,3,2] 3查重的位置明显小于1查重
		}
		map.set(str[j], j);
		maxLen = Math.max(j - i + 1, maxLen);
	}
}

计算二进制数中 1 的个数

// n 为32位二进制数
function hammingWeight1(n) {
	const numStr = n.toString(2);
	// 转为二进制后记数
	let showTimes = 0;
	for (let i = 0; i < numStr.length; i++) {
		if (numStr[i] === "1") {
			showTimes++;
		}
	}
	return showTimes;
}

// 位运算
// >>> 无符号向右移
function hammingWeight2(n) {
	let showTimes = 0;
	while (n != 0) {
		showTimes += n & 1;
		// &运算，1的二进制为1
		// 则左右都为1时输出1
		n >>>= 1;
	}
	return showTimes;
}

// 整体n &
function hammingWeight3(n) {
	let showTimes = 0;
	while (n != 0) {
		showTimes++;
		n &= n - 1;
		// 二进制 - 中
		// n-1 相当 于n把最右边的1变为0,其后面的0变为1
		// n与n-1进行与运算,1&1=1,即只改变了最右边第一个1
		// n       => 0001100
		// n-1     => 0001011
		// n&(n-1) => 0001000
		// n-1     => 0000111
		// n&(n-1) => 0000000
		// 跳出循环
	}
	return showTimes;
}

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）

function numberCheck(s) {
	if (/^\s$/.test(s)) return false;
	return Number(s).toString() !== "NaN";
}

千分位加逗号

function numFormat(num) {
	var res = num.toString().replace(/\d+/, function (n) {
		// 整数部分
		return n.replace(/\d(?=(\d{3})+$)/g, ($1) => $1 + ",");
	});
	return res;
}

// or
Number.toLocaleString();

解析 URL 参数

function parseQueryString(url) {
	const rule = /([^?=&]+)=([^&#]*)/g;
	return url.match.reduce((a, b) => {
		const [key, value] = b.split("=");
		k = decodeURIComponent(key);
		v = decodeURIComponent(value);
		a[k] = a[k] ? [...a[k], value] : value;
		return a;
	}, {});
}

字符串相加/大数相加

function stringAdd(num1, num2) {
	let l1 = num1.length;
	let l2 = num2.length;
	let res = "";
	// 进位
	let carry = 0;
	while (l1 || l2) {
		if (l1) carry += +num1[--l1];
		if (l2) carry += +num2[--l2];
		// 当前位
		res = (carry % 10) + res;
		// 计算出超过十的进位
		carry = carry >= 10 ? 1 : 0;
	}
	if (carry) res = carry + res;
	return res;
}

字符串相乘/大数相乘

function stringMulti(x, y) {
	if (x === "0" || y === "0") return "0";
	if (x === "1") return y;
	if (y === "1") return x;

	const len1 = x.length;
	const len2 = y.length;
	const pos = new Array(len1 + len2).fill(0);

	let num1, num2;

	for (let i = len1 - 1; i >= 0; i--) {
		num1 = x[i];
		for (let j = len2 - 1; j >= 0; j--) {
			num2 = y[j];

			multi = num1 * num2;
			console.log("multi" + multi);
			// 参考乘法草稿
			const cur = multi + pos[i + j + 1];
			console.log("cur" + cur);
			// 进位
			pos[i + j] += (cur / 10) | 0;
			// 余数
			pos[i + j + 1] = cur % 10;
		}
	}

	let res = pos.join("");
	while (res[0] === "0") {
		res = res.substring(1);
	}
	return res;
}

实现一个trim函数

// trim 返回去除了首尾空白的字符串
String.prototype._trim = function () {
	//1.regexp
	return this.replace(/^\s+/, "").replace(/\s+$/, "");
};
String.prototype._trim = function () {
	const str = this;
	let res = "";
	let trimFlag = true;
	let tailIndex; // 找出最后一个不是空格的索引
	for (let j = str.length - 1; j > 0; j--) {
		if (str[j] !== " ") {
			tailIndex = j;
			break;
		}
	}

	for (let i = 0; i < str.length; i++) {
		// 越过末位后又开始忽略空格
		if (i >= tailIndex) {
			trimFlag = true;
		}

		if (str[i] === " " && trimFlag) {
			continue;
		} else {
			trimFlag = false;
			res += str[i];
		}
	}
	return res;
};

实现前缀树 prefixTree

function PrefixTree() {
	this.tree = {};
}
PrefixTree.prototype.insert = function (word) {
	// 依次将单词的每个字母向tree对象中递归添加属性
	// msy= >
	// {m:{s:{y:{isEnd:true}}}}
	let node = this.tree;
	for (let n of word) {
		if (!node[n]) node[n] = {};
		node = node[n];
	}
	node.isEnd = true;
};
PrefixTree.prototype.loop = function (word) {
	let node = this.tree;
	for (let n of word) {
		if (!node[n]) return false;
		node = node[n];
	}
	return node;
};
PrefixTree.prototype.search = function (word) {
	const ret = this.loop(word);
	return ret !== undefined && ret.isEnd === true;
};
PrefixTree.prototype.startWith = function (prefix) {
	return this.loop(prefix);
};

自定义字符串排序

将 s 字符串中的字符按照 order 字符串中的前后顺序进行排序

输入: order = "cba", s = "abcd"
输出: "cbad"
解释:
“a”、“b”、“c”是按顺序出现的，所以“a”、“b”、“c”的顺序应该是“c”、“b”、“a”。
因为“d”不是按顺序出现的，所以它可以在返回的字符串中的任何位置。“dcba”、“cdba”、“cbda”也是有效的输出。

var customSort = function (order, s) {
	const map = new Map();
	for (const str of order) {
		// Map是有序的，保证遍历map的顺序就是order的顺序,
		map.set(str, 0); // 首先假设这个位置的str出现了0次
	}

	for (const str of s) {
		map.set(str, map.get(str) ? map.get(str) + 1 : 1); // 遍历s，查找是否存在在map上,存储这个字符出现的次数
	}
	res = "";
	for (const [str, time] of map) {
		// 按照顺序遍历map给res添加字符
		res += str.repeat(time);
	}
	return res;
};

版本号排序

// 0.0.1 , 0.2.1
const versions = ["9.0.1", "0.1.2", "0.3.1", "1.0.0"];

function sort(arr) {
	return arr.sort((a, b) => {
		let Arr = a.split(".");
		let Brr = b.split(".");
		while (Arr.length || Brr.length) {
			let A = Arr.shift() || 0;
			let B = Brr.shift() || 0;
			if (A - B !== 0) {
				return A - B;
			}
		}
	});
}

字母的所有组合

const anagrams = str => {
  if(str.length===2) return [str , str[1] + str[0]]
  // 手写长度为2时候的排列

  // 这里使用reduce的第三个参数index，正在处理的元素
  // 如果提供了initialValue，则起始索引号为0，否则从索引1起始。
  return str.split('').reduce((acc,cur,index)=>{
    let other = str.slice(0,index)+str.slice(index+1)
    // other为除了当前处理元素外的字母
    // a bcd =>
    // b cd => bcd bdc
    // c bd => cbd cdb
    // d bc => dbc dcb
    // b...
    return acc.push(anagrams(other).map(char=>cur+char))
    // 递归至两位数数组颠倒排序,并将所有可能与当前处理元素组合
  },[])
  // 指定initialValue
}
anagrams('abcd') => [
  'abcd', 'abdc', 'acbd',
  'acdb', 'adbc', 'adcb',
  'bacd', 'badc', 'bcad',
  'bcda', 'bdac', 'bdca',
  'cabd', 'cadb', 'cbad',
  'cbda', 'cdab', 'cdba',
  'dabc', 'dacb', 'dbac',
  'dbca', 'dcab', 'dcba'
]

字符串按字母排序

const sortCharactersInString = (str) =>
	str
		.split("")
		.sort((a, b) => a.localeCompare(b))
		.join("");
// sortCharactersInString('cabbage') -> 'aabbceg'