leetcode刷题|Day1：新手村

1.题目：1480. 一维数组的动态和

 给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。请返回 nums 的动态和。

我的想法：设置整数值sum和空列表list，循环将每个sum=sum+nums[i]添加到list末尾，返回list。

优化：

原地算法：

var runningSum = function(nums) {const n = nums.length;for (let i = 1; i < n; i++) {nums[i] += nums[i - 1];}return nums;
};作者：LeetCode-Solution
链接：https://leetcode.cn/problems/running-sum-of-1d-array/solution/yi-wei-shu-zu-de-dong-tai-he-by-leetcode-flkm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析：

时间复杂度：O(n)，其中 n 是给定数组长度。

空间复杂度：O(1)。我们只需要常数的空间保存若干变量。

2.题目：1342. 将数字变成 0 的操作次数

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

我的想法：（当num为1时需要特殊处理）

/*** @param {number} num* @return {number}*/
var numberOfSteps = function(num) {var k=0;while(num != 0){if(num%2 != 0){num=num-1;k=k+1;if(num == 0) break;}num=num/2;k++;}return k;
};

位运算：（判断奇偶、除2）

var numberOfSteps = function(num) {let ret = 0;while (num > 0) {ret += (num > 1 ? 1 : 0) + (num & 0x01);num >>= 1;}return ret;
};作者：LeetCode-Solution
链接：https://leetcode.cn/problems/number-of-steps-to-reduce-a-number-to-zero/solution/jiang-shu-zi-bian-cheng-0-de-cao-zuo-ci-ucaa4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(lognum)，其中 num是输入数值。每次循环都将 num 的数值减半，因此时间复杂度为lognumO(lognum)。

空间复杂度：O(1)。只需要常数空间。

进一步归纳：

当 num>0 时，总操作次数等于总减 1 的操作数与总除以 2 的操作数之和。总减 1 的操作数等于 num 二进制位 1 的个数，总除以 2 的操作数等于 num 二进制数长度减 1，即最高位右移到最低位的距离。

递归方法：

/*
@可爱抱抱呀
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：38.4 MB, 在所有 Java 提交中击败了5.42%的用户
2022年1月29日 14:23
*/
class Solution {public int numberOfSteps(int num) {return num==0?0:((num&1)==1?numberOfSteps(num-1):numberOfSteps(num>>1))+1;}
}

3.题目：1672. 最富有客户的资产总量 

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

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

我的思路：

双层循环，内层计算某客户的资产总量，外层比较是否最大。

使用reduce函数： 

var maximumWealth = function(accounts) {let maxWealth = -Number.MAX_VALUE;for (const account of accounts) {maxWealth = Math.max(maxWealth, account.reduce((a, b) => a + b));}return maxWealth;
};作者：LeetCode-Solution
链接：https://leetcode.cn/problems/richest-customer-wealth/solution/zui-fu-you-ke-hu-de-zi-chan-zong-liang-b-8p06/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

python写法（很简单）

class Solution:def maximumWealth(self, accounts: List[List[int]]) -> int:return max(map(sum, accounts))作者：LeetCode-Solution
链接：https://leetcode.cn/problems/richest-customer-wealth/solution/zui-fu-you-ke-hu-de-zi-chan-zong-liang-b-8p06/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O（mn）

空间复杂度：O（1）

4.题目：412. Fizz Buzz

给你一个整数 n ，找出从 1 到 n 各个整数的 Fizz Buzz 表示，并用字符串数组 answer（下标从 1 开始）返回结果，其中：

answer[i] == "FizzBuzz" 如果 i 同时是 3 和 5 的倍数。
answer[i] == "Fizz" 如果 i 是 3 的倍数。
answer[i] == "Buzz" 如果 i 是 5 的倍数。
answer[i] == i （以字符串形式）如果上述条件全不满足。

我的思路：

对各个选项if，用push（）加入结果array。数字需要toString（）方法转换。

优化：循环内用字符串拼接，以减少if选项。

join() 方法用于把数组中的所有元素放入一个字符串。 

var fizzBuzz = function(n) {const answer = [];for (let i = 1; i <= n; i++) {const sb = [];if (i % 3 === 0) {sb.push("Fizz");}if (i % 5 === 0) {sb.push("Buzz");}if (sb.length === 0) {sb.push(i);}answer.push(sb.join(''));}return answer;
};作者：LeetCode-Solution
链接：https://leetcode.cn/problems/fizz-buzz/solution/fizz-buzz-by-leetcode-solution-s0s5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

5.题目：876. 链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

快慢指针法 ：（终于想到了一个高级一点的算法）

用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。那么当 fast 到达链表的末尾时，slow 必然位于中间。

var middleNode = function(head) {slow = fast = head;while (fast && fast.next) {slow = slow.next;fast = fast.next.next;}return slow;
};作者：LeetCode-Solution
链接：https://leetcode.cn/problems/middle-of-the-linked-list/solution/lian-biao-de-zhong-jian-jie-dian-by-leetcode-solut/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(N)

空间复杂度：O(1)

6.题目：383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

我的想法：遍历magazine的每个字符，如果与ransomNote中的某个字符相同就在ransomNote中删去这个字符，最终如果ransomNote长度为0，返回true；否则返回false。但是没有解出来，因为对于substring（start，end）的切分不好设计。

字符统计：

var canConstruct = function(ransomNote, magazine) {if (ransomNote.length > magazine.length) {return false;}const cnt = new Array(26).fill(0);for (const c of magazine) {cnt[c.charCodeAt() - 'a'.charCodeAt()]++;}for (const c of ransomNote) {cnt[c.charCodeAt() - 'a'.charCodeAt()]--;if(cnt[c.charCodeAt() - 'a'.charCodeAt()] < 0) {return false;}}return true;
};作者：LeetCode-Solution
链接：https://leetcode.cn/problems/ransom-note/solution/shu-jin-xin-by-leetcode-solution-ji8a/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。