每日刷题记录（十二）
目录
第一题：Fibonacci数列
描述
Fibonacci数列是这样定义的：
F[0] = 0
F[1] = 1
for each i ≥ 2: F[i] = F[i-1] + F[i-2]
因此，Fibonacci数列就形如：0, 1, 1, 2, 3, 5, 8, 13, …，在Fibonacci数列中的数我们称为Fibonacci数。给你一个N，你想让其变为一个Fibonacci数，每一步你可以把当前数字X变为X-1或者X+1，现在给你一个数N求最少需要多少步可以变为Fibonacci数。
输入描述：
输入为一个正整数N(1 ≤ N ≤ 1,000,000)
输出描述：
输出一个最小的步数变为Fibonacci数"
示例1
输入： 15
输出： 2
解题思路：
- 先找到距离n最近的两个Fibonacci数
- 求出这两个Fibonacci数距离n最短的距离
代码实现：
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextInt()) { int n = in.nextInt();int f1 = 0;int f2 = 1;while(n > f2) {int f3 = f1 + f2;f1 = f2;f2 = f3;}int ret = Math.min(n-f1,f2-n);System.out.println(ret);}}
}
第二题：合法括号序列判断
描述
给定一个字符串A和其长度n，请返回一个bool值代表它是否为一个合法的括号串（只能由括号组成）。
测试样例：
“(()())”,6
返回：true
测试样例：
“()a()()”,7
返回：false
测试样例：
“()(()()”,7
返回：false
解题思路：
- 先判断字符串是否为偶数个字符
- 用栈结构实现，栈中存放左括号，当遇到右括号之后，检查栈中是否有左括号，如果有则出栈，如果没有，则说明不匹配
代码实现：
public class Parenthesis {public boolean chkParenthesis(String A, int n) {if(n%2 != 0) {return false;}Stack<Character> stack = new Stack<>();for(char ch : A.toCharArray()) {if(ch == '(') {stack.push(ch);}else if(ch == ')') {if(stack.isEmpty()) {return false;} else if(stack.peek() == '(') {stack.pop();}}else {return false;}}return stack.isEmpty();}
}
第三题：求最小公倍数
描述
正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。
数据范围：
1≤a,b≤100000
输入描述：
输入两个正整数A和B。
输出描述：
输出A和B的最小公倍数。
示例1
输入： 5 7
输出： 35
示例2
输入： 2 4
输出： 4
解题思路：
- 最小公倍数 = 两数之积除以最大公约数
- 使用碾转相除法进行最大公约数的求解，对于输入的两个数进行连续求余，直到
余数为0，求余的分母即为结果
代码实现：
public class Main {public static int fun(int a, int b) {if (a == b) {return a;}if (a < b) {int tmp = a;a = b;b = tmp;}int r = 0;while ((r = a % b) > 0) {a = b;b = r;}return b;}public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNextInt()) {int a = in.nextInt();int b = in.nextInt();int ret = fun(a, b);System.out.println((a*b)/ret);}}
}
第四题：两种排序方法
描述
考拉有n个字符串字符串，任意两个字符串长度都是不同的。考拉最近学习到有两种字符串的排序方法： 1.根据字符串的字典序排序。例如：
“car” < “carriage” < “cats” < "doggies < “koala”
2.根据字符串的长度排序。例如：
“car” < “cats” < “koala” < “doggies” < “carriage”
考拉想知道自己的这些字符串排列顺序是否满足这两种排序方法，考拉要忙着吃树叶，所以需要你来帮忙验证。
输入描述：
输入第一行为字符串个数n(n ≤ 100) 接下来的n行,每行一个字符串,字符串长度均小于100，均由小写字母组成
输出描述：
如果这些字符串是根据字典序排列而不是根据长度排列输出"lexicographically",
如果根据长度排列而不是字典序排列输出"lengths",
如果两种方式都符合输出"both"，否则输出"none"
示例1
输入： 3 a aa bbb
输出： both
解题思路：
- 将接收的字符串都放到String数组中
- 利用string的compareTo方法来按ascii比较字符串字典序排序
- 利用string的length方法来比较字符串的长度排序
代码实现：
import java.util.*;
import java.io.*;public class Main {public static void main(String[] args) throws IOException {BufferedReader re = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(re.readLine());String[] str = new String[n];for (int i = 0; i < n; i++) {str[i] = re.readLine();}if (isSortZhiDian(str) && isSortLength((str))) {System.out.println("both");} else if (isSortZhiDian(str)) {System.out.println("lexicographically");} else if (isSortLength(str)) {System.out.println("lengths");} else {System.out.println("none");}}public static boolean isSortZhiDian(String[] str) {for (int i = 0; i < str.length - 1; i++) {if (str[i].compareTo(str[i + 1]) > 0) {return false;}}return true;}public static boolean isSortLength(String[] str) {for (int i = 0; i < str.length - 1; i++) {if (str[i].length() > str[i + 1].length()) {return false;}}return true;}
}
第五题：另类加法
描述
给定两个int A和B。编写一个函数返回A+B的值，但不得使用+或其他算数运算符。
测试样例：
1,2
返回：3
解题思路：
- 二进制位异或运算相当于对应位相加，不考虑进位
- 二进制位与运算左移一位相当于对应位相加之后的进位
- 两个数相加：对应二进制位相加的结果 + 进位的结果,当进位之后的结果为0时，相加结束
代码实现：
import java.util.*;
public class UnusualAdd {public int addAB(int A, int B) {if(B == 0) {return A;}int sum = 0;int carry = 0;while(B != 0) {sum = A^B;carry = (A&B)<<1;A = sum;B = carry;}return A;}
}