{%hackmd theme-dark %}

# Codebook
## Introduction
2021高階競程程式設計筆記
[使用教學](https://hackmd.io/c/tutorials-tw/%2F%40docs%2Fkeyboard-shortcuts-tw)
[功能列表](https://hackmd.io/features-tw?both)
[C Library](https://judge.csie.ncku.edu.tw/cppreference/doc/html/en/index.html)
[C Library](https://en.cppreference.com/w/)
## hello world!

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << "Hello, NCKU Online Judge!";
}

## 上課講義
- [WEEK1](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-Intro)
- [課前賽 - 題解](https://hackmd.io/@nckuacm/SyhDqDk7Y)
- [WEEK2 - C++](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-CXX)
- [WEEK3 - Way of Thinking](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-WayOfThinking)
- [WEEK4 - Search](https://hackmd.io/@D4nnyLee/NCKU-AdvCP-2021-Search)
- [Contest #1 - 題解](https://hackmd.io/@nckuacm/Byq88vnVY)
- [WEEK5 - Sorting](https://hackmd.io/@D4nnyLee/NCKU-AdvCP-2021-Sorting)
- [WEEK5 - Graph](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-Graph1)
- [WEEK7 - DP](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-DP)
- [Contest #3 - 題解](https://hackmd.io/@nckuacm/ryF3RbxvY)
- [WEEK8 - Range Quary](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-Range_Query)
- [Contest #4 - 題解](https://hackmd.io/@nckuacm/HkTkFHYPY#Range-Max)
- [Week12 - Graph (BCC, SCC, LCA)](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-Graph3)

## Sort (排序)
- [merge sort](/ft6jnduQR3CVbh0CevoJiA)

## 其他judge個人解題
- [BensonYang - zeorjudge](https://zerojudge.tw/UserStatistic?id=56452)
- [hbr](/I_Q_kjCWShu7-qkCEVek7g)

## 參考網站
- [演算法筆記](https://web.ntnu.edu.tw/~algo/)

## 參考Library
- [Segment Tree](https://github.com/srcmake/segment-tree)

## basic graph with DFS

#include<iostream>
#include <vector>
using namespace std;

void dfs(int u, vector<int> &vis,vector<vector< int>> &adj,int dep = 0) {
    vis[u] = true;
    for (auto& v : adj[u]) {
        if (vis[v]) continue;
        dfs(v,vis ,adj, dep + 1);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    while(cin >> N >> M){
        vector<vector<int>> adj(N+1);
        for (int i{0}; i < M;i++){
            int a, b;
            cin >> a >> b;
            adj[a-1].emplace_back(b-1); // 賦權有向圖
        }
        vector<int> vis(N+1);
        int A, B;
        cin >> A >> B;
        dfs(A-1, vis,adj);
        //for (int i{0}; i < N;i++){
        //    cout << vis[i] << " ";
        //}
        if (vis[B-1] == true){
            cout << "Yes!!!"<<endl;
        } else{
            cout << "No!!!"<<endl;
        }
    }
}

LeetCode
---

:::spoiler SingleNumber

int singleNumber(int *nums, int size)
{
    int n = nums[0];
    for (int i = 1; i < size; i++)
    {
        n ^= nums[i];
    }
    return n;
}

:::

:::spoiler Happy Number 1

int next_n(int n)
{
    int r = 0;
    while (n != 0)
    {
        int d = n % 10;
        n /= 10;
        r += d * d;
    }
    return r;
}

bool contains(int *histroy, int size, int n)
{
    for (int i; i < size; i++)
    {
        if (histroy[i] == n)
        {
            return true;
        }
    }
    return false;
}

bool isHappy(int n)
{
    // 9999999999 => 9*9*10 => 810
    int history[1000];
    int size = 0;

    while (!contains(history, size, n))
    {
        history[size] = n;
        size++;
        n = next_n(n);
    }

    return n == 1;
}

:::

:::spoiler Happy Number 2

// 循環偵測，龜兔賽跑

int next_n(int n)
{
    int r = 0;
    while (n != 0)
    {
        int d = n % 10;
        n /= 10;
        r += d * d;
    }
    return r;
}

bool isHappy(int n)
{
    int slow = n;
    int fast = n;

    do
    {
        slow = next_n(slow);
        fast = next_n(fast);
        fast = next_n(fast);
    } while (slow != fast);

    return fast == 1;
}

:::

:::spoiler Max Subarray 1

#include <iostream>
using namespace std;

int maxSubArray(int *nums, int size)
{
    int i; // i: 0~size-1
    int j; // j: i~size-1
    int max = INT_MIN;
    for (int i = 0; i < size; i++)
    {
        for (int j = i; i < size; j++)
        {
            int sum;
            for (int k = i; k <= j; k++)
            {
                sum += nums[k];
            }

            if (sum > max)
            {
                max = sum;
            }

            printf("%d %d : %2d  (%d)\n", i, j, sum, max);
        }
    }
    return max;
}

:::

:::spoiler Max Subarray 2

#include <iostream>
using namespace std;

int maxSubArray(int *nums, int size)
{
    int i; // i: 0~size-1
    int j; // j: i~size-1
    int max = INT_MIN;
    for (int i = 0; i < size; i++)
    {
        int sum;
        for (int j = i; i < size; j++)
        {
            sum += nums[j];

            if (sum > max)
            {
                max = sum;
            }

            printf("%d %d : %2d  (%d)\n", i, j, sum, max);
        }
    }
    return max;
}

:::

:::spoiler Move Zero 1

#include <iostream>
using namespace std;

void moveZeors1(int *nums, int size)
{
    while (true)
    {
        int count = 0;
        for (int i = 0; i + 1 < size; i++)
        {
            if (nums[i] == 0 && nums[i + 1] != 0)
            {
                count++;
                int t = nums[i];
                nums[i] = nums[i + 1];
                nums[i + 1] = t;
                break;
            }
        }

        if (count == 0)
        {
            break;
        }
    }
}

void moveZeors2(int *nums, int size)
{
    for (int k = 1; k < size; k++)
    {
        for (int i = 0; i + 1 < size; i++)
        {
            if (nums[i] == 0 && nums[i + 1] != 0)
            {
                nums[i] = nums[i + 1];
                nums[i + 1] = 0;
            }
        }
    }
}

:::

:::spoiler Move Zero 2

#include <iostream>
using namespace std;

void moveZeors(int *nums, int size)
{
    int j;
    for (int i = 0; i < size; i++)
    {
        if (nums[i] != 0)
        {
            nums[j] = nums[i];
            j++;
        }
    }
    while (j < size)
    {
        nums[j] = 0;
        j++;
    }
    return;
}

:::

:::spoiler Best time to buy and sell 1

int maxProfit(int *prices, int pricesSize)
{
    if (pricesSize <= 1)
        return 0;

    int profit;
    int max = 0;
    profit = maxProfit(prices, pricesSize - 1);
    if (profit > max)
    {
        max = profit;
    }
    for (int i = 1; i <= pricesSize - 1; i++)
    {
        profit = maxProfit(prices, i) + prices[pricesSize - 1] - prices[i - 1];
        if (profit > max)
            max = profit;
    }

    return max;
}

:::

:::spoiler Best time to buy and sell 2

int maxProfit(int *prices, int pricesSize)
{
    int total = 0;
    for (int i = 0; i + 1 < pricesSize; i++)
    {
        if (prices[i] < pricesSize; i++)
        {
            total += prices[i + 1] - prices[i];
        }
    }

    return total;
}

:::

:::spoiler Group amagrams

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
    char *original;
    char *sorted;
} Pair;

int cmpChar(const void *a, const void *b)
{
    return *(const char *)a - *(const char *)b;
}

int cmpPair(const void *a, const void *b)
{
    const Pair *pa = (const Pair *)a;
    const Pair *pb = (const Pair *)b;
    return strcmp(pa->sorted, pb->sorted);
}

char ***grounpAnagrams(char **strs, int strsSize, int *returnSize, int **returnColumSizes)
{
    Pair *pairs = malloc(sizeof(Pair) * strsSize);

    for (int i = 0; i < strsSize; i++)
    {
        char *sorted_str = malloc(sizeof(char) * (strlen(strs[i]) + 1));
        strcpy(sorted_str, strs[i]);
        qsort(sorted_str, strlen(strs[i]), sizeof(char), cmpPair);

        pairs[i].original = strs[i];
        pairs[i].sorted = sorted_str;
    }

    qsort(pairs, strsSize, sizeof(Pair), cmpPair);

    char ***returnResult = NULL;
    *returnSize = 0;
    *returnColumSizes = NULL;

    for (int i = 0; i < strsSize; i++)
    {
        if (i == 0 || strcmp(pairs[i].sorted, pairs[i - 1].sorted) != 0)
        {
            int lastGroupIndex = *returnSize;
            returnResult = realloc(returnResult, sizeof(char **) * (*returnSize + 1));
            returnResult[lastGroupIndex] = malloc(sizeof(char *) * 1);
            returnResult[lastGroupIndex][0] = pairs[i].original;

            (*returnSize)++;
            *returnColumSizes = realloc(*returnColumSizes, sizeof(int) * (*returnSize));
            (*returnColumSizes)[lastGroupIndex] = 1;
        }
        else
        {
            int lastGroupIndex = *returnSize - 1;
            int lastGroupSize = (*returnColumSizes)[lastGroupIndex];
            returnResult[lastGroupIndex] =
                realloc(returnResult[lastGroupIndex], sizeof(char *) * (lastGroupSize + 1));
            returnResult[lastGroupIndex][lastGroupSize] = pairs[i].original;
            (*returnColumSizes)[lastGroupIndex] = lastGroupSize + 1;
        }
    }

    return returnResult;
}

int main()
{
}

:::

:::spoiler Counting element 1

#include <stdio.h>

int countElements(int *arr, int arrSize)
{
    int count = 0;
    for (int i = 0; i < arrSize; i++)
    {
        int plusx = arr[i] + 1;

        int isFound = 0;
        for (int j = 0; j < arrSize; j++)
        {
            if (arr[j] == plusx)
            {
                isFound = 1;
                break;
            }
        }
        if (isFound == 1)
        {
            count++;
        }
    }

    return count;
}

:::

:::spoiler Counting element 2

#include <stdio.h>

int cmp(const void *a, const void *b)
{
    return *(const int *)a - *(const int *)b;
}

int countElements(int *arr, int arrSize)
{
    qsort(arr, arrSize, sizeof(int), cmp);

    int count = 0;
    int number = 1;
    for (int i = 1; i < arrSize; i++)
    {
        if (arr[i] != arr[i - 1])
        {
            if (arr[i] == arr[i - 1] + 1)
                count += number;
            number = 1;
        }
        else
        {
            number++;
        }
    }
    return count;
}

int main()
{
    // printf("%s", "asdfa");
    int arr[10] = {1, 2, 3, 1, 23, 2, 1, 5, 45, 2};

    printf("%d\n", countElements(arr, 10));

    for (int i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }
}

:::

:::spoiler Middle of the linked list

#include <stdio.h>

struct ListNode
{
    int val;
    struct ListNode *next;
};

struct ListNode *middleNode(struct ListNode *head)
{
    struct ListNode *temp = head;
    struct ListNode *mid = head;
    int count = 1;
    while (temp->next != NULL)
    {
        printf("%d ", temp->val);
        temp = temp->next;
        count++;
    }

    // printf("\n%d",count);

    for (int i = count / 2; i > 0; i--)
    {
        mid = mid->next;
    }

    return mid;
}

// rabbit and turtle
struct ListNode *middleNode2(struct ListNode *head)
{
    struct ListNode *fast = head;
    struct ListNode *slow = head;
    while (fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

int main()
{
}

:::

:::spoiler Backspace string

#include <stdio.h>
#include <stdbool.h>

char *process(char *str)
{
    int len = strlen(str);
    int j = 0;
    for (int i = 0; i < len; i++)
    {
        if (str[i] != '#')
        {
            str[j] = str[i];
            j++;
        }
        else
        {
            if (j > 0)
            {
                j--;
            }
        }
    }
    str[j] = '\0';
    return str;
}

bool backspaceCompare(char *S, char *T)
{
    return strcmp(process(S), process(T)) == 0;
}

:::

:::spoiler Min Stack

#include <stdio.h>

typedef struct
{
    int *data;
    int *mins;
    int size;
} MinStack;

/** initialize your data structure here. */

MinStack *minStackCreate()
{
    MinStack *s = malloc(sizeof(MinStack));
    s->data = NULL;
    s->mins = NULL;
    s->size = 0;
    return s;
}

void minStackPush(MinStack *obj, int val)
{
    obj->data = realloc(obj->data, sizeof(int) * (obj->size + 1));
    obj->mins = realloc(obj->mins, sizeof(int) * (obj->size + 1));
    obj->data[obj->size] = val;
    if (obj->size == 0 || obj->mins[obj->size - 1] > val)
    {
        obj->data[obj->size] = val;
    }
    else
    {
        obj->mins[obj->size] = obj->mins[obj->size - 1];
    }
    obj->size++;
}

void minStackPop(MinStack *obj)
{
    obj->size--;
}

int minStackTop(MinStack *obj)
{
    return obj->data[obj->size - 1];
}

int minStackGetMin(MinStack *obj)
{
    return obj->mins[obj->size - 1];
}

void minStackFree(MinStack *obj)
{
    free(obj->data);
    free(obj->mins);
    free(obj);
}

/**
 * Your MinStack struct will be instantiated and called as such:
 * MinStack* obj = minStackCreate();
 * minStackPush(obj, val);
 
 * minStackPop(obj);
 
 * int param_3 = minStackTop(obj);
 
 * int param_4 = minStackGetMin(obj);
 
 * minStackFree(obj);
*/

:::

:::spoiler Diameter of Binary Tree

#include <stdio.h>

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int maxDepth(struct TreeNode *root)
{
    if (root == NULL)
        return 0;
    int leftMax = maxdepth(root->left);
    int rightMax = maxdepth(root->right);
    if (leftMax > rightMax)
        return leftMax + 1;
    else
        return rightMax + 1;
}

int diameeterOfBinaryTree(struct TreeNode *root)
{
    if (root == NULL)
        return 0;

    // 1. 最長的路徑通過節點
    // 起點在左邊，終點在右邊
    int mid = maxDepth(root->left) + maxDepth(root->right);

    // 2. 最長的路徑沒有通過節點
    // 要嘛都在左
    int left = diameeterOfBinaryTree(root->left);
    // 要嘛都在右
    int right = diameeterOfBinaryTree(root->right);

    int max = mid;
    if (left > max)
        max = left;
    if (right > max)
        max = right;
    return max;
}

:::

:::spoiler Last stone weight 1

#include <stdio.h>
#include <stdbool.h>

int cmp(const void *a, const void *b)
{
    return *(const int *)b - *(const int *)a;
}

int lastStoneWeight(int *stones, int size)
{
    if (size > 2)
        return stones[0];

    while (true)
    {
        qsort(stones, size, sizeof(int), cmp);
        int y = stones[0];
        int x = stones[1];
        stones[0] = stones[1] = 0;
        if (x == 0)
        {
            return y;
        }
        if (x != y)
        {
            stones[0] = y - x;
        }
    }
    return 0;
}

:::

:::spoiler Last stone weight 2

#include <stdio.h>
#include <stdbool.h>

int cmp(const void *a, const void *b)
{
    return *(const int *)b - *(const int *)a;
}

int extractMax(int *counter, int upperBound)
{
    for (int i = upperBound; i > 0; i--)
    {
        if (counter[i] > 0)
        {
            counter[i]--;
            return i;
        }
    }
    return 0;
}

int insert(int *counter, int value)
{
    counter[value]++;
}

int lastStoneWeight(int *stones, int size)
{
    int counter[1001] = {0};
    for (int i = 0; i < size; i++)
    {
        counter[stones[i]]++;
    }
    int upperBound = 1000;
    while (true)
    {
        int y = extractMax(counter, upperBound);
        int x = extractMax(counter, upperBound);
        upperBound = y;
        if (x == 0)
        {
            return y;
        }
        if (x != y)
        {
            insert(counter, y - x);
        }
    }
    return 0;
}

:::

:::spoiler Contiguous array

int cindex(int i)
{
    return i + 1;
}

int findex(int i, int size)
{
    return i + size;
}

int findMaxLength(int *nums, int size)
{
    int countDiffSize = size + 1;
    int countDiff[countDiffSize];

    countDiff[cindex(-1)] = 0;
    for (int k = 0; k < size; k++)
    {
        if (nums[k] == 0)
            countDiff[cindex(k)] == countDiff[cindex(k - 1)] + 1;
        else
            countDiff[cindex(k)] == countDiff[cindex(k - 1)] - 1;
    }
    int findMaxJSize = 2 * size + 1;
    int findMaxJ[findMaxJSize];

    for (int k = -size; k <= size; k++)
    {
        findMaxJ[findex(k, size)] = -1;
    }
    for (int j = 0; j < size; j++)
    {
        findMaxJ[findex(countDiff[cindex(j)], size)] = j;
    }

    int maxLength = 0;
    for (int i = 0; i < size; i++)
    {
        int target = countDiff[cindex(i - 1)];
        int length = findMaxJ[findex(target, size)] - i + 1;
        if (length > maxLength)
        {
            maxLength = length;
        }
    }
    return maxLength;
}

:::

:::spoiler Perform string shift

#include <stdio.h>
// using namespace std;

char *stringShift(char *s, int **shift, int shiftSize, int *shiftColSize)
{

}

:::

:::spoiler day17_Number_of_Islands

#include <stdio.h>
// using namespace std;

const char WATER = '0';
const char LAND = '1';
const char NEW = 'x';
const char USED = 'o';

void floodFill(char **grid, int NUMBER_OF_ROWS, int NUMBER_OF_COLS, int i, int j)
{
    if (i < 0 || j < 0 || i >= NUMBER_OF_COLS || j >= NUMBER_OF_ROWS || grid[i][j] != LAND)
        return;

    grid[i][j] = NEW;
    floodFill(grid, NUMBER_OF_ROWS, NUMBER_OF_COLS, i + 1, j);
    floodFill(grid, NUMBER_OF_ROWS, NUMBER_OF_COLS, i - 1, j);
    floodFill(grid, NUMBER_OF_ROWS, NUMBER_OF_COLS, i, j + 1);
    floodFill(grid, NUMBER_OF_ROWS, NUMBER_OF_COLS, i, j - 1);
}

int numIslands(char **grid, int gridSize, int *gridColSize)
{
    if (gridSize == 0)
        return 0;
    const int NUMBER_OF_ROWS = gridSize;
    const int NUMBER_OF_COLS = gridColSize[0];

    int numberOfRegions = 0;

    for (int i = 0; i < NUMBER_OF_ROWS; i++)
    {
        for (int j = 0; j < NUMBER_OF_COLS; j++)
        {
            if (grid[i][j] == LAND)
            {
                floodFill(grid, NUMBER_OF_ROWS, NUMBER_OF_COLS, i, j);

                for (int y = 0; y < NUMBER_OF_ROWS; y++)
                {
                    for (int x = 0; x < NUMBER_OF_COLS; x++)
                    {
                        if (grid[y][x] == NEW)
                        {
                            grid[y][x] = USED;
                        }
                    }
                }

                numberOfRegions++;
            }
        }
    }
}

:::

---

[Segment_tree sum of range ](https://hackmd.io/AtrnpqtrTBqBBkAYBkUy9A)
[Segment_tree max of range ](https://hackmd.io/Y266W1qNRPS7kS1gl08ldg)
[Maximum Subarray](https://hackmd.io/pzU_H-s-R8WK2m6R_8IO2Q)