算法相关2

1.给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2, s) {
    // 递归方式
    var node = new ListNode()
    var carry = (s === undefined ? 0 : s)
    var firstNum = (l1 === null ? 0 : l1.val)
    var secondNum = (l2 === null ? 0 : l2.val)
    node.val = (firstNum + secondNum + carry) % 10
    if (l1.next === null && l2.next === null) {
        if (parseInt((l1.val + l2.val + carry) / 10) > 0){
            var nextNode = new ListNode()
            nextNode.val = parseInt((l1.val + l2.val + carry) / 10)
            node.next = nextNode
        }
        return node
    }
    node.next = addTwoNumbers(l1.next ? l1.next : new ListNode, l2.next ? l2.next : new ListNode, parseInt((l1.val + l2.val + carry) / 10))
    return node
}

2.给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

示例 1：

输入：arr = [1,2,2,1,1,3]
输出：true
解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。
示例 2：

输入：arr = [1,2]
输出：false
示例 3：

输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出：true

提示：

1 <= arr.length <= 1000
-1000 <= arr[i] <= 1000

// map和set结合使用
var uniqueOccurrences = function(arr) {
    var map = {}
    for (let n = 0; n < arr.length; n++) {
        if (map.hasOwnProperty(arr[n])){
            map[arr[n]] = map[arr[n]] + 1
        } else {
            map[arr[n]] = 1
        }
    }
    var mySet = new Set()
    for (var key in map) {
        if (mySet.has(map[key])) {
            return false
            break
        }
        mySet.add(map[key])
    }
    return true

};

3.一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

注意：本题相对原题稍作改动

示例 1：

输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
示例 2：

输入： [2,7,9,3,1]
输出： 12
解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
示例 3：

输入： [2,1,4,5,3,1,1,3]
输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

/**
 * @param {number[]} nums
 * @return {number}
 */
var massage = function(nums) {
    var dp = []
    if (nums.length === 0) return 0
    if (nums.length === 1) return nums[0]
    if (nums.length === 2) return Math.max(nums[0], nums[1])
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1]);
    for (var index = 2; index < nums.length; index++) {
        dp[index] = Math.max(nums[index] + dp[index - 2], dp[index - 1])
    }
    return dp[index - 1]
};  

4.给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：

输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
示例 4：

输入：root = [1,2]
输出：[1,2]
示例 5：

输入：root = [1,null,2]
输出：[1,2]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

/**
 * 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 {number[]}
 */
var preorderTraversal = function(root) {
    if (!root) return []
    var results = []
    const preFuc = function (data) {
        if (!data) return
        results.push(data.val)
        preFuc(data.left)
        preFuc(data.right)
    }
    preFuc(root)
    return results
};

5.给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

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

这个问题其实有更好的解法这个是O(n²),从别人那看到的就是使用hash映射O(n/2),简单说一下思路
(1).遍历每一个变量
(2).创建一个map,key存储的是target减变量的值
(3).然后判断map中是否存在这个key
然后找到就可以了,思路就是这样
6.给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。
示例 1：

输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]
解释：
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。
对于 nums[3]=2 存在一个比它小的数字：（1）。
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。
示例 2：

输入：nums = [6,5,4,8]
输出：[2,1,0,3]
示例 3：

输入：nums = [7,7,7,7]
输出：[0,0,0,0]

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var smallerNumbersThanCurrent = function (nums) {
    var i = nums.length
    var newArr = []
    var j = 0
    while (j < i) {
        var num = nums[j]
        if (newArr[num] === undefined) {
            newArr[num] = 1
        } else {
            var n = newArr[num]
            newArr[num] = ++n
        }
        j++
    }
    var m = 0
    var all = 0
    while (m < i) {
        all = 0
        let num = nums[m]
        for (let s = 0; s < num; s++) {
            if (newArr[s] !== undefined) {
                all = all + newArr[s]
            }
        }
        nums[m] = all
        m++
    }
    return nums
};

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。