Tag: Stack

今後 Easy 題若沒碰到非常精彩的就不每題都更了。

題目描述：

給定一個按非遞減順序排序的整數數組 nums，就地刪除重複項，使每個單獨的元素只出現一次。元素的相對順序應保持不變。

由於在某些語言中無法更改數組的長度，因此您必須將結果放在數組 nums 的前半部分。更正式地說，如果刪除重複項後有 k 個元素，則 nums 的前 k 個元素應持有最終結果。除了前 k 個元素之外，留下什麼都不重要。

將最終結果放入 nums 的前 k 個插槽後返回 k值。

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Stack 解法：

自己還是只能想出來蠢方法，應該刷題量還遠遠不夠吧：

class Solution {
    public int removeDuplicates(int[] nums) {
		Stack<Integer> Stack = new Stack<Integer>();
		int k = 0;
		for (int i = 0; i < nums.length; i++) {
			if (Stack.search(nums[i])==-1) {
				Stack.push(nums[i]);
				nums[k] = nums[i];
				k++;
			} 
		}
		return k;
	}
}

7 ms

利用順序的取巧方法：

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for(int n: nums){
            if(i == 0 || n > nums[i - 1]){
                nums[i] = n;
                i++;
            }
        }
        return i;
    }
}

1 ms

題目描述：

給定一個僅包含字符 '(', ')', '{', '}', '[' 和 ']' 的字符串 s，確定輸入字符串是否有效。

有效的情況指：

1. 前括號必須用相同類型的括號閉合。
2. 前括號必須以正確的順序閉合。

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

暴力解法：

昨天半夜擼的，還是想不到什麽好點子：

class Solution {
    public boolean isValid(String s) {
        StringBuilder sb = new StringBuilder();
        sb.append(s);
        
        for(int i = 0; i<sb.length()-1; i++ ){
            if ( (sb.charAt(i) == '(' && sb.charAt(i+1) == ')') || 
                 (sb.charAt(i) == '[' && sb.charAt(i+1) == ']') || 
                 (sb.charAt(i) == '{' && sb.charAt(i+1) == '}') 
               ){
                sb = sb.deleteCharAt(i+1);
                sb = sb.deleteCharAt(i);
                i = -1;
            }
        }
        if (sb.toString() == ""){
            return true;
        }
        else{
            return false;
        }
    } 
}

79 ms，慘不忍睹。

Stack 解法：

Hint 中已經提到，應該使用 Stack ：

class Solution {
    public boolean isValid(String s) {
	   Stack<Character> stack = new Stack<Character>();
	   for (char c : s.toCharArray()) {
		   if (c == '(')
			   stack.push(')');
		   else if (c == '{')
			   stack.push('}');
		   else if (c == '[')
			   stack.push(']');
		   else if (stack.isEmpty() || stack.pop() != c)
			   return false;
	   }
	   return stack.isEmpty();
    }
}

2 ms