iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 4
0
自我挑戰組

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

【從面試題學邏輯-4】CTCI 1.1 檢查字串內是否有重複字元

這題是CTCI上的第一題,也是這系列第一題講到的CTCI題目。作為避免直接勸退的一題,本題的難度也不高,所以有不同的解法來讓大家自由發揮/images/emoticon/emoticon12.gif

讓我們來看看題目的內容(已翻譯成中文):

" 在不使用其他資料結構的情況下,寫一個演算法來判斷字串內的所有字元都是unique的(不重複的意思) "


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

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


好,讓我們開始吧

如同前面文章所說「先求有再求好」,直覺想到暴力解並不是壞事。可能已經有讀者想到用迴圈包迴圈,來逐一去比較了。

static boolean isUnique(String s) {
	for(int i = 0 ; i < s.length() ; i++) {
		for(int j = 0 ; j < s.length() ; j++) {
			if(i == j) continue; // 不和自己比
			if(s.charAt(i)==s.charAt(j)) return false;
                        // 如果有相同,代表有重複字元
		}
	}
	return true; // 跑完迴圈代表都不重複
}

這個解法真的十分經典,甚至在學校考題中也會出現類似應用的題目呢/images/emoticon/emoticon16.gif

又或者是,先把字串中的字元先排好順序,兩個一組檢查是否有重複
從第二個字元開始兩個一組,檢查到最後一個字元,如果同一組中的字元相同,就代表字串中有重複(同邏輯下,也可以從第一個開始一組,比到倒數第二個)

static boolean isUnique(String s) {
	char[] arr = s.toCharArray(); // 先轉成字元陣列
	Arrays.sort(arr); // 排好順序
	for(int i = 1 ; i < arr.length ; i++) {
		if(arr[i]==arr[i-1]) return false; 
                // 兩兩相同就是有重複
	}
	return true;
}

舉個例子:
假設我們輸入"apple",就會先把"apple"變成陣列的['a','p','p','l','e'],再依照字母順序排列好,就會變成成['a', 'e', 'l', 'p', 'p']

此時我們兩個一組開始比較,從第二個字元開始比到最後一個

  1. e ≠ a
  2. l ≠ e
  3. p ≠ l
  4. p = p → 有重複!

以上都是可行的解法,但單純這樣似乎有點太單調了,所以接下來會講解另一種解法,也先為我們日後會講到的題目鋪梗。

不知道大家有沒有聽過ASCII這個東西呢?

沒錯!每個字元都可以變成一個數字,如果我們運用這個原理,開一個夠大的Boolean陣列,把字元轉換成對應的ASCII。再依照ASCII的數字,在陣列內紀錄誰已經出現過了,如果下次要再紀錄時發現這個字元紀錄過,就代表有重複!

不好理解嗎/images/emoticon/emoticon06.gif?那我們把它想像成***開燈泡***吧

  1. 先建立一整排夠記錄所有字元的燈泡來做紀錄,這些燈泡一開始都是關著的
  2. 我們訂一個規則,用ASCII給對應的字元一個數字,就想像成是第N個燈泡吧
  3. 開始依序讀字串中的字元,假設先讀到A好了,我們依照ASCII的編號,去把代表A的燈泡打開
  4. 接著往下讀字元,假設又碰到要打開A時,我們發現代表A的燈泡已經打開了,就代表字元有重複

(參考下圖)

這樣是不是比較好懂了呢?

另外能幫程式省一點時間的是,ASCII就128個字元,如果要在不重複的情況下組出最長的字串,最長一定是128,再多一定會有重複。
就好比可以拿三個字造句,不重複的話,最長也就三個字

所以最終可以得到這段程式碼

static boolean isUnique(String s) {
    if(s.length() > 128) return false; // 超過128就一定重複
    boolean[] chars = new boolean[128]; 
    // 建一個紀錄出現過的陣列
    for(int i = 0 ; i < s.length() ; i++) {
    	if(chars[s.charAt(i)]) return false;
    	else chars[s.charAt(i)] = true;
        // 如果對應的燈泡已經打開就代表重複
        // 沒有的話,就把燈泡打開
    }
    return true; // 跑完就代表沒出現重複
}

提醒:
如果題目不是使用ASCII,而是使用Unicode的話,陣列大小就不是128嘍!
請視情況做大小的調整


小結:
今天我們看了用陣列紀錄的方法,而這個方法類似的應用也不少,明天我們就來一題類似的題目,給大家小試身手一下吧


上一篇
【從面試題學邏輯-3】計算最後一詞的長度(leetcode 58. Length of Last Word)
下一篇
【從面試題學邏輯-5】CTCI 1.2 如何判斷兩個字串是否互為排列組合
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言