每日刷題記錄 (十一)

第一題: 劍指 Offer II 005. 單詞長度的最大乘積

LeetCode: 劍指 Offer II 005. 單詞長度的最大乘積
描述:
給定一個字符串數組 words，請計算當兩個字符串 words[i] 和 words[j] 不包含相同字符時，它們長度的乘積的最大值。假設字符串中只包含英語的小寫字母。如果沒有不包含相同字符的一對字符串，返回 0。

解題思路:

1. 這裏使用長度為 words.length 的數組 ret 來記錄每一個word 的字符串轉二進制的格式.
   例如: ac ===> 101 ; ad ===> 1001 ; bd ===> 1010
2. 實現字符串轉二進制的方法, 就是遍曆每個字符, 讓 ret[i] |= (1<<words[i].charAt(j)) , 意思就是: 當前字符出現了, 那麼就按二進制的形式記錄下它對應的比特次, 因為字符一共是a~z 26個, 從右往左, 只要有1, 就錶示出現當前元素.
3. 遍曆, 兩兩 與 運算, 只要結果等於 0 , 就錶示兩者不含相同的元素. 此時,記錄下最大的兩個不含相同元素的字符串的長度乘積.

代碼實現:

class Solution {
    
    public int maxProduct(String[] words) {
    
        int[] ret = new int[words.length];
        for(int i = 0; i < words.length; i++) {
    
            for(int j = 0; j < words[i].length(); j++) {
    
            	// 只要該字符出現, 就把這個比特置變成1
                ret[i] = ret[i] | (1 << (words[i].charAt(j) - 'a'));
            }
        }
        int ans = 0;
        for(int i = 0; i < words.length-1; i++) {
    
            for(int j = i + 1; j < words.length; j++) {
    
            	// 兩兩與運算
                if((ret[i] & ret[j]) == 0) {
    
                	// 記錄最大的乘積
                    ans = Math.max(ans, words[i].length() * words[j].length());
                }
            }
        }
        return ans;
    }
}

第二題: 劍指 Offer II 007. 數組中和為 0 的三個數

LeetCode: 劍指 Offer II 007. 數組中和為 0 的三個數

描述:
給定一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a ，b ，c ，使得 a + b + c = 0 ？請找出所有和為 0 且 不重複 的三元組。

解題思路:

1. 首先進行排序,
2. 首先拿到第 i 個 元素, 讓left = i+1, right = len - 1;
3. 從剩下的元素中, 拿取, 只要nums[left] + nums[right] == target 就把這3個元素放入結果集中, 這裏注意, 加入之後, 要對當前的left下標的值 和 right下標的值進行去重 ,以免重複添加
4. 每次拿元素的時候注意, 當 i > 0 的時候. 要注意重複拿取相同的元素. nums[i] = nums[i-1]

代碼實現:

class Solution {
    
    public List<List<Integer>> threeSum(int[] nums) {
    
    	// 排序
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length - 2;i++) {
    
            // 這裏防止重複拿取相同的元素
            if(i != 0 && nums[i] == nums[i-1]) continue;
            // 因為拿到了nums[i] 要想相加為0, 就需要找到和為 -nums[i]的
            int target = -nums[i];
            int left = i + 1;
            int right = nums.length-1;
            while (left < right) {
    
                if (nums[left] + nums[right] == target) {
    
                    // 這裏出現兩個下標的數能够滿足要求, 就將這三元素加入集中
                    List<Integer> ret = new ArrayList<>();
                    ret.add(nums[i]);
                    ret.add(nums[left]);
                    ret.add(nums[right]);
                    ans.add(ret);
                    // 這裏防止left和right下標下重複拿到相同的值, 進行去重
                    int tmp = nums[left];
                    while (left < right && nums[left] == tmp){
    
                        left++;
                    }
                    tmp = nums[right];
                    while (left < right && nums[right] == tmp) {
    
                        right--;
                    }
                }else if (nums[left] + nums[right] < target) {
    
                    left++;
                }else {
    
                    right--;
                }
            }
        }
        return ans;
    }
}

第三題: 劍指 Offer II 008. 和大於等於 target 的最短子數組

LeetCode: 劍指 Offer II 008. 和大於等於 target 的最短子數組

描述:
給定一個含有 n 個正整數的數組和一個正整數 target 。

找出該數組中滿足其和 ≥ target 的長度最小的 連續子數組 [numsl, numsl+1, ..., numsr-1, numsr] ，並返回其長度。如果不存在符合條件的子數組，返回 0 。

解題思路:

1. 這裏使用滑動窗口的方式
2. 讓left = 0, right =0, 初始時窗口大小為0
3. 用 total 記錄 nums[right] 的值. 判斷當前 total 和 target值
   • 如果當前 total >= target , 記錄當前的 下標距離(最終只記錄最小的) , 此時讓 total -= nums[left] , left++,
4. 循環每次讓 right++
5. 滑動窗口大小始終保持 [left,right]
6. 返回最小的下標距離
   

代碼實現:

class Solution {
    
    public int minSubArrayLen(int target, int[] nums) {
    
        int start = 0;
        int end = 0;
        int ans = Integer.MAX_VALUE;
        int total = 0;
        // 大小為 [start,end] 的滑動窗口
        while (end < nums.length) {
    
            total += nums[end];
            while (total >= target) {
    
                ans = Math.min(ans, end-start+1);
                total -= nums[start];
                start++;
            }
            end++;
        }
        return ans==Integer.MAX_VALUE?0:ans;
    }
}

第四題: 劍指 Offer II 009. 乘積小於 K 的子數組

LeetCode: 劍指 Offer II 009. 乘積小於 K 的子數組

描述:
給定一個正整數數組 nums和整數 k ，請找出該數組內乘積小於 k 的連續的子數組的個數。

解題思路:

1. 使用滑動窗口解題
2. 每次記錄當前的乘積 ret *= nums[j], 判斷是否大於k
   • 如果這裏大於 k, 就讓窗口左邊界移動(i++), 記錄當前下標
3. 返回所有可能的次數

代碼實現:

class Solution {
    
    public int numSubarrayProductLessThanK(int[] nums, int k) {
    
        int i = 0;
        int ret = 1;
        int ans = 0;
        // 滑動窗口 [i,j]
        for (int j = 0; j < nums.length; j++) {
    
            ret *= nums[j];
            while(i <= j && ret >= k) {
    
                ret /= nums[i];
                i++;
            }
            // 這裏使用這種辦法來計算並防止重複計算
            ans += j - i + 1;
        }
        return ans;
    }
}

第五題: 劍指 Offer II 010. 和為 k 的子數組

LeetCode: 劍指 Offer II 010. 和為 k 的子數組

描述:
給定一個整數數組和一個整數 k ，請找到該數組中和為 k 的連續子數組的個數。

解題思路:

1. 這裏使用哈希錶, 記錄下當前和的值ret.
2. 判斷 是否存在元素 ret-k, 這樣加起來就能為k, 存在就記錄當前的value值
3. 這裏注意 k = nums[i] 的情况, 就需要提前添加 0的情况.

代碼實現:

class Solution {
    
    public int subarraySum(int[] nums, int k) {
    
        Map<Integer,Integer> map = new HashMap<>();
        int ans = 0; 
        map.put(0,1);
        int ret = 0;
        for(int i = 0; i < nums.length; i++) {
    
            ret += nums[i];
            if (map.containsKey(ret - k)) {
    
                ans += map.get(ret - k);
            }
            map.put(ret,map.getOrDefault(ret,0)+1);
        }
        return ans;
    }
}

第六題: 劍指 Offer II 011. 0 和 1 個數相同的子數組

LeetCode: 劍指 Offer II 011. 0 和 1 個數相同的子數組

描述:
給定一個二進制數組 nums , 找到含有相同數量的 0 和 1 的最長連續子數組，並返回該子數組的長度。

解題思路:

1. 首先讓數組中所有為0的元素變成-1, 這樣就只需要判斷加起來是否為0, 就可以知道0和1的個數是否相同.
2. 如果當前元素不存在哈希錶中, 就添加到哈希錶中,value值為當前的下標
3. 如果當前元素存在哈希錶中, 記錄當前最大下標差

代碼實現:

class Solution {
    
    public int findMaxLength(int[] nums) {
    
        for(int i = 0; i < nums.length; i++) {
    
            if(nums[i] == 0) nums[i] = -1;
        }
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        int ans = 0;
        int target = 0;
        for(int i = 0; i < nums.length; i++) {
    
            target += nums[i];
            if (map.containsKey(target)) {
    
                ans = Math.max(ans,i-map.get(target));
            }else {
    
                map.put(target,i);
            }
        }
        return ans;
    }
}