非leetcode算法

Word count: 4.4k   |   Reading time≈ 26 min

二维数组中-3位置找-2位置

dfs 8维以上时间太长。

bfs 

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

public class ParentChildGame {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N =Integer.valueOf(sc.nextLine());
        int[][] a = new int[N][N];
        for (int i=0;i<N;i++){
            a[i]= Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        }
        int[] mom = new int[2],baby = new int[2];
        for (int i=0;i<N;i++){
            for (int j=0;j<N;j++){
                if (a[i][j]==-3){
                    mom[0]=i;
                    mom[1]=j;
                }else if (a[i][j]==-2){
                    baby[0]=i;
                    baby[1]=j;
                }
            }
        }

        bfs(a,mom[0],mom[1],baby[0],baby[1]);

        System.out.println(maxRes);

    }

    private static int minSize = Integer.MAX_VALUE;//最小时间
    private static int maxRes = -1;//最大糖果数

    private static void bfs(int[][] a, int x, int y, int bi, int bj) {
        boolean[][] visited = new boolean[a.length][a[0].length];
        // x y 时间 糖果
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((c, d) -> {
            if (c[2]!=d[2]){
                return c[2]-d[2];
            }
            return d[3]-c[3];
        });
        priorityQueue.add(new int[]{x,y,0,0});
        visited[x][y]=true;
        while (priorityQueue.size()>0){
            int[] poll =priorityQueue.poll();

            int i=poll[0],j=poll[1],size=poll[2],res=poll[3];

            if (i==bi && j==bj){
                if (size<minSize){
                    minSize=size;
                    maxRes=res;
                    continue;
                }
                if (size==minSize && res>maxRes){
                    maxRes=res;
                }
                continue;
            }

            int[][] dir ={{1,0},{-1,0},{0,1},{0,-1}};
            for (int[] d :dir){
                int ci=i+d[0],cj=j+d[1];
                if (ci>=0 && cj>=0 && ci<a.length && cj<a[0].length && visited[ci][cj]==false && a[ci][cj]!=-1){
                    visited[ci][cj]=true;
                    priorityQueue.add(new int[]{ci,cj,size+1,res+(a[ci][cj]>0?a[ci][cj]:0)});
                }
            }
        }

    }
}


重复字母的全排列

dfs用下标+set去重

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

import java.util.*;
import java.util.stream.Collectors;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len= sc.nextInt();
        String[] a= new String[len];
        for (int i=0;i<len;i++){
            a[i]=sc.next();
        }

        Set<String> result = new HashSet<>();
        Arrays.sort(a);
        bt(a,result,0);
        result.stream().sorted().forEach(System.out::println);
    }

    private static void bt(String[] a, Set<String> result,int start) {
        if (start==a.length){
            result.add(Arrays.stream(a).collect(Collectors.joining()));
            return;
        }

        for (int i=start;i<a.length;i++){
            if (i!=start && a[i]==a[start]){
                continue;
            }
            swap(a,i,start);
            bt(a,result,start+1);
            swap(a,i,start);
        }

    }

    private static void swap(String[] a, int i, int j) {
        String t =a[i];
        a[i]=a[j];
        a[j]=t;
    }
    
}

dfs用list记录下标+set去重

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
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len= sc.nextInt();
        String[] a= new String[len];
        for (int i=0;i<len;i++){
            a[i]=sc.next();
        }

        HashSet<String> result = new HashSet<>();
        bt(a,result,new LinkedList<Integer>());
        result.stream().sorted().forEach(System.out::println);
    }

    private static void bt(String[] a, HashSet<String> result, LinkedList<Integer> list) {
        if (list.size()==a.length){
            StringBuilder sb  = new StringBuilder();
            for (int i=0;i<list.size();i++){
                sb.append(a[list.get(i)]);
            }
            result.add(sb.toString());
            return;
        }

        for (int i=0;i<a.length;i++){
            if (list.contains(i)) continue;
            list.addLast(i);
            bt(a,result,list);
            list.removeLast();
        }

    }


}

打印螺旋矩阵

1
2
3
4
1 2 3
* * 4
9 * 5
8 7 6
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
public class SpiralMatrixGenerator {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt(),m= sc.nextInt();
        int col = (n+m-1)/m;
        String[][] a = new String[m][col];
        int count=m*col;
        int k=1;
        int i=0,j=0;
        while (k<=n){
            while (k<=n&&j<col && a[i][j]==null){
                a[i][j]= String.valueOf(k);
                k++;
                j++;
            }
            j--;
            i++;

            while (k<=n&&i<m&& a[i][j]==null){
                a[i][j]= String.valueOf(k);
                i++;
                k++;
            }
            i--;
            j--;
            while (k<=n&&j>=0&& a[i][j]==null){
                a[i][j]= String.valueOf(k);
                j--;
                k++;
            }
            j++;
            i--;
            while (k<=n&&i>0&& a[i][j]==null){
                a[i][j]= String.valueOf(k);
                i--;
                k++;
            }
            i++;
            j++;

        }
        for ( i = 0; i < a.length; i++) {
            for ( j = 0; j < a[i].length; j++) {
                if (a[i][j]==null){
                    a[i][j]="*";
                }
            }
            System.out.println(Arrays.stream(a[i]).collect(Collectors.joining(" ")));
        }
    }

}

数组排列

1 ~ 9 中任意 4 个不重复的数字

2和5可以互相当作，69类似

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
public class NumberSort {

    public static void main(String[] args) {
        int[] a = Arrays.stream(new Scanner(System.in).nextLine().split(","))
                .map(m->Integer.valueOf(m)).mapToInt(Integer::intValue).toArray();
        Arrays.sort(a);
        if(check(a)==false){
            System.out.println(-1);
            return;
        }

        int N = a[a.length-1];
        for (int i=0;i<a.length;i++){
            if (a[i]==5){
                a[i]=2;
            }else if (a[i]==9){
                a[i]=6;
            }
        }
        backtrack(a,0,new LinkedList<>());
        System.out.println(Arrays.toString(a));
        List<List<Integer>> otherList = new ArrayList<>();
        for (List<Integer> list : resList){
            if (list.contains(2)){
                List<Integer> oList = new ArrayList<>(list);
                oList.remove(Integer.valueOf(2));
                oList.add(5);
                otherList.add(oList);
            }else if (list.contains(6)){
                List<Integer> oList = new ArrayList<>(list);
                oList.remove(Integer.valueOf(6));
                oList.add(9);
                otherList.add(oList);
            }
        }
        resList.addAll(otherList);
        for (List<Integer> list : resList){
            backtrack2(list.stream().mapToInt(Integer::intValue).toArray(),new LinkedList<Integer>());
        }
        set=set.stream().sorted(Comparator.comparingInt(Integer::valueOf)).collect(Collectors.toList());
        System.out.println(set.get(N-1));

    }

    private static boolean check(int[] a) {
        if (a.length!=4){
            return false;
        }
        int a2=0,a6=0;
        for(int aa : a){
            if (aa==2 || aa==5){
                a2++;
            }
            if (aa==6 || aa==9){
                a6++;
            }
            if (aa<1 || aa>9){
                return false;
            }
        }
        if (a2>1 || a6>1){
            return false;
        }
        for (int i=1;i<a.length;i++){
            if (a[i]==a[i-1]){
                return false;
            }
        }
        return true;
    }

    private static void backtrack2(int[] a, LinkedList<Integer> list) {
        if (list.size()==a.length){
            set.add(list.stream().map(Objects::toString).collect(Collectors.joining()));
        }
        for (int i=0;i<a.length;i++){
            if (list.contains(a[i])){
                continue;
            }
            list.addLast(a[i]);
            backtrack2(a,list);
            list.removeLast();
        }
    }

    private static List<String> set = new ArrayList<>();
    private static List<List<Integer>> resList = new ArrayList<>();
    private static void backtrack(int[] a, int start, LinkedList<Integer> list) {
        for (int i=start;i<a.length;i++){

            list.addLast(a[i]);
            backtrack(a,i+1,list);
            list.removeLast();
        }
        if (list.isEmpty()==false){
            resList.add((new ArrayList<>(list)));
        }
    }

}

二维数组中的广播

1
2
3
4
1 1 0
1 1 0
0 0 1
2
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
public class BroadcastSender  {
    public static void main(String[] args) {
        String[] s = new Scanner(System.in).nextLine().split(",");
        int n = s.length,m=s[0].length();
        int[][] a = new int[n][m];
        boolean[] visited = new boolean[n];
        for (int i=0;i<n;i++){
            a[i] =  Arrays.stream(s[i].split("")).mapToInt(Integer::parseInt).toArray();
        }
        int res =0;
        for(int i=0;i<a.length;i++){
            if (visited[i]==false){
                res++;
                dfs(a,i,visited);
            }

        }
        System.out.println(res);
    }

    private static void dfs(int[][] a, int start,boolean[] visited) {
         visited[start]=true;
         for (int j=0;j<a[0].length;j++){
             if (a[start][j]==1 && visited[j]==false){
                 dfs(a,j,visited);
             }
         }
    }
}

伐木头收益

木头n可拆分（n-x）*x收益

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
public class Woodcutter {
    public static void main(String[] args) {
        int x = new Scanner(System.in).nextInt();
        int[] dp = new int[x+1];//可分割第i长度时候最大收益
        dp[0] =1;
        for (int i=1;i<=x;i++){
            dp[i]=i;
            for (int j=1;j<i;j++){
                dp[i] = Math.max(dp[i],dp[i-j]*j);
            }
        }
        System.out.println(Arrays.toString(dp));
        List<Integer> list = new ArrayList<>();
        while (x>0){
            for (int i=1;i<=x;i++){
                if (dp[x]==dp[x-i]*i){
                    list.add(i);
                    x-=i;
                    break;
                }
            }
        }
        int[] a= list.stream().sorted().mapToInt(Integer::intValue).toArray();
        for (int i=1;i<list.size();i++){
            if (a[i]+a[i-1] == a[i]*a[i-1]){
                a[i]=a[i]+a[i-1];
                a[i-1] = 0 ;
            }
        }
        System.out.println(Arrays.stream(a).filter(f->f!=0).sorted().boxed().map(Objects::toString).collect(Collectors.joining(" ")));
    }
}

生成哈夫曼树

权重从小到大，高度从小到大

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
public class BuildHuffmanNode {

    static class HuffmanNode{
        public int weight,height;
        public HuffmanNode left,right;

        public HuffmanNode(int weight, int height) {
            this.weight = weight;
            this.height = height;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        PriorityQueue<HuffmanNode> queue = new PriorityQueue<>((Comparator<HuffmanNode>) (a, b) -> {
            if (a.weight!=b.weight){
                return a.weight-b.weight;
            }
            return a.height-b.height;
        });
        for (int i=0;i<n;i++){
            int a= sc.nextInt();
            queue.offer(new HuffmanNode(a,0));
        }
        HuffmanNode root = buildHuffmanTree(queue);
        System.out.println(inOrder(new StringBuilder(),root));
    }

    private static String inOrder(StringBuilder sb,HuffmanNode root) {
        if (root==null){
            return null;
        }
        inOrder(sb,root.left);
        sb.append(root.weight+" ");
        inOrder(sb,root.right);
        return sb.toString().trim();
    }

    private static HuffmanNode buildHuffmanTree(PriorityQueue<HuffmanNode> queue) {
        while (queue.size()>1){
            HuffmanNode a = queue.poll();
            HuffmanNode right = queue.poll();
            HuffmanNode parent  = new HuffmanNode(a.weight + right.weight,Math.max(a.height,right.height)+1);
            parent.left=a;
            parent.right=right;
            queue.offer(parent);
        }
        return queue.poll();
    }

}

多任务启动顺序

如果同时有多个任务要执行，则根据任务名称字母顺序排序

A->B C->B

BAC

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

public class MultiTaskScheduler {
    public static void main(String[] args) {
        //C->D C->B A->B
        String[] s = new Scanner(System.in).nextLine().split(" ");
        Map<String, List<String>> map = new HashMap<>();
        for (String a : s){
            String[] b= a.split("->");
            if (map.containsKey(b[1])){
                List<String> list =map.get(b[1]);
                list.add(b[0]);
                map.put(b[1],list);
            }else {
                List<String> list = new ArrayList<>();
                list.add(b[0]);
                map.put(b[1],list);
            }
        }

        List<String> l = new ArrayList<>();
        for (String key : map.keySet()){
//            System.out.println(key+"=>"+map.get(key));
            boolean isInclude= false;
            for (List<String> list : map.values()){
                if (list.contains(key)){
                    isInclude=true;
                    break;
                }
            }
            if (isInclude==false){
                l.add(key);
            }
        }
        PriorityQueue<String> queue = new PriorityQueue<>(Comparator.naturalOrder());
        //   System.out.println("l:"+l);
        for (int i=0;i<l.size();i++){
            queue.offer(l.get(i));
        }

        List<String> res = new ArrayList<>();
        List<String> inList = new ArrayList<>();//包含

        while (queue.isEmpty()==false || inList.isEmpty()==false){
            if (queue.isEmpty()) {
                // 这里改变为检查inList中的任务是否可以移入queue
                List<String> readyToQueue = new ArrayList<>();
                for (String task : inList) {
                    boolean isInclude = true;
                    for (List<String> list : map.values()) {
                        if (list.contains(task)) {
                            isInclude = false;
                            break;
                        }
                    }
                    if (isInclude) {
                        readyToQueue.add(task);
                    }
                }
                inList.removeAll(readyToQueue);
                queue.addAll(readyToQueue);

                if (queue.isEmpty() && inList.isEmpty()) {
                    break;  // 防止死循环
                }
            }

            String key = queue.poll();
            boolean isInclude =false;
            for (List<String> list : map.values()){
                if (list.contains(key)){
                    isInclude=true;
                    break;
                }
            }
            if (isInclude){
                inList.add(key);
                continue;
            }

            if (res.contains(key)==false){
                res.add(key);
            }

            List<String> list =map.get(key);
            map.remove(key);

            if (list==null){
                continue;
            }

            for (int i=0;i<list.size();i++){
                inList.add(list.get(i));
            }
        }
        System.out.println(res.stream().collect(Collectors.joining(" ")));
    }
}

长度为m的和为n的数组个数

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
public class MooncakeAllocator {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        scanner.close();
        for (int i=1;i<=n/m;i++){ //数组的第一个元素只能是i
            processCake(m,n,1,i,i);
        }

        System.out.println(c);
    }
    private static int c=0;
    private static void processCake(int len, int n, int start,int sum,int pre ) {
        if (start==len) {
            if (sum==n){
                c++;
            }
            return;
        }
        //数组后面的元素比前一个元素大0-3
        for (int i = pre; i<=pre+3 && i<=n-len+1; i++) {
            if (i+sum<=n){
                processCake(len, n,start+1,i+sum,i);
            }
        }
    }
}

抢7游戏

A报N，B报N-1或N-2，依次循环，保证B为7的组合。

递归：数据大会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Main {
    public static void main(String[] args) {
        int n = new Scanner(System.in).nextInt();
        System.out.println(sevenGame(n, false));
    }
    private static int sevenGame(int n, boolean isB) {
        if (n<7){
            return 0;
        }
        if (n == 7) {
            return isB ? 1 : 0;
        }
        int res = 0;
        if (n > 1) {
            res += sevenGame(n - 1, !isB);
        }
        if (n > 2) {
            res += sevenGame(n - 2, !isB);
        }
        return res;
    }
}

动态规划

n属于A开始，A=B的上一个（可能是i+1，i+2）

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
private static BigInteger sevenGameDp(int n) {
    if (n <= 7) {
        return BigInteger.ZERO;
    }
    BigInteger[][] dp = new BigInteger[n + 1][2];
    for (int i=0;i<dp.length;i++){
        for (int j=0;j<dp[0].length;j++){
            dp[i][j]=BigInteger.ZERO;
        }
    }
    dp[n][0] = BigInteger.ONE; // A开始
    dp[n][1] = BigInteger.ZERO;

    for (int i = n ; i >= 7; i--) {
        if (i+1<=n){
            dp[i][0] = dp[i][0].add(dp[i + 1][1]);
            dp[i][1] = dp[i][1].add(dp[i + 1][0]);
        }
        if (i+2<=n){
            dp[i][0] = dp[i][0].add(dp[i + 2][1]);
            dp[i][1] = dp[i][1].add(dp[i + 2][0]);
        }
    }
    return dp[7][1];
}

游乐园最低消费

输入一行，分别为一日票（1天）、三日票（3天）、周票（7天）和月票（30天）

输入第二行，小王计划游玩日期数组为days，1 ≤ days.length ≤ 365，1 ≤ days[i] ≤ 365，默认顺序为升序。
输出描述：完成游玩计划的最低消费。

会有部分Memory Exceeded的做法

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
private static void dfs(int[] costs, List<Integer> dayList, int start,int maxIndex, LinkedList<Integer> list) {
    while (start<=maxIndex && dayList.contains(start)==false){
        start++;
    }


    if (list.stream().mapToInt(Integer::intValue).sum()>=minCost){
        return;
    }

    List<Integer> indexCost =   List.of(1,3,7,30);
    if (start>maxIndex ){
        minCost= Math.min(minCost,list.stream().mapToInt(Integer::intValue).sum());
        return;
    }


    for (int i=0;i<4;i++){
        list.addLast(costs[i]);
        start+=indexCost.get(i);
        dfs(costs,dayList,start,maxIndex,list);
        list.removeLast();
        start-=indexCost.get(i);

    }
}

LinkedList list演变为currentCost，又成功了多几个，数量大还是回溯深度过大

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
private static void dfs(int[] costs, List<Integer> dayList, int start,int maxIndex, int currentCost) {
    while (start<=maxIndex && dayList.contains(start)==false){
        start++;
    }


    if (currentCost>=minCost){
        return;
    }

    List<Integer> indexCost =   List.of(1,3,7,30);
    if (start>maxIndex ){
        minCost= Math.min(minCost,currentCost);
        return;
    }


    for (int i=0;i<4;i++){
        currentCost+=costs[i];
        start+=indexCost.get(i);
        dfs(costs,dayList,start,maxIndex,currentCost);
        currentCost-=costs[i];
        start-=indexCost.get(i);

    }
}

dp动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static int minDp(int[] costs, List<Integer> dayList) {
       int[] dp = new int[dayList.get(dayList.size() - 1) + 1];
       for (int i = 1; i < dp.length; i++) {
           if (dayList.contains(i) == false) {
               dp[i] = dp[i - 1];//在非游玩天数，dp[i]应继承前一天的值，因为当天不需要额外的花费
               continue;
           }

           // 第一个不能Math.min(dp[i], (i -1>0?dp[i - 1]:0) + costs[0]);
           dp[i] = (i - 1 > 0 ? dp[i - 1] : 0) + costs[0];// dp[i - 1] + costs[0];
           dp[i] = Math.min(dp[i], (i -3>0?dp[i - 3]:0) + costs[1]);
           dp[i] = Math.min(dp[i], (i -7>0?dp[i - 7]:0) + costs[2]);
           dp[i] = Math.min(dp[i], (i -30>0?dp[i - 30]:0)+ costs[3]);

       }
       return dp[dp.length - 1];
   }

分披萨

AB从缺口两边分披萨

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
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i]=sc.nextInt();
        }

        long max = 0;
        memo= new long[n][n];
        for (int i = 0; i < n; i++) {
            for (long[] m :memo){
                Arrays.fill(m,0);
            }

            int temp=array[0];
            for (int j=1;j<n;j++){
                array[j-1]=array[j];
            }
            array[n-1]=temp;

            max = Math.max(process(array,true,0,array.length-1), max);
        }
        System.out.println(max);
    }
    private static long [][] memo;//记忆搜索
    private static long process(int[] array, boolean isTrueA,int left,int right) {
        if (left>right){
            return 0;
        }
        if (isTrueA==false){
            if (array[left]>array[right]){
                return process(array,true,left+1,right);
            }else {
                return process(array,true,left,right-1);
            }
        }else {
            if (memo[left][right]!=0){
                return memo[left][right];
            }
            long a = array[left]+process(array,false,left+1,right);
            long b =array[right]+process(array,false,left,right-1);
            long max= Math.max(a,b);
            memo[left][right]=max;
            return max;
        }
    }

}

数组连续和

长度3数组连续大于等于7的个数

3 7
3 4 7

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
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        int[] a = new int[n];
        for (int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
        int v = sc.nextInt();
        int l=0,r=0,winSum=a[0];
        int max =0;
        while (r<n){
            if (winSum<=v){
                max=Math.max(r-l+1,max);
            }else {
                winSum-=a[l];
                l++;
            }
            
            r++;
            if (r>=n){
                break;
            }
            winSum+=a[r];
        }
        System.out.println(max);
    }
}

左上角到右下角（各值最大的）路径中的最小值

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
59
60
61
62
63
64
65
66
67
68
69
70
71
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =Integer.valueOf(sc.nextLine()),m=Integer.valueOf(sc.nextLine());
        int[][] a = new int[n][m];
        int left=0,right=0,res=0;
        for (int i=0;i<n;i++){
            a[i]= Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::valueOf).toArray();
            for (int aa:a[i]){
                right=right>aa?right:aa;
            }
        }

        while (left<=right){
            int mid =(left+right)/2;//默认是最小的
            if (bfs(a,n,m,mid)){//dfs(a,0,0,n,m,mid,new boolean[n][m])
                res=mid;
                left=mid+1;
            }else {
                right=mid-1; //找不到就变小
            }
        }
        System.out.println(res);
    }

    private static boolean bfs(int[][] a, int n, int m, int k) {
        if (a[0][0]<k || a[n-1][m-1]<k){
            return false;
        }
        boolean[][] visited= new boolean[n][m];
        LinkedList<int[]> list = new LinkedList<>();
        visited[0][0] =true;
        list.add(new int[]{0,0});
        int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
        while (list.isEmpty()==false){
            int[] poll = list.removeFirst();
            int x=poll[0],y=poll[1];
            if (x==n-1 && y==m-1){
                return true;
            }

            for (int[] d:dir){
                int i=d[0]+x,j=d[1]+y;
                if (i>=0 && j>=0 && i<n && j<m && visited[i][j]==false && a[i][j]>=k){
                    visited[i][j]=true;
                    list.offer(new int[]{i,j});
                }
            }

        }
        return false;
    }


    //数据大会超时
    private static boolean dfs(int[][] a, int i, int j, int n, int m, int k, boolean[][] visited) {
        if (i<0 || i>=n || j<0 || j>=m || visited[i][j] || a[i][j]<k){
            return false;
        }
        if (i==n-1 && j==m-1){
            return true;
        }
        visited[i][j]=true;
        boolean b= dfs(a,i+1,j,n,m,k,visited)
                ||dfs(a,i-1,j,n,m,k,visited)
                ||dfs(a,i,j+1,n,m,k,visited)
                ||dfs(a,i,j-1,n,m,k,visited);
        visited[i][j]=false;
        return b;
    }
}

24点扑克牌

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
59
60
61
62
63
64
65
66
67
68
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] a = Arrays.stream(new Scanner(System.in).nextLine()
                .split(" ")).mapToInt(Integer::parseInt).toArray();
        System.out.println(getResult(a));

    }
    private static List<List<Integer>> resList;
    private static boolean getResult(int[] a) {
        resList = new ArrayList<>();
        dfs(a,new LinkedList<>(),new LinkedList<>());
        for (List<Integer> list : resList){
            if (check(list)){
                return true;
            }
        }
        return false;

    }

    private static boolean check(List<Integer> list) {
        for (double a:cal(list.get(0),list.get(1))){
            for (double b:cal(list.get(2),a)){
                for (double res:cal(list.get(3),b)){
                    if (24==res){
                        return true;
                    }
                }
            }
        }
        return false;

    }


    private static List<Double> cal(double a, double b) {
        List<Double> list=new ArrayList<>();
        list.add((double) (a+b));
        list.add((double) (a-b));
        list.add((double) (b-a));
        list.add((double) (a/b));
        list.add((double) (b/a));
        list.add((double) (a*b));
        return list;

    }

    private static void dfs(int[] a, LinkedList<Integer> indexList, LinkedList<Integer> list) {
        if (list.size()==4){
            resList.add(new ArrayList<>(list));
            return;
        }

        for (int i=0;i<4;i++){
            if (indexList.contains(i)){
                continue;
            }
            indexList.addLast(i);
            list.addLast(a[i]);
            dfs(a,indexList,list);
            indexList.removeLast();
            list.removeLast();
        }
    }
    
}
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2025 Lin

加载中……