# LeetCode | Data Structure I | 14 Days Challenge | Day 3-4
###### tags: `LeetCode` `Data Structure I` `14 Days Challenge`
## Day 3

### [350. Intersection of Two Arrays II](https://leetcode.com/problems/intersection-of-two-arrays-ii/?envType=study-plan&id=data-structure-i)

### 題目敘述

>*Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.*

### 測資

Example 1:
:::info
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
:::

Example 2:
:::info
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.
:::

### 核心概念

==map、unordered_map==

### 數值範圍

1 <= nums1.length, nums2.length <= 1000
0 <= nums1\[i], nums2\[i] <= 1000

### 想法

一樣用map輕鬆做~

***time : 12 mins
time complexity : $O(m+n)$
space complexity : $O(m+n)$
(m = nums1.length, n =nums2.length)***

### 程式碼

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;
        unordered_map<int,int> mp;
        int len1 = nums1.size(), len2 = nums2.size();

        for(int i=0;i<len1;i++){
            if(!mp[nums1[i]])
                mp[nums1[i]] = 1;
            else
                mp[nums1[i]]++;
        }

        for(int i=0;i<len2;i++){
            if(mp[nums2[i]]){
                mp[nums2[i]]--;
                ans.push_back(nums2[i]);
            }
        }

        return ans;
    }
};

### [121. Best Time to Buy and Sell Stock](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/?envType=study-plan&id=data-structure-i)

### 題目敘述

>*You are given an array prices where prices[i] is the price of a given stock on the ith day.*

>*You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.*

>*Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.*

### 測資

Example 1:
:::info
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
:::

Example 2:
:::info
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
:::

### 核心概念

==DP==

### 數值範圍

1 <= prices.length <= 10^5^
0 <= prices\[i] <= 10^4^

### 想法

又到了地獄的DP環節了~

第一種解法：

首先，判斷最大值(maxx)最小值(minn)，如果當前的值大於maxx，代表可以賣了！並且求maximum；如果當前的值小於minn，代表該買了！***但是之前的maxx則要作廢***，不然你就會變穿越時空賣股票了，**因此將maxx和minn皆設為當前的值**。

第二種解法(參考大佬)：

判斷買的最小值(買的值, 當前的值)
判斷最大利潤(先前最大利潤, 當前的值 - 買的最小值)

簡潔好懂，大佬我跪了。

***time : 20 mins
time complexity : $O(n)$
space complexity : $O(1)$***

### 程式碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minn = prices[0], maxx = prices[0];
        int ans = 0;
        int len = prices.size();

        for (int i = 1; i < len; i++) {
            if (prices[i] > maxx) {
                maxx = prices[i];
                ans = max(ans, maxx - minn);
            }
            else if (prices[i] < minn) {
                maxx = prices[i];
                minn = prices[i];
            }
        }
        
        return ans;
    }
};

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxpro = 0, buy = INT_MAX;
        for(int i : prices){
            buy = min(buy, i);
            maxpro = max(maxpro, i - buy);
        }
        
        return maxpro;
    }
};

## Day 4

### [566. Reshape the Matrix](https://leetcode.com/problems/reshape-the-matrix/?envType=study-plan&id=data-structure-i)

### 題目敘述

>*You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.*

>*The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.*

>*If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.*

### 測資

Example 1:


:::info
Input: mat = [[1,2],[3,4]], r = 1, c = 4
Output: [[1,2,3,4]]
:::

Example 2:


:::info
Input: mat = [[1,2],[3,4]], r = 2, c = 4
Output: [[1,2],[3,4]]
:::

### 核心概念

==二維陣列、二維vector==

### 數值範圍

m == mat.length
n == mat[i].length
1 <= m, n <= 100
-1000 <= mat[i][j] <= 1000
1 <= r, c <= 300

### 想法

很單純的"reshape"，分享兩種解法。

第一種解法：
賦值，到底了就換行，比較直觀。

第二種解法：
不直觀，但簡潔。
公式 : $result[i/c][i\%c]=mat[i/n][i\%n]$

***time : 10 mins
time complexity : $O(m*n)$
space complexity : $O(m*n)$***

### 程式碼

class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
        int mat_r = mat.size(), mat_c = mat[0].size();
        if (mat_r * mat_c != r * c) return mat;

        vector<vector<int>> res(r, vector<int>(c));
        int res_r = 0, res_c = 0;
        for (int i = 0; i < mat_r;i++) {
            for (int j = 0; j < mat_c; j++) {
                res[res_r][res_c++] = mat[i][j];
                if (res_c >= c) {
                    res_r++;
                    res_c = 0;
                }
            }
        }

        return res;
    }
};

class Solution {
public:
	vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
		int m = mat.size(), n = mat[0].size();
		if (m*n != r*c) return mat;
		
		vector<vector<int>> result(r, vector<int>(c));
		for (int i = 0;i < m*n;i++) {
			result[i / c][i % c] = mat[i / n][i % n];
		}
		return result;
	}
};

### [118. Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/?envType=study-plan&id=data-structure-i)

### 題目敘述

>*Given an integer numRows, return the first numRows of Pascal's triangle.

>*In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:*


### 測資

Example 1:

:::info
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
:::

Example 2:

:::info
Input: numRows = 1
Output: [[1]]
:::

### 核心概念

==DP、二維vector==

### 數值範圍

1 <= numRows <= 30

### 想法

相對簡單的DP，令人開心不已。
仔細觀察就會發現規律(i=row, j=column):

if (!j || j == i) pascal[i].push_back(1);
else pascal[i].push_back(pascal[i-1][j-1] + pascal[i - 1][j]);

當j=0 or j=i時，pascal.num = 1;
否則，pascal[i][j] = pascal[i-1][j-1]+pascal[i-1][j]

***time : 10 mins
time complexity : $O(n^2)$
space complexity : $O(n^2)$***

==實際為 N*(N+1)/2==

### 程式碼

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> pascal(numRows);

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j <= i; j++) {
                if (!j || j == i) 
                    pascal[i].push_back(1);
                else 
                    pascal[i].push_back(pascal[i-1][j-1] + pascal[i - 1][j]);
            }
        }

        return pascal;
    }
};