4.队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列的数据结构在JavaScript中可以表示为：
//队列的构造函数
function Queue() {
this.items = [];
this.length = this.itmes.length;
this.front = null;
}
//向队列尾插入一个元素的方法enqueue
Queue.prototype.enqueue = function (ele) {
this.items.push(ele);
this.front = this.items[0];
}
//向队列头删除一个元素的方法dequeue
Queue.prototype.dequeue = function (ele) {
this.items.shift(ele);
this.front = this.itmes.length ? this.itmes[0] : null;
}JavaScript中没有内置的队列结构，一般用Array来实现，Array的shift和push操作能很好的完成队列的出队和入队操作。length和isEmpty等根据Array的length来判断即可实现。队列在leetcode的联系题也基本是用array来实现队列，不再展开。
5.字符串
字符串遍历时可以自前向后，也可以自后向前。利用这一点可以轻松解决反转字符串和验证回文字符串。再加上字符串和数字类型转换的知识，即可解决整数反转和字符串转换整数。
//给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
/**
* @param {string} s
* @return {number}
*/
var firstUniqChar = function(s) {
for(let i=0;i<s.length;i++){
//若字符串自前向后遍历得到的索引与自后向前遍历得到的索引相同，则字符唯一
if(s.indexOf(s[i])==s.lastIndexOf(s[i])){
return i;
}
}
return -1;
};
(2).有效的字母异位词
//给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isAnagram = function (s, t) {
function sortString(str) {
let arr = [];
//for-of循环可以遍历unicode大于0XFFFFFF的情况
for (let i of str) {
arr.push(i);
}
//利用数组的排序方法，优于冒泡排序
arr.sort();
//将数组转换为字符串方便判断相等，Array类型不能直接判断相等
return arr.join("");
}
return sortString(s)== sortString(t);
}如果不对字符串进行排序的话，也可以选择利用嵌套循环，两个字符串中的字符相等时，将字符串中的字符删除，这样可以避免字母重复对判断相等造成的影响。
(3).实现 strStr()
//给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle
//字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1
var strStr = function (haystack, needle) {
let len = needle.length;
if(len<=0) return 0;
for(let i=0;i<haystack.length-len;i++){
//将needle看作一个整体，haystack截取相同长度字符串，判断相等
let s = haystack.slice(i,i+len);
if(s===needle) return i;
}
return -1;
}也可以利用一个while循环
var strStr = function(haystack, needle) {
if(needle ==="") return 0;
let i=0;
let j=0;
while(i<haystack.length&&j<needle.length){
if(haystack[i] === needle[j]){
i++;
j++;
}else{
i = i-j+1;
j = 0;
}
}
if(j==needle.length) return i-j;
return -1;
};(4).外观数列
//「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
/**
* @param {number} n
* @return {string}
*/
var countAndSay = function (n) {
if (n == 1) {
return "1";
} else {
return countNum(countAndSay(n - 1));
}
function countNum(str) {
str = str + "/";
//num用来记录数字
let num = [];
//count用来记录数字出现的次数
let count = [];
let temp = 1;
let result = "";
for (let i = 0; i < str.length - 1; i++) {
if (str[i] !== str[i + 1]) {
num.push(str[i]);
count.push(temp);
temp = 1;
} else {
temp++;
}
}
for (let j = 0; j < num.length; j++) {
result += count[j] + num[j];
}
return result;
}
};
(5).最长公共前缀
//编写一个函数来查找字符串数组中的最长公共前缀。
//如果不存在公共前缀，返回空字符串 ""。
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function (strs) {
if(strs.length==0) return "";
//以第一个字符串的长度作为公共前缀
let size = strs[0].length;
let pub = "";
for (let i = 0; i < size; i++) {
pub += strs[0][i];
for (let j = 1; j < strs.length; j++) {
//若存在字符串为空，直接返回空字符串
if (strs[j] === "") return "";
//若存在字符串长度小于第一个字符串长度，改变size,减少循环次数
if (strs[j].length < size) size = strs[j].length;
if (strs[j][i] !== strs[0][i]) {
pub = pub.slice(0, pub.length - 1);
return pub;
}
}
}
return pub;
};6.数组
利用数组的splice方法即可轻松解决从排序数组中删除重复项、旋转数组、移动零问题。数组先排序再遍历即可解决存在重复、只出现一次的数字问题。双层的遍历循环即可解决两个数组的交集 II、两数之和问题。
使用线性时间复杂度来解决只出现一次的数字可以用异或操作解决，相同的数字异或结果为0，0和任意数字异或的结果为数字本身。
(1).买卖股票的最佳时机 II
//给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
//设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易,多次买卖一支股票。
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
let result = 0;
if (prices.length <= 1) return result;
for (let i = 0; i <= prices.length - 2; i++) {
if (prices[i + 1] - prices[i] > 0) {
result = result + prices[i + 1] - prices[i];
}
}
return result;
};只要后一天的价格大于前一天就进行一次交易，从数组[1,2,3,4,5]得到的结果可以知道，不论是(2-1)+(3-2)+(4-3)+(5-4)还是(5-1)得到结果并没有不同。
(2).有效的数独
//判断一个 9x9 的数独是否有效。
/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function (board) {
let valid = true;
//数组先排序，再判断是否存在重复
function exist(arr) {
let tempArr = [];
for (let i = 0; i < arr.length; i++) {
if (Number(arr[i])) {
tempArr.push(Number(arr[i]));
}
}
tempArr.sort();
for (let w = 0; w < tempArr.length - 1; w++) {
if (tempArr[w] == tempArr[w + 1]) {
return false;
}
}
return true;;
}
for (let j = 0; j < 9; j++) {
//数独的每一行是否有效
valid = valid && exist(board[j]);
let a = [];
//数独的每一列是否有效
for (let k = 0; k < 9; k++) {
a.push(board[k][j]);
}
valid = valid && exist(a);
}
//数独的每个小九宫格是否有效
for (let x = 0; x < 3; x++) {
let b = [];
let c = [];
let d = [];
for (let y = 3 * x; y < 3 * x + 3; y++) {
for (let z = 0; z < 3; z++) {
b.push(board[y][z]);
c.push(board[y][z + 3]);
d.push(board[y][z + 6]);
}
}
valid = valid && exist(b);
valid = valid && exist(c);
valid = valid && exist(d);
}
return valid;
};
(3).旋转图像
//给定一个 n × n 的二维矩阵表示一个图像。
//将图像顺时针旋转 90 度。
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var rotate = function (matrix) {
let len = matrix.length - 1;
//i,j为第一次交换的起始位置，x,y为要旋转的元素的下标
function swap(i, j, temp, x, y) {
//如果旋转回起始位置，则跳出循环
if (x == i && y == j) {
return;
} else {
// 矩阵A中位置[i,j]处的数据，旋转后应该处于[j, n-i-1],构成一个循环
let a = y < 0 ? j : y;
let b = x < 0 ? len - i : len - x;
let t = matrix[a][b];
matrix[a][b] = temp;
swap(i, j, t, a, b);
}
}
for (let i = 0; i < len; i++) {
for (let j = i; j < len - i; j++) {
swap(i, j, matrix[i][j], -1, -1);
}
}
};首先要清楚矩阵转换时的关系，是将[i][j]位置的元素旋转至[j][n-i-1].以上这样的解法时间复杂度为O(n3)。在网上看到将矩阵转换为json深拷贝一份数组再移动位置的解法，非常巧妙，通过O(n2)时间复杂度即可解决。
var rotate = function(matrix) {
let n = matrix.length
let mm = JSON.parse(JSON.stringify(matrix))
//矩阵顺指针旋转
for(let i = 0; i < n; i++) {
for(let j = 0; j < n; j++) {
matrix[i][j] = mm[n-1-j][i]
}
}
return matrix
};