算法笔记 | WuRui

resource

OI Wiki
OI Wiki 致力于成为一个免费开放且持续更新的编程竞赛 (competitive programming) 知识整合站点。

code

// 删除重复元素
ListNode* method(ListNode* head)
{
    ListNode* res = new ListNode(0);
    res->next = head;
    ListNode* cur = head;
    while(cur->next && cur->next->next)
    {
        if(cur->next->val == cur->next->next->val)
        {
            int val = cur->next->val;
            while(cur->next && cur->next->next->val)
                cur->next =  cur->next->next;
        }
        else
            cur = cur->next;
    }
    return res->next;
}
// 重复元素 保留一个
ListNode* method(ListNode* head)
{
    if(!head) return head;
    ListNode* cur = head;
    while(cur && cur->next)
    {
        if (cur->val == cur->next->val)
        {
            cur->next = cur->next->next;
        }
        else
            cur = cur->next;
    }
    return head;
}

// binarysearch
int bsearch(vector<int> nums, int target)
{
    int l = 0;
    int r =  nums.size();
    while(l<=r)
    {
        int m = (l+r)/2
        if (nums[m] == target)
            return m;
        if (nums[m] < target)
            l = m + 1;
        else
            r = m - 1;
    }
    return -1;
}

// level order
vector<vector<int>> levelOrder(TreeNode* root)
{
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty)
    {
        int size = q.size();
        vector<int> cur;
        for(int i=0;i<size;i++)
        {
            TreeNode* node = q.front();
            q.pop();
            cur.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(cur);
    }
    return res;
}

// 之字打印
// level order
vector<vector<int>> levelOrder(TreeNode* root)
{
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    int level = 0;
    while(!q.empty)
    {
        int size = q.size();
        vector<int> cur;
        for(int i=0;i<size;i++)
        {
            TreeNode* node = q.front();
            q.pop();
            cur.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        if (level % 2 != 0)
            reverse(cur.begin(), cur.end());
        res.push_back(cur);
        level++;
    }
    return res;
}

// isValidBst
int pre = INT_MIN;
bool isValidBst(TreeNode* root);
{
    if(!root) return true;
    if (!isValidBst(root->left)) return false;
    if (root->val <= pre) return false;
    pre = root->val;
    if (!isValidBst(root->right)) return false;
    return true;
}

// bubblesort
void bubblesort(int arr[], int n)
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n-1-i;j++)
            if (arr[j] > arr[j+1])
                std::swap(arr[j], arr[j+1]);
}

// selectsort
void selectsort(int arr[], int n)
{
    for(int i=0;i<n-1;i++)
    {
        int min = i;
        for(int j=i+1;j<n;j++)
            if (arr[j] < arr[min])
                min = j
        std::swap(arr[i], arr[min]);
    }
}

// insertsort
void insertsort(int arr[], int n)
{
    for(int i=1;i<len;i++)
    {
        int key = arr[i];
        int j = i-1;
        while((j>0) && (key< arr[j]))
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

// quicksort
int part(int A[], int low, int high)
{
    int pivot = A[low];
    while(low < high)
    {
        while(low < high && A[high] >= pivot) --high;
        A[low] = A[high];
        while(low < high && A[low] <= pivot) ++low;
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}

void quicksort(int A[], int low, int high)
{
	if (low >= high) return;
	int pivot = part(A, low, high);
	quicksort(A, low, pivot - 1);
	quicksort(A, pivot + 1, high);
}

// quicksort all in one
void quicksort(int arr[], int low, int high)
{
	if (low >= high) return;
	int i=low, j=high, index = arr[i];
	while(i<j)
	{
		while(i<j && arr[j] >= index)--j;
		arr[i] = arr[j];
		while(i<j && arr[i] <= index)++i;
		arr[j] = arr[i];
	}
	arr[i] = index;
	quicksort(arr, low, i-1);
	quicksort(arr, i+1, high);
}

void test()
{
    int arr[] = {3,1,4,6,2};
    quicksort(arr, 0, 4);
    for(auto ele:arr)
    {
        printf("%d\n", ele);
    }
}

// merge sort
void merge(vector<int>& nums, int low, int mid, int high)
{
    int i = low, j = mid + 1;
    int index = 0;
    vector<int> arr(nums.size());
    while(i<= low && j <= high)
    {
        if (nums[i]<=nums[j]) arr[index++] = nums[i++];
        else arr[index++] = nums[j++];
    }
    while(i<=low) arr[index++] = nums[i++];
    while(j<=high) arr[index++] = nums[j++];
    for(int i=0;i<index;i++)
    {
        nums[low] = arr[i];
    }
}

void mergesort(vector<int>& nums, int left, int right)
{
    if (left>=right) return;
    int mid = (left + right)/2;
    mergesort(nums, left, mid);
    mergesort(nums, mid+1, right);
    merge(nums, left, mid, right);
}

// heapsort
void heap(int arr[], int start, int end)
{
    int dad = start;
    int son = dad*2 + 1;
    while(son <= end)
    {
        if (son+1<=end&& arr[son] < arr[son+1]) son++;
        if (arr[dad] > arr[son]) return;
        else{
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad*2 + 1;
        }
    }
}

void heapsort(int arr[], int len)
{
    for(int i=len/2-1;i>=0;i--)
        heap(arr, i, len - 1);
    for(int i=len-1; i>0;i--)
    {
        swap(arr[0], arr[i]);
        heap(arr, 0, i-1);
    }
}

// tree height / depth
void depth(TreeNode* root)
{
	if(!root) return 0;
	return max(depth(root->left), detph(root->right)) + 1;
}

// big add
string add(string a, string b)
{
    int an = a.size();
    int bn = b.size();
    int l = max(an, bn);
    string ans;
    int d = 0;
    for(int i=0;i<l;i++)
    {
        if (i<an) d += a[an-1-i] - '0';
        if (i<bn) d + b[bn-1-i] - '0';
        ans += d%10 + '0';
        d/=10;
    }
    if (d) ans += d + '0';
    reverse(ans.begin(), ans.end())
    return ans;
}

// big sub
string sub(string a, string b)
{
    int an =  a.size();
    int bn =  b.size();
    int l =  max(an, bn);
    string ans;
    int borrow = 0;
    for(int i=0;i<l;i++)
    {
        int d = a[an-1-i] - '0';
        d -= borrow;
        borrow = 0;
        if (i < bn)
        {
            int s = b[bn-1-i] - '0';
            if (d<s) borrow=1, d+=10;
            d -= s;
        }
        if (d<0) borrow=1, d+=10;
        if (d>=0) ans += d + '0';
    }
    while(ans.back() == '0') ans.pop_back();
    reverse(ans.begin(), ans.end());
    return ans;
}

string substring(string a, string b)
{
    if (a.size() > b.size()) return sub(a,b);
    if (a.size() < b.size()) return "-" + sub(b,a);
    if (a>b) return sub(a,b);
    if (a<b) return "-" + sub(a,b);
    return "0";
}

// quickselect / findK
// 改进 BFPRT算法 -> https://www.cnblogs.com/ldy-miss/p/12031077.html
void part(int arr[], int l, int h)
{
    int p = arr[l];
    while(l<h)
    {
        while(l<h && a[h]>=p) --h;
        a[l]=a[h];
        while(l<h && a[l]<=p) ++l;
        a[h]=a[l];
    }
    a[l]=p;
    return l;
}

int quickselect(int arr[], int left, int right, k)
{
    k = n - k;
    while(left<right)
    {
        if (left == right) return arr[k];
        int p = part(arr, left, right);
        if (k==p) return arr[k];
        if (k<p) right = p - 1;
        else left = p + 1;
    }
    return arr[k];
}

int findk(int arr[], int n, int k)
{
	return quickselect(arr, n-1, k);
}

// perm
void dfs(string num, int idx)
{
    if(idx == num.size() - 1) 
    {
        cout << num << end;
        return;
    }
    for(int i=idx;i<num.size();i++)
    {
        swap(num[i], num[idx]);
        dfs(num, idx + 1);
        swap(num[i], num[idx]);
    }
}
void perm(string num)
{
    dfs(num, 0);
}

// iter remove
void remote_iter()
{
    std::list<int> l = {1,2,3,4,3,5,6};
    for(auto s = l.begin();s!=l.end();s++)
    {
        if (3==*s) s=l.erase(s);
    }
    for(auto ele:l) cout << ele << endl;
}

topsort

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

int main() 
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>>dp(n + 1);
    vector<int>d(n + 1);
    queue<int> que;
    vector<int>res;
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        int tmp1, tmp2;
        cin >> tmp1;
        cin >> tmp2;
        dp[tmp1].push_back(tmp2);
        d[tmp2]++;
    }

    for (int i = 1; i <= n; i++) {
        if (d[i] == 0) 
            que.push(i);
    }
    while (!que.empty()) {
        int u = que.front();
        res.push_back(u);
        que.pop();
        for (int i:dp[u]) {
            if (--d[i] == 0) {
                que.push(i);
            }
        }
        cnt++;
    }
    if (cnt != n) {
        cout << -1;
        return 0;
    }
    cout << res[0];
    for (int i = 1; i < res.size(); i++) {
        cout << " " << res[i];
    }
    cout << endl;
    return 0;
}