00509 斐波那契数
题目描述
斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N，计算 F(N)。
示例 1：
输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
示例 2：
输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
示例 3：
输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
提示：
0 ≤ N ≤ 30
力扣地址
解题报告
本题解由微信公众号
小猿刷题提供, 错误之处, 欢迎指正.
基于递归实现
/**
* 微信公众号"小猿刷题"
*/
public int fib(int N) {
if(N == 0){
return 0;
}
if(N == 1){
return 1;
}
return fib(N-2) + fib(N-1);
}
基于数组实现
/**
* 微信公众号"小猿刷题"
*/
public int fib(int N) {
if(N == 0){
return 0;
}
if(N == 1){
return 1;
}
int [] arr = new int[N+1];
arr[0] = 0;
arr[1] = 1;
for(int i = 2; i <= N; i++){
arr[i] = arr[i-2] + arr[i-1];
}
return arr[N];
}
基于交换实现
/**
* 微信公众号"小猿刷题"
*/
public int fib(int N) {
if(N == 0){
return 0;
}
if(N == 1){
return 1;
}
int a = 0;
int b = 1;
for(int i = 2; i <= N; i++){
int sum = a + b;
a = b;
b = sum;
}
return b;
}
小猿刷题
00344 反转字符串
题目描述
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
力扣地址
解题报告
本题解由微信公众号
小猿刷题提供, 错误之处, 欢迎指正.
通过异或实现
通过异或交换字符串的高低位
/**
* 微信公众号"小猿刷题"
*/
public static String reverse(String source){
char[] chars = source.toCharArray();
int low = 0;
int top = chars.length - 1;
while (low < top){
chars[low] ^= chars[top];
chars[top] ^= chars[low];
chars[low] ^= chars[top];
low++;
top--;
}
return new String(chars);
}
使用charAt实现
将目标字符串从第一个字符到最后一个字符逆向追加
/**
* 微信公众号"小猿刷题"
*/
public static String reverse(String source) {
int length = source.length();
String reverse = "";
for (int i = 0; i < length; i++) {
reverse = source.charAt(i) + reverse;
}
return reverse;
}
使用StringBuffer或者StringBuilder实现
利用java集合内置算法翻转
/**
* 微信公众号"小猿刷题"
*/
public static String reverse(String source) {
return new StringBuffer(source).reverse().toString();
}
或者
/**
* 微信公众号"小猿刷题"
*/
public static String reverse(String source) {
return new StringBuilder(source).reverse().toString();
}
通过栈实现
利用栈先进后出的特点进行翻转
/**
* 微信公众号"小猿刷题"
*/
public static String reverse(String source) {
char[] chars = source.toCharArray();
Stack<Character> stack = new Stack<Character>();
for (char ch : chars) {
stack.push(ch);
}
String target = "";
while (!stack.isEmpty()) {
target += stack.pop();
}
return target;
}
使用递归实现
使用递归进行左右交换
/**
* 微信公众号"小猿刷题"
*/
public static String reverse(String source) {
int length = source.length();
if (length <= 1) {
return source;
}
String left = source.substring(0, length / 2);
String right = source.substring(length / 2, length);
return reverse(right) + reverse(left);
}
使用二分法
/**
* 微信公众号"小猿刷题"
*/
public static String reverse(String source) {
char[] s = source.toCharArray();
int n = s.length - 1;
int half = n / 2;
for (int i = 0; i <= half; i++) {
char temp = s[i];
s[i] = s[n - i];
s[n - i] = temp;
}
return new String(s);
}
使用for循环
/**
* 微信公众号"小猿刷题"
*/
public static String reverse(String source) {
char[] array = source.toCharArray();
String reverse = "";
for (int i = array.length - 1; i >= 0; i--)
reverse += array[i];
return reverse;
}
小猿刷题
