面试遇到的算法题

1.字符串转换整数

1. 读入字符串并丢弃无用的前导空格
2. 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
3. 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
4. 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
5. 如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
6. 返回整数作为最终结果。

class Solution {
    public int myAtoi(String s) {
        if(s.length() == 0)return 0;
        int index = 0,n = s.length(),sign = 1,res = 0;
        //处理前置空格
        while(index < n && s.charAt(index) == ' ') index++;
        //处理符号
        if(index < n && (s.charAt(index)=='+' || s.charAt(index)=='-')){
            sign = s.charAt(index++) == '+'?1:-1;
        }
        //处理数字
        while(index<n && Character.isDigit(s.charAt(index))){
            int digit = s.charAt(index) - '0';
            //判断是否溢出
            if(res > (Integer.MAX_VALUE - digit)/10){
                return sign == 1? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            res = res*10 + digit;
            index++;
        }
        return res*sign;
    }
}

2.求岛屿周长

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

思路：直接暴力解法，简单易懂：求边长，其实就是判断每个陆地的四周是什么，从上下左右四个方向找，遇到非陆地就可以+1（其实本题的dfs解法也是这个道理，个人感觉没必要用dfs去做搜索）

class Solution {  
    public int islandPerimeter(int[][] grid) {
        int sum = 0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j] == 1) sum = dfs(grid,i,j);
            }
        }
        return sum;
    }
    public int dfs(int[][] grid,int i,int j){
        if(i<0 || i>=grid.length || j<0 || j>=grid[0].length || grid[i][j] == 0)return 1;
        if(grid[i][j] == -1)return 0;
        grid[i][j] = -1;
        int count = 0;
        count += dfs(grid,i+1,j);
        count += dfs(grid,i,j+1);
        count += dfs(grid,i-1,j);
        count += dfs(grid,i,j-1);
        return count;
    }
}

3.设计微信抢红包算法

 
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
 
public class Main {
 
 /*Random 随机生成一个区间在[min , max]的数值
 randNumber 将被赋值为一个 MIN 和 MAX 范围内的随机数
  int randNumber =rand.nextInt(MAX - MIN + 1) + MIN; */
 /**
  * 生成min到max范围的浮点数
  **/
 public static double nextDouble(final double min, final double max) {
  return min + ((max - min) * new Random().nextDouble());
 }
 
 public static String format(double value) {
   
   return new java.text.DecimalFormat("0.00").format(value); // 保留两位小数
  }
 
 
 //二倍均值法
 public static List<Double> doubleMeanMethod(double money,int number){
  List<Double> result = new ArrayList<Double>();
  if(money<0&&number<1)
   return null;
  double amount,sum=0;
  int remainingNumber=number;
  int i=1;
  while(remainingNumber>1){
   amount= nextDouble(0.01,2*(money/remainingNumber));
   sum+=amount;
   System.out.println("第"+i+"个人领取的红包金额为："+format(amount));
   money -= amount;
   remainingNumber--;
   result.add(amount);
   i++;
  }
  result.add(money);
  System.out.println("第"+i+"个人领取的红包金额为："+format(money));
  sum+=money;
  System.out.println("验证发出的红包总金额为："+format(sum));
  
  return result;
  
 }
 
 
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int number;
  double money;
  System.out.print("请输入红包总金额：");
  money = sc.nextDouble();
  System.out.print("请输入红包数量：");
  number = sc.nextInt();
  //System.out.println(money + " " + number);
  //二倍均值法
  doubleMeanMethod(money,number);
  //System.out.println(doubleMeanMethod(money,number).toString());
  //也是可以直接输出list的，为了观察方便，我就在循环中输出了，存在list里主要是为了后续方便数据的使用
  System.out.println();
 
 }
 
}