問題描述

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.
Given N, calculate F(N).

Example:

翻譯

• 經典不敗題型
• 費式數列，通常使用 F(n)來表示數列，每一個數都是由前兩個數所構成的，頭兩個數值分別為 0,1

解題思維

1. 遞迴版本：每次呼叫 fib(N-1)+fib(N-2)，若 N 為 0 則回傳 0,1 則回傳 1，最終回傳答案
2. 迭代版本：先開好 N 個空間的陣列，頭兩個元素分別設為 1,1，透過迭代方式，最後回傳最後一個元素

解題報告

Level: Easy
Time Complexity: O(n)
Runtime: 0 ms, faster than 100.00% of Java online submissions for Fibonacci Number.
Memory Usage: 36.3 MB, less than 5.51% of Java online submissions for Fibonacci Number.

程式完整解題

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    //遞迴版本
    public int fib(int N) {
         if(N<=1)
            return N;
         return fib(N-1)+fib(N-2);
    }

    //迭代版本
    public int fib(int n) {
        if(n<2){
         return n;
        }else {
          int[] ans = new int[n];
              ans[0] = 1;
              ans[1] = 1;
              for(int i=2;i<n;i++) {
                  ans[i]=ans[i-1]+ans[i-2];
              }
              return ans[n-1];
        }
    }
}

問題描述

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

翻譯

給定兩個排序過整數陣列，請將兩組陣列合併成一個排序過後的陣列
nums1、nums2 陣列大小分別為 m、n，你可以假定 nums1 有足夠的額外空間(空間可能是 n + m，或者更大)存放從 num2 陣列的元素。

解題思維

1. 由於已知 num1 有足夠空間存放來自 num2 的元素，所以我們可以將 num2 元素從 num1 末端插入
2. 重新排序

解題報告

Level: Easy
Time Complexity: O(nlog(n))
Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Sorted Array.
Memory Usage: 39.7 MB, less than 5.94% of Java online submissions for Merge Sorted Array.

程式完整解題

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import java.util.Arrays;
class Solution {
    /**
    *@param nums1 陣列一
    *@param m 陣列一大小
    *@param nums2 陣列二
    *@param n 陣列二大小
    *@return
    **/
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for(int i = m ; i < n + m ; i++)
            nums1[i] = nums2[i-m];

        Arrays.sort(nums1);
    }
}

問題描述

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

翻譯

給定一個非空存正整數位數的陣列，你要替這串數值加上一
最高有效數位存放在陣列初始位置，數值每個數字各依序別存在陣列裡頭
你能假定這串整數不以零開頭，除了本身為零

解題思維

1. 先替陣列最後一個數值加上一
2. 以迭代方式判斷是否大於 9，以此判斷是否要進位
3. 最後判斷進位的變數是否不等於零，若不為零，將進位數填入陣列第一個位置
   ，將計算後陣列依序填入新的陣列

解題報告

Level: Easy
Time Complexity: O(n)
Runtime: 0 ms, faster than 100.00% of Java online submissions for Plus One.
Memory Usage: 37.9 MB, less than 5.64% of Java online submissions for Plus One.

程式完整解題

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    /** 數值陣列加一
    * @param 數值陣列
    * @return 加一後的數值陣列
    */
    public int[] plusOne(int[] digits) {
        digits[digits.length - 1 ] += 1;

        int carry = 0;
        for(int i = digits.length - 1 ; i >= 0 ; i--){
            digits[i] += carry;
            if(digits[i] > 9){
                digits[i] %= 10;
                carry = 1;
            } else{
                carry = 0;
            }
        }

        if(carry == 1){
            int[] answer = new int[digits.length + 1 ];
            answer[0] = carry;
            System.arraycopy(answer, 1, digits, 0, digits.length);
            return answer;
        }
         return digits;
    }
}