webproblem/algorithms-code

算法刷题整理

algorithms-code's Issues

两数之和

两数之和

实现

暴力遍历

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let result = []
    for (let i = 0; i < nums.lemgth; i++) {
        for (let j = i + 1; j <nums.length; j++) {
            if (target - nums[i] === nums[j]) {
                result = [...result, i, j]
            }
        }
    }
    return result
};

利用哈希

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const map = new Map()
    let result = []
    for (let i = 0; i < nums.length; i++) {
        const diff = target - nums[i]
        if (map.has(diff)) {
            result = [...result, map.get(diff), i]
        } else {
            map.set(nums[i], i)
        }
    }
    return result
};

数组中连续N个数和的最大值

数组中连续N个数和的最大值

实现

循环遍历

/**
 * @param {number[]} nums
 * @param {number} n
 * @return {number[][]}
 */
var getMaxSum = function(nums, n) {
    let max = 0
    let temp = 0
    for (let i = 0; i <= nums.length - n; i++) {
        temp = 0
        for (let j = i; j < i + n; j++) {
            temp += nums[j]
        }
        if (temp > max) {
            max = temp
        }
    }
    return max
};

const array = [1,6,8,6,9,10]
console.log(getMaxSum(array, 4))

使用数组截取求和

/**
 * @param {number[]} array
 * @param {number} n
 * @return {number[][]}
 */
function test (array, n) {
    let temp = 0
    let max = 0
    for(let i = 0;  i <= array.length - n; i++) {
        temp = array.slice(i, i + n).reduce((pValue, cValue) => pValue + cValue)
        if (temp > max) {
            max = temp
        }
    }
    return max
}

const array = [1,6,8,16,9,10]
console.log(test(array, 3))

参考

https://www.bilibili.com/video/BV17L4y1F7ye

括号的最大嵌套深度

括号的最大嵌套深度

实现

/**
 * @param {string} s
 * @return {number}
 * 实现思路
 * 利用栈存储左括号，遍历与右括号匹配
 * 匹配时只需要判断当前栈的长度大于上次的长度，
 * 就存储当前最大长度为括号的最大嵌套深度
 */
var maxDepth = function(s) {
    if (s.length === 0) return s.length
    let stacks = []
    let max = 0
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stacks.push(i)
        } else if (s[i] === ')') {
            if (stacks.length > max) {
                max = stacks.length
            }
            stacks.pop()
        }
    }
    return max
};

中划线字符串转、驼峰式互转

中划线字符串转换成驼峰式

function main (str) {
    return str.replace(/[\-]+(.)/g, (math, p1) => p1.toLocaleUpperCase())
}

驼峰式转换成中划线字符串

function main (str) {
    return str.replace(/[A-Z]/g, (math) => `-${math.toLocaleLowerCase()}`)
}

有效的括号

有效的括号

实现

/**
 * @param {string} s
 * @return {boolean}
 * 实现思路：
    1. 将左括号按顺序放入栈中带匹配相应的右括号
    2. 匹配右括号的顺序是先进先出
 */
var isValid = function(s) {
    // 如果字符长度不是偶数就直接返回 false
    if(s.length % 2 !== 0) return false
    let stacks = []
    for (let i of s) {
        if (['(', '[', '{'].includes(i)) {
            stacks.push(i)
        } else if (
            (i === ')' && stacks[stacks.length - 1] === '(') ||
            (i === ']' && stacks[stacks.length - 1] === '[') ||
            (i === '}' && stacks[stacks.length - 1] === '{')
        ) {
            stacks.pop()
        } else {
            stacks.push(i)
        }
    }
    return !stacks.length
};

获取最长字符长度

获取最长字符长度

腾讯云智面试题

给定字符串

const string = 'this is my gith01ub registry algor1ithms url';

获取连续字符串的字符最大长度。

实现

function getMaxLength (string = '') {
    const lengths = string.split(' ').filter((item) => /^[a-z]+$/i.test(item)).map(item => item.length)
    return Math.max(...lengths)
}

螺旋矩阵

螺旋矩阵

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    if (!matrix.length && !matrix[0].length) {
        return []
    }
    const copyMatrix = JSON.parse(JSON.stringify(matrix))
    let top = 0
    let right = matrix[0].length - 1
    let bottom = matrix.length - 1
    let left = 0
    let array = []

    while(left <= right && top <= bottom) {
        for (let i = left; i <= right; i++) {
            array.push(matrix[top][i])
        }
        top++
        for (let i = top; i <= bottom; i++) {
            array.push(matrix[i][right])
        }
        right--
        if (left > right || top > bottom) break;
        for (let i = right; i >= left; i--) {
            array.push(matrix[bottom][i])
        }
        bottom--
        for (let i = bottom; i >= top; i--) {
            array.push(matrix[i][left])
        }
        left++
    }

    return array
};