每日刷题记录 (十一)

第一题: 剑指 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;
    }
}