Skip to content

Commit 3cd2924

Browse files
leosanqingleosanqing
committed
update
1. 优化代码格式，并添加注释
1 parent 4069701 commit 3cd2924

16 files changed

Lines changed: 238 additions & 252 deletions

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/easy/_121_BestTimeToBuyAndSellStock.java‎

Lines changed: 28 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -1,36 +1,35 @@
11
package com.leosanqing.leetcode.easy;
22

33
/**
4-
*描述 ： 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
5-
* 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
6-
* 注意你不能在买入股票前卖出股票。
7-
*
8-
*示例1： 输入: [7,1,5,3,6,4]
9-
* 输出: 5
10-
* 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
11-
* 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
12-
*
13-
*示例2 输入: [7,6,4,3,1]
14-
* 输出: 0
15-
* 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
4+
* 描述 ： 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
5+
* 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
6+
* 注意你不能在买入股票前卖出股票。
7+
* <p>
8+
* 示例1： 输入: [7,1,5,3,6,4]
9+
* 输出: 5
10+
* 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
11+
* 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
12+
* <p>
13+
* 示例2 输入: [7,6,4,3,1]
14+
* 输出: 0
15+
* 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
1616
*/
1717

1818
public class _121_BestTimeToBuyAndSellStock {
1919

2020
/**
21-
*
2221
* 直接暴力求解，遍历两次数组，求出最优解
2322
*/
2423

25-
public static int violence(int[] prices){
26-
if(prices == null || prices.length ==0){
24+
public static int violence(int[] prices) {
25+
if (prices == null || prices.length == 0) {
2726
return 0;
2827
}
2928
int maxProfit = 0;
3029
for (int i = 0; i < prices.length; i++) {
31-
for (int j = i+1; j < prices.length; j++) {
32-
if(prices[j]-prices[i] >maxProfit){
33-
maxProfit = prices[j]-prices[i];
30+
for (int j = i + 1; j < prices.length; j++) {
31+
if (prices[j] - prices[i] > maxProfit) {
32+
maxProfit = prices[j] - prices[i];
3433
}
3534

3635
}
@@ -40,31 +39,29 @@ public static int violence(int[] prices){
4039

4140

4241
/**
43-
* 动态规划：
44-
* 1.定义一个从最开始到当前位置的最小值
45-
* 2.计算今天减去最小值的值，也就是当天的利润
46-
* 3.比较当天的利润和之前的最大利润
42+
* 动态规划：
43+
* 1.定义一个从最开始到当前位置的最小值
44+
* 2.计算今天减去最小值的值，也就是当天的利润
45+
* 3.比较当天的利润和之前的最大利润
4746
*/
48-
public static int dp(int[] prices){
49-
if(prices == null || prices.length == 0)
47+
public static int dp(int[] prices) {
48+
if (prices == null || prices.length == 0)
5049
return 0;
5150

52-
int mixProfit = Integer.MAX_VALUE;
51+
int minProfit = Integer.MAX_VALUE;
5352
int maxProfit = 0;
5453

55-
for (int i = 0; i < prices.length; i++) {
54+
for (int price : prices) {
5655
//找到最小值
57-
mixProfit = Math.min(mixProfit,prices[i]);
56+
minProfit = Math.min(minProfit, price);
5857
//比较当天的利润和最大利润
59-
maxProfit = Math.max(maxProfit,(prices[i]-mixProfit));
60-
58+
maxProfit = Math.max(maxProfit, (price - minProfit));
6159
}
6260
return maxProfit;
63-
6461
}
6562

6663
public static void main(String[] args) {
67-
int a[] ={7,6,4,3,1};
64+
int[] a = {7, 6, 4, 3, 1};
6865
System.out.println(violence(a) == dp(a));
6966
}
7067
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/easy/_122_BestTimeToBuyAndSellStock2.java‎

Lines changed: 27 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -2,42 +2,43 @@
22

33
/**
44
* 描述： 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
5-
* 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
6-
* 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
7-
*
5+
* 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
6+
* 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
7+
* <p>
88
* 示例1： 输入: [7,1,5,3,6,4]
9-
* 输出: 7
10-
* 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
11-
* 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
9+
* 输出: 7
10+
* 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
11+
* 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
1212
* 示例2： 输入: [1,2,3,4,5]
13-
* 输出: 4
14-
* 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
15-
* 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
16-
* 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
17-
*
13+
* 输出: 4
14+
* 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
15+
* 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
16+
* 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
17+
* <p>
1818
* 思路：使用两个变量 一个valley表示当天天数中最低价，
19-
* 一个peek表示当前所有的天数中的最高价
20-
* 因为我们可以买卖股票且是不用付手续费的，也就是我们可以卖了这一只股票，然后再把它买回来
21-
* 所以上面示例2中，5-1和 （2-1）+（3-2）+（4-3）+（5-4）的效果是一样的，所以顶峰就找递增的，底就找递减的
22-
*
19+
* 一个peek表示当前所有的天数中的最高价
20+
* 因为我们可以买卖股票且是不用付手续费的，也就是我们可以卖了这一只股票，然后再把它买回来
21+
* 所以上面示例2中，5-1和 （2-1）+（3-2）+（4-3）+（5-4）的效果是一样的，所以顶峰就找递增的，底就找递减的
2322
*/
2423
public class _122_BestTimeToBuyAndSellStock2 {
2524
public int maxProfit(int[] prices) {
26-
if(prices.length == 0 || prices == null)
25+
if (prices == null || prices.length == 0)
2726
return 0;
28-
int valley = prices[0],peek = prices[0];
29-
int i =0;
27+
28+
int valley = prices[0], peek = prices[0];
29+
int i = 0;
3030
int maxProfit = 0;
31-
while(i < prices.length-1){
32-
while(i<prices.length-1 && prices[i]>=prices[i+1])
31+
32+
while (i < prices.length - 1) {
33+
while (i < prices.length - 1 && prices[i] >= prices[i + 1])
3334
i++;
3435
valley = prices[i];
35-
while(i<prices.length-1 && prices[i]<=prices[i+1])
36+
37+
while (i < prices.length - 1 && prices[i] <= prices[i + 1])
3638
i++;
3739
peek = prices[i];
38-
maxProfit += peek-valley;
39-
}
40-
41-
return maxProfit;
40+
maxProfit += peek - valley;
4241
}
43-
}
42+
return maxProfit;
43+
}
44+
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/easy/_136_singleNum.java‎

Lines changed: 19 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,33 +1,32 @@
11
package com.leosanqing.leetcode.easy;
22

3-
/**描述：
4-
* Given a non-empty array of integers, every element appears twice except for one. Find that single one.
5-
* 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
6-
* 说明：
7-
* 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
8-
* 输入: [4,1,2,1,2]
9-
* 输出: 4
10-
*
11-
*
12-
* 思路：使用异或运算：
13-
* 异或运算有三个特征：
14-
* 1、0 ^ 任何数都为 那个数 0^a = a；
15-
* 2、两个相同的数异或结果为 0 a^a = 0;
16-
* 3、异或具有交换律 a^b^c = a^c^b
17-
*
3+
/**
4+
* 描述：
5+
* ` Given a non-empty array of integers, every element appears twice except for one. Find that single one.
6+
* ` 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
7+
* ` 说明：
8+
* ` 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
9+
* ` 输入: [4,1,2,1,2]
10+
* ` 输出: 4
11+
* `
12+
* `
13+
* ` 思路：使用异或运算：
14+
* ` 异或运算有三个特征：
15+
* ` 1、0 ^ 任何数都为 那个数 0^a = a；
16+
* ` 2、两个相同的数异或结果为 0 a^a = 0;
17+
* ` 3、异或具有交换律 a^b^c = a^c^b
1818
*/
1919
public class _136_singleNum {
2020
public static void main(String[] args) {
21-
int[] nums = {4,2,1,2,1};
21+
int[] nums = {4, 2, 1, 2, 1};
2222
System.out.println("singleNum(nums) = " + singleNum(nums));
2323

2424
}
2525

26-
public static int singleNum(int[] nums){
26+
public static int singleNum(int[] nums) {
2727
int result = 0;
28-
for (int num :
29-
nums) {
30-
result ^=num;
28+
for (int num : nums) {
29+
result ^= num;
3130
}
3231
return result;
3332
}

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/easy/_202_happyNumber.java‎

Lines changed: 22 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -9,29 +9,28 @@
99
* @Package: easy
1010
* @Description: leetCode 202题
1111
* <p>
12-
* A happy number is a number defined by the following process:
13-
* Starting with any positive integer, replace the number by the sum of the squares of
14-
* its digits,
15-
* and repeat the process until the number equals 1 (where it will stay),
16-
* or it loops endlessly in a cycle which does not include 1.
17-
* Those numbers for which this process ends in 1 are happy numbers.
18-
* <p>
19-
* Input: 19
20-
* Output: true
21-
* Explanation:
22-
* 12 + 92 = 82
23-
* 82 + 22 = 68
24-
* 62 + 82 = 100
25-
* 12 + 02 + 02 = 1
26-
* @Version: v1
27-
*
28-
*
29-
* 思路：
30-
* 我们看到最后，其实可以猜出来，只有最终变成一位数才有可能达到他的预期，
31-
* 如果有两位数或者以上，我们肯定是要对他再一次进行运算的，所以我们就一直往下拆数字就行，
32-
* 但是这里还有个坑，我们怎么让他不会陷入死循环呢？我们要判断他之前是否运算过，因为如果运算过，就会陷入死循环
33-
* 我们使用 HashSet ，来判断，如果有值，那么这个肯定之前就运算过，就会陷入死循环。不可能是我们想要的 HappyNum
34-
*
12+
* ` A happy number is a number defined by the following process:
13+
* ` Starting with any positive integer, replace the number by the sum of the squares of
14+
* ` its digits,
15+
* ` and repeat the process until the number equals 1 (where it will stay),
16+
* ` or it loops endlessly in a cycle which does not include 1.
17+
* ` Those numbers for which this process ends in 1 are happy numbers.
18+
* ` <p>
19+
* ` Input: 19
20+
* ` Output: true
21+
* ` Explanation:
22+
* ` 1² + 9² = 82
23+
* ` 8² + 2² = 68
24+
* ` 6² + 8² = 100
25+
* ` 1² + 0² + 0² = 1
26+
* ` @Version: v1
27+
* `
28+
* `
29+
* ` 思路：
30+
* ` 我们看到最后，其实可以猜出来，只有最终变成一位数才有可能达到他的预期，
31+
* ` 如果有两位数或者以上，我们肯定是要对他再一次进行运算的，所以我们就一直往下拆数字就行，
32+
* ` 但是这里还有个坑，我们怎么让他不会陷入死循环呢？我们要判断他之前是否运算过，因为如果运算过，就会陷入死循环
33+
* ` 我们使用 HashSet ，来判断，如果有值，那么这个肯定之前就运算过，就会陷入死循环。不可能是我们想要的 HappyNum
3534
*/
3635
public class _202_happyNumber {
3736
public static void main(String[] args) {
@@ -47,7 +46,6 @@ public boolean isHappy(int n) {
4746
Set<Integer> set = new HashSet<>();
4847

4948
while (n > 1) {
50-
5149
int m = 0;
5250
// 计算每位的平方的和
5351
while (n > 0) {

‎java-note-algorithm/src/main/java/com/leosanqing/leetcode/easy/_237_deleteNodeInLinkedList.java‎

Lines changed: 25 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -1,31 +1,31 @@
11
package com.leosanqing.leetcode.easy;
22

33
/**
4-
* 描述：Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
5-
*
6-
* Given linked list -- head = [4,5,1,9], which looks like following:
7-
*
8-
* 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
9-
*
10-
* 现有一个链表 -- head = [4,5,1,9]，它可以表示为:
11-
*
12-
* Input: head = [4,5,1,9], node = 5
13-
* Output: [4,1,9]
14-
* Explanation: You are given the second node with value 5,
15-
* the linked list should become 4 -> 1 -> 9 after calling your function.
16-
*
17-
*
18-
*
19-
* 提示：你已经进入了那个节点，并不是从头开始。
20-
* 链表至少包含两个节点。
21-
* 链表中所有节点的值都是唯一的。
22-
* 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
23-
* 不要从你的函数中返回任何结果。
24-
*
25-
* 请一定要注意描述和提示！！！！
26-
*
27-
*
28-
* 解法： 直接用后面的覆盖前面的，然后将指针修改下就行
4+
*` 描述：Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
5+
*`
6+
*` Given linked list -- head = [4,5,1,9], which looks like following:
7+
*`
8+
*` 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
9+
*`
10+
*` 现有一个链表 -- head = [4,5,1,9]，它可以表示为:
11+
*`
12+
*` Input: head = [4,5,1,9], node = 5
13+
*` Output: [4,1,9]
14+
*` Explanation: You are given the second node with value 5,
15+
*` the linked list should become 4 -> 1 -> 9 after calling your function.
16+
*`
17+
*`
18+
*`
19+
*` 提示：你已经进入了那个节点，并不是从头开始。
20+
*` 链表至少包含两个节点。
21+
*` 链表中所有节点的值都是唯一的。
22+
*` 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
23+
*` 不要从你的函数中返回任何结果。
24+
*`
25+
*` 请一定要注意描述和提示！！！！
26+
*`
27+
*`
28+
*` 解法： 直接用后面的覆盖前面的，然后将指针修改下就行
2929
*/
3030

3131
public class _237_deleteNodeInLinkedList {

0 commit comments

Comments
 (0)