头像

PP帮主


访客:603

离线:10天前


活动打卡代码 AcWing 1490. 最长上升子串

PP帮主
2个月前
import java.io.*;
import java.util.*;

class Main{
    static final int N = 100010;
    static int[] a = new int[N];
    //以i结尾的最长上升子串的长度
    static int[] f = new int[N];
    //以i开头的最长上升子串的长度
    static int[] g = new int[N];
    static int n;

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        n = Integer.parseInt(s1);
        String[] s2 = br.readLine().split(" ");
        for(int i = 1;i<=n;i++){
            a[i] = Integer.parseInt(s2[i-1]);
        }
        for(int i = 1;i<=n;i++){
            if(a[i]>a[i-1]) f[i] = f[i-1]+1;
            else f[i] = 1;
        }
        for(int i = n;i>=1;i--){
            if(a[i+1]>a[i]) g[i] = g[i+1]+1;
            else g[i] = 1;
        }
        int res = 0;
        for(int i = 1;i<=n;i++){
            if(a[i-1]<a[i+1]) res = Math.max(res,f[i-1]+g[i+1]);
            else res = Math.max(res,Math.max(f[i-1],g[i+1]));
        }
        System.out.print(res);
    }
}


活动打卡代码 AcWing 1259. 二叉树遍历

PP帮主
2个月前
import java.io.*;
import java.util.*;

class Main{
    static final int N = 30;
    static char[] inorder = new char[N];
    static char[] lorder = new char[N];
    static boolean[] st = new boolean[N];
    static Map<Character,Integer> map = new HashMap();
    static int n;

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();
        n = s1.length();
        for(int i = 0;i<n;i++){
            inorder[i] = s1.charAt(i);
            lorder[i] = s2.charAt(i);
            map.put(inorder[i],i);
        }
        ArrayDeque<Node> ad = new ArrayDeque();
        Node root = new Node(lorder[0]);
        ad.add(root);
        for(int i = 0,j = 1;j<n;){
            for(int end = j;i<end;i++){
                Node node = ad.pop();
                int p = map.get(lorder[i]);
                st[p] = true;
                if(p!=0&&!st[p-1]){
                    node.left = new Node(lorder[j++]);
                    ad.add(node.left);
                }
                if(p+1<n&&!st[p+1]){
                    node.right = new Node(lorder[j++]);
                    ad.add(node.right);
                }
            }
        }
        System.out.print(dfs(root));
    }
    static String dfs(Node root){
        if(root==null) return "";
        String res = root.val+"";
        res += dfs(root.left);
        res += dfs(root.right);
        return res;
    }
}
class Node{
    char val;
    Node left;
    Node right;
    public Node(char val){
        this.val = val;
    }
}


活动打卡代码 AcWing 1491. 圆桌座位

PP帮主
2个月前
import java.io.*;
import java.util.*;

class Main{
    static final int N = 11;
    static boolean[][] g = new boolean[N][N];
    static boolean[] st = new boolean[N];
    static int[] pos = new int[N];
    static int n,m;

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        while(m--!=0){
            s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            g[a][b] = g[b][a] = true;
        }
        pos[0] = 1;
        st[1] = true;
        System.out.print(dfs(1));

    }
    static int dfs(int u){
        if(u==n){
            if(g[pos[n-1]][pos[0]]) return 0;
            return 1;
        }
        int res = 0;
        for(int i = 1;i<=n;i++){
            if(!st[i]&&!g[i][pos[u-1]]){
                st[i] = true;
                pos[u] = i;
                res += dfs(u+1);
                st[i] = false;
            }
        }
        return res;
    }
}



PP帮主
2个月前
class Solution {
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        boolean[][] f = new boolean[n+1][m+1];
        f[0][0] = true;
        for(int i = 2;i<=m;i++){
            if(p.charAt(i-1)=='*'){
                f[0][i] = f[0][i-2];
            }
        }
        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=m;j++){
                if((s.charAt(i-1)==p.charAt(j-1))||(p.charAt(j-1)=='.')) f[i][j] = f[i-1][j-1];
                else if(p.charAt(j-1)=='*'){
                    if(s.charAt(i-1)==p.charAt(j-2)||p.charAt(j-2)=='.') f[i][j] = f[i][j-1]||f[i-1][j]||f[i][j-2];
                    else if(s.charAt(i-1)!=p.charAt(j-2)) f[i][j] = f[i][j-2];
                }
            }
        }
        return f[n][m];
    }
}


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

PP帮主
2个月前
/**
 * 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 node = new ListNode(0);
        while(head!=null){
            ListNode temp = head.next;
            head.next = node.next;
            node.next = head;
            head = temp;
        }
        return node.next;
    }
}


活动打卡代码 AcWing 1048. 鸡蛋的硬度

PP帮主
2个月前
import java.io.*;
import java.util.*;

class Main{
    static final int N = 110;
    static final int M = 11;
    //用j个鸡蛋测量i次的集合,属性为最多能测多长的区间
    static int[][] f = new int[N][M];
    static int n,m;

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        while(!(s==null)){
            String[] s1 = s.split(" ");
            int n = Integer.parseInt(s1[0]);
            int m = Integer.parseInt(s1[1]);
            for(int i = 1;i<=n;i++){
                for(int j = 1;j<=m;j++){
                    //上下两种情况,碎了可能的长度加上没碎的长度再加上测的那值
                    f[i][j] = f[i-1][j-1]+f[i-1][j]+1;
                }
                if(f[i][m]>=n){
                    System.out.println(i);
                    break;
                }
            }
            s = br.readLine();
        }
    }
}



PP帮主
2个月前
// The query API is defined in the parent class Getvalue:
// int query(int x, int y);
// return int means matrix[x][y].

class Solution extends Getvalue {
    final int INT = Integer.MAX_VALUE;
    public int[] getMinimumValue(int n) {
        int l = 0;
        int r = n-1;
        while(l<r){
            int mid = (l+r)/2;
            int res = INT;
            int k = 0;
            for(int i = 0;i<n;i++){
                int x = query(i,mid);
                if(res>x){
                    res = x;
                    k = i;
                }
            }
            if(query(k,mid-1)>res&&query(k,mid+1)>res) return new int[] {k,mid};
            if(query(k,mid-1)<res) r = mid-1;
            else l = mid+1;
        }
        int res = INT;
        int k = 0;
        for(int i = 0;i<n;i++){
                int x = query(i,l);
                if(res>x){
                    res = x;
                    k = i;
                }
            }
        return new int[] {k,l};
    }
}



PP帮主
2个月前
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode quickSortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode left = new ListNode(-1);
        ListNode mid = new ListNode(-1);
        ListNode right = new ListNode(-1);
        ListNode ltail = left,mtail = mid,rtail = right;
        int a = head.val;
        while(true){
            if(head == null) break;
            if(head.val<a){
                ltail.next = head;
                ltail = ltail.next;
            }else if(head.val == a){
                mtail.next = head;
                mtail = mtail.next;
            }else if(head.val > a){
                rtail.next = head;
                rtail = rtail.next;
            }
            head = head.next;
        }
        ltail.next = mtail.next = rtail.next = null;
        left.next = quickSortList(left.next);
        right.next = quickSortList(right.next);
        get_tail(left).next = mid.next;
        get_tail(left).next = right.next;
        return left.next;
    }
    static ListNode get_tail(ListNode node){
        while(node.next!=null){
            node = node.next;
        }
        return node;
    }
}


活动打卡代码 AcWing 756. 蛇形矩阵

PP帮主
2个月前
import java.io.*;
import java.util.*;

class Main{
    static final int N = 110;
    static int[][] res = new int[N][N];
    static int n,m;

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        int[] dx = {0,1,0,-1};
        int[] dy = {1,0,-1,0};
        for(int a = 0,b = 0,k = 1,d = 0;k<=n*m;k++){
            res[a][b] = k;
            int x = a+dx[d],y = b+dy[d];
            if(x>=n||y>=m||x<0||y<0||res[x][y]!=0){
                d = (d+1)%4;
                x = a+dx[d];
                y = b+dy[d];
            }
            a = x;b = y;
        }
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                System.out.print(res[i][j]+" ");
            }
            System.out.println();
        }
    }
}


活动打卡代码 AcWing 1072. 树的最长路径

PP帮主
3个月前
import java.io.*;
import java.util.*;

class Main{
    static final int N = 10010;
    static Node[] nodes = new Node[N];
    static int n;
    static int ans = 0;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        for(int i = 1;i<=n;i++){
            nodes[i] = new Node(i);
        }
        for(int i = 1;i<=n-1;i++){
            String[] s = br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            add(a,b,c);
        }
        dfs(1,-1);
        System.out.print(ans);
    }
    static void add(int a,int b,int c){
        nodes[a].neighbors.put(nodes[b],c);
        nodes[b].neighbors.put(nodes[a],c);
    }
    static int dfs(int u,int father){
        int d1 = 0;
        int d2 = 0;
        for(Map.Entry<Node,Integer> entry:nodes[u].neighbors.entrySet()){
            Node node = entry.getKey();
            if(node.val == father){
                continue;
            }
            int t = entry.getValue();
            int d = dfs(node.val,u)+t;
            nodes[u].dist = Math.max(nodes[u].dist,d);
            if(d>=d1){
                d2 = d1;
                d1 = d;
            }else if(d>d2){
                d2 = d;
            }
        }
        ans = Math.max(ans,d1+d2);
        return nodes[u].dist;
    }
}
class Node{
    int val;
    int dist;
    Map<Node,Integer> neighbors;
    public Node(int x){
        val = x;
        dist = 0;
        neighbors = new HashMap();
    }
}