「算法」斐波那契数 & 反转字符串

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

力扣地址

• https://leetcode.com/problems/fibonacci-number/
• https://leetcode-cn.com/problems/fibonacci-number/

解题报告

本题解由微信公众号小猿刷题提供, 错误之处, 欢迎指正.

基于递归实现

/**
 *  微信公众号"小猿刷题"
 */
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"]

力扣地址

• https://leetcode.com/problems/reverse-string/
• https://leetcode-cn.com/problems/reverse-string/

解题报告

本题解由微信公众号小猿刷题提供, 错误之处, 欢迎指正.

通过异或实现

通过异或交换字符串的高低位

/**
 *  微信公众号"小猿刷题"
 */
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;
}

小猿刷题