ARTS打卡：第六周

每周完成一个ARTS：

Algorithm：每周至少做一个 leetcode 的算法题

Review：阅读并点评至少一篇英文技术文章

Tip：学习至少一个技术技巧

Share：分享一篇有观点和思考的技术文章

Algorithm

这周的 LeetCode 记录如下：

26. Remove Duplicates from Sorted Array（Easy）

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn’t matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn’t matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}

@DevDocsleetcode.com/problems/remove-duplicates-from-sorted-array

大致题意：
删除排序数组中的重复项，要求给定一个排序数组，在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

解题思路：
这道题，我们可以借鉴快慢指针的思想来做，不过不是用链表，是用数组进行模拟：
假设 slow 为慢指针，fast 为快指针，因为 nums 数组是已经排好序的升序数组，所以当 nums[slow] = nums[fast]，我们让快指针前进一步，跳过重复的数据，即 fast++；若 nums[slow] != nums[fast]时，让慢指针前进一步，即 slow++，然后交换快指针与慢指针的值，将新数据替换掉重复数据，即 nums[slow] = nums[fast]；重复步骤直至快指针走到数组尾部，即 fast == nums.length时，输出结果 slow + 1，这就是去重后的数组长度了。

代码实现：

public int removeDuplicates(int[] nums) {
    // 当是空数组时，直接返回 0，边界条件
    if (nums.length == 0) {
        return 0;
    }
    // slow 为慢指针
    int slow = 0;
    // fast 为 快指针
    for (int fast = 1; fast < nums.length; fast++
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

复杂度分析：
时间复杂度：O(n)
空间复杂度：O(1)

运行结果：
Runtime: 1 ms, faster than 99.98% of Java online submissions for Remove Duplicates from Sorted Array.
Memory Usage: 40.8 MB, less than 84.56% of Java online submissions for Remove Duplicates from Sorted Array.

122. Best Time to Buy and Sell Stock II(Easy)

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation:
Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.

Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

@DevDocsleetcode.com/problems/best-time-to-buy-and-sell-stock-ii

题意：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意： 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解题思路：
这道题是看答案才明白过来的，感觉挺有趣的，虽然挺多人认为这道题就是拿来搞笑的。
有三种解决方法，详情请查看：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/solution/
第三种解法，着实我眼前一亮。
先暂时忽略题目的限制，那么我们就可以得出这个结果：只要我们每次买进股票的价格比我们卖出的价格低的机会，就能实现利润最大化。

代码实现：

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i - 1] < prices[i]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }
}