回文数判断

  1. //回文数判断
  2.     public static boolean isPalindrome(int x) {
  3.         String s = String.valueOf(x);  //int转换为String
  4.         char[] arr = new char[s.length()];  //s.length() -->返回字符串长度
  5.         for (int i = 0, len = arr.length; i < len; i++) {
  6.             arr[i] = s.charAt(i);  //遍历字符串每个字符，存入字符数组arr中
  7.         }
  8.         //System.out.println(Arrays.toString(arr));
  9.         char[] arr1 = new char[s.length()];
  10.         for (int i = 0, len = arr1.length; i < len; i++) {
  11.             arr1[i] = s.charAt(len-i-1);
  12.         }
  13.         //System.out.println(Arrays.toString(arr1));
  14.         for (int i = 0;i<s.length();i++){
  15.             if (arr[i]!=arr1[i]){
  16.                 return false;
  17.             }
  18.         }
  19.         return true;
  20.     }

两数相加

  1.     public int[] twoSum(int[] nums, int target) {
  2.         int[] arr = new int[2];
  3.         for(int i = 0;i < nums.length;i++){
  4.             for(int j = i+1;j < nums.length;j++){
  5.                 if(nums[i]+nums[j]==target){
  6.                     arr[0]=i;
  7.                     arr[1]=j;
  8.                     break;
  9.                 }
  10.             }
  11.         }
  12.         return arr;
  13.     }

罗马数字

  1.  //罗马数字
  2.     public static int romanToInt(String s) {
  3.         char[] arr = new char[s.length()];  //s.length() -->返回字符串长度
  4.         for (int i = 0, len = arr.length; i < len; i++) {
  5.             arr[i] = s.charAt(i);  //遍历字符串每个字符，存入字符数组arr中
  6.         }
  7.         System.out.println(Arrays.toString(arr));
  8.         int result = 0;
  9.         for (int i = 0; i < arr.length; i++) {
  10.             switch (arr[i]) {
  11.                 case 'I':
  12.                     if (arr[i+1]!='V' && arr[i+1]!='X'){
  13.                         result += 1;
  14.                     }
  15.                     if (arr[i+1]=='V'){
  16.                         result += 4;
  17.                         i++;
  18.                     }
  19.                     if (arr[i+1]=='X'){
  20.                         result += 9;
  21.                         i++;
  22.                     }
  23.                     break;
  24.                 case 'V':
  25.                     result += 5;
  26.                     break;
  27.                 case 'X':
  28.                     result += 10;
  29.                     break;
  30.                 case 'L':
  31.                     result += 50;
  32.                     break;
  33.                 case 'C':
  34.                     result += 100;
  35.                     break;
  36.                 case 'D':
  37.                     result += 500;
  38.                     break;
  39.                 case 'M':
  40.                     result += 1000;
  41.                     break;
  42.                 //你可以有任意数量的case语句
  43.                 default:
  44.                     System.out.println("输入有误！");
  45.                     break;
  46.             }
  47.         }
  48.         return result;
  49.     }

整数反转

  1. public static int reverse(int x) {
  2.         if(x==0){
  3.             return 0;
  4.         }
  5.         String s = String.valueOf(x);  //int转换为String
  6.         int len = s.length();
  7.         //判断如果为负数,需截取掉前面的符号,长度减一
  8.         //不能使用Math.abs取绝对值,-2147483648取绝对值后还是为负数
  9.         if (x<0){
  10.             s = s.substring(1,len);
  11.             len = len-1;
  12.         }
  13.         char[] arr = new char[len];  //s.length() -->返回字符串长度
  14.         for (int i = 0; i < len; i++) {
  15.             arr[i] = s.charAt(len - i - 1);  //遍历字符串每个字符，倒序存入字符数组arr中
  16.         }
  17.         StringBuilder sb = new StringBuilder();
  18.         int flag = 0;  //标志第一个0
  19.         for (int i = 0; i < len; i++) {
  20.             if (arr[i] != '0') {
  21.                 flag = 1;
  22.             }
  23.             if (flag == 1) {
  24.                 sb.append(arr[i]);
  25.             }
  26.         }
  27.         String ss = sb.toString();  //StringBuilder转字符串
  28.         long result = Long.parseLong(ss);  //因为ss转为数值后可能会大于2^31,所以不能使用int储存
  29.         if (x < 0) {
  30.             result = -Math.abs(result);
  31.         }
  32.         //2,147,483,648
  33.         if (result > (Math.pow(2, 31) - 1) || result < Math.pow(-2, 31)) {
  34.             result = 0;
  35.         }
  36.         int xxx = (int)result; //long转int
  37.         return xxx;
  38.     }

字符串转整数

  1. //字符串转整数
  2.     public static int myAtoi(String s) {
  3.         System.out.println(s);
  4. //        if (s.isBlank()){
  5. //            return 0;
  6. //        }
  7.         StringBuilder sb = new StringBuilder();
  8.         s = s.trim();  //去除空格
  9.         int flag = 0;  //标志为正
  10.         if (s.charAt(0) >= 58 || s.charAt(0) <= 47) {
  11.             if (s.charAt(0) == 45) {
  12.                 flag = 1; //标志为负
  13.             } else if (s.charAt(0)==43){
  14.                 flag = 0;
  15.             }else{
  16.                 return 0;
  17.             }
  18.         }
  19.         int flag1 =0;
  20.         for (int i = 0, len = s.length(); i < len; i++) {
  21.             if (s.charAt(i) < 58 && s.charAt(i) > 47) {
  22.                 sb.append(s.charAt(i));
  23.                 flag1 =1;
  24.             }else if (i!=0){
  25.                 if (flag1==0){
  26.                     sb.append('0');
  27.                 }
  28.                 break;
  29.             }
  30.         }
  31.         StringBuilder sb1 = new StringBuilder();
  32.         if (flag == 1&&s.length()!=1) {
  33.             sb1.append("-").append(sb);
  34.         } else {
  35.             sb1.append(sb);
  36.         }
  37.         String str = sb1.toString();
  38.         System.out.println("str:"+str);
  39.         if (s.length()>19){
  40.             return 0;
  41.         }
  42.         long result = Long.parseLong(str);  //18,446,744,073,709,551,616
  43.         if (result > (Math.pow(2, 31) - 1)) {
  44.             result = 2147483647;
  45.         } else if (result < Math.pow(-2, 31)) {
  46.             result = -2147483648;
  47.         }
  48.         int xxx = (int) result;
  49.         return xxx;
  50.     }

用两个栈实现队列

栈—>只能在栈顶执行添加或删除操作.

  1. class CQueue {
  2.     //两个栈，一个出栈，一个入栈
  3.     private Stack<Integer> s1;  //执行添加
  4.     private Stack<Integer> s2;  //执行删除
  5.     private int size;  //记录删除添加元素的操作次数
  7.     public CQueue() {
  8.         //初始化
  9.         s1 = new Stack<>();
  10.         s2 = new Stack<>();
  11.     }
  13.     public void appendTail(int value) {
  14.         s1.push(value);
  15.         size++;  //增加一次
  16.     }
  18.     public int deleteHead() {
  19.         //先判断
  20.         if (size == 0) {
  21.             return -1;
  22.         }
  23.         //s2栈 为空
  24.         if (s2.empty()) {
  25.             //当s1栈不为空,将s1的所有元素 倒给 s2栈 **
  26.             //--> s1栈就变为空,s2栈为原s1栈 倒置
  27.             while (!s1.empty()) {
  28.                 s2.push(s1.pop());
  29.             }
  30.         }
  31.         size--;  //删除一次
  32.         return s2.pop();
  33.     }
  34. }
  1.  public static void main(String[] args){
  2.         CQueue obj = new CQueue();
  3.         int param_0 = obj.deleteHead();
  4.         obj.appendTail(5);
  5.         obj.appendTail(2);
  6.         int param_1 = obj.deleteHead();
  7.         int param_2 = obj.deleteHead();
  8.     }

剑指 Offer 10- I. 斐波那契数列

递归效率极低!!!会超时
方式一:使用BigDecimal数组,可储存2的64次方以上的数,使用循环,计算出结果再取余

  1.  /*
  2.            斐波那契数列
  3.            n=[0,100]
  4.      */
  5.     public static void main(String[] args) {
  6.         long start = System.currentTimeMillis();
  7.         //System.out.println(fib(50));  //32214毫秒
  8.         System.out.println(fib1(95));  //1毫秒
  9.         long end = System.currentTimeMillis();
  10.         System.out.println("耗时:" + (end - start) + "毫秒");
  11.     }
  12.  public static int fib(int n) {
  13.         if (n < 2) {
  14.             return n;
  15.         }
  16.         return fib(n - 1) + fib(n - 2);
  17.     }
  19.     public static int fib1(int n) {
  20.         int mod = 1000000007;  //取余
  21.         int len = 101;
  22.         BigDecimal[] arr = new BigDecimal[len];
  23.         arr[0] = BigDecimal.valueOf(0);
  24.         arr[1] = BigDecimal.valueOf(1);
  25.         //只计算到 arr[n]
  26.         for (int i = 2; i < (n + 1); i++) {
  27.             arr[i] = arr[i - 1].add(arr[i - 2]);  //add 相加
  28.         }
  29.         //divideAndRemainder 返回一个数组: result[0]为商,result[1]为余
  30.         BigDecimal[] result = arr[n].divideAndRemainder(BigDecimal.valueOf(mod));
  31.         return result[1].intValue(); //转为int返回
  32.     }
  34.     public static int fib2(int n) {
  35.         int mod = 1000000007;  //取余
  36.         int[] arr = new int[n + 1];
  37.         //arr[0] = 0;  //可省-->默认值为0
  38.         arr[1] = 1;
  39.         for (int i = 2; i < (n + 1); i++) {
  40.             arr[i] = arr[i - 1] + (arr[i - 2]);
  41.             //每当下一项大于mod时,减去mod,即相当于进行取余操作,以减法代替取余 效率更高
  42.             if (arr[i] > mod) {
  43.                 arr[i] -= mod;
  44.             }
  45.         }
  46.         return arr[n];
  47.     }
  49.     public static int fib3(int n) {
  50.         if (n <= 1) {
  51.             return n;
  52.         }
  53.         int mod = 1000000007;  //取余
  54.         int f = 0;  //first
  55.         int s = 1;  //second
  56.         int result = 0;
  57.         while (--n > 0) {
  58.             result = f + s;
  59.             if (result > mod) {
  60.                 result -= mod;
  61.             }
  62.             f = s;
  63.             s = result;
  64.         }
  65.         return result;
  66.     }