LeetCode: 剑指 Offer II 005. 单词长度的最大乘积
描述:
给定一个字符串数组 words,请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时,它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串,返回 0。
words.length
的数组 ret
来记录每一个word 的字符串转二进制的格式.ac
===> 101
; ad
===> 1001
; bd
===> 1010
ret[i] |= (1<<words[i].charAt(j))
, 意思就是: 当前字符出现了, 那么就按二进制的形式记录下它对应的位次, 因为字符一共是a~z
26个, 从右往左, 只要有1, 就表示出现当前元素.与
运算, 只要结果等于 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;
}
}
LeetCode: 剑指 Offer II 007. 数组中和为 0 的三个数
描述:
给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a ,b ,c ,
使得 a + b + c = 0 ?
请找出所有和为 0 且 不重复 的三元组。
nums[left] + nums[right] == target
就把这3个元素放入结果集中, 这里注意, 加入之后, 要对当前的left下标的值 和 right下标的值进行去重 ,以免重复添加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;
}
}
LeetCode: 剑指 Offer II 008. 和大于等于 target 的最短子数组
描述:
给定一个含有 n
个正整数的数组和一个正整数 target
。
找出该数组中满足其和 ≥ target
的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,
并返回其长度。如果不存在符合条件的子数组,返回 0 。
用 total 记录 nums[right] 的值. 判断当前 total 和 target值
如果当前 total >= target
, 记录当前的 下标距离(最终只记录最小的) , 此时让 total -= nums[left]
, left++
,
循环每次让 right++
滑动窗口大小始终保持 [left,right]
返回最小的下标距离
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;
}
}
LeetCode: 剑指 Offer II 009. 乘积小于 K 的子数组
描述:
给定一个正整数数组 nums
和整数 k
,请找出该数组内乘积小于 k
的连续的子数组的个数。
每次记录当前的乘积 ret *= nums[j]
, 判断是否大于k
如果这里大于 k, 就让窗口左边界移动(i++), 记录当前下标
返回所有可能的次数
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;
}
}
LeetCode: 剑指 Offer II 010. 和为 k 的子数组
描述:
给定一个整数数组和一个整数 k ,请找到该数组中和为 k 的连续子数组的个数。
ret-k
, 这样加起来就能为k, 存在就记录当前的value值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;
}
}
LeetCode: 剑指 Offer II 011. 0 和 1 个数相同的子数组
描述:
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组,并返回该子数组的长度。
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;
}
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://wangzhi430.blog.csdn.net/article/details/125577028
内容来源于网络,如有侵权,请联系作者删除!