在做算法題，遇到一個(gè)小坑，記錄一下。

題目：

Consider a sequence u where u is defined as follows:
The number u(0) = 1 is the first one in u.
For each x in u, then y = 2 * x + 1 and z = 3 * x + 1 must be in u too.
There are no other numbers in u.
Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]

1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on...

Task:
Given parameter n the function dbl_linear (or dblLinear...) returns the element u(n) of the ordered (with <) sequence u (so, there are no duplicates).

Example:
dbl_linear(10) should return 22

Note:
Focus attention on efficiency

思路：

固定兩個(gè) 隊(duì)列，一個(gè)隊(duì)列存放 2 * x + 1，另外一個(gè)隊(duì)列存放 3 * x + 1
每次取最前面的數(shù)進(jìn)行比較，取出小的那個(gè)。再將取出數(shù)的對(duì)應(yīng)關(guān)系值放到對(duì)應(yīng)隊(duì)列中。

代碼

public class DoubleLinear {

    public static int dblLinear (int n) {
        Queue<Integer> arr1 = new LinkedList<Integer>();
        Queue<Integer> arr2 = new LinkedList<Integer>();
        int temp = 1;
        int ant = 0;
        while(ant<n){
            arr1.offer(2*temp+1);
            arr2.offer(3*temp+1);
            if(arr1.element()==arr2.element()){
                arr2.poll();
                temp = arr1.poll();
            }else{
                temp = arr1.element()<arr2.element()?arr1.poll():arr2.poll();
            }
            ant++;
        }
        return temp;
    }

坑：
上面的代碼在運(yùn)行基礎(chǔ)用例的時(shí)候是通過(guò)的，但是提交上去的n數(shù)量級(jí)大的話用例就會(huì)出錯(cuò)。
https://blog.csdn.net/weixin_39800144/article/details/81165898
最后發(fā)現(xiàn) 具體原因 如上 博文所述 ??
代碼在比較 Integer對(duì)象的時(shí)候用了“==”，結(jié)果比較的是 對(duì)象的地址值。
代碼判斷語(yǔ)句地方換成

if(arr1.element().equals(arr2.element()))

后通過(guò)所有測(cè)試用例。
附上 Integer對(duì)象 equals()的源碼：

    public boolean equals(Object obj) {
        if (obj instanceof Integer) {
            return value == ((Integer)obj).intValue();
        }
        return false;
    }

以下，摘自原博文：
Integer值的比較有個(gè)坑：對(duì)于Integer var = ?,在-128至127范圍內(nèi)的賦值， Integer 對(duì)象是在IntegerCache.cache 產(chǎn)生，會(huì)復(fù)用已有對(duì)象，這個(gè)區(qū)間內(nèi)的 Integer 值可以直接使用==進(jìn)行判斷，但是這個(gè)區(qū)間之外的所有數(shù)據(jù)，都會(huì)在堆上產(chǎn)生，并不會(huì)復(fù)用已有對(duì)象;所以，在上面，我們的c和d兩個(gè)，雖然值是一樣的，但是地址不一樣。
這是一個(gè)大坑，很多人會(huì)在項(xiàng)目中使用==來(lái)比較Integer！強(qiáng)烈建議，必須使用equals來(lái)比較。