- 题目描述：
给你一个数组nums。数组「动态和」的计算公式为：runningSum[i]= sum(nums[0]···nums[i]）。 请返回nums[的动态和。
- 解题思路：
(1)创建一个结果数组，来维护结果集
(2)利用动态和更新给出的数组（原地修改）
方法一：
class Solution {
public int[] runningSum(int[] nums) {
int len = nums.length;
int [] sum = new int[len];
sum[0] = nums[0];
for(int i = 1; i < len; i++){
sum[i] = nums[i] + sum[i - 1];
}
return sum;
}
}
方法二：
class Solution {
public int[] runningSum(int[] nums) {
for(int i = 1; i < nums.length; i++){
nums[i] += nums[i - 1];
}
return nums;
}
}
二、赎金信
- 题目描述：
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。
- 解题思路：
(1)利用到了散列表的映射思想，但没用利用其数据结构。创建两个数组，分别记录两个字符串中每个字符出现的次数。两个字符进行算数运算是其对应ASCII码的运算。所以我们利用运算结果来得到数组的索引，共有26个字母所以数组长度应该至少为26，该字符每出现一次将其的值加一，最后如果ransomNote中存在某一个字符出现的次数比magazine中多，则直接返回false，否则返回true。
(2) 对于以上方法的改进，只利用一个数组完成检验，在获取数组下标时不再单独设置两个字符数组，而是利用超级for循环直接完成。
- 代码部分：
方法一：
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if(ransomNote.length() > magazine.length()){
return false;
}
//统计两个字符串中每个字符出现的次数
int [] cnt1 = new int[26];
int [] cnt2 = new int[26];
char [] ch1 = ransomNote.toCharArray();
char [] ch2 = magazine.toCharArray();
for(int i = 0; i < ransomNote.length(); i++){
cnt1[ch1[i] - 'a'] +=1;
}
for(int i = 0; i < magazine.length(); i++){
cnt2[ch2[i] - 'a'] +=1;
}
for(int j = 0; j < 26; j++){
if(cnt1[j] > cnt2[j]){
return false;
}
}
return true;
}
}
方法二：
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
//magazine的长度小于ransomNote说明肯定其中字符肯定不够组成ransomNote的
if(magazine.length() < ransomNote.length()){
return false;
}
//判断字符出现次数的数组
int [] count = new int[26];
for (char c : magazine.toCharArray()) {
cnt[c - 'a']++;
}
for (char c : ransomNote.toCharArray()) {
cnt[c - 'a']--;
if(cnt[c - 'a'] < 0) {
return false;
}
}
return true;
}
}
三、FizzBuzz
- 问题描述：给你一个整数 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）模拟题，分类判断，利用集合来存储字符串类型的结果。
（2）利用StringBuffer类，简化判断次数(但实际运行速度更慢)
- 代码部分：
方法一：
class Solution {
public List fizzBuzz(int n) {
List list = new ArrayList();
for(int i = 1; i <= n; i++){
if(i % 3 == 0 || i % 5 == 0){
if(i % 3 == 0 && i % 5 == 0){
list.add("FizzBuzz");
}else if(i % 3 == 0){
list.add("Fizz");
}else{
list.add("Buzz");
}
}else{
list.add("" + i);
}
}
return list;
}
}
方法二：
class Solution {
public List fizzBuzz(int n) {
List list = new ArrayList();
for(int i = 1; i <= n; i++){
StringBuffer sb = new StringBuffer();
if(i % 3 == 0){
sb.append("Fizz");
}
if(i % 5 == 0){
sb.append("Buzz");
}
if(sb.length() == 0){
sb.append(i);
}
list.add(sb.toString());
}
return list;
}
}
四、链表的中间结点
- 问题描述：给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
- 解题思路：
(1) 统计链表中结点的个数，创建一个新的指针初始化为链表头结点，移动(int)( n / 2)次，返回该指针即可
(2) 创建一个结点类型的数组，将链表中的指针保存到数组中，返回数组中的后半部分即可
(3)利用快慢指针，慢指针每次走一步，快指针每次走两步，当快指针到达链表的末尾时，慢指针也到达了链表的中间位置，返回慢指针即可
方法一：
class Solution {
public ListNode middleNode(ListNode head) {
int len = 0;
ListNode h = head;
while(head != null){
len++;
head = head.next;
}
for(int i = 1; i <= len >> 1; i++){
h = h.next;
}
return h;
}
}
方法二：
class Solution {
public ListNode middleNode(ListNode head) {
ListNode [] res = new ListNode[100];
int num = 0;
while(head != null){
res[num++] = head;
head = head.next;
}
return res[num >> 1];
}
}
方法三：
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
五、将数字变成0的操作次数
- 题目描述：给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。
- 解题思路：
利用了最简单的算数运算，也使用了三目运算符针对不同的情况采取不同的方法
- 代码部分：
class Solution {
public int numberOfSteps(int num) {
int count = 0;
while(num != 0){
num = num % 2 == 0 ? num >> 1 : num - 1;
count++;
}
return count;
}
}
六、最富有客户的资产总量
- 问题描述：给你一个 m x n 的整数网格 accounts ，其中 accounts[i][j] 是第 i 位客户在第 j 家银行托管的资产数量。返回最富有客户所拥有的 资产总量 。客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。
- 解题思路：
(1) 双层for循环，不断更新最大的资产总量
(2)第二版：利用到了Java的流运算，直接将数组求和
Arrays.stream(account).sum();
- 代码部分：
方法一：
class Solution {
public int maximumWealth(int[][] accounts) {
int maxNum = 0;
for(int i = 0; i < accounts.length; i++){
int count = 0;
for(int num : accounts[i]){
count += num;
}
if(count > maxNum){
maxNum = count;
}
}
return maxNum;
}
}
方法二：
class Solution {
public int maximumWealth(int[][] accounts) {
int maxNum = Integer.MIN_VALUE;
for(int [] arr : accounts){
maxNum = Math.max(maxNum, Arrays.stream(arr).sum());
}
return maxNum;
}
}
结果说明：使用流运算并不快
