122. Best Time to Buy and Sell Stock II

122. Best Time to Buy and Sell Stock II   ( https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/ )

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [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.

Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [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.

Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]

Output: 0

Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

 

Constraints:

1 <= prices.length <= 3 * 10^4

0 <= prices[i] <= 10^4

因為你有上帝視角，你知道兩天之間是賺還是賠
你就把任兩天之間有賺錢的加起來，就是最大獲利

假設 profit(b, s) 代表 b 這天買，s 這天賣的獲利
如果 profit(1~n) 天的獲利會比 profit(1~n-1) 好
那profit(n-1~n)一定是正的
所以把所有可能 profit(n-1~n) 加起來，就一定會是最佳獲利
 

class Solution {

public:

    int maxProfit(vector<int>& prices) {

        int profit = 0;

        if (prices.size() <= 1)

        {

            return profit;

        }

        for (int i=1; i<prices.size(); i++)

        {

            int thisProfit = prices[i] - prices[i-1];

            if (thisProfit > 0)

            {

                profit += thisProfit;

            }

        }

        return profit;

    }

};

參考：https://www.youtube.com/watch?v=akTjUKEP7Co&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=5

283. Move Zeroes

 283. Move Zeroes  (https://leetcode.com/problems/move-zeroes/)

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:
Input: nums = [0]
Output: [0]
 
Constraints:
1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1

 

Follow up: Could you minimize the total number of operations done?

用雙指標
快指標去找出所有非零的元素
逐一的排列到慢指標的位置
最後再從慢指標的位置，把之後的所有元素都設為零
這樣就可以依序保存所有非零的元素
並且把零都挪到陣列末端

class Solution {

public:

    void moveZeroes(vector<int>& nums) {

        if (nums.size() == 1)

            return;

        int i = 0;

        int j = 0;

        while (j < nums.size())

        {

            if (nums[j] != 0)

            {

                nums[i] = nums[j];

                i++;

            }

            j++;

        }

        while(i < nums.size())

        {

            nums[i] = 0;

            i++;

        }

    }

};

參考: https://www.youtube.com/watch?v=vy9QG75U77g&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=4

53. Maximum Subarray

 53. Maximum Subarray  ( https://leetcode.com/problems/maximum-subarray/ )

Given an integer array nums, find the subarray

 with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]

Output: 1

Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]

Output: 23

Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

 

Constraints:

1 <= nums.length <= 10^5

-10^4 <= nums[i] <= 10^4

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

你可以用兩個迴圈 i 代表起點，j 代表終點
求得 i~j 的總和，保留最大的總和
i~j 的總和，可以用 i~(j-1) 的總和 + j
不需要每次都重新算 i+.....+j
這樣時間複雜度約 O(n^2)

class Solution {

public:

    int maxSubArray(vector<int>& nums) {

        int max = INT_MIN;

        for (int i=0; i<nums.size(); i++)

        {

            int sum = 0;

            for (int j=i; j<nums.size(); j++)

            {

                sum += nums[j];

                if (sum > max)

                {

                    max = sum;

                }

            }

        }

        return max;

    }

};

有更快的 O(n) 解法
從第一個元素一路往後逐一加總
如果最大值的序列出現在   i~nums.size()
那就表示 0~(i-1) 的總和是負數
那最大值總和就不需要加上 0~(i-1) 的和
所以當 sum < 0  的時候，就重設 sum = 0
繼續求接下來 i~nums.size() 的總和即可

如果最大值的序列不包含最後一個元素
那表示最後一個元素是負數
i~ (nums.size()-1) 的總和，會 keep 在 max 之中
i~nums.size() 的總和，不會取代成為新的 max
同樣的如果最後 n 個元素的總和是負數
i~ (nums.size()-n) 的總和，會 keep 在 max 之中
i~nums.size() 的總和，不會取代成為新的 max

依此邏輯，只需要依序加總每個元素
當 sum >max，就更新 max
當 sum <0，就設 sum=0
這樣執行一次 for 迴圈，就可以得到最大的子序列和

class Solution {

public:

    int maxSubArray(vector<int>& nums) {

        int max = INT_MIN;

        int sum = 0;

        for (int i=0; i<nums.size(); i++)

        {

            if (sum < 0)

            {

                sum = 0;

            }

            sum += nums[i];

            if (sum > max)

            {

                max = sum;

            }

        }

        return max;

    }

};

這邊要注意一下的是 sum 用 int 即可
因為 nums 內最大值是 10000，最多 100000 個，總和不會超過 1000000000
int 的最大值是2147483647，不會破表，所以用 int 就好

參考:
https://www.youtube.com/watch?v=cL5tRclvvCI&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=3

202. Happy Number

 202. Happy Number    ( https://leetcode.com/problems/happy-number/ )

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.

Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.

Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19

Output: true

Explanation:

1^2 + 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1

Example 2:

Input: n = 2

Output: false

Constraints:

1 <= n <= 2^31 - 1


思路筆記：
首先要能求各位數的平方和
就是要 mod 10 平方
然後除 10，再mod 10 平方....
全部加起來

如果加起來的數字是 1 ，就 return true
要用 Set 記住加起來的數字 sum
如果 sum 曾經出現過，那就是繞回原點了
繼續往下走，也會再繞到這個數字，這樣就 return false

class Solution {

public:

    bool isHappy(int n) {

        set<int> numSet;

        int sum = 0;

        while (numSet.count(sum) == 0)

        {

            numSet.insert(sum);

            sum = 0;

            while (n != 0)

            {

                sum += pow(n % 10, 2) ;

                n /= 10;

            }

            n = sum;

            if (n == 1)

                return true;

        }

        return false;

    }

};

參考: 
https://www.youtube.com/watch?v=sYjmFRujbRI&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=3

136. Single Number

136. Single Number  

( https://leetcode.com/problems/single-number/description/ )

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]

Output: 1

Example 2:

Input: nums = [4,1,2,1,2]

Output: 4

Example 3:

Input: nums = [1]

Output: 1

Constraints:

1 <= nums.length <= 3 * 104

-3 * 104 <= nums[i] <= 3 * 104

Each element in the array appears twice except for one element which appears only once.

思路筆記:
任何數字 XOR 自己，會等於 0

任何數字 XOR 0 會等於自己

所以你只要把陣列裡面所有的數字 XOR 起來

出現兩次的數字就會變成 0

出現一次的數字跟其他的 0，XOR 起來還是原本的數字

那我們就得到答案了

class Solution {

public:

    int singleNumber(vector<int>& nums) {

        int ans = nums[0];

        for(vector<int>::iterator it = nums.begin() + 1; it != nums.end(); it++)

        {

            ans ^= *it;

        }

        return ans;

    }

};

參考：

https://www.youtube.com/watch?v=Hy1hE0HBR3U&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=1