00509 斐波那契數(shù)
題目描述
斐波那契數(shù)，通常用 F(n) 表示，形成的序列稱為斐波那契數(shù)列。該數(shù)列由 0 和 1 開始茅主，后面的每一項(xiàng)數(shù)字都是前面兩項(xiàng)數(shù)字的和。也就是：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
給定 N土榴，計(jì)算 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
力扣地址
解題報(bào)告
本題解由微信公眾號(hào)
小猿刷題提供, 錯(cuò)誤之處, 歡迎指正.
基于遞歸實(shí)現(xiàn)
/**
* 微信公眾號(hào)"小猿刷題"
*/
public int fib(int N) {
if(N == 0){
return 0;
}
if(N == 1){
return 1;
}
return fib(N-2) + fib(N-1);
}
基于數(shù)組實(shí)現(xiàn)
/**
* 微信公眾號(hào)"小猿刷題"
*/
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];
}
基于交換實(shí)現(xiàn)
/**
* 微信公眾號(hào)"小猿刷題"
*/
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 反轉(zhuǎn)字符串
題目描述
編寫一個(gè)函數(shù)，其作用是將輸入的字符串反轉(zhuǎn)過(guò)來(lái)玷禽。輸入字符串以字符數(shù)組 char[] 的形式給出赫段。
不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組矢赁、使用 O(1) 的額外空間解決這一問(wèn)題糯笙。
你可以假設(shè)數(shù)組中的所有字符都是 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"]
力扣地址
解題報(bào)告
本題解由微信公眾號(hào)
小猿刷題提供, 錯(cuò)誤之處, 歡迎指正.
通過(guò)異或?qū)崿F(xiàn)
通過(guò)異或交換字符串的高低位
/**
* 微信公眾號(hào)"小猿刷題"
*/
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實(shí)現(xiàn)
將目標(biāo)字符串從第一個(gè)字符到最后一個(gè)字符逆向追加
/**
* 微信公眾號(hào)"小猿刷題"
*/
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實(shí)現(xiàn)
利用java集合內(nèi)置算法翻轉(zhuǎn)
/**
* 微信公眾號(hào)"小猿刷題"
*/
public static String reverse(String source) {
return new StringBuffer(source).reverse().toString();
}
或者
/**
* 微信公眾號(hào)"小猿刷題"
*/
public static String reverse(String source) {
return new StringBuilder(source).reverse().toString();
}
通過(guò)棧實(shí)現(xiàn)
利用棧先進(jìn)后出的特點(diǎn)進(jìn)行翻轉(zhuǎn)
/**
* 微信公眾號(hào)"小猿刷題"
*/
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;
}
使用遞歸實(shí)現(xiàn)
使用遞歸進(jìn)行左右交換
/**
* 微信公眾號(hào)"小猿刷題"
*/
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);
}
使用二分法
/**
* 微信公眾號(hào)"小猿刷題"
*/
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循環(huán)
/**
* 微信公眾號(hào)"小猿刷題"
*/
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;
}
小猿刷題
