算法题

作者: 林思念 | 来源:发表于2021-06-25 10:47 被阅读0次

Android面经| 算法题解
面试题高频算法题整理
回溯,贪心,动态规划
算法题
算法题
算法题
算法题
算法题
算法题
算法题

1、二分查找法

console.log(search(0, array.length, 5))
function search(begin, end, n){
    if(begin > end){
        return -1
    }
    let mid = (begin + end) >> 1
    if(array[mid] > n){
        return search(begin, mid, n)
    }else if(array[mid] < n){
        return search(mid, end, n)
    }else{
        return mid
    }
    return -1
}

2、上楼梯（步数1或2、步数1～n）、阶乘、斐波那契、机器人走方格（有无障碍物）

f(x, y) = f(x, y-1) + f(x-1, y)    (机器人走方格)   （有障碍物的情况，位置直接赋值为0）
f(n) = n * f(n-1)    (阶乘)
f(n) = f(n-1) + f(n-2)   （步数为1或2）
f(n) = Math.pow(2, n-1)  （步数为1～n）

3、数组最长递增序列长度或者值为多少（双指针法）

let array = [1,9,2,5,7,3,4,6,8,0]
console.log(maxLength(array))
function maxLength(array){
    let left = 0
    let right = 1
    let max = 0
    while(right <= array.length -1){
        while(array[right] > array[right - 1]){
            right++
        }
        let len = right - left
        if(max < len){
            max = len
        }
        left = right
        right++
    }
    return max
}

4、求a的n次幂

console.log(pow(10,6))
function pow(a, n){
    if(n == 0){
        return 1
    }
    let res = a
    let ex = 1
    while((ex << 1) < n){
        res = res*res
        ex <<= 1
    }
    return res * pow(a, n-ex)
}

5、数组排序奇数在左偶数在右（排序算法好像都可以做到）

let array = [2,3,5,2,3,5,7,8,10,3,5]
console.log(insert(array))
function insert(array){
    for(let i=1;i<array.length;i++){
        let cur = i
        while(array[cur]%2!=0 && array[cur-1]%2==0){
            let swap = array[cur]
            array[cur] = array[cur -1]
            array[cur -1] = swap
            cur--
        }
    }
    return array
}
function quick(array){
    let left = 0
    let right = array.length - 1
    let i = 0
    while(left <= right){
        if(array[left] % 2 ==0){
            let swap = array[left]
            array[left] = array[right]
            array[right] = swap
            right--
        }else{
            left++
        }
    }
    return array
}

6、求顺序或倒序的第N个或前N个元素（快排）

let array = [2,3,5,2,3,5,7,8,10,3,5]
console.log(quick(array,1))
//正序第n个元素
function quick(array,n){
    if(array.length < n){
        return false
    }
    let left = []
    let right = []
    let mid = array.splice(0,1)[0]
    for(let i=0;i<array.length;i++){
        if(mid > array[i]){
            left.push(array[i])
        }else{
            right.push(array[i])
        }
    }
    if(left.length == n-1){
        return mid
    }else if(left.length > n-1){
        return quick(left, n)
    }else{
        return quick(right, n - left.length - 1)
    }    
}

7、出现次数超过一半的数字（排序后中位数、两两抵消）

let array = [5,3,3,5,3,3,3,7,3,10,3,5]
console.log(solvel(array))
//两两抵消
function solvel(array){
    let contrast = array[0]
    let times = 1
    for(let i=1;i<array.length;i++){
        if(times == 0){
            contrast = array[i]
            times = 1
            continue
        }
        if(contrast == array[i]){
            times++
        }else{
            times--
        }
    }
    return contrast
}

8、最小可用id（计数排序）

9、逆序对（归并）

let array = [5,3,3,5,3,3]
let res = 0
merge(0, array.length)
console.log(res)
function merge(begin, end){
    console.log(begin, end)
    if(end - begin < 2){
        return
    }
    let mid = (begin + end) >> 1
    merge(begin, mid)
    merge(mid,end)
    sort(begin, mid, end)
}
function sort(begin, mid, end){
    let li = 0, le = mid - begin
    let ri = mid, re = end
    let ai = begin
    let leftArray = []
    for(let i=0;i<le;i++){
        leftArray[i] = array[begin++]
    }
    while(li < le){
        if(ri < re && array[ri] < leftArray[li]){
            res += leftArray.length - li
            array[ai++] = array[ri++]
        }else{
            array[ai++] = leftArray[li++]
        }
    }
}

10、字符串匹配（indexOf、穷举、hash滚动、kmp算法）

let s = 'ababbababbaaabba'
let p = 'bbaa' 
console.log(indexOf(s,p))
//kmp算法
function indexOf(s, p){
    let i = 0
    let j = 0
    let next = table(p)
    while(i < s.length){
        if(j<0||s.charAt(i) == p.charAt(j)){
            i++
            j++
            if(j == p.length){
                return i-j
            }
        }else{
            j = next[j]
        }
    }
    return -1
}
function table(p){
    let next = [-1]
    if(p.length == 1){
        return next
    }
    next[1] = 0
    let j = 1
    let k = next[j]
    while(j < p.length - 1){
        if(k<0 || p[k] == p[j]){
            next[++j] = ++k
        }else{
            k = next[k]
        }
    }
    return next
}

11、两（三）数之和为目标值，判断是否可以满足条件（或者全部打印出来）（双指针+外层循环）

//回溯法（任意个）

let array = [1,2,3,4,5,6,7,8,9
sum(array, 0, 13, [])
function sum(array, cur, target, arr){
  if(cur >= array.length || target < 0){
    return
  }
  if(target == 0){
    return console.log(arr)
  }
  sum(array, cur + 1, target, arr)
  arr.push(array[cur])
  sum(array, cur + 1, target - array[cur], arr)
  arr.pop()
}
//三个值之和
let array = [-8,-4,-3,0,2,4,5,8,9,10]
console.log(complier(array, 19, []))
function complier(array, target, results){
    for(let i=0;i<array.length-2;i++){
        let left = i+1
        let right = array.length-1
        while(left < right){
            if(array[i] + array[left] + array[right] < target){
                left++
            }else if(array[i] + array[left] + array[right] > target){
                right--
            }else{
                results.push([array[i], array[left++], array[right--]])
            }
        }
    }
    return results
}

12、逆序列topK问题，海量数据不能全部读取，只能一个一个读入（堆排序）

13、正整数数组所有项，拼成一个数，求最值（sort方法，比较器）

let array = [3,32,321,1,4,112]
array.sort(function(a,b){
    let str1 = String(a)+String(b)
    let str2 = String(b)+String(b)
    console.log(str1, str2)
    if(str1 > str2){
        return 1
    }else if(str1 < str2){
        return -1
    }else{
        return 0
    }
})

14、输入两个字符串判断str1中的所有字符s2是否都包含（穷举、hash表、计数排序）

let str1 = 'absbsdadafs'
let str2 = 'absdsessdd'
console.log(flag(str1, str2))
function flag(str1, str2){
    let hash = {}
    for(let i=0;i<str2.length;i++){
        if(!hash[str2.charAt(i)]){
            hash[str2.charAt(i)] = 1
        }
    }
    for(let i=0;i<str1.length;i++){
        if(!hash[str1.charAt(i)]){ 
            return false
        }
    }
    return true
}

15、两个字符串重排列是否相等，是否为旋转字符串（sort排序，判定相等，计数排序）

16、顺时针打印二维数组、旋转矩阵、z形打印

17、子数组最大累加和（当前位置左侧和为0就舍去，累加）

let array = [1,-2,3,5,-2,6,-3,-2,4]
console.log(find(array))
function find(array){
    let sum = array[0]
    let max = 0
    for(let i=1;i<array.length;i++){
        if(sum > 0){
            sum +=array[i]
        }else{
            sum = array[i]
        }
        if(max < sum){
            max = sum
        }
    }
    return max
}

18、天平砝码称重1，3，9，27，...,给定目标值，计算出方案（进制）

let array = [1,3,9,27,81]
let target = 10
let str = target.toString(3)
str = str.split('')
str.unshift(0)
for(let i=str.length-1;i>=0;i--){
    if(str[i] == 2){
        str[i-1] = Number(str[i-1]) + 1
        str[i] = -1
    }
}

19、n堆石子，分别为arr[i]个，两个人先后手取石子，最少一个，最多取完当前堆，假定两人都采用最优策略，谁会获胜（nim问题，进制+异或，多堆石子转化为2进制进行异或，每次取“1”）

20、阶梯上有若个石子，向某一方向进行移动，移动为1或者直到前者后一位（偶数石子，两两差值进行异或，奇数第一个数字和边界计算差值，其余进行两两差值计算在进行异或）

21、一组数字组合为目标值（单选、多选=>循环递归）

//任意个硬币，组合，多少种情况 
let array = [1,2,5,10,20]
let target = 5
console.log(call(array.length-1, target))
function call(cur, target){
    if(cur == 0){
        return 1
    }
    let res = 0
    for(let i=0;i * array[cur]<=target;i++){
        res += call(cur-1, target-i*array[cur])
    }
    return res
}

22、n个括号所有排列方式、子集 (进制法、递推法)

//n个括号递归排列方式
console.log(complier(3))
function complier(n){
    if(n == 1){
        let set = new Set(["()"])
        return set
    }else{
        let set = new Set()
        let prev = complier(n-1)
        prev.forEach(t=>{
            set.add('()' + t)
            set.add(t + '()')
            set.add('(' + t + ')')
        })
    return set
    }
}
//子集递推法
let array = [1,2,3,4]
console.log(complier(array))
function complier(array){
    let i = 0
    let arr = [[]]
    while(i<array.length){
        let newArr = []
        let cur = array[i]
        for(let j=0;j<arr.length;j++){
            newArr.push(JSON.parse(JSON.stringify(arr[j])))
        }
        for(let j=0;j<arr.length;j++){
            let swap = arr[j]
            swap.push(cur)
            newArr.push(swap)
        }
        arr = newArr
        i++
    }
    return arr
}
//子集进制法
let array = [1,2,3,4,5,6]
console.log(complier(array))
function complier(array){
    let len = array.length
    let max = Math.pow(2, len)
    let results = []
    array.reverse()
    for(let i=1;i<max;i++){ //每种组合情况
        let val = i.toString(2)
        val = val.split('')
        val.reverse()
        val = val.join('')
        let arr = []
        for(let j=0;j<val.length;j++){
            if(val.charAt(j) == 1){
                arr.push(array[j])
            }
        }
        results.push(arr)
    }
    return results
}

23、全排列（逐步生成迭代法、递归法）

//递归法
let array = [1,2,3,4,5,6]
function swap(array, i, j){
    let temp = array[i]
    array[i] = array[j]
    array[j] = temp
}
sort(array, 0, array.length)
function sort(array, p, q){
    if(p == q){
        console.log(array)
    }else{
    for(let i=p;i<q;i++){
        swap(array, p, i)
        sort(array, p+1, q)
        swap(array, p, i)
    }
    }
}
//逐步生成迭代法
let array = [1,2,3,4]
console.log(complier(array))
function complier(array){
    let count = 1
    let results = [[]]
    while(count <= array.length){
        let arr = []
        for(let j=0;j<results.length;j++){
            for(let i=0;i<array.length;i++){
                if(!results[j].includes(array[i])){
                    let temp = JSON.parse(JSON.stringify(results[j]))
                    temp.push(array[i])
                    arr.push(temp)
                }else{
                    continue
                }
            }
        }
        results = arr
        count++
    }
    return results
}

24、10种排序算法及优化、最好情况、最差情况、out-place、in-place、时间复杂度

25、数独游戏、n皇后（回溯）、部分数组求目标值

//8皇后问题
let col = [0,0,0,0,0,0,0,0] //对应第index行的第col位置放置皇后
let d1 = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] //上对角线是否已占用
let d2 = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] //下对角线是否已占用
let flag = [1,1,1,1,1,1,1,1]//对应列是否已占用
let count = 1
generate(0) //第0行
function generate(n){
    for(let i=0;i<8;i++){
        if(flag[i]&&d1[n-i+7]&&d2[n+i]){
            col[n] = i
            flag[i] = 0
            d1[n-i+7] = 0
            d2[n+i] = 0
            if(n < 7){
                generate(n+1)
            }else{
                console.log(count++)
                print(col)
            }
            col[n] = 0
            flag[i] = 1
            d1[n-i+7] = 1
            d2[n+i] = 1
        }
    }
}
function print(col){
    let array = []
    for(let i=0;i<8;i++){
        let arr = new Array(8)
        arr.fill(0)
        array.push(arr)
    }
    for(let i=0;i<col.length;i++){
        array[i][col[i]] = 1
    }
    console.log(array)
}
//数独游戏
let array = generArray(9)
array = fillArray(array)
console.log(array)
dfs(0, 0, array) 
function dfs(x, y, array){
    if(x == 9){
        console.log(array)
        return
    }
    if(!array[x][y]){
        for(let i=1;i<10;i++){
            let flag = check(array, x, y, i)
            if(flag){
                array[x][y] = i
                let arr = JSON.parse(JSON.stringify(array))
                dfs(x + Math.floor((y+1)/9), (y+1)%9, arr)
                array[x][y] = 0
            }
        }
    }else{
        dfs(x + Math.floor((y+1)/9), (y+1)%9, array)
    }
}
function check(array, x, y, k){
    for(let i=0;i<9;i++){
        if(array[i][y] == k){
            return false
        }
        if(array[x][i] == k){
            return false
        }
    }
    let col = Math.floor(y / 3)
    let row = Math.floor(x / 3)
    for(let i=0;i<3;i++){
        for(let j=0;j<3;j++){
            if(array[row*3+i][col*3+j] == k){
                return false
            }
        }
    }
    return true
}
function fillArray(array){
    array[0][2] = 5
    array[0][3] = 3
    array[1][0] = 8
    array[1][7] = 2
    array[2][1] = 7
    array[2][4] = 1
    array[2][6] = 5
    array[3][0] = 4
    array[3][5] = 5
    array[3][6] = 3
    array[4][1] = 1
    array[4][4] = 7
    array[4][8] = 6
    array[5][2] = 3
    array[5][3] = 2
    array[5][7] = 8
    array[6][1] = 6
    array[6][3] = 5
    array[6][8] = 9
    array[7][2] = 4
    array[7][7] = 3
    array[8][5] = 9
    array[8][6] = 7
    return array
}
function generArray(n){
    let array = []
    for(let i=0;i<n;i++){
        let arr = new Array(n)
        arr.fill(0)
        array.push(arr)
    }
    return array
}
//数组部分值求目标和
let array = [1,2,3,4,5,6]
back(array, 0, 13, [])
function back(array, cur, target, arr){
    if(target == 0){
        console.log(arr)
        return true
    }
    if(target<0 || cur>=array.length){
        return
    }
    back(array, cur+1, target, arr)
    arr.push(array[cur])
    let arrStr = JSON.parse(JSON.stringify(arr))
    back(array, cur+1, target - array[cur], arrStr)
    arr.pop()
}

贪心算法

26、硬币问题最少个、划船最快渡河问题

//渡河问题
let array = [1,2,5,10]
console.log(fun(array))
function fun(array){
    let right = array.length
    let sum = 0
    while(right > 0){
        if(right == 1){
            return sum+=array[0]
        }else if(right == 2){
            return sum+=array[1]
        }else if(right == 3){
            return sum +=array[0] + array[1] + array[2]
        }else{
            let d1 = array[right-1] + array[right-2] + array[0] * 2
            let d2 = array[right-1] + 2 * array[1] + array[0]
            let min = Math.min(d1, d2)
            sum+=min
            right-=2
        }
    }
}

27、01背包问题

//01背包问题，极限重量为5，求最大价值
let w = [2,1,3,2] //w极限为5
let v = [3,2,4,2]
let array = wrap(w,v)
array.sort((a,b)=>{
    return a.w - b.w
})
console.log(array)
let maxValue = 0
complier(array, 0, 5, [])
console.log(maxValue)
function complier(array, cur, target, arr){
    if(cur >= array.length || target < 0){ 
        return false
    }
    if(cur == array.length-1){
        let a = JSON.parse(JSON.stringify(arr))
        let sum = 0
        console.log(a)
        a.forEach((item,index)=>{ 
            sum+= Number(item['v'])
        }) 
        maxValue = Math.max(sum, maxValue) 
    }
    complier(array, cur+1, target, arr)
    arr.push(array[cur])
    complier(array, cur+1, target - array[cur][w], arr)
    arr.pop()
}
function wrap(w,v){
    let array = []
    for(let i=0;i<w.length;i++){
        let obj = {
            i:i,
            w:w[i],
            v:v[i]
        }
        array.push(obj)
}
return array
}

28、二维网格迁移，（旋转一位）

function back(grid){
    let row = grid.length
    let colmun = grid[0].length
    let last = grid[row-1][colmun-1]
    for(let i=row-1;i>=0;i--){
        for(let j=colmun-1;j>=1;j--){
            grid[i][j] = grid[i][j-1]
        }
        grid[i][0] = grid[i-1] && grid[i-1][colmun-1]
    }
    grid[0][0] = last
    return grid
}

29、链表

删除重复节点
将重复的节点全部删除
用基准值将链表分区
判断环链表的起点
回文链表
插入排序
https://www.jianshu.com/p/a2d53142860c

30、二叉树

二叉树的深度遍历（前中后序遍历，递归和栈两种方式）
二叉树层级遍历（队列）
重构二叉树
二叉搜索(查找、排序)树、平衡二叉树

Android面经| 算法题解
整理了校招面试算法题，部分《剑指offer》算法题，以及LeetCode算法题，本博文中算法题均使用Java实现校...
面试题高频算法题整理
以下算法题几乎都是简单题，都为面试算法题值得刷的题，需要理解并记住解题思路，而其中★标注的题，更是面试算法题中的高...
回溯,贪心,动态规划
1.回溯算法思想leetcode 112 号算法题：路径总和leetcode 113 号算法题：路径总和 IIle...
算法题
一、对一组数据进行降序或者升序排序（冒泡算法） intnums[10] = {4,5,1,10,7,1,8,3,6...
算法题
现在有一个字符串 string，它是一段英文，要求你统计这段英文里每个字母出现的次数。*例如输入 'Hello'，...
算法题
名企笔试：网易2017春招笔试（工作安排）【http://mp.weixin.qq.com/s/y08d3WhZK...
算法题
写一个方法获取一个字符串的长度？写一个冒泡排序数组去重 javascript实现格式化输出，比如输入9999...
算法题
1.求出1-100累加的和 2.求出1-100中奇数相加的和 3.求1000以内的斐波那契数 4.求1000以内的素数
算法题
1、求二进制数字中1的个数自带库 (binary_num).count('1') 按位运算符有：左移运算符（<<...
算法题
1. 租金卡大放送题目：“司庆大放送，一元即租房”，司庆当日，签约入住的客户，住满30天，返还（首月租金-1元）...

算法题

1、二分查找法

2、上楼梯（步数1或2、步数1～n）、阶乘、斐波那契、机器人走方格（有无障碍物）

3、数组最长递增序列长度或者值为多少（双指针法）

4、求a的n次幂

5、数组排序奇数在左偶数在右（排序算法好像都可以做到）

6、求顺序或倒序的第N个或前N个元素（快排）

7、出现次数超过一半的数字（排序后中位数、两两抵消）

8、最小可用id（计数排序）

9、逆序对（归并）

10、字符串匹配（indexOf、穷举、hash滚动、kmp算法）

11、两（三）数之和为目标值，判断是否可以满足条件（或者全部打印出来）（双指针+外层循环）

12、逆序列topK问题，海量数据不能全部读取，只能一个一个读入（堆排序）

13、正整数数组所有项，拼成一个数，求最值（sort方法，比较器）

14、输入两个字符串判断str1中的所有字符s2是否都包含（穷举、hash表、计数排序）

15、两个字符串重排列是否相等，是否为旋转字符串（sort排序，判定相等，计数排序）

16、顺时针打印二维数组、旋转矩阵、z形打印

17、子数组最大累加和（当前位置左侧和为0就舍去，累加）

18、天平砝码称重1，3，9，27，...,给定目标值，计算出方案（进制）

19、n堆石子，分别为arr[i]个，两个人先后手取石子，最少一个，最多取完当前堆，假定两人都采用最优策略，谁会获胜（nim问题，进制+异或，多堆石子转化为2进制进行异或，每次取“1”）

20、阶梯上有若个石子，向某一方向进行移动，移动为1或者直到前者后一位（偶数石子，两两差值进行异或，奇数第一个数字和边界计算差值，其余进行两两差值计算在进行异或）

21、一组数字组合为目标值（单选、多选=>循环递归）

22、n个括号所有排列方式、子集 (进制法、递推法)

23、全排列（逐步生成迭代法、递归法）

24、10种排序算法及优化、最好情况、最差情况、out-place、in-place、时间复杂度

25、数独游戏、n皇后（回溯）、部分数组求目标值

贪心算法

26、硬币问题最少个、划船最快渡河问题

27、01背包问题

28、二维网格迁移，（旋转一位）

29、链表

30、二叉树

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读