前言

本文隸屬于專欄《LeetCode 刷題匯總》，該專欄為筆者原創，參考請注明來源，不足和錯誤之處請在評論區幫忙指出，謝謝！

本專欄目錄結構請見LeetCode 刷題匯總

正文

幕布

幕布鏈接

76. 最小覆寫子串

題解

簡簡單單，非常容易理解的滑動視窗思想?

滑動視窗

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0){
            return "";
        }
        int[] need = new int[128];
        //記錄需要的字符的個數
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }
        //l是當前左邊界，r是當前右邊界，size記錄視窗大小，count是需求的字符個數，start是最小覆寫串開始的index
        int l = 0, r = 0, size = Integer.MAX_VALUE, count = t.length(), start = 0;
        //遍歷所有字符
        while (r < s.length()) {
            char c = s.charAt(r);
            if (need[c] > 0) {//需要字符c
                count--;
            }
            need[c]--;//把右邊的字符加入視窗
            if (count == 0) {//視窗中已經包含所有字符
                while (l < r && need[s.charAt(l)] < 0) {
                    need[s.charAt(l)]++;//釋放右邊移動出視窗的字符
                    l++;//指標右移
                }
                if (r - l + 1 < size) {//不能右移時候調整最小視窗大小，更新最小視窗開始的start
                    size = r - l + 1;
                    start = l;//記錄下最小值時候的開始位置，最后回傳覆寫串時候會用到
                }
                //l向右移動后視窗肯定不能滿足了 重新開始回圈
                need[s.charAt(l)]++;
                l++;
                count++;
            }
            r++;
        }
        return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
    }
}

77. 組合

題解

官方題解?

標準回溯

class Solution {
    private List<List<Integer>> results = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        pick(new ArrayList<>(k), n, k, 1);
        return results;
    }

    private void pick(List<Integer> list, int n, int k, int cur){
        if(k <= 0){
            results.add(new ArrayList<>(list));
            return;
        }
        for(int i = cur; i <= n - k + 1; i++){
            list.add(i);
            pick(list, n, k-1, i + 1);
            list.remove(list.size() - 1);
        }
    }
}

78. 子集

題解

官方題解?

標準回溯

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(list, new ArrayList<>(), nums, 0);
        return list;
    }

    private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
        list.add(new ArrayList<>(tempList));
        for(int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, i + 1);
            tempList.remove(tempList.size() - 1);
        }
    }
}

79. 單詞搜索

題解

官方題解?

同小島沉沒問題

class Solution {
    public boolean exist(char[][] board, String word) {
		for (int x = 0; x < board.length; x++) {
			for (int y = 0; y < board[0].length; y++) {
				if (board[x][y] == word.charAt(0) && helper(board, word, 0, x, y)) {
					return true;
				}
			}
		}
		return false;
	}

	private boolean helper(char[][] board, String word, int index, int x, int y) {
		if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != word.charAt(index)) {
			return false;
		}
		if (index == word.length() - 1) {
			return true;
		}
		board[x][y] = '*';
		boolean res = helper(board, word, index + 1, x + 1, y) ||
			helper(board, word, index + 1, x - 1, y) ||
			helper(board, word, index + 1, x, y + 1) ||
			helper(board, word, index + 1, x, y - 1);
		board[x][y] = word.charAt(index);
		return res;
	}
}

80. 洗掉有序陣列中的重復項 II

題解

3-6 easy lines, C++, Java, Python, Ruby?

雙指標，一個用來遍歷，一個用來占位

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