[数据结构与算法]【思特奇杯·云上蓝桥-算法集训营】第3周

1…斐波那契数

import java.util.Scanner;

public class t_1 {
    public static void main(String[] args) {
        Scanner scanner= new Scanner(System.in);
        int n=scanner.nextInt();
        System.out.println(f(n));
    }
    public static int f(int n){
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else {
            return f(n-1)+f(n-2);
        }
    }
}

2.第 N 个泰波那契数

import java.util.Scanner;

public class t_2 {
    public static void main(String[] args) {
        Scanner scanner= new Scanner(System.in);
        int n=scanner.nextInt();
        System.out.println(f(n));
    }
    public static int f(int n){
        if(n==0){
            return 0;
        }else if(n==1||n==2){
            return 1;
        }else {
            return f(n-1)+f(n-2)+f(n-3);
        }
    }
}

3.爬楼梯

import java.util.Scanner;

public class t_3 {
    public static int num;
    public static void main(String[] args) {
        Scanner scanner= new Scanner(System.in);
        int n=scanner.nextInt();
        f(n);
        System.out.println(num);
    }
    public static void f(int n){
        if(n>0){
            f(n-1);
            f(n-2);
        }
        if(n==0){
            num++;
        }
    }
}

4.使用最小花费爬楼梯

public class t_4 {
    public static int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
    public static void main(String[] args) {
        System.out.println(f(cost));
    }
    public static int f(int[] cost) {
        int n = cost.length;
        int prev = 0, curr = 0;
        for (int i = 2; i <= n; i++) {
            int next = Math.min(curr + cost[i - 1], prev + cost[i - 2]);
            prev = curr;
            curr = next;
        }
        return curr;
    }
}

5.买卖股票的最佳时机

public class t_5 {
    public static int[] cost = {7,6,4,3,1};
    public static void main(String[] args) {
        System.out.println(f(cost));
    }
    public static int f(int[] cost) {
        int jmin=0,imin=0;
        for(int i=0;i<cost.length;i++){
            for(int j=i+1;j<cost.length;j++){
                jmin=Math.max(cost[j]-cost[i],jmin );
            }
            imin=Math.max(jmin,imin);
        }
        if(imin<0){
            return 0;
        }
        return imin;
    }
}

6.最长公共子序列

import java.util.Scanner;

public class t_6 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        String text1=scanner.next();
        String text2=scanner.next();
        System.out.println(f(text1,text2));
    }
    public static int f(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = text1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = text2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

7.杨辉三角

import java.util.Scanner;
public class t_7 {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        System.out.println(f(n));
    }
    public static long f(int n){
        long x=0l;
        long y[]=new long[50010];
        y[1]=1;
        if(n==1)    return 1;
        long cur=0l;
        for(int i=2;i<50000;i++){
            cur+=2*i-1;
            for(int j=i;j>=1;j--){
                y[j]=y[j-1]+y[j];
                if(y[j]==n) {
                    x = cur;
                }
                cur--;
            }
            if(x!=0){
                return x;
            }
        }
        return (n+1)*n/2+2;
    }
}

8.节点选择

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class t_8{
    private static int[][] dp;
    private static List<List<Integer>> vertex = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            dp[i][1]=scanner.nextInt();
            vertex.add(new ArrayList<Integer>());
        }
        scanner.nextLine();
        for (int i = 0; i < n - 1; i++) {
            final String[] ab =scanner.nextLine().split(" ");
            int a = Integer.parseInt(ab[0]) - 1;
            int b = Integer.parseInt(ab[1]) - 1;
            vertex.get(a).add(b);
            vertex.get(b).add(a);
        }
        scanner.close();
        dfs(0, -1);
        System.out.println(Math.max(dp[0][0], dp[0][1]));
    }

    private static void dfs(int root, int pre) {
        List<Integer> temp = vertex.get(root);
        for (int i = 0; i < temp.size(); i++) {
            if (temp.get(i) != pre) {
                dfs(temp.get(i), root);
                dp[root][1] += dp[temp.get(i)][0];
                dp[root][0] += Math.max(dp[temp.get(i)][0], dp[temp.get(i)][1]);
            }
        }
    }
}

9.耐摔指数

import java.util.Scanner;

public class t_9 {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int [] x=new int [1000];
        int sum=1;
        for(int i=0;sum<n;i++){
            sum=i+sum;
            x[i]=sum;
        }
        sum=1;
        int k=0;
        for(int i=0;sum<n;i++){
            sum=x[i]+sum;
            k++;
        }
        System.out.println(k);
    }
}

10.K好数

import java.math.BigInteger;
import java.util.Scanner;

public class t_10 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int k=scanner.nextInt();
        int l=scanner.nextInt();
        System.out.println(f(k,l));
    }
    public static BigInteger f(int k, int l){
        int [][] array = new int[l][k];
        for (int i = 1; i < k; i++) {
            array[0][i] = 1;
        }
        for (int i = 1; i < l; i++) {
            for (int j = 0; j < k; j++) {
                for (int j2 = 0; j2 < k; j2++) {
                    if ((j != j2 + 1) && (j != j2 - 1)) {
                        array[i][j] = (array[i][j] + array[i-1][j2]) % 1000000007;
                    }
                }
            }
        }
        BigInteger sum = new BigInteger("0");
        for (int i = 0; i < k; i++) {
            sum = sum.add(new BigInteger(Integer.toString(array[l - 1][i])));
        }
        return sum.mod(new BigInteger("1000000007"));
    }
}