<repo_name>weixr18/LeetCode<file_sep>/src/22_brackets.cpp
/*
22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

/*
    思路：
    等效成二维平面上等腰直角三角形内的曼哈顿寻路问题
    用一个栈辅助，做深度优先搜索，遍历所有可能路径。
*/

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

struct State
{
    int x;
    int y;
    char *path;
    int p; //pointer

    State(int _x, int _y)
    {
        x = _x;
        y = _y;
        path = nullptr;
        p = 0;
    }

    bool operator==(State &s)
    {
        return (this->x == s.x) && (this->y == s.y);
    }
};

template <typename T>
class Stack
{
public:
    T *b; //base
    T *t; //top
    int count;

    Stack(int capacity)
    {
        b = new T[capacity];
        t = b;
        count = 0;
    }

    ~Stack()
    {
        delete[] b;
    }

    void push(T &a)
    {
        *t = a;
        t++;
        count++;
    }

    T pop()
    {
        if (count > 0)
        {
            t--;
            count--;
            return *t;
        }
        else
        {
            throw out_of_range("Stack reached bottom");
        }
    }

    int size()
    {
        return count;
    }
};

class Solution
{
public:
    vector<string> generateParenthesis(int n)
    {
        vector<string> *results = new vector<string>();
        Stack<State *> st(n);

        State *cur_state = new State(0, 0);
        cur_state->path = new char[2 * n];

        State final_state = State(n, n);
        int cur_x;
        int cur_y;

        while (true)
        {
            cur_x = cur_state->x;
            cur_y = cur_state->y;

            if (cur_x == n)
            {
                if (*cur_state == final_state)
                {
                    if (cur_state->p != 2 * n)
                    {
                        throw logic_error("path should be n characters.");
                    }
                    string s = string(cur_state->path, 2 * n);
                    //cout << s << endl;
                    results->push_back(s);

                    delete[] cur_state->path;
                    cur_state->path = nullptr;
                    delete cur_state;

                    if (st.size() > 0)
                    {
                        cur_state = st.pop();
                    }
                    else
                    {
                        break;
                    }
                }
                else
                {
                    for (int i = cur_state->p; i < 2 * n; i++)
                    {
                        cur_state->path[i] = ')';
                    }
                    cur_state->p = 2 * n;
                    cur_state->y = n;
                }
            }
            else if (cur_x == cur_y)
            {
                cur_state->x += 1;
                cur_state->path[cur_state->p] = '(';
                cur_state->p++;
            }
            else
            {
                State *new_state = new State(cur_x, cur_y + 1);
                new_state->path = new char[2 * n];

                memcpy(new_state->path, cur_state->path, cur_state->p);
                new_state->path[cur_state->p] = ')';
                new_state->p = cur_state->p;
                new_state->p += 1;
                st.push(new_state);

                cur_state->x += 1;
                cur_state->path[cur_state->p] = '(';
                cur_state->p++;
            }
        }

        return *results;
    }
};

int main()
{
    try
    {
        Solution s;
        s.generateParenthesis(10);
    }
    catch (exception e)
    {
        cout << e.what() << endl;
    }

    return 0;
}
<file_sep>/note.md
# Notes

## Trivial

### 1 两数之和

+ 题目
  + 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
+ 思路
  + 带index排序 O(nlogn)
  + 带指针扫描 O(n)

### 866 回文素数

+ 题目
  + 求出大于或等于 N 的最小回文素数。
+ 思路
  1. 拿到最小回文基，依次递增找回文数
  2. 模6+方根法判断是否素数

### O07 重构二叉树

+ 题目
  + 先序遍历和中序遍历重构二叉树
+ 思路
  + 先序遍历最左侧为当前子树根节点。在中序遍历中看到该节点时，说明此时应该生长其右子树。
  + 用栈依次保存根节点。

## Medium

### 22 括号生成

+ 题目
  + 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
+ 思路
  + 等效成二维平面上等腰直角三角形内的曼哈顿寻路问题。
  + 用一个栈辅助，做深度优先搜索，遍历所有可能路径。

### 51 逆序对个数

+ 题目
  + 求给定数组逆序对个数
+ 思路
  + 归并排序 O(nlogn)

## Star

### O41 数据流中位数

+ 题目
  + 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
+ 思路
  + 双堆
    + 一个大顶堆保存较小的一半，一个小顶堆保存较大的一半
    + O(log n)

### O04 有序二维数组查找

+ 题目
  + 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
+ 思路
  + 从右上角开始，大于往左，小于往下，等于返回true，走到左下角返回false。

### 53 最大子数组和

+ 题目
  + 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
+ 思路
  + **线段树**
    + 每个线段维护4个值：左起最大和，右起最大和，总最大和，总和，遍历更新即可。O(log n)

### 300 最长上升子序列

+ 题目
  + 给定一个无序的整数数组，找到其中最长上升子序列的长度。
+ 思路
  + O(n^2) DP
    + 每个位置存储一个数：以该位置数结尾的上升子序列的最大长度
    + 从前到后遍历[0,i]的位置，获取第i+1位置的最大长度
    + 所有最大长度之最大值即为解
  + **O(nlogn) 贪心二分**
    + 记录每个长度对应的上升子序列的最小终值
    + 对于第i个位置，要么增长最长可能长度（比所有最小终值都大），要么更新某个最小终值

### 523 连续的子数组和

+ 题目
  + 给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组**是否**含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
+ 思路
  + 最暴力
    + 对所有可能求和，O(n^3)
  + less 暴力
    + 用O(n^2)空间保存之前的所有子组和，O(n^2)
  + **Hashmap**
    + 若有[a_i, a_j]连续和模k余0，则必有[0, a_i]和[0, a_j]模k相同。
    + 用Hashmap保存每一个从头开始的连续和模k余数，重复即确定含有。

### O39 超过一半的数字

+ 题目
  + 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
+ 思路
  + Hash
    + 时间复杂度O(n) 空间复杂度O(n)
  + **摩尔投票法**
    + 众数票数为1，非众数票数为-1.由题，总票数为正
    + 若把某非众数的数当做众数
      + 当正负相消时，要么消了偶数票负数，要么消了0，即总票数仍为正，真正的众数仍为众数
      + 根据题目条件，一定可以相消
    + 因此可以无脑选众数，相消就换。最终剩下的数一定是众数。
<file_sep>/src/866_round_prime.cpp
/*866. 回文素数

求出大于或等于 N 的最小回文素数。
回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。
例如，2，3，5，7，11 以及 13 是素数。
回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。
例如，12321 是回文数。

*/

#include <cmath>
#include <iostream>

bool isPrime(int num)
{
    if (num == 2 || num == 3 || num == 5)
        return true;
    unsigned long c = 7;
    if (num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num == 1)
        return false;
    int maxc = int(sqrt(num));
    while (c <= maxc)
    {
        if (num % c == 0)
            return false;
        c += 4;
        if (num % c == 0)
            return false;
        c += 2;
        if (num % c == 0)
            return false;
        c += 4;
        if (num % c == 0)
            return false;
        c += 2;
        if (num % c == 0)
            return false;
        c += 4;
        if (num % c == 0)
            return false;
        c += 6;
        if (num % c == 0)
            return false;
        c += 2;
        if (num % c == 0)
            return false;
        c += 6;
    }
    return true;
}

int my_pow10(int n)
{
    if (n == 0)
    {
        return 1;
    }
    else if (n == 1)
    {
        return 10;
    }
    else if (n == 2)
    {
        return 100;
    }
    else if (n == 3)
    {
        return 1000;
    }
    else if (n == 4)
    {
        return 10000;
    }
    else if (n == 5)
    {
        return 100000;
    }
    else if (n == 6)
    {
        return 1000000;
    }
    else if (n == 7)
    {
        return 10000000;
    }
    else if (n == 8)
    {
        return 100000000;
    }
    else if (n == 9)
    {
        return 1000000000;
    }
    return -1;
}

class Solution
{
public:
    int getRound(int base, int d)
    {
        int sum = 0;
        int N = base * my_pow10(d / 2);
        sum += N;
        for (int i = 0; i < d / 2; i++)
        {
            sum += ((N / my_pow10(d - 1 - i)) % 10) * (my_pow10(i));
        }
        return sum;
    }

    int primePalindrome(int N)
    {
        int n_copy = N;
        int d = 0;

        //int num[10] = {0};

        while (n_copy > 0)
        {
            //num[d] = n_copy % 10;
            n_copy = n_copy / 10;
            d++;
        }

        int base = (N / my_pow10(d / 2));

        int current = getRound(base, d);
        if (N > current)
        {
            if (base < (my_pow10((d + 1) / 2) - 1))
            {
                base++;
                current = getRound(base, d);
            }
            else
            {
                if (d % 2 == 0)
                {
                    base++;
                    d++;
                    current = getRound(base, d);
                }
                else
                {
                    base = (base++) / 10;
                    d++;
                    current = getRound(base, d);
                }
            }
        }

        while (!isPrime(current))
        {
            if (base < (my_pow10((d + 1) / 2) - 1))
            {
                base++;
                current = getRound(base, d);
            }
            else
            {
                if (d % 2 == 0)
                {
                    base++;
                    d++;
                    current = getRound(base, d);
                }
                else
                {
                    base = (base++) / 10;
                    d++;
                    current = getRound(base, d);
                }
            }
        }

        return current;
    }
};

/*
int main()
{
    Solution s;
    int n;

    //s.primePalindrome(456);

    while (true)
    {
        std::cin >> n;
        std::cout << s.primePalindrome(n) << std::endl;
    }

    return 0;
}
*/<file_sep>/src/983_min_cost_for_tickets.cpp
/*
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。
在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。
每一项是一个从 1 到 365 的整数。

火车票有三种不同的销售方式：

    一张为期一天的通行证售价为 costs[0] 美元；
    一张为期七天的通行证售价为 costs[1] 美元；
    一张为期三十天的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。 
例如，如果我们在第 2 天获得一张为期 7 天的通行证，
那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。

 
示例 1：
输入：days = [1,4,6,7,8,20], costs = [2,7,15]
输出：11
解释： 
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
你总共花了 $11，并完成了你计划的每一天旅行。

示例 2：
输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出：17
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 
在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。
在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。 
你总共花了 $17，并完成了你计划的每一天旅行。

 
提示：
    1 <= days.length <= 365
    1 <= days[i] <= 365
    days 按顺序严格递增
    costs.length == 3
    1 <= costs[i] <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-cost-for-tickets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

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

class Solution
{
public:
    int mincostTickets(vector<int> &days, vector<int> &costs)
    {
        return 0;
    }
};<file_sep>/src/1_two_sum.cpp
/*
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

/*
    思路：
    1. 带index排序 O(nlogn)
    2. 双指针扫描 O(n)
*/

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

template <class T>
class Stack
{
public:
    Stack(int n);
    ~Stack();
    void push(const T &t);
    T top();
    T pop();
    int size();
    int isEmpty();

private:
    T *arr;
    int count;
};

template <class T>
Stack<T>::Stack(int n)
{
    arr = new T[n];
    count = 0;
    if (!arr)
    {
        cout << "arr malloc error!" << endl;
    }
}
template <class T>
Stack<T>::~Stack()
{
    if (arr)
    {
        delete[] arr;
        arr = NULL;
    }
}

template <class T>
void Stack<T>::push(const T &t)
{
    arr[count] = t;
    count++;
}

template <class T>
T Stack<T>::top()
{
    return arr[count - 1];
}

template <class T>
T Stack<T>::pop()
{
    int ret = arr[count - 1];
    count--;
    return ret;
}

template <class T>
int Stack<T>::size()
{
    return count;
}

template <class T>
int Stack<T>::isEmpty()
{
    return size() == 0;
}

class Solution
{
public:
    struct pair
    {
        int num;
        int index;
    };

    vector<int> twoSum(vector<int> &nums, int target)
    {
        pair *num_and_index = new pair[nums.size()];

        for (int i = 0; i < nums.size(); i++)
        {
            num_and_index[i].num = nums[i];
            num_and_index[i].index = i;
        }

        quickSortNonRecursive(num_and_index, 0, nums.size() - 1);

        for (int i = 0; i < nums.size(); i++)
        {
            cout << num_and_index[i].num << ' ';
        }

        int lo = 0;
        int hi = nums.size() - 1;

        while (lo < hi)
        {
            while (num_and_index[hi].num > target - num_and_index[lo].num && lo < hi)
            {
                hi--;
            }
            if (num_and_index[hi].num == target - num_and_index[lo].num)
            {
                return vector<int>({num_and_index[lo].index, num_and_index[hi].index});
            }
            while (num_and_index[lo].num < target - num_and_index[hi].num && lo < hi)
            {
                lo++;
            }
            if (num_and_index[hi].num == target - num_and_index[lo].num)
            {
                return vector<int>({num_and_index[lo].index, num_and_index[hi].index});
            }
        }
        return vector<int>({num_and_index[lo].index, num_and_index[hi].index});
    }

    int getPartition(pair *pairs, int lo, int hi)
    {
        pair keyVal = pairs[lo];
        while (lo < hi)
        {
            while (lo < hi && pairs[hi].num >= keyVal.num)
                hi--;
            pairs[lo] = pairs[hi];
            while (lo < hi && pairs[lo].num <= keyVal.num)
                lo++;
            pairs[hi] = pairs[lo];
        }
        pairs[lo] = keyVal;
        return lo;
    }

    void quickSortNonRecursive(pair *pairs, int lo, int hi)
    {
        Stack<int> s(hi + 1); //hi+1 is length.
        if (lo < hi)
        {
            int mid = getPartition(pairs, lo, hi);
            if (mid - 1 > lo)
            {
                s.push(lo);
                s.push(mid - 1);
            }
            if (mid + 1 < hi)
            {
                s.push(mid + 1);
                s.push(hi);
            }

            while (!s.isEmpty())
            {
                int qhi = s.top();
                s.pop();
                int plo = s.top();
                s.pop();
                int pqMid = getPartition(pairs, plo, qhi);
                if (pqMid - 1 > plo)
                {
                    s.push(plo);
                    s.push(pqMid - 1);
                }
                if (pqMid + 1 < qhi)
                {
                    s.push(pqMid + 1);
                    s.push(qhi);
                }
            }
        }
    }
};

int main()
{

    vector<int> nums = vector<int>({3, 2, 4});
    int target = 6;

    Solution solution;
    auto a = solution.twoSum(nums, target);

    cout << endl;
    cout << a[0] << a[1];
    return 0;
}
