头像

一万小时定律

菜鸡罢了,欢迎互关




在线 


最近来访(234)
用户头像
Yuyi
用户头像
gzxxy
用户头像
NO.1-Finn
用户头像
生在逢时
用户头像
冰之韵
用户头像
_叽嘻嘻_
用户头像
disheng
用户头像
LonelyLove
用户头像
Cold_heartless
用户头像
山东交通大学
用户头像
种花家的兔兔
用户头像
yao云
用户头像
仙女的笨蛋涛
用户头像
rarestark
用户头像
学不明白啊
用户头像
我要出去乱说
用户头像
lixiaoqian
用户头像
铁锅炖大鹅
用户头像
稚于初心
用户头像
1357649762

活动打卡代码 AcWing 1098. 城堡问题

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second

typedef pair<int ,int > PII;

const int N = 55 ,M = N * N;

int n,m;
int g[N][N];
PII q[M];
bool st[N][N];

int bfs(int sx,int sy)
{
    int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};

    int hh=0,tt=0;
    int area =0;
    q[0] ={sx,sy};
    st[sx][sy] =true;

    while(hh<=tt)
    {
        PII t = q[hh++];
        area ++;
        for(int i=0;i<4;i++)
        {
            int a=t.x + dx[i],b=t.y+dy[i];
            if(a<0||a>=n||b<0||b>=m) continue;
            if(st[a][b]) continue;
            if(g[t.x][t.y]>>i&1 ) continue;

            q[++tt] = {a,b};
            st[a][b] = true;
        }
    }
    return area;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> g[i][j];

    int cnt = 0, area = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (!st[i][j])
            {
                area = max(area, bfs(i, j));
                cnt ++ ;
            }

    cout << cnt << endl;
    cout << area << endl;

    return 0;
}



题目链接

#include<bits/stdc++.h>
#define x first  
#define y second 

using namespace std;

typedef pair<int, int> PII;  //pair记录坐标

const int N = 1010,M = N * N;

int n, m;  
char g[N][N];
PII q[M];  //队列
bool st[M][N];
//使用一次得到一个连通块
void Flood_Fill(int x, int y)
{
    int hh = 0, tt = -1;//定义队头队尾

    q[ ++ tt] = {x, y};//把这个要搜的点先放到队列和st判重数组里
    st[x][y] = true;

    while(hh <= tt) 
    {
        pair<int, int> t = q[hh ++];//弹出队头
        //拓展队头我们使用循环,最后把中间那个点扣掉
        for(int i = t.first - 1; i <= t.first + 1; i ++)
        {
            for(int j = t.second - 1; j <= t.second + 1; j ++)
            {
                if(g[i][j] == '.') continue;
                //如果这个点不是水洼,那这个点不行
                if(i < 0 || i >= n || j < 0 || j >= m) continue;
                //如果这个点越界,那也不行
                if(st[i][j]) continue;
                //如果已经被搜到,不行
                if(i == t.first && j == t.second) continue;
                //如果当前这个点是中间
                q[ ++ tt] = {i, j};
                //放进队列
                st[i][j] = true;
                //标记判重数组
            }
        }
    }
    //一切完毕
}
int bfs()
{
    int cnt = 0;
    //定义cnt
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            if(g[i][j] == 'W') 
            {
                //这个点必须是水洼才可以开始Flood_Fill
                if(!st[i][j])
                {
                    //这个点必须还没有搜过
                    //可以开始Flood_Fill
                    Flood_Fill(i, j);
                    //cnt ++
                    cnt ++;
                }
            }
        }
    }
    //最后返回cnt
    return cnt;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++) scanf("%s", g[i]);
    //输入
    cout << bfs() << endl;
    //直接输出bfs
    return 0;
}

y总板子

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n, m;
char g[N][N];
PII q[M];
bool st[N][N];

void bfs(int sx, int sy)
{
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    st[sx][sy] = true;

    while (hh <= tt)
    {
        PII t = q[hh ++ ];

        for (int i = t.x - 1; i <= t.x + 1; i ++ )
            for (int j = t.y - 1; j <= t.y + 1; j ++ )
            {
                if (i == t.x && j == t.y) continue;
                if (i < 0 || i >= n || j < 0 || j >= m) continue;
                if (g[i][j] == '.' || st[i][j]) continue;

                q[ ++ tt] = {i, j};
                st[i][j] = true;
            }
    }
}

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

    int cnt = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == 'W' && !st[i][j])
            {
                bfs(i, j);
                cnt ++ ;
            }

    printf("%d\n", cnt);

    return 0;
}


活动打卡代码 AcWing 1097. 池塘计数

#include<bits/stdc++.h>
#define x first  
#define y second 

using namespace std;

typedef pair<int, int> PII;  //pair记录坐标

const int N = 1010,M = N * N;

int n, m;  
char g[N][N];
PII q[M];  //队列
bool st[M][N];
//使用一次得到一个连通块
void Flood_Fill(int x, int y)
{
    int hh = 0, tt = -1;//定义队头队尾

    q[ ++ tt] = {x, y};//把这个要搜的点先放到队列和st判重数组里
    st[x][y] = true;

    while(hh <= tt) 
    {
        pair<int, int> t = q[hh ++];//弹出队头
        //拓展队头我们使用循环,最后把中间那个点扣掉
        for(int i = t.first - 1; i <= t.first + 1; i ++)
        {
            for(int j = t.second - 1; j <= t.second + 1; j ++)
            {
                if(g[i][j] == '.') continue;
                //如果这个点不是水洼,那这个点不行
                if(i < 0 || i >= n || j < 0 || j >= m) continue;
                //如果这个点越界,那也不行
                if(st[i][j]) continue;
                //如果已经被搜到,不行
                if(i == t.first && j == t.second) continue;
                //如果当前这个点是中间
                q[ ++ tt] = {i, j};
                //放进队列
                st[i][j] = true;
                //标记判重数组
            }
        }
    }
    //一切完毕
}
int bfs()
{
    int cnt = 0;
    //定义cnt
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            if(g[i][j] == 'W') 
            {
                //这个点必须是水洼才可以开始Flood_Fill
                if(!st[i][j])
                {
                    //这个点必须还没有搜过
                    //可以开始Flood_Fill
                    Flood_Fill(i, j);
                    //cnt ++
                    cnt ++;
                }
            }
        }
    }
    //最后返回cnt
    return cnt;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++) scanf("%s", g[i]);
    //输入
    cout << bfs() << endl;
    //直接输出bfs
    return 0;
}

y总板子

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

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n, m;
char g[N][N];
PII q[M];
bool st[N][N];

void bfs(int sx, int sy)
{
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    st[sx][sy] = true;

    while (hh <= tt)
    {
        PII t = q[hh ++ ];

        for (int i = t.x - 1; i <= t.x + 1; i ++ )
            for (int j = t.y - 1; j <= t.y + 1; j ++ )
            {
                if (i == t.x && j == t.y) continue;
                if (i < 0 || i >= n || j < 0 || j >= m) continue;
                if (g[i][j] == '.' || st[i][j]) continue;

                q[ ++ tt] = {i, j};
                st[i][j] = true;
            }
    }
}

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

    int cnt = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            if (g[i][j] == 'W' && !st[i][j])
            {
                bfs(i, j);
                cnt ++ ;
            }

    printf("%d\n", cnt);

    return 0;
}



便于复习

#include<iostream>
#include<cstring>

using namespace std;

const int N = 510, M = 10010;

struct Edge {
    int a;
    int b;
    int w;
} e[M];//把每个边保存下来即可
int dist[N];
int back[N];//备份数组防止串联
int n, m, k;//k代表最短路径最多包涵k条边

int bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < k; i++) {//k次循环
        memcpy(back, dist, sizeof dist);
        for (int j = 0; j < m; j++) {//遍历所有边
            int a = e[j].a, b = e[j].b, w = e[j].w;
            dist[b] = min(dist[b], back[a] + w);
            //使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
        }
    }
    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    else return dist[n];

}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        e[i] = {a, b, w};
    }
    int res = bellman_ford();
    if (res == -1) puts("impossible");
    else cout << res;

    return 0;
}




数组模拟

import java.util.*;
public class Main {
    static int q[],hh,tt,N = 100010;

    static {
        q = new int[N];
        hh = 0;
        tt = -1;
    }

    static void push(int x){
        q[++tt] = x;
    }

    static int pop(){
        return q[hh++];
    }

    static int query(){
        return q[hh];
    }

    static boolean empty(){
        return hh > tt;
    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();

        while(m -- >= 0 ) {
            String[] s = sc.nextLine().split(" ");
            if(s[0].equals("push")) {
                push(Integer.parseInt(s[1]));
            }else if(s[0].equals("pop")) {
                pop();
            }else if(s[0].equals("empty")) {
                if(empty()) System.out.println("YES");
                else System.out.println("NO");
            }else if(s[0].equals("query")) {
                System.out.println(query());
            }
        }
    }
}

API

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            if("push".equals(s)){
                int x = sc.nextInt();
                q.add(x);
            } else if ("pop".equals(s)) {
                q.remove();
            } else if ("empty".equals(s)) {
               if(q.isEmpty()) System.out.println("YES");
               else System.out.println("NO");
            }else if ("query".equals(s)){
                System.out.println(q.peek());
            }
        }
    }
}



数组模拟

import java.util.Scanner;

public class Main {

    public static int N = (int) 1e5 + 10, top = 0;
    public static int[] stack = new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();

        while (m-- > 0){
            String op = sc.next();
            if ("push".equals(op)){
                int x = sc.nextInt();
                push(x);
            }else if ("pop".equals(op)){
                pop();
            }else if ("empty".equals(op)){
                System.out.println(isEmpty());
            }else {
                System.out.println(query());
            }
        }
        sc.close();
    }

    public static void push(int x){
        stack[++top] = x;
    }

    public static void pop(){
        top--;
    }

    public static String isEmpty(){
        return top == 0 ? "YES" : "NO";
    }

    public static int query(){
        return stack[top];
    }
}

API

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Stack<Integer> stk = new Stack<>();
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            if("push".equals(s)){
                int x = sc.nextInt();
                stk.push(x);
            } else if ("pop".equals(s)) {
                stk.pop();
            } else if ("empty".equals(s)) {
               if(stk.empty()) System.out.println("YES");
               else System.out.println("NO");
            }else ("query".equals(s)){
                System.out.println(stk.peek());
            }
        }
    }
}



迭代思路

翻转即将所有节点的next指针指向前驱节点。
由于是单链表,我们在迭代时不能直接找到前驱节点,所以我们需要一个额外的指针保存前驱节点。同时在改变当前节点的next指针前,不要忘记保存它的后继节点。

c4c62eb9aace26751ab1a46a7e0ca0c.png
51d8497751b8f9b41a76cc7603df611.png

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

递归思路

efb9091b81a025ed0019356c23ef32c.png
ee6b5d532cdecd961e02a2bdcb283ae.png
581841eb99d407c19b6b84f4d816358.png

首先我们先考虑 reverseList 函数能做什么,它可以翻转一个链表,并返回新链表的头节点,也就是原链表的尾节点。
所以我们可以先递归处理 reverseList(head->next),这样我们可以将以head->next为头节点的链表翻转,并得到原链表的尾节点tail,此时head->next是新链表的尾节点,我们令它的next指针指向head,并将head->next指向空即可将整个链表翻转,且新链表的头节点是tail。
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)return head;
        ListNode tail = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return tail;
    }
}


活动打卡代码 AcWing 35. 反转链表

迭代思路

翻转即将所有节点的next指针指向前驱节点。
由于是单链表,我们在迭代时不能直接找到前驱节点,所以我们需要一个额外的指针保存前驱节点。同时在改变当前节点的next指针前,不要忘记保存它的后继节点。

c4c62eb9aace26751ab1a46a7e0ca0c.png
51d8497751b8f9b41a76cc7603df611.png

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

递归思路

efb9091b81a025ed0019356c23ef32c.png
ee6b5d532cdecd961e02a2bdcb283ae.png
581841eb99d407c19b6b84f4d816358.png

首先我们先考虑 reverseList 函数能做什么,它可以翻转一个链表,并返回新链表的头节点,也就是原链表的尾节点。
所以我们可以先递归处理 reverseList(head->next),这样我们可以将以head->next为头节点的链表翻转,并得到原链表的尾节点tail,此时head->next是新链表的尾节点,我们令它的next指针指向head,并将head->next指向空即可将整个链表翻转,且新链表的头节点是tail。
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)return head;
        ListNode tail = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return tail;
    }
}



由于是单链表,我们不能找到前驱节点,所以我们不能按常规方法将该节点删除。
我们可以换一种思路,将下一个节点的值复制到当前节点,然后将下一个节点删除即可。

c851ff27e5e6c15e32cccfafb447d49.png
f97525f0eb628c17b85cd1acc171d9b.png

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        ListNode p = node.next;
        node.val=p.val;
        node.next=p.next;
    }
}



迭代思路

翻转即将所有节点的next指针指向前驱节点。
由于是单链表,我们在迭代时不能直接找到前驱节点,所以我们需要一个额外的指针保存前驱节点。同时在改变当前节点的next指针前,不要忘记保存它的后继节点。

c4c62eb9aace26751ab1a46a7e0ca0c.png
51d8497751b8f9b41a76cc7603df611.png

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

递归思路

efb9091b81a025ed0019356c23ef32c.png
ee6b5d532cdecd961e02a2bdcb283ae.png
581841eb99d407c19b6b84f4d816358.png

首先我们先考虑 reverseList 函数能做什么,它可以翻转一个链表,并返回新链表的头节点,也就是原链表的尾节点。
所以我们可以先递归处理 reverseList(head->next),这样我们可以将以head->next为头节点的链表翻转,并得到原链表的尾节点tail,此时head->next是新链表的尾节点,我们令它的next指针指向head,并将head->next指向空即可将整个链表翻转,且新链表的头节点是tail。
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null)return head;
        ListNode tail = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return tail;
    }
}