class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:

        Dict = collections.defaultdict(list)
        Indegree = collections.defaultdict(int)

        for ele in prerequisites:
            Dict[ele[1]].append(ele[0])
            Indegree[ele[0]] += 1

        res = []

        Q = collections.deque([])

        for i in range(numCourses):
            if Indegree[i] == 0:
                Q.append(i)
                del Indegree[i]

        if not Q:
            return res

        while Q:
            parent = Q.popleft()
            res.append(parent)

            for child in Dict[parent]:
                Indegree[child] -= 1
                if Indegree[child] == 0:
                    Q.append(child)

                    del Indegree[child]
        if len(Indegree) > 0:
            return []
        else:
            return res

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

        if len(prerequisites) == 0:
            return True

        Indegree = collections.defaultdict(int)
        Dict = collections.defaultdict(list)

        for ele in prerequisites:
            Dict[ele[1]].append(ele[0])
            Indegree[ele[0]] += 1


        Q = collections.deque([])

        for i in range(numCourses):
            if Indegree[i] == 0:
                Q.append(i)
                del Indegree[i]


        if len(Q) == 0:
            return False

        while Q:
            parent = Q.popleft()

            for child in Dict[parent]:
                Indegree[child] -= 1
                if Indegree[child] == 0:
                    del Indegree[child]
                    Q.append(child)

        if len(Indegree) > 0:
            return False
        else:
            return True

/**
1. 找出s的一个子串是t的最小覆盖集
1.1 -> 判断一个字符串str包含t的所有字符
1.2 -> 让str最小

2. 怎么维护当前字符串包含t?
2.1  先预处理t, 记录一共有total个字符, 并且用map记录每个字符的个数
2.2 遍历字符串str, 如果在map中, map[char]--, 如果 map[char] == 0, 说明该字符完全包含, count++, 
2.3 如果最后 count == total 那么str完全包含t的所有字符

3. 怎么让str最小?
3.1 指针i每次向右扩展一位, 并更新map
3.2 指针j在满足完全覆盖的情况下向右扩展, 向右收缩边界到最小, 同时更新map
3.3 如果满足完全覆盖, 更新结果集l, r


4. 参照: https://www.acwing.com/solution/LeetCode/content/160/
*/

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0) return "";

        Map<Character, Integer> pattern = new HashMap<>();

        int l = 0, r = Integer.MAX_VALUE, total = 0;
        for (int i = 0 ; i < t.length() ; i ++){
            char c = t.charAt(i);
            if (pattern.get(c) == null) {
                pattern.put(c, 0);
                total++;
            }
            pattern.put(c, pattern.get(c) + 1);
        }

        char[] str = s.toCharArray();
        for (int i = 0, j = 0, count = 0; i < str.length; i ++){
            if (pattern.get(str[i]) == null) continue;
            pattern.put(str[i], pattern.get(str[i]) - 1);
            if (pattern.get(str[i]) == 0) count ++ ;

            if (count != total)  continue;
            for ( ; ; j++){
                if (pattern.get(str[j]) == null)  continue;
                if (pattern.get(str[j]) >= 0)     break;
                pattern.put(str[j], pattern.get(str[j]) + 1);
            }

            if (i - j < r - l || r == Integer.MAX_VALUE){
                r = i;
                l = j;
            }
        }

        return r == Integer.MAX_VALUE ? "": s.substring(l, r+1);
    }
}

基于动态规划，k是中间结点，遍历所有可能，更新i,j的距离；

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

const int N = 230;
int d[N][N];
int n, m, k;

void floyd()
{
    for(int k = 1; k <= n; k++ )
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main()
{
    cin>> n >> m >> k;
    memset(d, 0x3f, sizeof d);              //初始化所有点都不通
    for(int i = 1; i <= n; i++) d[i][i] = 0; //初始化自己到自己；如果设成INF，那么最后求出
    int x, y, z;                             //的d[i][i]表示从i出发再回到i的最短距离，
    for(int i = 0; i < m; i++)               //但在这道题目里在查询的时候应该返回0。（引用yxc）
    {
        scanf("%d%d%d", &x, &y, &z);
        d[x][y] = min(d[x][y], z);
    }

    floyd();

    for(int i = 0; i < k; i++)
    {
        scanf("%d%d", &x, &y);
        if(d[x][y] > 0x3f3f3f3f/2) cout<< "impossible" << endl;  //因为存在负边；
        else cout<< d[x][y] << endl;

    }

    return 0;
}

题目描述

blablabla

样例

blablabla

可以这样理解， 当我们求单源的是时候会把d[1]初始化为0，并且放进队列，来更新可以到达它的结点；
现在问图中有没有负权环，图可能不连通，我们不知道是哪个点可以到哪个负权，所以每个点i都初始化d[i]=0;
然后放进队列，做和单源点一样的操作。

C++ 代码

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

const int N = 1e5 + 10;
int h[N], e[N], w[N], ne[N], idx, n, m; 
int d[N], cnt[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

bool spfa()
{
    //不用初始化，因为d[]默认为0；
    queue<int> q;
    for(int i = 1; i <= n; i++)  //每个点都放进队列
    {
        st[i] = true;
        q.push(i);
    }

    while(q.size()){
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(d[j] > d[t] + w[i])
            {
                d[j] = d[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= n) return true;  //对于n个点如果没有环的话，那么只会有n-1条边；由于我们只在
                if(!st[j])                    // if(d[j] > d[t] + w[i])条件下更新，那么如果出现环，
                {                             //这个环一定是可以减小距离的；即负环；
                    q.push(j);
                    st[j] = true;
                }

            }

        }

    }

    return false;
}



int main()
{
    cin>> n >> m;

    memset(h, -1, sizeof h);  //一定要初始化链表头节点；！！！！！！！！！！！
    int a, b, c;
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }

    if( spfa() ) cout<< "Yes";
    else cout<< "No";

    return 0;
}

鄙人才疏学浅，此中鄙陋甚多，望海涵。

题目描述

给定N个闭区间[ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

输入格式
第一行包含整数N，表示区间数。

接下来N行，每行包含两个整数ai,bi，表示一个区间的两个端点。

输出格式
输出一个整数，表示所需的点的最小数量。

数据范围
1≤N≤105,
−109≤ai≤bi≤109

样例

输入样例：
3
-1 1
2 4
3 5
输出样例：
2

这道题目要求在数轴选点，使每个区间至少包含一个点，本质上是说，相交的区间选一点即可，不相交区间须选二点，其实也就是找到最大不相交区间数量（可参考 Acwing 908）

算法1

按照右端点排序

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>

using  namespace std;

const int N=1e5+10;

struct Range
{
    int l,r;
    bool operator< (const Range &W)const
    {
        return r<W.r;
    }
}ranges[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        ranges[i]={l,r};
    }
    sort(ranges,ranges+n);
    int res=0,st=-2e9;
    for(int i=0;i<n;i++)
    {
        if(st<ranges[i].l)
        {
            res++;
            st=ranges[i].r;
        }
    }
    cout<< res <<endl;
    return 0;
}

算法2

按照左端点排序

C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N=1e5+10;

struct Range
{
    int  l,r;
    bool operator <(const Range &W)const
    {
        return l<W.l;
    }
}range[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        range[i]={l,r};
    }
    sort(range,range+n);
    int res=0,st=-2e9;
    for(int i=0;i<n;i++)
    {
        if(st<range[i].l)
        {
            res++;
            st=range[i].r;
        }
        else
        {
            st=min(st,range[i].r);
        }
    }
    printf("%d\n",res);
    return 0;
}

题目描述

blablabla

样例

blablabla

算法1

(qsort) $O(nlogn)$

C++ 代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

int s[2010000];


void quicksort(int l,int r){
    if(l>=r)return;
    int i = l-1,j = r+1;int x = s[(l+r)>>1];
    while(i<j)
    {
        do i++;while(s[i]<x);
        do j--;while(s[j]>x);
        if(i<j)swap(s[i],s[j]);

    }

    quicksort(l,j);
    quicksort(j + 1 ,r);

}

int main(){
    int n;
    scanf("%d",&n);

    for(int i = 0 ; i < n ; i++)
        scanf("%d",&s[i]);

    quicksort(0,n-1);
    int cnt = 0,sum = 0;
    // for (int i = n-1; i >= 0; i -- ) 
     //{
      //   sum+=s[i];
      //   cnt++;
      //   if(sum>=h)
   //         break;
   //  }

    for(int i = 0 ; i < n ; i++)printf("%d ",s[i]);

}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

题目描述

从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

输入格式
两个整数 n,m ,在同一行用空格隔开。

输出格式
按照从小到大的顺序输出所有方案，每行1个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 5 7排在1 3 6 8前面）。

数据范围
n>0 ,
0≤m≤n ,
n+(n−m)≤25

样例

输入样例：
5 3
输出样例：
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 
思考题：如果要求使用非递归方法，该怎么做呢？

算法1

(暴力枚举) $O(n^2)$

C++ 代码

#include<iostream>
using namespace std;

int n,m;
int p[25];
bool vis[20];

void dfs(int u,int start)
{
    if(u+n-start<m)return;
    if(u > m)
    {
        for(int i = 1 ; i <= m ; i++)
            cout<<p[i]<<' ';

        cout<<endl;
        return;
    }

    for(int i = start ; i <= n ; i++)
    {

            p[u] = i;
            dfs(u + 1, i + 1); // 每次从当前已选的数开始选下一个数
            p[u] = 0;

    }
}

int main(){

    cin>>n>>m;

    dfs(1,1);
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

C++ 代码

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

const int N = 10010, M = N * 2;

int h[N], w[M], ne[M], v[M], idx;
int ans;
int n;

void add(int a, int b, int c){
    ++idx;v[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx;
}
//返回从u为起点往下走的最大长度
int dfs(int u, int fa){
    int d1 = -1, d2 = -1;//d1表示从u往下走的第一大长度，d2表示第二大长度
    for(int i = h[u];i;i = ne[i]){
        int k = v[i];
        if(k == fa) continue;//防止往回走

        int d = dfs(k, u) + w[i];

        if(d >= d1) d2 = d1, d1 = d;
        else if (d > d2) d2 = d;
    }
    ans = max(ans, d1 + d2);
    return d1;
}

int main(){
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 1;i <= n-1;++i){
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c);add(b, a, c);
    }
    dfs(1, -1);
    cout << ans << endl;
    return 0;
}

题目描述

你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态

10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011
给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。

输入格式
第一行输入正整数n，代表数据中共有n个待解决的游戏初始状态。

以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。

输出格式
一共输出n行数据，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出“-1”。

数据范围
0<n≤500

样例

数据范围
0<n≤500
输入样例：
3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111
输出样例：

3
2
-1

算法1

(暴力枚举) $O(n^2)$

C++ 代码

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

char map[6][6];
char backup[6][6];

int dx[5]={0,1,0,-1,0},dy[5]={0,0,-1,0,1};

inline bool is_in(int x,int y){
    return x >= 0 && x < 5 && y >= 0 && y < 5;

}

void press(int x,int y)
{
    for(int i = 0 ; i <= 4 ; i++)
    {
        int a = x + dx[i] , b = y + dy[i];
        if(is_in(a,b))
            map[a][b] ^= 1 ;
    }
}

int solve(){

    int res  = 1 << 6;
    for(int op = 0 ; op < (1 << 5) ; op++)
    {
        memcpy(backup,map,sizeof(map));
        int cnt = 0;
        for(int i = 0 ; i < 5 ; i ++)
            if(op >> i & 1)
               {
                   press(0,i);
                    cnt++;
               }

        for(int i = 0 ; i < 4 ; i++)
            for(int j = 0 ; j <= 4 ; j++)
                if(map[i][j] == '0')
                {
                    press(i + 1 , j);
                    cnt++;
                }
        bool sucess = true;    
        for(int i = 0 ; i <= 4 ; i ++)
            if(map[4][i] == '0')
                sucess = false;

        if(sucess)
            res = min(res,cnt);

        memcpy(map,backup,sizeof(backup));
    }

    if(res <= 6)
        return res;
    else
        return -1;
}

int main(){
    int n;
    cin>>n;

    while(n--)
    {
        for(int i = 0 ; i < 5 ; i++)
            cin>>map[i];

        cout<<solve()<<endl;

    }


    return 0;
}