yangpeng-chn

// BFS
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph(numCourses, vector<int>());
    vector<int> in(numCourses);
    for (auto a : prerequisites) {
        graph[a[0]].push_back(a[1]);
        ++in[a[1]];
    }
    queue<int> q;
    for (int i = 0; i < numCourses; ++i) {

yangpeng-chn

int V = 6;    // No. of vertices
list<int> *adj = new list<int>[V];  // Pointer to an array containing adjacency list (adj[0]-adj[5])

void topologicalSortUtil(int v, bool visited[], stack<int>& s) 
{ 
    visited[v] = true; 
  
    // Recur for all the vertices adjacent to this vertex 
    for (list<int>::iterator i = adj[v].begin(); i != adj[v].end(); ++i) 
        if (!visited[*i]) 

yangpeng-chn

class MedianFinder {
private:
    priority_queue<int> lomax;
    priority_queue<int, vector<int>, greater<int>> himin;
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    

yangpeng-chn

ListNode *reverseBetween(ListNode *head, int m, int n) {
    ListNode dummy(-1), *pre = &dummy;
    dummy.next = head;
    for (int i = 0; i < m - 1; ++i) pre = pre->next;
    ListNode *cur = pre->next;
    for (int i = m; i < n; ++i) {
        ListNode *t = cur->next;
        cur->next = t->next;
        t->next = pre->next;
        pre->next = t;

yangpeng-chn

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            swap(nums[i], nums[nums[i] - 1]);
        }
    }
    for (int i = 0; i < n; ++i) {
        if (nums[i] != i + 1) return i + 1;
    }

yangpeng-chn

bool canPartition(vector<int>& nums) {
    const int sum = std::accumulate(nums.begin(), nums.end(), 0);
    if(sum % 2 != 0) return false;
    vector<bool> dp(sum+1, false);
    dp[0] = true;
    for( const int num : nums){
        for(int i = sum; i >= 0; i--){
            if(dp[i]) dp[i+num]=true;
        }
        if(dp[sum/2])

yangpeng-chn

// Iteration
int knapSack(int v[], int w[], int n, int W) //Values, Weights, Number of distinct item, Knapsack capacity
{
    // T[i][j] stores the maximum value that can be attained with
    // weight less than or equal to j using items up to first i items
    int T[n+1][W+1];
    for (int j = 0; j <= W; j++)
        T[0][j] = 0;
    // or memset (T[0], 0, sizeof T[0]);

yangpeng-chn

// min-heap
int kthSmallest(vector<vector<int>>& matrix, int k) {
    typedef pair<int, pair<int,int>> ppi;
    priority_queue<ppi, vector<ppi>, greater<ppi>> pq; //greater<ppi> will sort by ppi.first in ascending order
    for(int i = 0; i < matrix.size(); i++){
        pq.push(make_pair(matrix[i][0], make_pair(i, 0)));
        // or pq.push( {matrix[i][0], {i, 0} });
    }
    int i = 0, j = 0;
    while(!pq.empty() && k!=0){

yangpeng-chn

// min-heap
ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto comp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
    priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> pq(comp);
    ListNode dummy(0);
    ListNode *cur = &dummy;
    for(ListNode *list : lists){
        if(list) pq.push(list);
    }
    while(!pq.empty()){

yangpeng-chn

//max heap
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> um;
    for(auto num : nums)
        um[num]++;
    vector<int> res;
    priority_queue<pair<int,int>>pq; //max heap
    for(auto it = um.begin(); it != um.end(); it++){
        pq.push(make_pair(it->second, it->first)); //(occurence, element), sort by occurence
        if(pq.size() > um.size() - k){ //um.size() is the number of unique element, 1 <= k <= um.size().