途虎养车笔试21.9.13

编程题1【验证回文字符串 Ⅱ】

力扣原题：680. 验证回文字符串 Ⅱ

1.给定一个非空字符串s,最多删除一个字符，判断是否能成为回文字符串。

示例1：

输入：aba

输出：true

示例2：

输入：abca

输出：true

解释：你可以先删除c字符

示例3：

输入：abcbd

输出：false

解释：从左向右读为abcbd，从右向左读为dbcba。因此不是一个回文数，即使删除一个也没办法做回文数

注意：字符串只包含从a-z的小写字母。字符串的最大长度是50000

做法1：

当时的做法是这样：

package com.lxw.demo;

import java.util.Scanner;

public class Demo06 {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        boolean result = validPalindrome(s);
        System.out.println(result);    

    }

    public static boolean validPalindrome(String s){
        if (f(s)){
            return true;
        }else{

            for (int i = 0; i < s.length(); i++) {
                String sNew = "";
                for (int j = 0; j < s.length(); j++) {
                    if (j!=i){
                        sNew +=s.charAt(j);
                    }
                }
                if (f(sNew)){
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean f(String s){
        int i = 0, j = s.length()-1;
        while(i<j){
            if (s.charAt(i)==s.charAt(j)){
                i++;
                j--;
            }
            else{
                return false;
            }
        }
        return true;
    }
}

虽然当时通过了所有的全部用例，但是始终觉得这样做的效率太低了。尤其是删除一个字符串那里。

参考网上大佬的方法，重新修改代码后：

package com.lxw.demo;

import java.util.Scanner;

public class Demo10 {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        boolean result = validPalindrome(s);
        System.out.println(result);


    }

    public static boolean validPalindrome(String s){
        int i = 0, j = s.length()-1;

        while(i < j){
            if(s.charAt(i) == s.charAt(j)){
                i++;
                j--;
            }else{
                String sub1 = s.substring(i, j); // [i,j-1] 剔除j
                String sub2 = s.substring(i+1, j+1); // [i+1,j] 剔除i
                return f(sub1) || f(sub2);
            }
        }
        return true;
    }

    public static boolean f(String s){
        int i = 0, j = s.length()-1;
        while(i<j){
            if (s.charAt(i)==s.charAt(j)){
                i++;
                j--;
            }
            else{
                return false;
            }
        }
        return true;
    }

}

编程题2【途虎动物园-斐波那契】

在途虎动物园里有一对老虎，从出生后第3个月起每个月都生一对老虎，老虎长到第3个月后每个月又生一对老虎，假如老虎都不死，写下方法函数来计算n个月后的老虎总数为多少？

示例1：

输入1

输出2

示例2：

输入2

输出2

示例3：

输入4

输出6

我的答案：

典型的斐波那契数列问题

2，2，4，6，10，16

package com.lxw.demo;

public class Demo07 {

    public static void main(String[] args) {
        System.out.println(countTiger(4));
    }

    //可以用数组也可以直接计算，本题只计算一次，所以效率一样
    public static int countTiger (int month) {

        int a1 = 2;
        int a2 = 2;
        int a3 = 2;
        int i = 0;
        while(i<month-2) {
            i++;
            a3 = a1+a2;
            a1=a2;
            a2=a3;
        }

        return a3;
    }
}