什麼是雪花演算法？

我們都知道在自然界當中每一片雪花都是獨一無二的。在目前提倡容器化、分散式的架構時代下，很可能會遇到 ID 重號的問題，我們對 ID 的期望就會希望雪花般一樣都不重複。

這個演算法最早是由 Twitter 所創建的，主要是拿來產推文的 ID，後來這套演算法被 Discord、Instagram採用，也衍伸許多不同格式的版本。

會想要使用這套演算法的原因是因為筆者想要拿它產生 token，快取在 redis 上，合法的使用者可以拿著這個 token 存取筆者在部署 Docker 上的微服務系統。

雪花演算法核心組成

筆者先為大家科普一下雪花演算法的組成的成分，主要共分 4 個欄位組成 64 位元，頭一個位元我們不使用，其他欄位下方逐一跟各位說明。

時間戳記

第二欄位是時間戳記，共 41 個位元，以 UNIX 時間（起始年是 1970 年）的毫秒為單位正好可以填滿41 bits 的空間，可表示最大數為 2,199,023,255,551，以毫秒計算約 69 年，這個數值是兩個時戳相減得出的。

如果是拿當下的時間戳填進去這個欄位，那麼數值很快就會到達天花板，我們身為生活智慧王，當然要善用空間，所以才會以產生 token 的時間戳減去一個開始時間戳。

由於前面有提到是微服務，為了保持一致，開始時間戳需要寫死，建議可以訂在系統上線前的日期，像筆者就選擇把開始時間的時戳訂成自己的生日。

工作站台 ID

第三欄位是工作站台 ID，共 10 個位元，用來區分哪ㄧ台機器發出的 token。

流水號

第四欄位是流水號 ID，共 12 個位元，意思是同一個時間下同一機器所配發出去的流水號，從 0 開始遞增，直到進入下一個毫秒，流水號再重新編號。

演算法說明

位元分配器

筆者建立一個類別叫作 BitsAllocator，主要做兩件工作，第一件事是初起化各個欄位位元數，第二件是配發雪花演算法的唯一 ID，以下筆者會逐一說明。

一開始在 BitsAllocator 的建構子決定好各欄位要多長，由參考 BitsAllocator 的類別去制定，假設我們按造預設的長度，那麼建構子內的三個參數分別為 41, 10, 12。

第二步就是要製作位元遮罩，所以我們要取得這三個欄位的最大值，舉例來說如果我們想要取得工作站 ID 的最大值 2¹⁰ — 1，也就是 10 個位元都是 1。

如何取得最大值呢？在 Java 的世界中整數採用二的補數，先將 — 1 向左位移 10 個位元的位置，再位元 NOT 運算，就可以得到囉。

第三步要把各個欄位擺放到正確的位置，像是時間戳記需要位元要向左位移 10 + 12 個位元，工作站站台 ID 要向左位移 12 個位元，流水號則不需要移動，所以我們需要紀錄一下到時候要位移的個數。

第四步就是把它們像積木一樣拼起來，筆者這邊設計一個方法，讓參考BitsAllocator 的類別呼叫 allocate，把當下的時間戳、機器的 ID、配發的流水號傳進來，該方法會把這三個欄位推到正確的位置，用到的是我們上面紀錄下來位移的各個去推，最後用 OR 運算合併。

唯一性 ID 取號器

筆者設計了一個 SnowFlakeAlg 類別用來取號。

一開始建構 SnowFlakeAlg 類別，首先先注入 BitsAllocator，後續我們取號的時候會使用到。由於每一個放置在 Docker 容器內每一個微服務都會分配一組 IP，所以筆者是取其 IPv4 第四個欄位作為工作站站台 ID。

這組 IP 是怎麼得來的呢？Java 會在作業系統建立 Socket 連線，使用 InetAddress.getLocalHost().getHostAddress() ，可以得到本機的主機位址。

至於時戳怎麼產生呢？是呼叫 System.currentTimeMillis() 取得系統當下的時戳，記得前面我們有說雪花演算法時戳這個欄位是兩個毫秒相減得出的嗎？系統當下的時戳減去一個我們是先制定好的開始時戳，這邊我減去的是我去年的生日那天，如果結果值大於 2⁴¹ — 1，那就代表時戳佔用位元已耗盡，無法產製唯一性 ID。

會呼叫 nextMilliSecond() 方法原因在上一毫秒的流水號已經分配完，所以要循環等待到下一毫秒，為了避免因為機器硬體時鐘問題造成時戳還停留在過去，所以我們有寫了 while 迴圈，重新取時戳，同時判斷是否有大於上一個時戳的時間。

SnowFlakeAlg 類別主要功能也就是取號，第一先取得系統當下的時戳，同一個毫秒下，我們就讓遞增取流水號，在取號的過程中，我們會拿遞增後的流水號跟流水號的最大值做 AND 運算，看結果值是否為 0？如果是，那代表該時戳可分配的流水號全部分玩了，需要等到下一個毫秒，再重新分配。

最後我們拿系統時戳減開始時戳、工作站 ID、流水號當作參數呼叫bitsAllocator.allocate()，就可以拿到唯一性的 ID 當作 token 使用了。

完整程式碼

SnowflakeAlgo

問題

實務上，我們在程式中處理與金錢相關的議題不會使用浮點數，因為那會造成 Truncate Error，算出來的金額會有浮點數誤差，通常我們會使用 BigDecimal 來計算，提高計算的精度。

而我曾經要計算某金額除以匯率，計算結果四捨五入小數點取到第二位，於是我就寫了以下範例，使用 BigDecimal 除法，分別填入除數與 MathContext ， MathContext 的建構子的第一參數 setPrecision ，我以為設定的是小數點的精度，但事與願達，結果是2.4E2即 240 以科學記號表示。

1
2
3
4

BigDecimal dividend = new BigDecimal("999999.9999");
BigDecimal divisor = new BigDecimal("4096.00");
BigDecimal result = dividend.divide(divisor, new MathContext(2, RoundingMode.HALF_UP));
System.out.println(result);

Scale, Precision傻傻分不清楚

由於上述計算結果並不是我想要，我在網路上找到 BigDecimal 對 Scale , Precision 的介紹，我才赫然發現一開始我就搞錯用法了，原來 BigDecimal 也像 IEEE-754 採用類似的表示方式。

BigDecimal表示法

Java BigDecimal 是由兩個數值所構成的，分別是隨機的精度整數、跟 32 位元整數範圍，通常BigDecimal以表示，其中n為小數位數。

Precision

精度定義是未經 BigDecimal 正規表示的數值之位數，即該數值整數加上小數的數位，例如： 123.45 ，此精度會回傳 5 。

Scale

範圍定義是經 BigDecimal 正規表示後的小數位數，如果 Scale 是零、正整數，則會將該數的數個位數挪動到小數點符號的右邊，如若 Scale 是負整數，則該值會乘上 10 的幂次，例如： 12345 ， scale = 2，則回傳 123.45 ， 12345 ， scale = -1 ，則回傳 123450 。

解決方法

承上述例子，因為精度是設定 2 ，舊版的寫法會造成四捨五入到十位數，十數位以下通通進位，並以科學記號表示。解決方法是改用 BigDecimal 另一個重載 divide 的方法，就可以在第二參數設定小數範圍為 2 ，最後結果為244.14。

1
2
3
4
5

public class BigDecimal extends Number implements Comparable<BigDecimal> {
    public BigDecimal divide(BigDecimal divisor, int scale, RoundingMode roundingMode) {
        return divide(divisor, scale, roundingMode.oldMode);
    }
}

1
2
3
4

BigDecimal dividend = new BigDecimal("999999.9999");
BigDecimal divisor = new BigDecimal("4096.00");
BigDecimal result = dividend.divide(divisor, 2, RoundingMode.HALF_UP);
System.out.println(result);

問題描述

我在工作上有一個需求需要使用多執行緒完整多個工項，每一個工作都是獨立事務交易，所以我使用Java 8 CompletableFuture提供的方法實作Runnable，再利用Spring AOP代理機制處理事務交易，但當我發送Http Request到我的AP Server時，卻收到下述報錯訊息，從中可以得知發生此錯誤的原因有兩種可能，一、沒有打開代理Java @EnableAspectJAutoProxy(exposeProxy = true, proxyTargetClass = true)，另一個可能是不是在同一條執行緒使用代理機制，後來我才意識到我使用了不同的執行緒代理是無法生效的。

1

java.util.concurrent.ExecutionException: java.lang.IllegalStateException: Cannot find current proxy: Set exposeProxy property on Advised to 'true' to make it available, and ensure that AopContext.currentProxy() is invoked in the same thread as the AOP invocation context.

我就好奇為什麼AOP代理機制為不能跨執行緒，於是我去翻AopContext的source code，我才發現原來它是從ThreadLocal取得目前的代理類別，ThreadLocal本身特性就專屬於一個執行緒使用，其他的執行緒不能存取、修改。

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

public final class AopContext {
	private static final ThreadLocal<Object> currentProxy = new NamedThreadLocal<>("Current AOP proxy");

	private AopContext() {
	}
	
	public static Object currentProxy() throws IllegalStateException {
		Object proxy = currentProxy.get();
		if (proxy == null) {
			throw new IllegalStateException(
					"Cannot find current proxy: Set 'exposeProxy' property on Advised to 'true' to make it available, and " +
							"ensure that AopContext.currentProxy() is invoked in the same thread as the AOP invocation context.");
		}
		return proxy;
	}
}

範例

以下範例模擬我當時工作時發生的錯誤，在raiseEmployeeSalary()先到MongoDB撈所有員工的資料後，以多執行緒方式替員工加薪數額，由raiseSalary()完成，CompletableFuture.allOf意思是等所有員工加完薪水後，繼續往下作。如同上一節我所描述的，在透過代理機制去呼叫raiseSalary()就會報錯。

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

@Service
public class EmployeeService {
    @Autowired
    private EmployeeDao employeeDao;

    @Transactional(rollbackFor = Exception.class, propagation = Propagation.REQUIRED)
    public void raiseEmployeeSalary(RaiseSalaryBo raiseSalaryBo) throws ExecutionException, InterruptedException {
        List<Employee> employees = employeeDao.listAllEmployees();

        List<CompletableFuture<?>> tasks = new ArrayList<>();
        for (Employee employee : employees) {
            tasks.add(CompletableFuture.runAsync(()->((EmployeeService)AopContext.currentProxy()).raiseSalary(employee, raiseSalaryBo.getBonus())));
        }

        CompletableFuture.allOf(tasks.toArray(new CompletableFuture<?>[0])).get();
    }

    @Transactional(rollbackFor = Exception.class, propagation = Propagation.REQUIRES_NEW)
    public void raiseSalary(Employee employee, BigDecimal bonus) {
        employeeDao.raiseSalary(employee, bonus);
    }
}

解決方法

解決方法十分簡單，如若真的需要切割出子事務交易，那就不能使多執行緒來處理，依據上述範例必須把CompletableFuture移除，程式才能正常執行。

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

@Service
public class EmployeeService {
    @Autowired
    private EmployeeDao employeeDao;

   @Transactional(rollbackFor = Exception.class, propagation = Propagation.REQUIRED)
    public void raiseEmployeeSalary(RaiseSalaryBo raiseSalaryBo) {
        List<Employee> employees = employeeDao.listAllEmployees();

        for (Employee employee : employees) {
            ((EmployeeService) AopContext.currentProxy()).raiseSalary(employee, raiseSalaryBo.getBonus());
        }
    }

    @Transactional(rollbackFor = Exception.class, propagation = Propagation.REQUIRES_NEW)
    public void raiseSalary(Employee employee, BigDecimal bonus) {
        employeeDao.raiseSalary(employee, bonus);
    }
}

資料庫更新後的結果

題目連結

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

圖片資料壓縮 - 全彩轉換成索引色圖片

索引色概念 - Indexed color

在計算機領域當中，索引色是一種資料壓縮的技巧，主要是用來快速呈現圖片、或是加速資料傳輸，也稱之「向量量化壓縮」。如果一張圖片是上述方式編碼，顏色資訊就不會直接存在該張圖片裡，而是另外一個檔案中稱「調色盤」，以陣列的方式儲存，陣列中的每一個元素都代表著一個顏色。

換言之，該張圖片並不包含原圖的所有顏色，而是參照另一個檔案所提供的顏色，編寫而成。

調色盤的大小 - Palette size

一張數位全彩影像(含透明值)由 32 個位元所組成，Alpha、紅、綠、藍各占 4 個 bit，可以表示的顏色為 2 的 24 次方，相當為 16,777,216‬ 個顏色，我們可以得知控制位元大小可以控制可以表現出來的色彩。

調色盤為儲存索引顏色的地方，最常見有 4 色、 16 色、或 256 色，電腦數字表示都是 01 表示法，會根據位元的多寡來呈現，所以色彩種類都是 2 的次方。256 色就是由一個位元組(8 個位元)所組成的，4 個位元則可以表示 16 種顏色，以此類推。

PNG 圖檔、或是視訊覆蓋技術有使用到透明值，調色盤會額外保留一個位置來儲存透明值。

轉換公式 - Formula

在本作品裡頭是使用 256 種索引色彩，我使用歐幾里德距離公式對一張全彩的圖片進行色彩置換，我們國中所學的數學公式正好可以運用在此，利用巢狀走訪所有的像素值，將該像素值的 RGB 值與 256 色的索引色套此公式，會得到一個數值，求出數值差異最小的寫入一張空白的圖片上。

公式：dist((r1, r2), (g1, g2), (b1, b2)) = √((r1 - r2)² + (g1 - g2)² + (b1 - b2)²)

進一步說明，這套公式是在歐氏空間內求出距離，一顆像素值有紅、綠、藍，如果我們將紅、綠、藍視為座標，這顆像素則存在在三維空間，另外我們是用這顆像素值跟索引色比較，兩顆像素形成一向量。

主要程式

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

for(int i=0; i<height; i++){
    for(int j=0; j<width; j++){
        //變數是原圖像素值
        Color c = new Color(image.getRGB(j, i));
        //distance陣列存放歐幾里德公式算出的距離
        double distance[]=new double[256];

        int minindex=0; //抓取最小距離的索引色之索引
        double min = Math.sqrt(Math.pow((c.getRed()-r[0]),2)+Math.pow((c.getGreen()-g[0]),2)+Math.pow((c.getBlue()-b[0]),2));
        //兩兩比較算出最小距離
        for(int d=1;d<256; d++){
            distance[d]= Math.sqrt(Math.pow((c.getRed()-r[d]),2)+Math.pow((c.getGreen()-g[d]),2)+Math.pow((c.getBlue()-b[d]),2));
            if(min>distance[d]){
                min = distance[d];
                minindex = d;
            }
        }
    //上色，填上索引色
    buff.setRGB(j, i,palette[minindex]);
}

作品結果

原圖

處理過的圖片

問題描述

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

問題描述

Implement the following operations of a queue using stacks.

1
2
3
4

push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.

Example:

1
2
3
4
5
6
7

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

解題思維

首先我們要先釐清柱列(Queue)與 Stack(堆)的特性，前者為先進先出，後者為後進先出，題目是要我們使用堆來實現柱列的功能，我們需要用兩個堆來完成，
一個存放資料，另一個暫存資料，解題主要思維是利用堆後進先出的特性，將儲存在第一個堆的資料，依序 pop 出來，同時 push 到暫存的堆裡，將要放入
的資料放入第一堆，最後將暫存的堆裡依序吐出到第一堆，剛好最先進去的資料排在第一個。

Enqueue

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

/**
 * 實作Enqueue功能
 * @param x 資料
 * @remark
 */
public void push(int x) {
        //依序先將存在第一個Stack吐到第二個裡
        while(!stack1.empty()){
            stack2.push(stack1.pop());
        }

        //將我們儲存的元素存到第一個Stack裡
        stack1.push(x);

        //依序將存在暫存Stack的元素依序吐回第一個Stack
        //維持先進去的元素排在最前面
        while(!stack2.empty()){
            stack1.push(stack2.pop());
        }
    }

Dequeue

1
2
3
4
5
6
7
8
9

/**
 * 實作Dequeue功能
 * @return 返回Stack第一個元素
 * @remark
 */
public int pop() {
    //直接pop第一個Stack第一個元素
    return stack1.pop();
}

程式完整解題

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

/**
Runtime: 0 ms, faster than 100.00% of Java online submissions for Implement Queue using Stacks.
Memory Usage: 40.9 MB, less than 6.25% of Java online submissions for Implement Queue using Stacks.
*/
import java.util.Stack;

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        while(!stack1.empty()){
            stack2.push(stack1.pop());
        }

        stack1.push(x);

        while(!stack2.empty()){
            stack1.push(stack2.pop());
        }
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        return stack1.pop();
    }

    /** Get the front element. */
    public int peek() {
        return stack1.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.empty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */