iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 16
1
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 16

【從面試題學邏輯-16】拔智齒可以不要寫鐵人賽嗎?好像不能這樣做诶(leetcode 78. Subsets)

是的,在下我現在嘴巴還在麻,預估今晚不用睡了/images/emoticon/emoticon02.gif
因為是水平智齒的關係,真的不能不拔,而且這是上個月底就預定的,沒辦法。
顧及團隊精神,而且團隊內的組員其實每個人都是忙中硬ㄍㄧㄥ住,大家都這麼努力,我應該也要努力硬著頭皮寫下去

但所謂的智齒…根本製杖/images/emoticon/emoticon03.gif


題目:
請寫一個方法,輸入裡面東西不重複的int集合(set),請找出他所有的子集(subset)
(這題和CTCT 8.4 一模一樣)

舉例:
請看LeetCode上的舉例(太長啦)

點我前往LeetCode題目


那在開始前不乏提醒一下此系列的固定提醒:

這是一系列逐漸帶入解題的文章,難度會隨著進度增加,若還沒有讀過前面的文章,建議先從最前面開始來逐漸練習解題喔!


先和大家說一下,這題有兩個解法,一個是今天要說的,利用位元來解。另一個則是使用遞迴,那遞迴解法我們留到遞迴系列再提。

大家不知道還記不記得,之前說過二進位就好比電燈開或關的樣子

我們上一張圖,請大家看一下:

右方黑色請想像成,灰色表示,其實每個subset就像是一種電燈開關的組合!/images/emoticon/emoticon12.gif

以上面圖為例,空的subset就代表,原本set中所有數字的狀態為。[3, 5]就代表1的狀態是關,3、5的狀態是開。

如果我們把set內所有開和關的組合loop過一次,然後轉換成對應的subset……不就是正確答案了嗎!?/images/emoticon/emoticon07.gif

我們先上程式碼再慢慢解釋:

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        for(int i=0 ; i<(1<<nums.length) ; i++) {
            List<Integer> newlist = new ArrayList<Integer>();
            int index = 0;
            for(int j = i ; j > 0 ; j >>= 1) {
                if((j & 1) == 1) newlist.add(nums[index]);
                index++;
            }
            list.add(newlist);
        }
        return list;
    }
}
for(int i=0 ; i<(1<<nums.length) ; i++)

為什麼i要小於(1<<nums.length)呢?因為subset的總數為 2^n 個 (n=set長度),因為每個set中的數字都開關組合,所以就是2x2x2x...x2x2,很好想像吧?

而i會從二進位的000000到指定長度的111111,所以i就等於一種電燈開關的狀態,我們能利用這個特性來製造subset!

for(int j = i ; j > 0 ; j >>= 1) {
    if((j & 1) == 1) newlist.add(nums[index]);
        index++;
    }

上面的j又是什麼意思呢?記得我們最外層的i代表著一種set內數字的開關組合嗎?j迴圈就是依照這個組合,把要的數字塞進新的subset內。

(j&1)就代表取出j的最後一個位元,如果是1,就代表那個位置是開。之後j整個右移,就可以比對下一個位元。

index就是負責幫我們記現在比對到set中哪個東西用的。

其實沒有想像中的難,對吧?


因為在下今天狀況奇差,寫的不是很好,還望大家見諒/images/emoticon/emoticon10.gif


上一篇
【從面試題學邏輯-15】Java Integer.bitCount() 原理,當程式達到極致後……就看不懂了!?
下一篇
【從面試題學邏輯-17】找一個不會影分身的傢伙怎麼這麼討人厭?(leetcode 137. Single Number II)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言