OJ刷题Day1 · 一维数组的动态和 · 将数字变成 0 的操作次数 · 最富有的客户资产总量 · Fizz Buzz · 链表的中间结点 · 赎金信

一、一维数组的动态和

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

示例 1：
输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。

示例 2：
输入：nums = [1,1,1,1,1]
输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。

我的解法：

class Solution {public int[] runningSum(int[] nums) {//计算数组长度，生成相同长度的数组int[] arr = new int[nums.length];//通过计算公式，得出新数组每个元素上的数据int i = 0;for(i = 0; i < nums.length; i++) {int j = 0;int count = 0;for(j = 0; j < i; j++) {count += nums[j];}arr[i] = nums[j] + count;}return arr;}
}

大佬解法一： 数组第一元素不变，其它累加上去。

class Solution {public int[] runningSum(int[] nums) {for(int i=1; i<nums.length; i++) {nums[i] += nums[i-1];}return nums;}
}

大佬解法二：

class Solution {public int[] runningSum(int[] nums) {for(int i=1; i<nums.length; i++) {nums[i] = nums[i-1] + nums[i];}return nums;}
}

---

二、将数字变成 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 。

我的解法：

class Solution {public int numberOfSteps(int num) {int count = 0;while(num != 0) {count += 1;if(num % 2 == 0) {num /= 2;} else {num -= 1;}}return count;}
}

大佬解法： 用位运算和三元运算符。

class Solution {public static int numberOfSteps(int num) {  //14int ret = 0;while (num > 0) {  // ret = ret + [(num > 1 ? 1 : 0) + (num & 0x01)]// ret=1,num=7; ret=3,num=3; ret=5,num=1; ret=6,num=0.ret += (num > 1 ? 1 : 0) + (num & 0x01);num >>= 1;}return ret;}
}

我的解法优化： 吸取一丝大佬的思路

class Solution {public static int numberOfSteps(int num) {  //14int ret = 0;while(num != 0) {ret++;if(num % 2 == 0) {num >>= 1;}else if (num % 2 == 1) {num -= 1;}}return ret;}
}

---

三、最富有的客户资产总量

给你一个 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

我的解法：

class Solution {public int maximumWealth(int[][] accounts) {int max = 0;for(int i=0; i<accounts.length; i++) {int count = 0;for(int j=0; j<accounts[i].length; j++) {count += accounts[i][j];}if(max < count) {max = count;}}return max;}
}

大佬解法： 大佬总是会用上最高逼格的解法…

class Solution {public int maximumWealth(int[][] accounts) {int max = Integer.MIN_VALUE;for(int[] account : accounts) {max = Math.max(max, Arrays.stream(account).sum());}return max;}
}

---

四、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 （以字符串形式）如果上述条件全不满足。

示例 1：
输入：n = 3
输出：[“1”,“2”,“Fizz”]

示例 2：
输入：n = 5
输出：[“1”,“2”,“Fizz”,“4”,“Buzz”]

示例 3：
输入：n = 15
输出：[“1”,“2”,“Fizz”,“4”,“Buzz”,“Fizz”,“7”,“8”,“Fizz”,“Buzz”,“11”,“Fizz”,“13”,“14”,“FizzBuzz”]

我的解法：

class Solution {public List<String> fizzBuzz(int n) {List<String> list = new ArrayList<>();for(int i=1; i<=n; i++) {if((i%3==0) && (i%5==0)) {list.add("FizzBuzz");}else if(i%3==0) {list.add("Fizz");}else if(i%5==0) {list.add("Buzz");}else {list.add(Integer.toString(i));}}return list;}
}

想不到如此简单的一个题目，有大佬能讲出这么多道理：https://jtong.dev/2020/01/02/programmer-dojo/fizzbuzz-tdd/.

我的解法优化： 性能上提升了一点点…

class Solution {public List<String> fizzBuzz(int n) {List<String> list = new ArrayList<>();for(int i=1; i<=n; i++) {if((i%3==0) && (i%5==0)) {list.add("FizzBuzz");continue;}else if(i%3==0) {list.add("Fizz");continue;}else if(i%5==0) {list.add("Buzz");continue;}else {list.add(Integer.toString(i));continue;}}return list;}
}

---

五、链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

我的解法：

class Solution {public ListNode middleNode(ListNode head) {ListNode fast = head;ListNode slow = head;while((fast.next != null) && (fast.next.next != null)) {fast = fast.next.next;slow = slow.next;}if(fast.next == null) {return slow;}return slow.next;}
}

---

六、赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。
提示：
1 <= ransomNote.length, magazine.length <= 105
ransomNote 和 magazine 由小写英文字母组成

示例 1：
输入：ransomNote = “a”, magazine = “b”
输出：false

示例 2：
输入：ransomNote = “aa”, magazine = “ab”
输出：false

示例 3：
输入：ransomNote = “aa”, magazine = “aab”
输出：true

我的解法：

class Solution {public static boolean canConstruct(String ransomNote, String magazine) {// 创建个新数组，有 26 个元素位置int[] arr = new int[26];// 创建变量 i，遍历字符串 magazineint i = 0;for (i=0; i<magazine.length(); i++) {// 取 magazine 字符串的头元素 tmp，减去 'a'，得出该放在哪个元素位置int tmp = magazine.charAt(i) - 'a';arr[tmp] += 1;}// 创建变量 j，遍历字符串 ransomNoteint j = 0;for (j=0; j<ransomNote.length(); j++) {// 取 ransomNote 字符串的头元素 tmp，减去 'a'，再减去新数组中该元素的个数。int tmp = ransomNote.charAt(j) - 'a';arr[tmp] -= 1;// 然后判断，是否会遇到新数组中元素为 -1 的情况，遇到就是 falseif (arr[tmp] < 0) {return false;}}// 最后遍历结束，结果为 truereturn true;}
}