題目連結

844. Backspace String Compare

問題描述

Given two strings s and t, return true if they are equal when both are typed into empty text editors. ‘#’ means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: s = “ab#c”, t = “ad#c”
Output: true
Explanation: Both s and t become “ac”.
Example 2:

Input: s = “ab##”, t = “c#d#”
Output: true
Explanation: Both s and t become “”.
Example 3:

Input: s = “a##c”, t = “#a#c”
Output: true
Explanation: Both s and t become “c”.
Example 4:

Input: s = “a#c”, t = “b”
Output: false
Explanation: s becomes “c” while t becomes “b”.

翻譯

• 給定兩字串分別是s、 跟t，被輸入到空的文字編輯器的這兩段字串如果是一樣
  ，則回傳true，#表示一個退格鍵。
• 請注意在空字串輸入退格鍵，這段文字仍為空白。

解題思維

從字串頭讀到字串尾的解法

1. 準備一個Stack，以迭代方式讀取兩個字串中各個字元，將其儲存到Stack
2. 當讀取到字元是退格鍵#，將目前儲存在Stack第一個字元pop
   • ‘#’不儲到Stack
3. 最後將仍儲存在Stack的字元輸出成字串，即可以比對兩串字串是否一樣
4. 請參考Java解法

從字串尾讀到字串頭的解法

1. 從字串尾開始讀取各個字元
2. 當讀取到字元是退格鍵#，累加變數
   • 變數用來決定讀取下一個字元是否要跳過
3. 變數大於0，跳過該字元
4. 最後比對去除刪除部分字元字串是否一樣
5. 請參考C++解法

解題報告

Level: Easy
Time Complexity: O(n)
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Backspace String Compare.
Memory Usage: 6.3 MB, less than 57.92% of C++ online submissions for Backspace String Compare.

程式完整解題

Java 解法

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

class Solution {
    public boolean backspaceCompare(String s, String t) {
        return removeBackSpaces(s).removeBackSpaces(t);
    }
    
    private String removeBackSpaces(String str){
       Stack<Character> stack = new Stack<>();
       StringBuilder builder = new StringBuilder();
       for(char c : str.toCharArray()){
           if(c == '#') {
               if(!stack.isEmpty()) {
                   stack.pop();
               }
           } else {
               stack.push(c);
           }
       }
       
       while(!stack.isEmpty()){
           builder.append(stack.pop());
       }
       return builder.toString();
    }
}

C++ 解法

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

#include <string>
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        return removeBackSpaces(s).compare(removeBackSpaces(t)) == 0;
    }
private:
    string removeBackSpaces(string str) {
        string newString;
        int skip = 0;
        for(int i = str.length() - 1; i >= 0; i--) {
            if(str[i] == '#') {
                skip++;
            } else {
                if(skip > 0) {
                    skip--;
                } else {
                    newString.push_back(str[i]);
                }
            }
        }
        return newString;
    }
};

問題描述

The Employee table holds all employees. Every employee has an Id, and there is also a column for the department Id.

The Department table holds all departments of the company.

Write a SQL query to find employees who earn the top three salaries in each of the department. For the above tables, your SQL query should return the following rows (order of rows does not matter).

翻譯

• Employee 表格紀錄員工資訊，每位員工擁有 Id, 及所屬部門代碼。
• Department 表格紀錄公司所有部門資訊。
• 請撰寫一段 SQL 查詢，找出各部門業績排行的前三名，同名並列。

解題思維

利用 DENSE_RANK()函數以部門代號切割，業績從高至低排名
最後撈取前三名(含)，就可得出答案

解題報告

Level: Hard
Runtime: 1173 ms, faster than 80.22% of Oracle online submissions for Department Top Three Salaries.
Memory Usage: 0B, less than 100.00% of Oracle online submissions for Department Top Three Salaries.

程式完整解題

1
2
3
4
5
6
7
8
9
10
11
12

/* Write your PL/SQL query statement below */
SELECT DEPARTMENT
      ,EMPLOYEE
      ,SALARY
  FROM(SELECT DP.NAME   AS DEPARTMENT
             ,EM.NAME   AS EMPLOYEE
             ,EM.SALARY AS SALARY
             ,DENSE_RANK() OVER(PARTITION BY EM.DEPARTMENTID ORDER BY EM.SALARY DESC) AS RANK
         FROM EMPLOYEE   EM
         JOIN DEPARTMENT DP
           ON EM.DEPARTMENTID = DP.ID)
 WHERE RANK <= 3;

SQL Schema

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

Create table If Not Exists Employee (Id int, Name varchar(255), Salary int, DepartmentId int)
Create table If Not Exists Department (Id int, Name varchar(255))
Truncate table Employee
insert into Employee (Id, Name, Salary, DepartmentId) values ('1', 'Joe', '85000', '1')
insert into Employee (Id, Name, Salary, DepartmentId) values ('2', 'Henry', '80000', '2')
insert into Employee (Id, Name, Salary, DepartmentId) values ('3', 'Sam', '60000', '2')
insert into Employee (Id, Name, Salary, DepartmentId) values ('4', 'Max', '90000', '1')
insert into Employee (Id, Name, Salary, DepartmentId) values ('5', 'Janet', '69000', '1')
insert into Employee (Id, Name, Salary, DepartmentId) values ('6', 'Randy', '85000', '1')
insert into Employee (Id, Name, Salary, DepartmentId) values ('7', 'Will', '70000', '1')
Truncate table Department
insert into Department (Id, Name) values ('1', 'IT')
insert into Department (Id, Name) values ('2', 'Sales')

問題描述

The Trips table holds all taxi trips. Each trip has a unique Id, while Client_Id and Driver_Id are both foreign keys to the Users_Id at the Users table. Status is an ENUM type of (‘completed’, ‘cancelled_by_driver’, ‘cancelled_by_client’).

The Users table holds all users. Each user has an unique Users_Id, and Role is an ENUM type of (‘client’, ‘driver’, ‘partner’).

Write a SQL query to find the cancellation rate of requests made by unbanned users (both client and driver must be unbanned) between Oct 1, 2013 and Oct 3, 2013. The cancellation rate is computed by dividing the number of canceled (by client or driver) requests made by unbanned users by the total number of requests made by unbanned users.

For the above tables, your SQL query should return the following rows with the cancellation rate being rounded to two decimal places.

翻譯

• Trips 表格紀錄所有計程車的乘車紀錄，每一筆資料 Id 為唯一值, 其中 Client_Id, Driver_Id 為外部鍵，參照 Users 表格的 Users_Id，Status 為列舉型態，表示三種狀態，分別為”完成乘車”、”司機取消載客”、”乘客取消乘車”。
• Users 表格紀錄所有使用者，每一筆紀錄 Users_Id 為唯一值，其中 Role 欄位為列舉型態，分別為”司機”、”乘客”、”夥伴”。
• 請撰寫一段 SQL 查詢，找出 2013 年 10 月 1 日至 2013 年 10 月 3 日三日的當日乘車取消率，計算公式如下。
• 當日由”司機取消載客”、”乘客取消乘車”乘車紀錄次數 / 當日乘車紀錄總次數，且司機與乘客不得為禁用狀態。

解題思維

TRIPS 以 JOIN 方式關聯 Users 兩次，條件分別為乘客、司機非禁用狀態，時間篩選在 2013 年 10 月 1 日至 2013 年 10 月 3 日三日
再 COUNT, SUM 函數分別對第一步驟的結果計算出乘車紀錄總次數、取消乘車紀錄次數
最後使用 GROUP BY 方式，就可以得出三日當日的乘車取消率

解題報告

Level: Hard
Runtime: 796 ms, faster than 82.29% of Oracle online submissions for Trips and Users.
Memory Usage: 0B, less than 100.00% of Oracle online submissions for Trips and Users.

程式完整解題

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

/* Write your PL/SQL query statement below */
WITH TAXI AS(SELECT  TRIPS.STATUS       AS STATUS
                    ,TRIPS.REQUEST_AT   AS REQUESTED_DATE
               FROM TRIPS
               JOIN Users CLIENTS
                 ON (CLIENTS.Users_Id = TRIPS.CLIENT_ID)
                AND CLIENTS.BANNED = 'No'
               JOIN Users DRIVERS
                 ON (DRIVERS.Users_Id = TRIPS.CLIENT_ID)
                AND DRIVERS.BANNED = 'No'
              WHERE TO_DATE(TRIPS.REQUEST_AT, 'YYYY-MM-DD') BETWEEN TO_DATE('2013-10-01', 'YYYY-MM-DD') AND TO_DATE('2013-10-03', 'YYYY-MM-DD'))

SELECT TOTAL_REQ.REQ_DATE                                    AS "Day"
      ,ROUND(CANCELLEDL_REQ.TIMES *1.0/ TOTAL_REQ.TIMES, 2)  AS "Cancellation Rate"
  FROM  (SELECT REQUESTED_DATE AS REQ_DATE
               ,COUNT(*)       AS TIMES
          FROM TAXI
          GROUP BY REQUESTED_DATE) TOTAL_REQ
  JOIN(SELECT REQUESTED_DATE  AS REQ_DATE
             ,SUM(CASE WHEN (STATUS = 'cancelled_by_client' OR STATUS = 'cancelled_by_driver') THEN 1
                           ELSE 0 END)      AS TIMES
         FROM TAXI
        GROUP BY REQUESTED_DATE) CANCELLEDL_REQ
    ON TOTAL_REQ.REQ_DATE = CANCELLEDL_REQ.REQ_DATE
 ORDER BY TOTAL_REQ.REQ_DATE

SQL Schema

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

Create table If Not Exists Trips (Id int, Client_Id int, Driver_Id int, City_Id int, Status ENUM('completed', 'cancelled_by_driver', 'cancelled_by_client'), Request_at varchar(50))
Create table If Not Exists Users (Users_Id int, Banned varchar(50), Role ENUM('client', 'driver', 'partner'))
Truncate table Trips
insert into Trips (Id, Client_Id, Driver_Id, City_Id, Status, Request_at) values ('1', '1', '10', '1', 'completed', '2013-10-01')
insert into Trips (Id, Client_Id, Driver_Id, City_Id, Status, Request_at) values ('2', '2', '11', '1', 'cancelled_by_driver', '2013-10-01')
insert into Trips (Id, Client_Id, Driver_Id, City_Id, Status, Request_at) values ('3', '3', '12', '6', 'completed', '2013-10-01')
insert into Trips (Id, Client_Id, Driver_Id, City_Id, Status, Request_at) values ('4', '4', '13', '6', 'cancelled_by_client', '2013-10-01')
insert into Trips (Id, Client_Id, Driver_Id, City_Id, Status, Request_at) values ('5', '1', '10', '1', 'completed', '2013-10-02')
insert into Trips (Id, Client_Id, Driver_Id, City_Id, Status, Request_at) values ('6', '2', '11', '6', 'completed', '2013-10-02')
insert into Trips (Id, Client_Id, Driver_Id, City_Id, Status, Request_at) values ('7', '3', '12', '6', 'completed', '2013-10-02')
insert into Trips (Id, Client_Id, Driver_Id, City_Id, Status, Request_at) values ('8', '2', '12', '12', 'completed', '2013-10-03')
insert into Trips (Id, Client_Id, Driver_Id, City_Id, Status, Request_at) values ('9', '3', '10', '12', 'completed', '2013-10-03')
insert into Trips (Id, Client_Id, Driver_Id, City_Id, Status, Request_at) values ('10', '4', '13', '12', 'cancelled_by_driver', '2013-10-03')
Truncate table Users
insert into Users (Users_Id, Banned, Role) values ('1', 'No', 'client')
insert into Users (Users_Id, Banned, Role) values ('2', 'Yes', 'client')
insert into Users (Users_Id, Banned, Role) values ('3', 'No', 'client')
insert into Users (Users_Id, Banned, Role) values ('4', 'No', 'client')
insert into Users (Users_Id, Banned, Role) values ('10', 'No', 'driver')
insert into Users (Users_Id, Banned, Role) values ('11', 'No', 'driver')
insert into Users (Users_Id, Banned, Role) values ('12', 'No', 'driver')
insert into Users (Users_Id, Banned, Role) values ('13', 'No', 'driver')

問題描述

Write a SQL query to find all numbers that appear at least three times consecutively.

For example, given the above Logs table, 1 is the only number that appears consecutively for at least three times.

翻譯

請寫出一段 SQL 查詢能找出所有連續出現三次以上的數字

解題思維

利用 LEAD(), LAG() Oracle 分析函數可分別得出該數字的上下數字，再判斷上下數字、與該數字都是否相等，即為答案。

解題報告

Level: Medium
Runtime: 678 ms, faster than 98.93% of Oracle online submissions for Consecutive Numbers.
Memory Usage: 0B, less than 100.00% of Oracle online submissions for Consecutive Numbers.

程式完整解題

1
2
3
4
5
6
7
8
9

/* Write your PL/SQL query statement below */
SELECT NUM AS ConsecutiveNums
  FROM(SELECT NUM
             ,LEAD(NUM) OVER (ORDER BY ID) AS NEXT_NUM
             ,LAG(NUM)  OVER (ORDER BY ID) AS LAST_NUM
         FROM Logs)
 WHERE NEXT_NUM = LAST_NUM
   AND NEXT_NUM = NUM
 GROUP BY NUM;

SQL Schema

1
2
3
4
5
6
7
8
9

Create table If Not Exists Logs (Id int, Num int)
Truncate table Logs
insert into Logs (Id, Num) values ('1', '1')
insert into Logs (Id, Num) values ('2', '1')
insert into Logs (Id, Num) values ('3', '1')
insert into Logs (Id, Num) values ('4', '2')
insert into Logs (Id, Num) values ('5', '1')
insert into Logs (Id, Num) values ('6', '2')
insert into Logs (Id, Num) values ('7', '2')

問題描述

Write a SQL query to rank scores. If there is a tie between two scores, both should have the same ranking. Note that after a tie, the next ranking number should be the next consecutive integer value. In other words, there should be no “holes” between ranks.

For example, given the above Scores table, your query should generate the following report (order by highest score):

Important Note: For MySQL solutions, to escape reserved words used as column names, you can use an apostrophe before and after the keyword. For example Rank.

翻譯

請撰寫一段 SQL 查詢排名以下分數，若兩個分數趨近一樣，將並列為同一名次，下一個名次取次排名，換言之，並列後的分數後不會空出排名。
您必須產出如以下的依據分數從高至低的查詢結果。
注意：如果是以 MySql 作答，你可以在 Rank 前後加入撇號(`)來跳脫保留字當作是欄位名稱。

解題思維

用法： [ROW_NUM()|RANK()|DENSE_RANK()] OVER([PARTITION BY 欄位名稱] ORDER BY 欄位名稱 [DESC|ASC])
解題是利用 Oracle 分析函數進行排名，詳細可參考[Oracle SQL] rank(), dense_rank(), row_number()分析函數用法

解題報告

Level: Medium
Runtime: 544 ms, faster than 93.42% of Oracle online submissions for Rank Scores.
Memory Usage: 0B, less than 100.00% of Oracle online submissions for Rank Scores.

程式完整解題

1
2
3
4

/* Write your PL/SQL query statement below */
SELECT SCORE
      ,DENSE_RANK() OVER (ORDER BY SCORE DESC) AS RANK
  FROM SCORES;

SQL Schema

1
2
3
4
5
6
7
8

Create table If Not Exists Scores (Id int, Score DECIMAL(3,2))
Truncate table Scores
insert into Scores (Id, Score) values ('1', '3.5')
insert into Scores (Id, Score) values ('2', '3.65')
insert into Scores (Id, Score) values ('3', '4.0')
insert into Scores (Id, Score) values ('4', '3.85')
insert into Scores (Id, Score) values ('5', '4.0')
insert into Scores (Id, Score) values ('6', '3.65')

問題描述

The Employee table holds all employees. Every employee has an Id, a salary, and there is also a column for the department Id.

The Department table holds all departments of the company.

Write a SQL query to find employees who have the highest salary in each of the departments. For the above tables, your SQL query should return the following rows (order of rows does not matter).

Explanation:

Max and Jim both have the highest salary in the IT department and Henry has the highest salary in the Sales department.

翻譯

Employee 這張資料表擁有所有員工資訊，每一筆資料包含員工編號、名稱、薪水、以及部門代碼
Department 這張資料表擁有公司部門資訊
請撰寫一段 SQL 查詢能找出各個部門薪資最高的員工，並參考以下查詢結果格式作為解答標準（次序非必要條件）。

解題思維

1. 部門代號可以利用 JOIN 方式將 Employee 與 Department 兩張作關聯，如此以來就可以取得部門名稱
2. 要取得部門中最高薪資，使用 Group By 部門方式，則可以取到該部門最高薪資
3. 最後  將 1.查詢結果 JOIN2.，以薪水、部門代號作為關聯條件，就可以得出答案

解題報告

Level: Medium
Runtime: 983 ms, faster than 89.78% of Oracle online submissions for Department Highest Salary.
Memory Usage: 0B, less than 100.00% of Oracle online submissions for Department Highest Salary.

程式完整解題

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

/* Write your PL/SQL query statement below */

SELECT DP.NAME   AS DEPARTMENT -- 部門名稱
      ,EM.NAME   AS EMPLOYEE   -- 員工名稱
      ,EM.SALARY AS SALARY     -- 員工薪水
  FROM EMPLOYEE EM
 INNER JOIN DEPARTMENT DP
         ON EM.DEPARTMENTID = DP.ID
 INNER JOIN (SELECT    DEPARTMENTID
                      ,MAX(SALARY)   AS SALARY
               FROM    EMPLOYEE
              GROUP BY DEPARTMENTID) MAX_SALARY
         ON EM.SALARY = MAX_SALARY.SALARY
        AND EM.DEPARTMENTID = MAX_SALARY.DEPARTMENTID;

SQL Schema

1
2
3
4
5
6
7
8
9
10
11

Create table If Not Exists Employee (Id int, Name varchar(255), Salary int, DepartmentId int)
Create table If Not Exists Department (Id int, Name varchar(255))
Truncate table Employee
insert into Employee (Id, Name, Salary, DepartmentId) values ('1', 'Joe', '70000', '1')
insert into Employee (Id, Name, Salary, DepartmentId) values ('2', 'Jim', '90000', '1')
insert into Employee (Id, Name, Salary, DepartmentId) values ('3', 'Henry', '80000', '2')
insert into Employee (Id, Name, Salary, DepartmentId) values ('4', 'Sam', '60000', '2')
insert into Employee (Id, Name, Salary, DepartmentId) values ('5', 'Max', '90000', '1')
Truncate table Department
insert into Department (Id, Name) values ('1', 'IT')
insert into Department (Id, Name) values ('2', 'Sales')

問題描述

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];
        }
    }
}

問題描述

Invert a binary tree.

Example

翻譯

翻轉這顆二元樹

解題思維

1. 使用 level Order 方式拜訪這顆二元樹，用佇列將每一層  節點儲存起來
2. 同時檢查拜訪該節點是否有左右子樹，若有加入佇列裡面
3. 交換左右節點
4. 重複第二、三步驟直至佇列為空

解題報告

Level: Easy
Time Complexity: O(n)
Runtime: 0 ms, faster than 100.00% of Java online submissions for Invert Binary Tree.
Memory Usage: 37.4 MB, less than 5.10% of Java online submissions for Invert Binary Tree.

程式完整解題

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
29
30
31
32
33
34

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Queue;
import java.util.LinkedList;
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null)
            return root;

        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode node = q.poll();

            if(node.left!=null)
                q.add(node.left);

            if(node.right!=null)
                q.add(node.right);

            TreeNode temp_node = node.left;
            node.left = node.right ;
            node.right = temp_node;
        }
        return root;
    }
}

問題描述

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;
    }
}