9.9 用友笔试
1.兔子数量----斐波那契数列
public class Main1 {
public long calculateTotal (int count) {
// write code here
int prepre=1;
int pre=1;
int cur=0;
if(count==1||count==2) return 1;
while(count-->2){
cur=prepre+pre;
prepre=pre;
pre=cur;
}
return cur;
}
} 2.岛屿大小----DFS import java.util.Scanner;
public class Main2 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n=0;
String[][] grid = new String[100][];
while (scanner.hasNextLine()){
grid[n++]= scanner.nextLine().split(",");
}
int m=grid[0].length;
int max=0;
for (int i = 0; i <n ; i++) {
for (int j = 0; j < m; j++) {
if(grid[i][j].equals("1")){
max=Math.max(max,dfs(n,m,grid,i,j));
}
}
}
System.out.println(max);
}
static int dfs(int n,int m,String[][] grid,int x,int y){
if(x<0||x>=n||y<0||y>=m||grid[x][y].equals("0")) return 0;
grid[x][y]="0";
return 1+dfs(n, m, grid, x+1, y)+dfs(n, m, grid, x, y+1)+dfs(n, m, grid, x-1, y)+dfs(n, m, grid, x, y-1);
}
} 3.保安上楼----向前向后遍历 import java.util.Arrays;
public class Main3 {
public int[] findBuilding (int[] heights) {
// write code here
int n=heights.length;
int[] dp = new int[n];
Arrays.fill(dp,1);
for (int i = 0; i < n; i++) {
int Lmin=0;
int Rmin=0;
for (int j = i-1; j >= 0; j--) {
if(heights[j]>Lmin){
dp[i]++;
Lmin=heights[j];
}
}
for (int j = i+1; j < n; j++) {
if(heights[j]>Rmin){
dp[i]++;
Rmin=heights[j];
}
}
}
return dp;
}
} 
