算法题

1. 实现hello world变成 dlrow olleh

let str  = 'hello world'
let newStr = ''
newStr = str.split('').reverse().join('')           // 第一种方法
for(var i=str.length-1;i>= 0;i--){                   // 第二种方法
    newStr += str[i]
}
console.log('newStr', newStr)

2. 统计一个字符串中字符出现次数最多的字符并统计其次数

let str = "abcaaanmertaabsc"
let max = 0, s =''
let obj = {}
for(var i=0;i<str.length;i++){
    if(!obj[str[i]]){
        obj[str[i]] = 1
    }else{
        obj[str[i]] = obj[str[i]] + 1
    }
}
console.log(obj)

for(var key in obj){
    if(obj[key] > max){
        max = obj[key]
        s = key
    }
}
console.log('出现次数最多的字符是'+ s + '一共出现了'+ max + '次')

3. 实现对象的深拷贝

function deepCopy(target, source){
    if(!source || typeof source != 'object'){
        return 
    }
    if(!target || typeof target != 'object'){
        return
    }
    for(var key in source){
        if(source.hasOwnProperty(key)){
            // 如果目标数据是一个对象，那么使用递归再走一遍
            if(source[key] && typeof source[key] == 'object'){
                target[key] = Array.isArray(source[key]) ? [] : {}
                deepCopy(target[key], source[key])
            }else{
                target[key] = source[key]
            }
        }
    }
    return target
}

4. 实现二分法查找一个数组

二分法查找时候前提查找的是一个有序数组，如果数组是无序的，那么先做排序
方法1: 使用while循环
let arr = [1, 3, 5, 10, 30]
let key = 10
function findIndex(arr, key){
    let low = 0
    let high = arr.length -1
    while(low <= high){
        let mid = Math.floor((low + high)/2)
        if(key == arr[mid]){
            return mid
        }
        if(arr[mid] > key){
            high = mid - 1
        }else{
            low = mid + 1
        }
    }
    return -1
}

方法2: 使用递归
let low = 0
let high = arr.length -1
function findIndex(arr,key,low,high){
    var mid = Math.floor((low + high)/2)
    if(low > high){
        return -1
    }
    if(arr[mid] > key){
        findIndex(arr,key,low,mid -1)
    }else if(arr[mid] < key){
        findIndex(arr,key,mid + 1,high)
    }else{
        console.log('找到了 ' + key + ' ,下标为' + mid);
        return mid
    }
}
findIndex(arr,key,low,high)

5. 冒泡排序

let arr = [1, 3, 4, 7, 3, 5, 9, 2]
for(var i = 0;i<arr.length;i++){
    for(var j=0;j<arr.length-1-i;j++){
        if(arr[j] > arr [j+1]){
            var temp = arr[j]
            arr[j] = arr[j+1]
            arr[j+1] = temp
        }
    }
}
console.log(arr)

6. 查找斐波那契数列的第n项的值

// 斐波那契数列： [1,1,2,3,5,8,13,21,34,55,89....]
// 1，使用递归
function findFeibo(n){
    if(n == 1 || n == 2){
        return 1
    }else{
        return findFeibo(n-1) + findFeibo(n-2)
    }
}

// 2，循环
function findFeibo(n){
    var res1 = 1;
    var res2 = 1;
    for(var i = 2;i < n;i++){
        [res1, res2] = [res2, res1 + res2]
    }
    return res2;
}

let res = findFeibo(8)
console.log(res)

7、 数组扁平化处理(多维数组转化成一维数组)

let arr = [1, [2], [3, 4], 5] 
1. arr.toString().split(',')
1.1 (arr + '').split(',')
2. arr.join().split(',')
// 上述思路都是讲数组转化成字符串  '1,2,3,4,5'， 然后处理
3. 递归遍历
const arr1 = []
function formatArray(arr) {
    for(var i = 0; i< arr.length;i++){
        if(Array.isArray(arr[i])){
            formatArray(arr[i])
        }else{
            arr1.push(arr[i])
        }
    }
}

8、 数组去重

1、 let arr = [4, 2, 2, 3, 4, 4, 6]
    let array = [];
    for (let i = 0; i < arr.length; i++) {
        if (array.indexOf(arr[i]) === -1) {
            array.push(arr[i])
        }
    }

2、 let arr = [1, 2, 3, 3, 4, 4, 6]
    let array = [...new Set(arr)]