算法题（附答案）

作者: 林思念 | 来源:发表于2023-12-03 17:25 被阅读0次

高中物理易错题150题附答案，太经典了！
【中考真题】2021年北京市中考地理试卷（附答案）
2124、检查是否所有 A 都在 B 之前 | 算法（leeto
剑指 Offer II 091、粉刷房子 | 算法（leetco
剑指offer-Python版（上）
146、LRU 缓存 | 算法（leetcode，附思维导图 +
算法（leetode，附思维导图 + 全部解法）300题之（2）
算法（leetode，附思维导图 + 全部解法）300题之（1）
40、组合总和 II | 算法（leetode，附思维导图 +
2126、摧毁小行星 | 算法（leetode，附思维导图 +

排列组合

1. 全排列，无顺序要求
1. 全排列，取前n项
1. 全排列，数字重复
1. 全排列，有序，取第n项
1. 全排列，无重复数字
1. 全排列，有序，取第n项
问题 1-6，可通过对数组进行有序全排列解决

let array = [1, 2, 3]
let res = []
// 回溯
function ds(initArray) {   
    if (initArray.length === array.length) {
        return res.push(initArray)
    }
    for (let i = 0; i < array.length; i++) {
        if (initArray.includes(array[i])) continue
        initArray.push(array[i])
        ds([...initArray])
        initArray.pop()
    }
} 
ds([])
console.log(res)

或

let array = [1, 2, 3]
let res = []

function ds(initArray, array) {
    if (!array.length) {
        return res.push(initArray)
    }
    for (let i = 0; i < array.length; i++) {
        if (i > 0 && array[i] === array[i - 1]) continue
        const newArray = JSON.parse(JSON.stringify(array))
        newArray.splice(i, 1)
        ds(initArray.concat(array[i]), newArray)
    }
}
ds([], array)
console.log(res)

1. 全排列，求和，数字可重复选取
1. 全排列，求和，数字只能用一次
问题 7-8，回溯剪枝

let array = [2, 4, 6, 8]
let target = 8

let res = []

function ds(target, index, path) {
    if (target === 0) {
        return res.push([...path])
    }
    if (target > 0 && index < array.length) {
        for (let i = index; i < array.length; i++) {
            if (target < array[i]) return
            target -= array[i]
            path.push(array[i])
            ds(target, i, path)   // 允许选择数字重复
            // ds(target, i + 1, path)   不允许选择数字重复
            target += array[i]
            path.pop()
        }
    }
}
ds(target, 0, [])
console.log(res)

1. 全排列，求和，动态参数
1. 回文排列

二分查找

// 思路 ： 
1. 二分取中位数与最右值相比，若大于则左侧有序，否则右侧有序 
2. 使用有序一侧最大和最小值与target进行比较确定范围
3. 更改left或right值为中值向左或右移动
var search = function (nums, target) {
    function ds(left, right) {
        while (left <= right) {
        let mid = left + right >> 1
        if (nums[mid] === target) {
            return mid
        }
        if (nums[mid] > nums[right]) {
            if (nums[left] <= target && target < nums[mid]) {
            right = mid - 1
            } else {
            left = mid + 1
            }
        } else {
            if (nums[mid] < target && target <= nums[right]) {
            left = mid + 1
            } else {
            right = mid - 1
            }
        }
        }
        return -1
    }
    return ds(0, nums.length-1)
};

// 二分查找
let nums = [5, 7, 7, 8, 8, 10], target = 8

function ds(left, right) {
    let mid = left + right >> 1
    if (target > nums[mid]) {
        return ds(mid + 1, right)
    } else if (target < nums[mid]) {
        return ds(left, mid - 1)
    } else {
        let start = mid
        let end = mid
        while (nums[end + 1] === nums[mid]) {
            end++
        }
        while (nums[start - 1] === nums[mid]) {
            start--
        }
        return [start, end]
    }
}

console.log(ds(0, nums.length - 1))

最长递增子序列

// 动态规划
var lengthOfLIS = function (nums) {
    let res = 1
    let d = new Array(nums.length).fill(1)

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                d[i] = Math.max(d[i], d[j] + 1)
            }
        }
        res = Math.max(res, d[i])
    }
    return res
};
let nums = [10, 9, 2, 5, 3, 7, 101, 18]
console.log(lengthOfLIS(nums))

双指针法

let str = 'cvfddssssds'
let res = str.charAt(0)
let last = str.charAt(0)
let count = 1
for (let i = 1; i < str.length; i++) {
    if (last === str.charAt(i)) {
        count++
    } else {
        res += count
        res += str.charAt(i)
        last = str.charAt(i)
        count = 1
    }
}
if (count !== 0) {
    res += count
}
console.log(res)

var validPalindrome = function(s) {
    let i = 0
    let j =s.length-1
    if(flag(s,i,j)){
        return true
    }
    
    while(i<=j){
        if(s.charAt(i)!=s.charAt(j)){ 
            str1 = s.slice(0,i)+''+s.slice(i+1)
            str2 = s.slice(0,j)+''+s.slice(j+1) 
            return flag(str1,0,s.length-2) || flag(str2,0,s.length-2)
        }else{
            i++
            j--
        }
    }
    function flag(s,l,r){
        while(l<=r){
            if(s.charAt(l) != s.charAt(r)){
                return false
            }else{
                l++
                r--
            }
        }
        return true
    }
};

let s = 'abcd'
let t = 'ahbgdc'

let index = 0
let res = ''

for (let i = 0; i < s.length; i++) {
    for (let j = index; j < t.length; j++) {
        if (t.charAt(j) === s.charAt(i)) {
            res += t.charAt(j)
            index = j + 1
            break;
        }
    }
}
console.log(s === res)

let nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4,5,6,7]
let last = nums[0]
for (let i = 1; i < nums.length; i++) {
    if (nums[i] === last) {
        nums.splice(i, 1)
        i--
    } else {
        last = nums[i]
    }
}
console.log(nums, nums.length)

let nums = [-1, 0, 1, 2, -1, -4]
nums.sort((a, b) => a - b)
let res = []
for (let i = 0; i < nums.length; i++) {
    let start = i + 1
    let end = nums.length - 1
    
    while (start < end) {
        if (nums[i] + nums[start] + nums[end] === 0) {
            res.push([nums[i], nums[start], nums[end]])
            break;
        } else if (nums[i] + nums[start] + nums[end] > 0) {
            end--
        } else {
            start++
        }
    }
}
console.log(res)

let nums = [1, 0, -1, 0, -2, 2]
let res = []
nums.sort((a, b) => a - b)
for (let i = 0; i < nums.length - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) {
        continue
    }
    for (let j = i + 1; j < nums.length - 2; j++) {
        if (nums[j] === nums[j - 1]) {
            continue
        }
        if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > 0) {
            break;
        }
        let start = j + 1
        let end = nums.length - 1
        while (nums[start] === nums[1 + start]) {
            start++
        }
        while (nums[end] === nums[end - 1]) {
            end--
        }
        while (start < end) {
            if (nums[start] + nums[end] + nums[i] + nums[j] === 0) {
                res.push([nums[start], nums[end], nums[i], nums[j]])
                break;
            } else if (nums[start] + nums[end] + nums[i] + nums[j] > 0) {
                end--

            } else {
                start++

            }
        }
    }
}

console.log(res)

贪心算法

树的遍历

function recursion(root) {
    if (!root) return
 // outArray.push(root.val) //  前序遍历
    recursion(root.left)
 // outArray.push(root.val) //  中序遍历
    recursion(root.right)
    outArray.push(root.val) //  后序遍历
}
// 执行递归
recursion(root)

广度、深度优先

var levelOrder = function(root) {
    if(root == null){
        return []
    }
    let queue = []
    let res = []
    queue.push(root)
    while(queue.length > 0){
        let arr = []
        let n = queue.length 
        for(let i=0;i<n;i++){
            let ele = queue.shift()
            arr.push(ele.val) 
            if(ele.left){
                queue.push(ele.left)
            }
            if(ele.right){
                queue.push(ele.right)
            }
        }
        res.push(arr)
    }
    return res
};

var levelOrderBottom = function(root) {
    if(root == null){
        return []
    }
    let res = []
    let queue = []
    queue.push(root)
    while(queue.length > 0){
        let arr = []
        let  n = queue.length
        for(let i=0;i<n;i++){
            let ele = queue.shift()
            arr.push(ele.val)
            if(ele.left){
                queue.push(ele.left)
            }
            if(ele.right){
                queue.push(ele.right)
            }
        }
        res.push(arr)
    }
    return res.reverse()
};

var levelOrder = function(root) { 
    if(!root){
        return []
    }
    let res = []
    let queue = []
    queue.push(root) 
    while(queue.length>0){ 
        let arr = []  
        let n = queue.length
        for(let j=0;j<n;j++){ 
            let cur = queue.shift() 
            arr.push(cur.val)
            for(let i=0;i<cur.children.length;i++){
                queue.push(cur.children[i])
            } 
        }  
        res.push(arr)
    }
    return res
    
};

function recursion(root) {
    if (!root) return 
    recursion(root.left)
    outArray.push(root.val) //  中序遍历
    recursion(root.right) 
}
console.log(recursion(root)[k-1])

var minDepth = function(root) {
    if(!root){
        return 0 
    }
    let queue = []
    queue.push(root) 
    let height = 1
    while(queue.length>0){
        let n = queue.length 
        for(let i=0;i<n;i++){
            let cur = queue.shift() 
            if(cur.left){
                queue.push(cur.left)
            }
            if(cur.right){
                queue.push(cur.right)
            }
            if(!cur.left && !cur.right){
                return height
            }   
        }
        height++ 
    }
};

var maxDepth = function(root) {
    if(root == null){
        return []
    }
    let res =  []
    let queue  = []
    let count = 0
    queue.push(root)
    while(queue.length >  0){
        let n = queue.length
        let arr = []
        for(let i=0;i<n;i++){
            let ele = queue.shift()
            arr.push(ele.val)
            if(ele.left){
                queue.push(ele.left)
            }
            if(ele.right){
                queue.push(ele.right)
            } 
        }
        count++
    }
    return count
};

动态规划

var uniquePaths = function(m, n) { 
    let min = m>n?n:m
    let max = m<n?n:m
    let array = [] 
    for(let i=0;i<min;i++){
        array[i] = []
    }
    array[0][0] = 0
    for(let i=0;i<min;i++){
        array[i][0] = 1
    }
    for(let i=0;i<max;i++){
        array[0][i] = 1
    }
    for(let i=1;i<min;i++){
        for(let j=1;j<max;j++){
            array[i][j] = array[i-1][j] + array[i][j-1]
        }
    }
    return array[min-1][max-1]
};

var climbStairs = function (n) {
  if (n === 0) { return 0 }
  if (n === 1) { return 1 }
  if (n === 2) { return 2 }
  let res = [0, 1, 2]
  for (let i = 3; i <= n; i++) {
    res.push(res[i - 2] + res[i - 1])
  }
  return res[n]
};

var climbStairs = function (n) {
  function f(n) {
    if (n === 0) return 0
    if (n === 1) return 1
    if (n === 2) return 2
    return f(n - 1) + f(n - 2)
  }
  return f(n)
};

数学技巧

var mySqrt = function(x) {
    for(let i=1;i<=Math.ceil(x/2)+1;i++){
        if(i * i >x){
            return i-1
        }
    }
};

var missingNumber = function(nums) {
    if(nums.length == 0){
        return 0
    }
    let max = nums[0]
    for(let i=1;i<nums.length;i++){
        if(max < nums[i]){
            max = nums[i]
        }
    }
    let array = []
    for(let i=0;i<=max;i++){
        let arr = new Array()
        array.push(arr)
    }
    for(let i=0;i<nums.length;i++){
        if(array[nums[i]]){
            array[nums[i]].push(nums[i])
        } 
    } 
    for(let i=0;i<=array.length;i++){
        if(i==array.length || array[i].length==0){ 
            return i
        }
    }
};

var isPowerOfTwo = function(n) {
    let i=0
    while(Math.pow(2,i)<n){
        i++
    }
    return Math.pow(2,i) == n
};

var isPowerOfThree = function(n) {
    let i=0
    while(Math.pow(3,i) <= n){
        i++
    }
    return Math.pow(3,i-1) == n
};

var countNumbersWithUniqueDigits = function(n) {
    if(n==0){
        return 1
    }else if(n==1){
        return 10
    }else{
        let sum = 9
        for(let i=0;i<n-1;i++){
            sum *= 9 - i
        } 
        return countNumbersWithUniqueDigits(n-1) + sum
    } 
};

var fib = function(n) {
    if(n ==0){
        return 0
    }else if(n <= 2){
        return 1
    }else {
        return fib(n-1) + fib(n-2)
    }
};

回溯

var letterCombinations = function(digits) {
    let arr =['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
    let res = []
    function dfs(count, prev){
        if(count==digits.length){
            res.push(prev)
            return 
        }
        let curStr = arr[digits.charAt(count)]
        for(let i=0;i<curStr.length;i++){
            dfs(count+1,prev+curStr.charAt(i))
        }
    }
    if(digits.length>0){
        dfs(0,'')
    }
    return res
};

var generateParenthesis = function(n) {
    let res = []
    function back(prev, count, number){
        if(count==0){
            res.push(prev+new Array(number).fill(')').join(""))
            return 
        }
        if(count !== number){ 
            back(prev+')',count,number-1)
        }
        back(prev+'(',count-1,number)
    }
    if(n>0){
        back('(', n-1,n)
    }
    return res
};

var partition = function(s) {
    let res = []
    let left = 0
    let right = 0
    back(left, right, [])
    function back(left, right, arr){
        if(left == s.length){
            return res.push([...arr])
        }
        for(let i = right;i<s.length;i++){
            if(flag(s,left,i)){
                arr.push(s.slice(left,i+1))
                back(i+1,i+1,arr)
                arr.pop()
            }
        }
    }
    function flag(s,l,r){
        while(l<r){
            if(s.charAt(l) == s.charAt(r)){
                l++
                r--
            }else{
                return false
            }
        }
        return true
    }
    return res
};

背包

最小路径
背包问题
股票问题
区间问题

高中物理易错题150题附答案，太经典了！
高中物理经典易错题150题（附参考答案）
【中考真题】2021年北京市中考地理试卷（附答案）
【中考真题】2021年北京市中考地理试卷（附答案）。#中考地理 #地理 #地理生物中考 #中考 #中考真题 #中考...
2124、检查是否所有 A 都在 B 之前 | 算法（leeto
零标题：算法（leetode，附思维导图 + 全部解法）300题之（2124）检查是否所有 A 都在 B 之前 ...
剑指 Offer II 091、粉刷房子 | 算法（leetco
零标题：算法（leetcode，附思维导图 + 全部解法）300题之（剑指 Offer II 091）粉刷房子 ...
剑指offer-Python版（上）
剑指offer上面的66道算法题是面试高频题，书中用C/C++写的答案，本篇笔记用python刷一遍所有的算法题，...
146、LRU 缓存 | 算法（leetcode，附思维导图 +
零标题：算法（leetcode，附思维导图 + 全部解法）300题之（146）LRU 缓存一题目描述二解...
算法（leetode，附思维导图 + 全部解法）300题之（2）
标题：算法（leetode，附思维导图 + 全部解法）300题之（2）两数相加导读：项目&作者 1 GitHu...
算法（leetode，附思维导图 + 全部解法）300题之（1）
标题：算法（leetode，附思维导图 + 全部解法）300题之（1）两数之和导读：项目&作者 1 GitHu...
40、组合总和 II | 算法（leetode，附思维导图 +
零标题 & 简介 1 标题算法（leetode，附思维导图 + 全部解法）300题之（40）组合总和 II 2...
2126、摧毁小行星 | 算法（leetode，附思维导图 +
零标题：算法（leetode，附思维导图 + 全部解法）300题之（2126）摧毁小行星一题目描述二解法...