算法-(2018-11-14) Sliding Window&Dijkstra枚举

Posted on
sliding window leetcode 239

https://leetcode.com/problems/sliding-window-maximum/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
method 1: time complexity O(Nlog(k))

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        
        multiset<int>st;
        vector<int>vec;
        list<int> lst;
        for(int i=0;i<nums.size();i++){
            if(i-k>=0){
                int top = lst.front();
                lst.pop_front();
                st.erase(st.find(top));
            }
         
            lst.push_back(nums[i]);
            st.insert(nums[i]);
              if(i-k>=-1){
                vec.push_back(*st.rbegin());
            }
            
        }
        
        return vec;
        
    }
};


method 2

1. use a deque to store the index in the window , each window must fall in the range(i-k+1,i). so whenever an index smaller than i-k+1,pop_front() to discard the element; 

2. when insert a new element nums[i], compare it with the top of the queue , until q[front]>nums[i] ,that is to say, q[front] is always the max element in the window

  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
       
         deque<int>dq;
         vector<int>res;
         if(nums.empty())
             return res;
         for(int i=0;i<nums.size();i++){
            while(!dq.empty()&&dq.front()<i-k+1){
                dq.pop_front();
            }
            //remove smaller elements in window
            while(!dq.empty()&&nums[dq.back()]<=nums[i]){
                dq.pop_back();
            }
             dq.push_back(i);
             if(i-k+1>=0){
                 res.push_back(nums[dq.front()]);
             }
         }
         return res;
        
    }

这里sliding window就是移动窗口的时候，每次把最左边的值pop掉，然后不断比较最右边的值与新插入的值，保证新插入的值是最好的candidate，那么窗口最左边的值就会是最大值。

Kattis

#include

#include

#include

#include

#include

#include

#include

using namespace std;

struct edge{
int from;
int to;
int weight;
};

typedef pair<int,int> ip;

#define INF 0x3f3f3f3f

void dijkstra(vector<vector>&adj,vector&dist,int source){

priority_queue<ip,vector<ip>,greater<ip>> q;
q.push({0,source});
dist[source] = 0;
while(!q.empty()){
    auto top = q.top();
    q.pop();
    int u = top.second;
    for(auto p:adj[u]){
        int v = p.first;
        int weight = p.second;
        if(dist[v]==INF||dist[v]>dist[u]+weight){
            dist[v] = dist[u]+weight;
            q.push(make_pair(dist[v],v));
        }
    }
}

}

https://open.kattis.com/problems/flowerytrails

对于有多条最短路，并且求所有最短路的路径之和

1.分别对起始点和终点跑DIjkstra

2.枚举每一条初始点与终点分别到这条边距离，分别为d1,d2，如果d1+d2+w==shortestPath,则ans+=w;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int main(){

    int P,T;
    cin>>P>>T;
    vector<vector<ip>> adj(P);
    vector<vector<ip>> parent(P);
    vector<int>distStart(P,INF);
    vector<int>distEnd(P,INF);
    vector<tuple<int,int,int>>edgeVec;

    for(int i=0;i<T;i++){
        int from,to,w;
        cin>>from>>to>>w;
        edgeVec.push_back(make_tuple(from,to,w));
        adj[from].push_back(make_pair(to,w));
        adj[to].push_back(make_pair(from,w));
    }

    dijkstra(adj,distStart,0);
    dijkstra(adj,distEnd,P-1);

    int shortestPath = distStart[P-1];
    int ans=0;
    for(int i=0;i<T;i++){
        int from = get<0>(edgeVec[i]);
        int to = get<1>(edgeVec[i]);
        int weight = get<2>(edgeVec[i]);

        if(distStart[to]+distEnd[from]+weight==shortestPath||
        distStart[from]+distEnd[to]+weight==shortestPath){
            ans+=weight;
        }

    }

    cout<<ans*2;

    return 0;
}