头像

三玖天下第一




离线:17天前



class Solution {
    public ListNode copyRandomList(ListNode head) {
        if (head == null) return null;
        HashMap<ListNode, ListNode> pos = new HashMap<ListNode, ListNode>();
        pos.put(null,null);
        for(ListNode p = head; p != null; p = p.next){
            pos.put(p, new ListNode(p.val));
        }
        for (ListNode p = head; p != null; p = p.next){
            pos.get(p).next = pos.get(p.next);
            pos.get(p).random = pos.get(p.random);
        }
        return pos.get(head);
    }
}



import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine().trim());
        String[] temp = reader.readLine().split(" ");
        int[] h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = Integer.parseInt(temp[i]);
        }
        int l = 0, r = 100000;
        while(l < r){
            int mid = (l + r) >> 1;
            int e = mid;
            for (int i = 0; i < n && e >= 0 && e <= 100000; i++) {
                e = 2*e - h[i];
            }
            if (e < 0) l = mid + 1;
            else r = mid;
        }
        System.out.println(l);
    }
}



import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] temp =reader.readLine().split(" ");
        int n = Integer.parseInt(temp[0]), m = Integer.parseInt(temp[1]);
        int[][] f = new int[n+1][m+1];
        int res = 0;
        for (int i = 1; i <=n; i++) {
            temp = reader.readLine().split(" ");
            for (int j = 1; j <=m; j++) {
                f[i][j] = Integer.parseInt(temp[j-1]);
                if (f[i][j] == 1){
                    f[i][j] = Math.min(Math.min(f[i-1][j], f[i][j-1]), f[i-1][j-1]) + 1;
                    res = Math.max(res, f[i][j]);
                }
            }
        }
        System.out.println(res*res);
    }
}



import java.io.*;
import java.util.ArrayDeque;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        ArrayDeque<Integer> nums = new ArrayDeque<>();
        ArrayDeque<Character> ops = new ArrayDeque<>();
        char[] temp = reader.readLine().toCharArray();
        for (int i = 0; i < temp.length; i++) {
            char c = temp[i];
            //当是数字时,计算数字的值
            if (c >= '0' && c <= '9'){
                int j = i+1, value = Integer.parseInt(String.valueOf(c));
                while(j < temp.length && temp[j] >= '0' && temp[j] <= '9'){
                    value = (value*10 + Integer.parseInt(String.valueOf(temp[j])))% 10000;
                    j++;
                }
                nums.push(value);
                i = j-1;
                //当是加号时,只要操作符栈非空,就一直计算
            }else if (c == '+'){
                while(!ops.isEmpty()){
                    char d = ops.pop();
                    if (d == '+'){
                        nums.push((nums.pop() + nums.pop())% 10000);
                    }else{
                        nums.push((nums.pop() * nums.pop())% 10000);
                    }
                }
                ops.push(c);
                //当是乘号时,仅当操作符栈非空且为乘号时才进行计算
            }else{
                while(!ops.isEmpty() && ops.peek() == '*'){
                    nums.push((nums.pop() * nums.pop())% 10000);
                    ops.pop();
                }
                ops.push(c);
            }
        }
        //当操作符栈非空时,按顺序计算数值即可,只会存在最多一个乘号
        while(!ops.isEmpty()){
            char x = ops.pop();
            if (x == '+'){
                nums.push((nums.pop() + nums.pop())% 10000);
            }else{
                nums.push((nums.pop() * nums.pop())% 10000);
            }
        }
        System.out.println(nums.pop() % 10000);
    }
}



import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(reader.readLine().trim());
        String[] temp = reader.readLine().split(" ");
        int[] h = new int[n+1];
        for (int i = 0; i < n; i++) {
            h[i] = Integer.parseInt(temp[i]);
        }
        int res = 0;
        for(int i = 0, j = n-1; i < j; ) {
          res = Math.max(res, Math.min(h[i], h[j]) * (j-i));
          if (h[i] < h[j]) i++;
          else j--;
        }
        System.out.println(res);
    }
}



import java.io.*;
import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        ArrayDeque<Integer> q = new ArrayDeque<>(10000+10);
        int m =  Integer.parseInt(reader.readLine().trim());
        String[] temp = reader.readLine().split(" ");
        int[] h = new int[m+2];
        int res = 0;
        for (int i = 0; i < m; i++) {
            h[i] = Integer.parseInt(temp[i]);
        }
        for (int i = 0; i < m; i++) {
            int last = 0;//用于存放上一个较小的高度值是多少
            while(!q.isEmpty() && h[q.peek()] <= h[i]){
                //当队列非空且队头元素小于当前元素时,计算两者之间的面积
                res += (h[q.peek()] - last) * (i - q.peek() - 1);
                //更新高度值
                last = h[q.peek()];
                q.pop();
            }
            if (!q.isEmpty()){
                res += (h[i] - last) * (i - q.peek() - 1);
            }
            q.push(i);
        }
        System.out.println(res);
    }
}



import java.io.*;
import java.util.ArrayDeque;

public class Main {
    static ArrayDeque<Integer> queue = new ArrayDeque<>(1002);
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] temp = reader.readLine().split(" ");
        int n = Integer.parseInt(temp[0]);
        int m = Integer.parseInt(temp[1]);
        int[][] s = new int[n+2][m+2];
        int[] l = new int[m+2], r = new int[m+2];
        //将左右两侧边界初始化为-1,
        for (int i = 0; i <= n; i++) {
            s[i][0] = s[i][m+1] = -1;
        }
        //读入数据
        for (int i = 1; i <= n; i++) {
            temp = reader.readLine().split(" ");
            for (int j = 1; j <= m; j++) {
                s[i][j] = temp[j-1].equals("R") ? 0 : s[i-1][j] + 1;
            }
        }
        long res = 0;
        for (int i = 1; i <= n; i++) {
            res =Math.max(res, work(s[i], l, r, m));
        }
        writer.write(res*3+"");
        writer.flush();
    }
    static long work(int[] h,int[] l,int[] r, int m){
        queue.clear();
        queue.push(0);
        for (int i = 1; i <= m; i++) {
            while(h[i] <= h[queue.peek()]) queue.pop();
            l[i] = queue.peek();
            queue.push(i);
        }
        queue.clear();
        queue.push(m+1);
        for (int i = m; i > 0; i--) {
            while(h[i] <= h[queue.peek()]) queue.pop();
            r[i] = queue.peek();
            queue.push(i);
        }
        long res = 0;
        for (int i = 1; i <= m; i++) {
            res = Math.max(res, (long)h[i]*(r[i]-l[i]-1));
        }
        return res;
    }
}



import java.io.*;
import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] temp = reader.readLine().split(" ");
        //都多申请几位,方便处理边界
        ArrayDeque<Integer> queue = new ArrayDeque<>(100000 + 10);
        int[] h = new int[100000 +2];
        int[] l = new int[100000 +2];
        int[] r = new int[100000 +2];
        h[0] = -1;//将左边界初始化为-1,方便进行边界判断
        while(Integer.parseInt(temp[0]) != 0){
            int n = Integer.parseInt(temp[0]);
            h[n+1] = -1;//同上
            for (int i = 1; i <= n; i++) {
                h[i] = Integer.parseInt(temp[i]);
            }
            //计算出左侧第一个比当前数小的数据的位置
            queue.push(0);
            for (int i = 1; i <= n; i++) {
                while(h[i] <= h[queue.peek()]){
                    queue.pop();
                }
                l[i] = queue.peek();
                queue.push(i);
            }
            queue.clear();
            //计算出右侧第一个比当前数小的数据的位置
            queue.push(n+1);
            for (int i = n; i > 0; i--) {
                while(h[i] <= h[queue.peek()]){
                    queue.pop();
                }
                r[i] = queue.peek();
                queue.push(i);
            }
            long res = 0;
            for (int i = 1; i <= n; i++) {
                //这里在计算时一定要手动强转为long,不然会按照int计算
                res = Math.max(res, (long)h[i]*(r[i] - l[i] - 1));
            }
            writer.write(res+"\n");
            temp = reader.readLine().split(" ");
        }
        writer.flush();
    }
}



大家可以参考这位老哥的分析,我就不写了
股票买卖 IV

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] temp = reader.readLine().split(" ");
        int n = Integer.parseInt(temp[0]);
        int k = Integer.parseInt(temp[1]);
        temp = reader.readLine().split(" ");
        int[] w = new int[n+1];
        for (int i = 0; i < n; i++) {
            w[i+1] = Integer.parseInt(temp[i]);
        }
        int[][][] f = new int[2][100010][110];
        //我为了方便初始化数据,改了一下状态数组的定义顺序
        for (int i = 0; i < n + 1; i++) {
            Arrays.fill(f[0][i], -0x3f3f3f3f);
            Arrays.fill(f[1][i], -0x3f3f3f3f);
        }
        f[0][0][0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                f[0][i][j] = f[0][i-1][j];
                if (j > 0){
                    f[0][i][j] = Math.max(f[0][i][j], f[1][i-1][j-1]+w[i]);
                }
                f[1][i][j] = Math.max(f[1][i-1][j], f[0][i-1][j]-w[i]);
            }
        }
        int res = 0;
        for (int i = 0; i <= k; i++) {
            res = Math.max(res, f[0][n][i]);
        }
        System.out.println(res);
    }
}




import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        ArrayList<Pair> list = new ArrayList<>(10000);
        PriorityQueue<Pair> res = new PriorityQueue<>((o1, o2) -> o1.value-o2.value);
        while(sc.hasNext()){
            int n = sc.nextInt();
            list.clear();
            res.clear();
            for (int i = 0; i < n; i++) {
                int value = sc.nextInt();
                int day = sc.nextInt();
                list.add(new Pair(day, value));
            }
            Collections.sort(list,(o1, o2) -> o1.day-o2.day);
            int days = 0;
            int le = 0, re = list.size();
            while(le<re){
                Pair p = list.get(le++);
                days = p.day;
                res.add(p);
                if (res.size() > days){
                    res.poll();
                }
            }
            int out = 0;
            while(!res.isEmpty()){
                out += res.poll().value;
            }
            writer.write(out+"\n");
        }
        writer.flush();
    }
    static class Pair{
        int day;
        int value;

        public Pair(int day, int value) {
            this.day = day;
            this.value = value;
        }
    }
}