1.找出數(shù)組中重復(fù)次數(shù)最多的元素
2.返回字符串第一個重復(fù)字符
3.快排 O(nlogN)
4.二分查找 O(nlogN)
5.Fibonacci
6.解析URL參數(shù)
7.深度優(yōu)先遍歷O(N)
8.廣度優(yōu)先遍歷O(N)
9.嵌套數(shù)組展開
1.找出數(shù)組中重復(fù)次數(shù)最多的元素
var arr = [1,2,2,1,1]
function highFrequency(arr){
var most = 0, map = {}, res = -1;
if(!arr.length){
return
}else if(arr.length == 1){
return arr[0];
}else{
for(let i = 0 ; i<arr.length ; i++){
map[arr[i]] ? map[arr[i]]++ : map[arr[i]] = 1;
if(map[arr[i]] > most){
most = map[arr[i]];
res = arr[i];
}
}
}
console.log(res);
}
highFrequency(arr);
2.返回字符串第一個重復(fù)字符
function getFirstDouble(str){
var anotherArr = [] , res = null;
for(let i = 0; i<str.length ; i++){
if(anotherArr.includes(str[i]) ){
res = str[i] ;
break;
}else{
anotherArr.push(str[i]);
}
}
console.log(res)
}
3.快排 O(nlogN)
至于為什么沒有用阮一峰老師的方法听想，那個方法被眾人所詬病的原因一是沒有使用最方便的下標取值绿渣，二是左右數(shù)組新開辟內(nèi)存空間矗愧，多余杯拐。
var arr=[5,7,2,9,3,8,4,7,1];
// 每次選擇最左邊的數(shù)作為基數(shù)
function quickSort(arr){
if (arr.length<2) { return arr; }
// 定義左指針
var left=0;
// 定義右指針
var right=arr.length-1;
//開啟每一輪的排序
while(left<right){
// 尋找右邊比arr[0]小的數(shù)的下標
while(arr[right]>=arr[0] && left<right){
right=right-1;
}
// 尋找左邊比arr[0]大的數(shù)的下標
while(arr[left]<=arr[0] && left<right){
left++;
}
//當左邊指針與右邊指針相遇后幔戏，交換arr[0]與當前兩個指針所在的元素
if (right==left) {
let mid=arr[right];
arr[right]=arr[0];
arr[0]=mid;
break;
}
// 當左指針小于右指針的位置缩挑，交換兩個指針當前位置的元素
let tem=arr[right];
arr[right]=arr[left];
arr[left]=tem;
}
//遞歸實現(xiàn)
return quickSort(arr.slice(0,left)).concat(arr.slice(left,right+1)).concat(quickSort(arr.slice(right+1)));
}
//對數(shù)組進行排序
console.log(quickSort(arr));
4.二分查找 O(nlogN)
function binarySearch(arr,key){
var low = 0, high = arr.length - 1;
while (low <= high){
let mid = parseInt((low + high)/2);
if(arr[mid] == key){
return mid;
}else if(key > arr[mid]){
low = mid + 1;
}else if(key < arr[mid]){
high = mid - 1;
}
}
return -1
}
var arr = [1,2,3,4,5,6,7,8,9,10];
console.log(binarySearch(arr,3));
5.Fibonacci
function fibonacci(n , ac1 = 1 , ac2 = 1){
if(n <= 1){
return ac2;
}
return fibonacci(n-1 , ac2 , ac1+ac2);
}
console.log(fibonacci(5))
6.解析URL參數(shù)
function getQueryStringArgs(){
//取得查詢字符串并去掉開頭問號
var qs = (location.search.length > 0 ? location.search.substring(1) : "");
//保存數(shù)據(jù)的對象
var args = {};
//取得每一項
var items = qs.length ? qs.split("&") : [];
var item = null , name = null ,value = null;
//在for循環(huán)中使用
var i = 0 , len = items.length;
//將每一項添加到args對象中
for(i = 0 ; i < len ; i++){
item = items[i].split('=');
name = item.decodeURIComponent(item[0]);
value = item.decodeURIComponent(item[1]);
if(name.length){
args[name] = value;
}
}
return args;
}
7.深度優(yōu)先遍歷O(N)
// 遞歸方式
let deepTraversall = (node,nodeList=[]) => {
if(node !=null){
nodeList.push(node);
let children = node.children;
for(let i=0 ; i<children.length ; i++){
deepTraversall(children[i],nodeList);
}
}
return nodeList;
}
// 非遞歸
function deepTraversall(node){
let nodes = [];
if(node != null){
let stack = [];
stack.push(node);
while(stack.length){
let item = stack.shift();
nodes.push(item);
let children = item.children;
for(let i=0 ; i<children.length ; i++){
stack.push(children[i]);
}
}
}
return nodes;
}
8.廣度優(yōu)先遍歷O(N)
// 非遞歸
function widthTraversal(node){
var nodes = [];
if(node){
var queue = [];
queue.unshift(node);
while(queue.length){
var item = queue.shift();
nodes.push(item);
var children = item.children;
for(let i=0 ; i<children.length ; i++){
queue.push(children[i]);
}
}
}
}
9.嵌套數(shù)組展開
// 遞歸
function flattenMd(arr) {
var result = [];
for(var i = 0; i < arr.length; i++){
if(arr[i] instanceof Array) {
result = result.concat(flattenMd(arr[i]));
}
else {
result.push(arr[i]);
}
}
return result;
}
var arr=[1, [2, 3, [4, 5], 6], 7, 8]
console.log(flattenMd(arr));
// 非遞歸
function flattenDeep(arr){
const res = [];
const stack = [...arr];
while(stack.length){
let item = stack.shift();
Array.isArray(item)?stack.unshift(...item):res.push(item);
}
return res;
}
var arr = [1,[2,[3,[[5]]],[4]]];
console.log(flattenDeep(arr))
