今日题目：将数字变成 0 的操作次数、最富有客户的资产总量、两数相加、无重复字符的最长子串、寻找两个正序数组的中位数

20220326算法题

将数字变成 0 的操作次数

给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。

示例 1：

输入： num = 14
输出： 6
解释： 步骤 1) 14 是偶数，除以 2 得到 7 。
步骤 2） 7 是奇数，减 1 得到 6 。
步骤 3） 6 是偶数，除以 2 得到 3 。
步骤 4） 3 是奇数，减 1 得到 2 。
步骤 5） 2 是偶数，除以 2 得到 1 。
步骤 6） 1 是奇数，减 1 得到 0 。

示例 2：

输入： num = 8
输出： 4
解释：
步骤 1） 8 是偶数，除以 2 得到 4 。
步骤 2） 4 是偶数，除以 2 得到 2 。
步骤 3） 2 是偶数，除以 2 得到 1 。
步骤 4） 1 是奇数，减 1 得到 0 。

示例 3：

输入： num = 123
输出： 12

提示：

  • 0 <= num <= 10^6

思路： 由题意可知，在 num 为奇数时需要执行 -1 操作，然后再进行 num/2，需要两步；当 num 为偶数时， 只需要执行 num/2 操作需要一步。循环执行直到 num 为 0 。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number} num
 * @return {number}
 */
var numberOfSteps = function(num) {
    let count = 0
    while(num != 0) {
        count += (num>1 ? 1 : 0) + (num & 0x01)
        num >>= 1
    }
    return count
};

最富有客户的资产总量

给你一个 m x n 的整数网格 accounts ，其中 accounts[i][j] 是第 i​​​​​​​​​​​​ 位客户在第
j 家银行托管的资产数量。返回最富有客户所拥有的 资产总量 。

客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。

示例 1：

输入： accounts = [[1,2,3],[3,2,1]]
输出： 6
解释：
第 1 位客户的资产总量 = 1 + 2 + 3 = 6
第 2 位客户的资产总量 = 3 + 2 + 1 = 6
两位客户都是最富有的，资产总量都是 6 ，所以返回 6 。

示例 2：

输入： accounts = [[1,5],[7,3],[3,5]]
输出： 10
解释：
第 1 位客户的资产总量 = 6
第 2 位客户的资产总量 = 10 
第 3 位客户的资产总量 = 8
第 2 位客户是最富有的，资产总量是 10

示例 3：

输入： accounts = [[2,8,7],[7,1,3],[1,9,5]]
输出： 17

提示：

  • m == accounts.length
  • n == accounts[i].length
  • 1 <= m, n <= 50
  • 1 <= accounts[i][j] <= 100

思路： 遍历 accounts 进行各项求和，得到和之后求出最大值就是最富有的客户的资产总量

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[][]} accounts
 * @return {number}
 */
var maximumWealth = function(accounts) {
    let sumArray = []
    for(i of accounts){
        let sum = 0
        for(j of i) {
            sum += j
        }
        sumArray.push(sum)
    }
    return Math.max.apply(Math, sumArray)
};

两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例 1：

输入： l1 = [2,4,3], l2 = [5,6,4]
输出： [7,0,8]
解释： 342 + 465 = 807.

示例 2：

输入： l1 = [0], l2 = [0]
输出： [0]

示例 3：

输入： l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出： [8,9,9,9,0,0,0,1]

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

思路： 本题首先需要循环遍历两条单链表并且需要考虑 l1 和 l2 长度不一致的情况， 其次需要考虑到两数相加进位的情况，需要保存当前循环因进位留下来的数值，到下一次循环中使用。具体公式表现为： 当前节点数 = (l1.val + l2.val + tem) % 10, 进位数 = (l1.val + l2.val + tem) / 10 。最最重要的循环结束后需要考虑最后一次产生的进位情况。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 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) {
    let head = null, p = null
    let tem = 0
    while(l1 != null || l2 != null) {
        let num1 = l1 ? l1.val : 0
        let num2 = l2 ? l2.val : 0
        let sum = num1 + num2 + tem 
        num1 = sum % 10 // 当前数
        tem = Math.floor(sum / 10) // 进位值
        if(!head){
            head = new ListNode(num1)
            p = head
        }else {
            p.next = new ListNode(num1)
            p = p.next
        }
        if(l1 != null)
            l1 = l1.next // 指针后移
        if(l2 != null)
            l2 = l2.next // 指针后移
    }
    if(tem > 0) { // 最后一次循环结束进位的情况
        p.next = new ListNode(tem)
    }
    return head
};

无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 **最长子串 **的长度。

示例 1:

**输入:** s = "abcabcbb"
**输出:** 3 
**解释:** 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

**输入:** s = "bbbbb"
**输出:** 1
**解释:** 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

**输入:** s = "pwwkew"
**输出:** 3
**解释:** 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 **子串** 的长度，"pwke" 是一个 _子序列，_ 不是子串。

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

思路： 首先定义一个变量 maxLength 用来保存最长无重复子串长度，并用另一个变量 str 保存当前的子串，然后遍历循环字符串 s ，每次循环判断当前循环的字符是否以及存在于 str 中，如果存在，截取掉字符串从开头到字串所在位置的字符串，如果不在，将字符加入到 str 中，再计算新子串的长度 maxlength 。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let maxLength = 0; // 保存最长无重复子串
    let str = '' // 保存当前无重复子串
    for (let i = 0; i < s.length; i++) {
        let index = str.indexOf(s[i])
        if (index == -1) {
            str += s[i]
            maxLength = maxLength > str.length ? maxLength : str.length
        } else {
            str = str.substring(index+1)
            str += s[i]
        }
    }
    return maxLength
};

寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入： nums1 = [1,3], nums2 = [2]
输出： 2.00000
解释： 合并数组 = [1,2,3] ，中位数 2

示例 2：

输入： nums1 = [1,2], nums2 = [3,4]
输出： 2.50000
解释： 合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

思路： 本题思路很简单，首先将两个数值合并，然后进行排序，需要考虑负值的情况，再根据排序后的数值的奇偶性来确定中位数的数值。奇数：合并后数组长度 / 2 的结果向下取整就是中位数的索引，偶数：合并后的数组长度 / 2 向下取整的结果对应第二个数的索引，再加上前一个数的和 / 2 就是中位数。

提示：切记排序的时候要指定排序的函数， JavaScript 中数组默认使用字符编码排序，当有负数时，结果会异常，笔者已踩坑。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    nums1 = nums1.concat(nums2)
    nums1 = nums1.sort((a, b) => a - b)
    let mid = Math.floor(nums1.length / 2)
    if(nums1.length % 2 == 0) {
        return (nums1[mid - 1] + nums1[mid]) / 2
    }else {
        return nums1[mid]
    }
};