【100天演算法入門 - 每日三題 - Day4】有效的括號、洗掉有序陣列中的重復項、實作strStr

大家好，我是哪吒，一個熱愛編碼的Java工程師，本著“欲速則不達，欲達則欲速”的學習態度，在程式猿這條不歸路上不斷成長，所謂成長，不過是用時間慢慢擦亮你的眼睛，少時看重的，年長后卻視若鴻毛，少時看輕的，年長后卻視若泰山，成長之路，亦是漸漸放下執念，內心歸于平靜的旅程，

也許，我們永遠都不會知道自己能走到何方，遇見何人，最后會變成什么樣的人，但一定要記住，能讓自己登高的，永遠不是別人的肩膀，而是挑燈夜戰的自己，人生的道路剛剛啟程，當你累了倦了也不要迷茫，回頭看一看，你早已不再是那個年少輕狂的少年，

1、LeetCode 20.有效的括號

題目

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字串 s ，判斷字串是否有效，

有效字串需滿足：

左括號必須用相同型別的右括號閉合，
左括號必須以正確的順序閉合，

小編菜解

public static boolean isValid(String s) {
    if (s.length()%2 != 0) return false;
    Map<Character,Character> hashMap = new HashMap<Character,Character>(){{
        put(')','(');
        put('}','{');
        put(']','[');
    }};
    //"{[]}"
    Queue<Character> queue = new LinkedList<Character>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if(hashMap.containsKey(c)){
            char t = queue.peek();
            System.out.println(t);//這個地方彈出的是{
            char tt = hashMap.get(c);//而這個對應的是],,上一處peek應該取得[
            System.out.println(tt);
            System.out.println(queue.peek() != hashMap.get(c));
            if (queue.isEmpty() || queue.peek() != hashMap.get(c)){
                return false;
            }
            queue.poll();
        }else{
            queue.offer(c);
        }
    }
    return queue.isEmpty();
}

思路及演算法

判斷括號的有效性可以使用「堆疊」這一資料結構來解決，

當我們遇到一個右括號時，我們需要將一個相同型別的左括號閉合，此時，我們可以取出堆疊頂的左括號并判斷它們是否是相同型別的括號，如果不是相同的型別，或者堆疊中并沒有左括號，那么字串 ss 無效，回傳 \text{False}False，為了快速判斷括號的型別，我們可以使用哈希表存盤每一種括號，哈希表的鍵為右括號，值為相同型別的左括號，

在遍歷結束后，如果堆疊中沒有左括號，說明我們將字串 ss 中的所有左括號閉合，回傳True，否則回傳False，

注意到有效字串的長度一定為偶數，因此如果字串的長度為奇數，我們可以直接回傳False，省去后續的遍歷判斷程序，

大神解法

public static boolean isValid(String s){
    int n = s.length();
    if (n % 2 == 1) {
        return false;
    }

    Map<Character, Character> pairs = new HashMap<Character, Character>() {{
        put(')', '(');
        put(']', '[');
        put('}', '{');
    }};
    Deque<Character> stack = new LinkedList<Character>();
    for (int i = 0; i < n; i++) {
        char ch = s.charAt(i);
        if (pairs.containsKey(ch)) {
            if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                return false;
            }
            stack.pop();
        } else {
            stack.push(ch);
        }
    }
    return stack.isEmpty();
}

思路和我的思路完全一致，就是我使用的是單向佇列，結果就是失敗，加油吧！

Java中Queue和Deque的區別

2、LeetCode 26.洗掉有序陣列中的重復項

題目

給你一個有序陣列 nums ，請你 原地 洗掉重復出現的元素，使每個元素 只出現一次 ，回傳洗掉后陣列的新長度，

不要使用額外的陣列空間，你必須在 原地 修改輸入陣列 并在使用 O(1) 額外空間的條件下完成，

說明:

為什么回傳數值是整數，但輸出的答案是陣列呢?

請注意，輸入陣列是以「參考」方式傳遞的，這意味著在函式里修改輸入陣列對于呼叫者是可見的，

小編菜解初版

public static Integer[] removeDuplicates(Integer[] nums) {
    if(nums == null || nums.length == 0){
        return nums;
    }
    List<Integer> tempList = Arrays.asList(nums);
    for (int i = tempList.size() - 1; i >= 0; i--) {
        Integer current = tempList.get(i);
        if(i-1>0){
            Integer next = tempList.get(i - 1);
            if(next == current){
                tempList.remove(current);
            }
        }
    }
    Integer[] ret = new Integer[tempList.size()];
    tempList.toArray(ret);
    return ret;
}

為什么為這樣呢？我記得list是可以remove的啊，百思不得其解，查一下原始碼，猛然發現

Arrays的內部類ArrayList和java.util.ArrayList都是繼承AbstractList，remove、add等方法在AbstractList中是默認throw UnsupportedOperationException而且不作任何操作，java.util.ArrayList重寫這些方法而Arrays的內部類ArrayList沒有重寫，所以會拋出例外，

小編菜解改進版

public static Integer[] removeDuplicates(Integer[] nums) {
    if(nums == null || nums.length == 0){
        return nums;
    }
    List<Integer> tempList = Arrays.asList(nums);
    List<Integer> list = new ArrayList<>(tempList);
    for (int i = list.size() - 1; i >= 0; i--) {
        Integer current = list.get(i);
        if(i-1>0){
            Integer next = list.get(i - 1);
            if(next == current){
                list.remove(current);
            }
        }
    }
    Integer[] ret = new Integer[list.size()];
    list.toArray(ret);
    return ret;
}

不報錯了，結果也對，perfect！

思路及演算法

相等的元素在陣列中的下標一定是連續的，利用陣列有序的特點，可以通過雙指標的方法洗掉重復元素，

大神解法

public static int removeDuplicates2(Integer[] nums) {
    int n = nums.length;
    if (n == 0) {
        return 0;
    }
    int fast = 1, slow = 1;
    while (fast < n) {
        if (nums[fast] != nums[fast - 1]) {
            nums[slow] = nums[fast];
            ++slow;
        }
        ++fast;
    }
    return slow;
}

我去，無情，我的解法果然很菜，題意都沒讀懂，人家要的是長度，你回傳一個陣列，作甚？？

3、LeetCode 28.實作strStr

題目

實作 strStr() 函式，

給你兩個字串 haystack 和 needle ，請你在 haystack 字串中找出 needle 字串出現的第一個位置（下標從 0 開始），如果不存在，則回傳 -1 ，

說明：

當 needle 是空字串時，我們應當回傳什么值呢？這是一個在面試中很好的問題，

對于本題而言，當 needle 是空字串時我們應當回傳 0 ，這與 C 語言的 strstr() 以及 Java 的 indexOf() 定義相符，

小編菜解

public static int strStr(String haystack, String needle) {
    if(haystack == null || !haystack.contains(needle)){
        return -1;
    }
    if(needle == ""){
        return 0;
    }

    int strLg = haystack.length();
    int findLg = needle.length();
    for (int i = 0; i < strLg; i++) {
        char c = haystack.charAt(i);
        if (c == needle.charAt(0) && i+findLg <= strLg){
            String temp = haystack.substring(i,i + findLg);
            if (temp.equals(needle)){
                return i;
            }
        }
    }
    return -1;
}

沒看出有什么問題，可是提交總是提示解答錯誤，也是無奈，

大神解法

public static int strStr(String haystack, String needle) {
    int strLg = haystack.length();
    int findLg = needle.length();
    for (int i = 0; i+findLg <= strLg; i++) {
        boolean flag = true;
        for (int j = 0; j < findLg; j++) {
            if (haystack.charAt(i+j)!=needle.charAt(j)){
                flag = false;
                break;
            }
        }
        if (true == flag){
            return i;
        }
    }
    return -1;
}

感覺大神的解法還沒我的解法簡單呢？可我的為何一直提交都是出錯，哎，無奈，

上一篇：【100天演算法入門 - 每日三題 - Day3】回文數、羅馬數字轉數字、最大公共前綴

往期精彩內容：

Java知識體系總結

【全堆疊最全Java框架總結】SSH、SSM、Springboot

超詳細的springBoot學習筆記

常見資料結構與演算法整理總結

Java設計模式：23種設計模式全面決議

Java面試題總結（附答案）

10萬字208道Java經典面試題總結(附答案，建議收藏)

MySql知識體系總結

Linux知識體系總結

【Vue基礎知識總結 1】Vue入門

Redis知識體系總結