1. 斐波那契数
import java.util.Scanner;
public class Main {
public final static long[][] UNIT = {{0,1,1,0,0,0,0,0},
{1,0,0,1,0,0,0,0},
{0,0,0,0,1,0,0,0},
{0,0,0,0,0,1,0,0},
{2,3,0,0,0,0,0,0},
{0,2,0,0,0,0,0,0},
{0,1,0,0,0,0,1,0},
{1,0,0,0,0,0,0,1}};
public final static long[][] ZERO = new long[8][8];
public final static long p = 99999999L;
public long[][] getNofMatrix(long n) {
if(n == 0)
return ZERO;
if(n == 1)
return UNIT;
if((n & 1) == 0) {
long[][] matrix = getNofMatrix( n >> 1);
return multiOfMatrix(matrix, matrix);
}
long[][] matrix = getNofMatrix((n - 1) >> 1);
return multiOfMatrix(multiOfMatrix(matrix, matrix), UNIT);
}
public long[][] multiOfMatrix(long[][] A, long[][] B) {
long result[][] = new long[A.length][B[0].length];
for(int i = 0;i < A.length;i++) {
for(int j = 0;j < B[0].length;j++) {
for(int k = 0;k < A[0].length;k++)
result[i][j] = (result[i][j] + A[i][k] * B[k][j]) % p;
}
}
return result;
}
public void printResult(long n) {
long[][] start = {{6,5,1,4,2,3,3,5}};
if(n == 1) {
System.out.println(start[0][4]+"n"+start[0][5]);
return;
} else if(n == 2) {
System.out.println(start[0][2]+"n"+start[0][3]);
return;
} else if(n == 3) {
System.out.println(start[0][0]+"n"+start[0][1]);
return;
}
long[][] A = getNofMatrix(n - 3);
start = multiOfMatrix(start, A);
System.out.println(start[0][0]+"n"+start[0][1]);
return;
}
public static void main(String[] args) {
Main test = new Main();
Scanner in = new Scanner(System.in);
long n = in.nextLong();
test.printResult(n);
}
}
2.第 N 个泰波那契数
public class Main{
public static void main(String[] args){
Solution slt = new Solution();
System.out.println(slt.tribonacci(5));
}
}
class Solution {
public int tribonacci(int n) {
if(n==0)
return 0;
if(n==1)
return 1;
if(n==2)
return 1;
int[] taibonaqie = new int[n+1];
taibonaqie[0] = 0;
taibonaqie[1] = 1;
taibonaqie[2] = 1;
for(int i = 3; i <= n; i++){
taibonaqie[i] = taibonaqie[i-1]+taibonaqie[i-2]+taibonaqie[i-3];
}
return taibonaqie[n];
}
}
3.爬楼梯
class Main {
public int maxSubArray(int[] nums) {
int dp[]=new int[nums.length];
dp[0]=nums[0];
int max=dp[0];
for(int i=1;i //compare the num last status plus current num and current num dp[i]=Math.max(dp[i-1]+nums[i],nums[i]); //compare max and dp[i],it will update max max=Math.max(max,dp[i]); } return max; } } 4.使用最小花费时间爬楼梯 class Main { public int minCostClimbingStairs(int[] cost) { int a = 0; int b = 0; for (int c : cost) { int cur = Math.min(a, b) + c; a = b; b = cur; } return Math.min(a, b); } } 5.买卖股票的最佳时机 class Main { public int maxProfit(int[] prices) { if (prices.length <= 1) { return 0; } int[] profitArr = new int[prices.length]; int minIndex = 0; int profit = 0; int leftMaxProfit = 0; for (int i = 0; i < prices.length; i++) { if (prices[i] - prices[minIndex] >= leftMaxProfit) { leftMaxProfit = prices[i] - prices[minIndex]; } profitArr[i] = leftMaxProfit; if (prices[i] < prices[minIndex]) { minIndex = i; } } int maxIndex = prices.length - 1; for (int i = prices.length - 1; i >= 0; i--) { if (prices[maxIndex] - prices[i] + profitArr[i] > profit) { profit = prices[maxIndex] - prices[i] + profitArr[i]; } if (prices[maxIndex] < prices[i]) { maxIndex = i; } } return profit; } } 6.最长公共子序列 import java.util.Scanner; public class Main { public static String S1,S2; public static char[] s1 ; public static char[] s2 ; public static void main(String[] args) { Scanner sc=new Scanner(System.in); S1=sc.next(); S2=sc.next(); s1=S1.toCharArray(); s2=S2.toCharArray(); int[][] dp = new int[1001][1001]; for(int i=1;i<=s1.length;i++){ for(int j=1;j<=s2.length;j++){ if(s1[i-1]==s2[j-1]){ dp[i][j]=1+dp[i-1][j-1]; } else if(s1[i-1]!=s2[j-1]){ dp[i][j]=dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1]; } } } System.out.println(dp[s1.length][s2.length]); } } 7.杨辉三角 import java.util.Scanner; public class Main { public static void main(String[] args) { int n, i, j; int arr[][] = new int[34][34]; Scanner sc = new Scanner(System.in); n = sc.nextInt(); sc.close(); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { arr[i][0] = 1; if (i == j) { arr[i][j] = 1; } } } // 求和 for (i = 2; i < n; i++) { for (j = 1; j < n; j++) { arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]; } } for (i = 0; i < n; i++) { for (j = 0; j <= i; j++) { System.out.print(arr[i][j] + " "); } System.out.println(); } } } 8.节点选择 import java.util.Scanner; public class Main { public int[][] dp = new int[100002][2]; public int[][] tree = new int[100002][300]; public void creatTree(int point1, int point2) { int i = 0; while(tree[point1][i] != 0) i++; tree[point1][i] = point2; int j = 0; while(tree[point2][j] != 0) j++; tree[point2][j] = point1; } public void dfs(int start, int root) { int child = tree[start][0]; for(int i = 0;child != 0;i++) { child = tree[start][i]; if(child != root) { dfs(child, start); dp[start][1] += dp[child][0]; dp[start][0] += (dp[child][1] > dp[child][0] ? dp[child][1] : dp[child][0]); } } } public static void main(String[] args) { Main test = new Main(); Scanner in = new Scanner(System.in); int n = in.nextInt(); for(int i = 0;i < n;i++) test.dp[i + 1][1] = in.nextInt(); for(int i = 0;i < n - 1;i++) { int point1 = in.nextInt(); int point2 = in.nextInt(); test.creatTree(point1, point2); } test.dfs(1, 0); int max = (test.dp[1][1] > test.dp[1][0] ? test.dp[1][1] : test.dp[1][0]); System.out.println(max); } } 9. 耐摔指数 public class Main { 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 sum=i+sum; x[i]=sum; } sum=1; int k=0; for(int i=0;sum sum=x[i]+sum; k++; } System.out.println(k); } } 10. K 好数 import java.util.Scanner; public class Main { public static int mod = 1000000007; public int[][] dp = new int[102][102]; public void printResult(int K, int L) { for(int i = 0;i < K;i++) dp[1][i] = 1; for(int i = 2;i <= L;i++) { for(int j = 0;j < K;j++) { for(int f = 0;f < K;f++) { if(f - 1 != j && f + 1 != j) { dp[i][j] += dp[i - 1][f]; dp[i][j] %= mod; } } } } int sum = 0; for(int i = 1;i < K;i++) { sum += dp[L][i]; sum %= mod; } System.out.println(sum); } public static void main(String[] args) { Main test = new Main(); Scanner in = new Scanner(System.in); int K = in.nextInt(); int L = in.nextInt(); test.printResult(K, L); } }
