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

Hello ninja and GYP

My English is not good to describe what is ninja and GYP, so I just list all steps that building a 'hello world' with these tools on Ubuntu.

1. Install ninja
    sudo apt-get install ninja

2. Install GYP
    sudo apt-get install gyp

3. Create a C file
    vi hello.c

with following content

#include <stdio.h>

int main(void)

{

    printf("Hello, world!\n");

    return 0;

}

4. Create GYP file for generating build.ninja or Makefile
    vi hello.gyp

with following content

{

    'targets': [

    {

        'target_name': 'hello',

            'type': 'executable',

            'sources': [

                'hello.c'

            ],

    },

    ],

}

5. Generate build.ninja file
    gyp hello.gyp --depth=. --generator-output=release -f ninja

    for generate Makefile
    gyp hello.gyp --depth=. --generator-output=release

6. Build with ninja
    ninja -C ./release/out/Default/ all

7. Execute
    ./release/out/Default/hello

8. You'll see output

Hello, world!

Reference:
http://erikge.com/articles/HelloGyp/

Add hard disk to Virtualbox

Add new SCSI hard disk to your setting and start Virtual Machine

Check disk partition
# sudo fdisk -l
Disk /dev/sdb: 17.2 GB, 17179869184 bytes
255 heads, 63 sectors/track, 2088 cylinders, total 33554432 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x00000000
Disk /dev/sdb doesn't contain a valid partition table

New hd is mount at /dev/sdb, it need to create new partition by fdisk
# sudo fdisk /dev/sdb
Device contains neither a valid DOS partition table, nor Sun, SGI or OSF disklabel
Building a new DOS disklabel with disk identifier 0x68da59e5.
Changes will remain in memory only, until you decide to write them.
After that, of course, the previous content won't be recoverable.
Warning: invalid flag 0x0000 of partition table 4 will be corrected by w(rite)
Command (m for help): n
Partition type:
p primary (0 primary, 0 extended, 4 free)
e extended
Select (default p): p
Partition number (1-4, default 1):
Using default value 1
First sector (2048-33554431, default 2048):
Using default value 2048
Last sector, +sectors or +size{K,M,G} (2048-33554431, default 33554431):
Using default value 33554431
Command (m for help): w
The partition table has been altered!
Calling ioctl() to re-read partition table.
Syncing disks.

Check partition again
# sudo fdisk -l
Disk /dev/sdb: 17.2 GB, 17179869184 bytes
171 heads, 2 sectors/track, 98112 cylinders, total 33554432 sectors
Units = sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disk identifier: 0x68da59e5
Device Boot Start End Blocks Id System
/dev/sdb1 2048 33554431 16776192 83 Linux

Format disk
# sudo mkfs -t ext4 /dev/sdb1
mke2fs 1.42 (29-Nov-2011)
Filesystem label=
OS type: Linux
Block size=4096 (log=2)
Fragment size=4096 (log=2)
Stride=0 blocks, Stripe width=0 blocks
1048576 inodes, 4194048 blocks
209702 blocks (5.00%) reserved for the super user
First data block=0
Maximum filesystem blocks=4294967296
128 block groups
32768 blocks per group, 32768 fragments per group
8192 inodes per group
Superblock backups stored on blocks:
32768, 98304, 163840, 229376, 294912, 819200, 884736, 1605632, 2654208,
4096000
Allocating group tables: done
Writing inode tables: done
Creating journal (32768 blocks): done
Writing superblocks and filesystem accounting information: done

Mount disk
# sudo mkdir /data
# sudo mount /dev/sdb1 /data

Set auto mount and reboot
# sudo vi /etc/fstab
/dev/sdb1 /data auto defaults,auto,noatime,nodiratime 0 0

Different between const int * , int const * and int * const

* Question: 

What different between const int * , int const * , int * const ?

* Answer: 

• int*                                                           - pointer to int
• const int * == int const *                     - pointer to const int
• int * const - const pointer to int
• const int * const == int const * const - const pointer to const int

• int **                       - pointer to pointer to int
• int ** const             - a const pointer to a pointer to an int
• int * const *           - a pointer to a const pointer to an int
• int const **            - a pointer to a pointer to a const int
• int * const * const - a const pointer to a const pointer to an int

* Reference: 

http://stackoverflow.com/questions/1143262/what-is-the-difference-between-const-int-const-int-const-int-const

Difference between std::thread and pthread

* Question: 

What are the differences between std::thread and pthread

* Answer: 

The std::thread library is implemented on top of pthreads in an environment supporting pthreads 

std::thread provides portability across different platforms like Windows, MacOS, and Linux, but may not be complete on all platforms yet.

The C++11 std::thread class unfortunately doesn't work reliably (yet) on every platform, even if C++11 seems available.

* Reference: 

http://stackoverflow.com/questions/13134186/c11-stdthreads-vs-posix-threads

Difference between size_t and std::size_t

* Question: 

What are the differences between size_t and std::size_t

* Answer: 

C's size_t and C++'s std::size_t are both same.

In C, it's defined in <stddef.h> and in C++, its defined in <cstddef> whose contents are the same 

as C header (see the quotation below). Its defined as unsigned integer type of the result of the 

sizeof operator.

* Reference: 

http://stackoverflow.com/questions/5813700/difference-between-size-t-and-stdsize-t