821 字符的最短距离简单

/**
 * @param {string} s
 * @param {character} c
 * @return {number[]}
 */
var shortestToChar = function(s, c) {
    let res = new Array(s.length), p = -1
    for(let i = 0; i < s.length; i++) {
        if (c === s[i]) {
            p = i
        }
        if (p !== -1) {
            res[i] = Math.abs(i - p)
        }
    }
    p = -1
    for(let i = s.length - 1; i >= 0; i--) {
        if (c === s[i]) {
            p = i
        }
        if (p != -1) {
            if (res[i]) {
                res[i] = Math.min(res[i], Math.abs(i - p))
            } else {
                res[i] = Math.abs(i - p)
            }
        }
    }
    return res
};

258 简单

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function(num) {
    let res = num, str = num + ''
    while(res > 9) {
        res = 0
        for(let i = 0; i < str.length; i++) {
            res += Number(str[i])
        }
        str = res + ''
    }
    return res
};

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function(num) {
    if (num === 0) {
        return 0
    }
    return num % 9 === 0 ? 9 : num % 9
};

1413 简单

/**
 * @param {number[]} nums
 * @return {number}
 */
var minStartValue = function(nums) {
    let min = 0
    nums.reduce((prev, cur) => {
        if (prev + cur < 1) {
            min = min < prev + cur ? min : prev + cur
        }
        return prev + cur
    }, 0)
    return Math.abs(min) + 1
};

39 简单
摩尔投票法

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let res = 0, count = 0
    for(let i = 0; i < nums.length; i++) {
        if (count === 0) {
            res = nums[i]
            count++
        } else {
            res === nums[i] ? count++ : count--
        }
    }
    return res
};

面试题02.01 简单

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var removeDuplicateNodes = function(head) {
    let start = head
    while(start) {
        let prev = start, cur = start.next
        while(cur) {
            if (cur.val === start.val) {
                prev.next = cur.next
            } else {
                prev = cur
            }
            cur = cur.next
        }
        start = start.next
    }
    return head
};

1800. 最大升序子数组和

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxAscendingSum = function(nums) {
    let max = nums[0], temp = nums[0]
    for(let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) {
            temp += nums[i]
        } else {
            max = max < temp ? temp : max
            temp = nums[i]
        }
    }
    return max < temp ? temp : max
};

575. 分糖果

/**
 * @param {number[]} candyType
 * @return {number}
 * 第一种情况，每个糖果都不相同，[1,2,3,4]，妹妹可以分得2种
 * 第二种情况，每2个糖果相同，[1,1,2,2]，妹妹可以分得2种
 * 第三种情况，每个糖果都相同，[1,1,1,1]，妹妹可以分得1种
 * 所以妹妹可以分得最多种类是，糖果种类 和 糖果个数/2 中的最小值
 */
var distributeCandies = function(candyType) {
    let type = new Set(candyType).size
    return Math.min(type, candyType.length / 2)
};

LCP 02. 分式化简

/**
 * @param {number[]} cont
 * @return {number[]}
 * 1/(a + 1/b) = b / (a * b + 1)
 */
var fraction = function(cont) {
    let len = cont.length, res = [1, cont[len - 1]]
    for(let i = len - 2; i >= 0; i--) {
        res = [res[1], cont[i] * res[1] + res[0]]
    }
    return res.reverse()
};

965. 单值二叉树

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isUnivalTree = function(root) {
    if (!root) {
        return true
    }
    if (root.left && root.val !== root.left.val) {
        return false
    }
    if (root.right && root.val !== root.right.val) {
        return false
    }
    return isUnivalTree(root.left) && isUnivalTree(root.right)
};

1619. 删除某些元素后的数组均值

/**
 * @param {number[]} arr
 * @return {number}
 */
var trimMean = function(arr) {
    let count = arr.length * 0.05, sum
    arr.sort((a, b) => a -b)
    arr.splice(0, count)
    arr.splice(arr.length - count, count)
    sum = arr.reduce((prev, cur) => {
        return prev + cur
    }, 0)
    return sum / arr.length
};

509. 斐波那契数

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if (n < 2) {
        return n
    }
    return fib(n - 1) + fib(n - 2)
};

496. 下一个更大元素 I

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function(nums1, nums2) {
    for(let i = 0; i < nums1.length; i++) {
        let num = nums1[i], idx = nums2.indexOf(num), flag = false
        for(let j = idx; j < nums2.length - 1; j++) {
            if (nums2[j + 1] > num) {
                nums1[i] = nums2[j + 1]
                flag = true
                break
            }
        }
        if (!flag) {
            nums1[i] = -1
        }
    }
    return nums1
};

122. 买卖股票的最佳时机 II

/**
 * @param {number[]} prices
 * @return {number}
 * 只要今天比昨天的价格高就卖出
 */
var maxProfit = function(prices) {
    let res = 0
    for(let i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            res += prices[i] - prices[i - 1]
        }
    }
    return res
};

1332. 删除回文子序列

/**
 * @param {string} s
 * @return {number}
 * 字符串为空返回0，字符串是回文串返回1，否则返回2
 */
var removePalindromeSub = function(s) {
    if (!s.length) {
        return 0
    }
    let flag = true, mid = (s.length >>> 1) + s.length % 2
    for(let i = 0; i < mid; i++) {
        if (s[i] !== s[s.length - i - 1]) {
            flag = false
            break
        }
    }
    return flag ? 1 : 2
};

剑指 Offer 03. 数组中重复的数字

/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function(nums) {
    for(let i = 0; i < nums.length; i++) {
        if (nums[i] < 0) {
            return i
        }
        if (nums[nums[i]] < 0) {
            return nums[i]
        }
        // 将nums数组中下标为nums[i]的标为负数，如果再遇到负数就说明出现过
        nums[nums[i]] = - nums[nums[i]]
    }
    // -0 < 0 是 false
    return 0
};

257. 二叉树的所有路径

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[]}
 */
var binaryTreePaths = function(root) {
    let res = []
    const getPath = (root, path) => {
        if (root) {
            path += root.val
            if (!root.left && !root.right) {
                res.push(path)
            } else {
                path += '->'
                getPath(root.left, path)
                getPath(root.right, path)
            }
        }
    }
    getPath(root, '')
    return res
};

1582. 二进制矩阵中的特殊位置

/**
 * @param {number[][]} mat
 * @return {number}
 */
var numSpecial = function(mat) {
    let res = 0, row = mat.length
    for(let i = 0; i < row; i++) {
        // 如果第i行元素和为1
        if (mat[i].reduce((prev, cur) => prev + cur) === 1) {
            // 找出哪一列为1
            const idx = mat[i].indexOf(1)
            let sum = 0
            // 判断idx列的和是否为1
            mat.map(item => {
                sum += item[idx]
            })
            if (sum === 1) {
                res++
            }
        }
    }
    return res
};

1640. 能否连接形成数组

/**
 * @param {number[]} arr
 * @param {number[][]} pieces
 * @return {boolean}
 */
var canFormArray = function(arr, pieces) {
    for(let i = 0; i < pieces.length; i++) {
        let temp = pieces[i]
        // 如果是多个元素，要判断这些元素在arr中是否相连
        if (temp.length > 1) {
            let idx = arr.indexOf(temp[0])
            if (idx === -1) {
                return false
            }
            for(let j = 1; j < temp.length; j++) {
                if (arr[idx + j] !== temp[j]) {
                    return false
                }
            }
        } else {
            // 如果只有一个，需要判断这个元素在arr中是否存在
            if (!arr.includes(temp[0])) {
                return false
            }
        }
    }
    return true
};

1790. 仅执行一次字符串交换能否使两个字符串相等

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var areAlmostEqual = function(s1, s2) {
    if (s1.length !== s2.length) {
        return false
    }
    let x1, y1, x2, y2, num = 0
    for(let i = 0; i < s1.length; i++) {
        if(s1[i] !== s2[i]) {
            num++
          // 如果超出2对不相等就返回false
            if (num > 2) {
            return false
        }
          // 记录一下不相等的位置的字符
        if (num === 1) {
            x1 = s1[i]
            x2 = s2[i]
        } else {
            y1 = s1[i]
            y2 = s2[i]
        }
        }
    }
  // 判断交换之后能否相等
    return x1 === y2 && x2 === y1 ? true : false
};

算法

其他题解

821 字符的最短距离简单

258 简单

1413 简单

39 简单
摩尔投票法

1800. 最大升序子数组和

575. 分糖果

LCP 02. 分式化简

965. 单值二叉树

1619. 删除某些元素后的数组均值

509. 斐波那契数

496. 下一个更大元素 I

122. 买卖股票的最佳时机 II

1332. 删除回文子序列

剑指 Offer 03. 数组中重复的数字

257. 二叉树的所有路径

1582. 二进制矩阵中的特殊位置

1640. 能否连接形成数组

1790. 仅执行一次字符串交换能否使两个字符串相等

其他题解

821 字符的最短距离 简单

258 简单

1413 简单

39 简单摩尔投票法

821 字符的最短距离简单

39 简单
摩尔投票法