SouthLeetCode-打卡24年02月第2周
// Date : 2024/02/05 ~ 2024/02/11
039.有效的字母异位词
(1) 题目描述
039#LeetCode.242.简单题目链接#Monday2024/02/05
给定两个字符串 *s* 和 *t* ,编写一个函数来判断 *t* 是否是 *s* 的字母异位词。
**注意:**若 *s* 和 *t* 中每个字符出现的次数都相同,则称 *s* 和 *t* 互为字母异位词。
(2) 题解代码
Version1.0
class Solution {
class Box{
String str;
int len;
HashMap
Box(String str){
this.str = str;
this.len = str.length();
this.map = new HashMap();
}
// 这段代码可以优化
// 优化后
HashMap
for(char curChar : str.toCharArray()){
map.put(curChar, map.getOrDefault(curChar, 0) + 1);
}
return map;
}
}
public boolean isAnagram(String s, String t) {
Box sBox = new Box(s);
Box tBox = new Box(t);
HashMap m1 = sBox.initMap();
HashMap m2 = tBox.initMap();
return m1.equals(m2);
}
}
V1-Tip
// 优化前的initMap
HashMap
char curChar;
int curVal;
for(int i=0 ; i curChar = str.charAt(i); if(map.containsKey(curChar)){ curVal = map.get(curChar)+1; }else{ curVal = 1; } map.put(curChar, curVal); } return map; } Version2.0 class Solution { class Box{ String str; int len; HashMap Box(String str){ this.str = str; this.len = str.length(); this.map = new HashMap(); for(char curChar : str.toCharArray()){ map.put(curChar, map.getOrDefault(curChar, 0) + 1); } } } public boolean isAnagram(String s, String t) { Box sBox = new Box(s); Box tBox = new Box(t); return sBox.map.equals(tBox.map); } } 040.两个数组的交集Ⅰ (1) 题目描述 040#LeetCode.349.简单题目链接#Tuesday2024/02/06 给你两个整数数组 nums1 和 nums2 ,请你以数组形式返回两数组的交集。 返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。 可以不考虑输出结果的顺序。 (2) 题解代码 class Solution { int[] listToArray(HashSet int[] array = new int[set.size()]; int index = 0; for (Integer element : set) { array[index++] = element; } return array; } public int[] intersection(int[] nums1, int[] nums2) { HashMap HashSet int i=0; for(int curVal : nums1){ map.put(curVal, 1); } for (int curVal : nums2) { if(map.containsKey(curVal)){ resSet.add(curVal); } } return setToArray(resSet); } } 041.两个数组的交集Ⅱ (1) 题目描述 041#LeetCode.350.简单题目链接#Tuesday2024/02/06 给你两个整数数组 nums1 和 nums2 ,请你以数组形式返回两数组的交集。 返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。 可以不考虑输出结果的顺序。 (2) 题解代码 class Solution { class Box{ int len; Map Box(int[] nums){ len = nums.length; map = new HashMap for (int num : nums) { int count = map.getOrDefault(num, 0) + 1; map.put(num, count); } } } public int[] intersect(int[] nums1, int[] nums2) { Box box1 = new Box(nums1); Box box2 = new Box(nums2); if (box1.len > box2.len) { return intersect(nums2, nums1); } int[] result = new int[box1.len]; int index = 0; for (int num : nums2) { int count = box1.map.getOrDefault(num, 0); if (count > 0) { result[index++] = num; count--; if(count > 0){ box1.map.put(num, count); }else{ box1.map.remove(num); } } } return Arrays.copyOfRange(result, 0, index); } } 042.快乐数 (1) 题目描述 042#LeetCode.202.简单题目链接#Wednesday2024/02/07 (2) 题解代码 class Solution { private int getNext(int n) { int totalSum = 0; while (n > 0) { int d = n % 10; n = n / 10; totalSum += d * d; } return totalSum; } public boolean isHappy(int n) { Set while (n != 1 && !seen.contains(n)) { seen.add(n); n = getNext(n); } return n == 1; } } 043.字符串中的单词数 (1) 题目描述 043#LeetCode.434.简单题目链接#北岸计划2024/02/07 (2) 题解代码 class Solution { public int countSegments(String s) { int size = s.length(); int res = 0; for(int i=0 ; i boolean flag = (i == 0 || s.charAt(i - 1) == ' ') && s.charAt(i) != ' '; if(flag){ res++; } } return res; } } 044.两数之和 (1) 题目描述 044#LeetCode.001.简单题目链接#Thursday2024/02/08 (2) 题解代码 Version1.0 class Solution { int[] result(int i, int j){ int[] res = new int[2]; res[0] = i; res[1] = j; return res; } public int[] twoSum(int[] nums, int target) { for(int i=0 ; i for(int j=i+1 ; j boolean flag = nums[i] + nums[j] == target; if(flag){ return result(i,j); } } } return null; } } Version2.0 class Solution { public int[] twoSum(int[] nums, int target) { Map for (int i = 0; i < nums.length; ++i) { if (map.containsKey(target - nums[i])) { return new int[]{map.get(target - nums[i]), i}; } map.put(nums[i], i); } return new int[0]; } } 045.赎金信 (1) 题目描述 045#LeetCode.383.简单题目链接#Thursday2024/02/08 (2) 题解代码 class Solution { static boolean isSubsetOf(Map Map // 遍历子集的所有键值对 for (Map.Entry Character key = entry.getKey(); Integer value = entry.getValue(); // 检查子集的键是否存在于父哈希表中 if (!parent.containsKey(key)) { return false; } // 检查子集的值是否与父哈希表中对应键的值相等 // if (!parent.get(key).equals(value)) { // return false; // } if (parent.get(key) < value) { return false; } } // 子集中的所有键值对都存在于父哈希表中且对应的值也相等 return true; } class Box{ HashMap Box(String str){ int len = str.length(); for(int i=0 ; i char ch = str.charAt(i); map.put(ch,map.getOrDefault(ch,0)+1); } } } public boolean canConstruct(String ransomNote, String magazine) { Box box1 = new Box(ransomNote); Box box2 = new Box(magazine); boolean result = isSubsetOf(box1.map,box2.map); return result; } } 046.三数之和 (1) 题目描述 046#LeetCode.046.中等题目链接#Friday2024/02/09 (2) 题解代码 class Solution { public List int length = nums.length; int sum = -1; int left = 0; int right = length-1; List if(nums == null || length < 3) return results; Arrays.sort(nums); for(int i=0; i if(nums[i] > 0){ return results; } if(i > 0 && nums[i] == nums[i-1]){ continue; } left = i+1 ; right = length-1; while(left < right){ sum = nums[i] + nums[left] + nums[right]; if(sum == 0){ List array.add(nums[i]); array.add(nums[left]); array.add(nums[right]); results.add(array); while(left < right && nums[left] == nums[left+1]){ left++; } while(left < right && nums[right] == nums[right-1]){ right--; } left++; right--; }else if(sum < 0){ left++; }else if(sum > 0){ right--; } } } return results; } } 047.四数之和 (1) 题目描述 047#LeetCode.018.中等题目链接#Saturday2024/02/10 给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复): 0 <= a, b, c, d < na、b、c 和 d 互不相同nums[a] + nums[b] + nums[c] + nums[d] == target 你可以按 任意顺序 返回答案 。 (2) 题解代码 class Solution { public List List if(nums==null||nums.length<4){ return result; } Arrays.sort(nums); int length=nums.length; for(int k=0;k if(nums[k] > 0 && nums[k] > target) break; if(k>0&&nums[k]==nums[k-1]){ continue; } long min1=(long)nums[k]+nums[k+1]+nums[k+2]+nums[k+3]; if(min1>target){ break; } long max1=(long)nums[k]+nums[length-1]+nums[length-2]+nums[length-3]; if(max1 continue; } for(int i=k+1;i if(nums[i] > 0 && (long)nums[k] + nums[i] > target) break; if(i>k+1&&nums[i]==nums[i-1]){ continue; } int j=i+1; int h=length-1; long min=(long)nums[k]+nums[i]+nums[j]+nums[j+1]; if(min>target){ break; } long max=(long)nums[k]+nums[i]+nums[h]+nums[h-1]; if(max continue; } while (j long curr=(long)nums[k]+nums[i]+nums[j]+nums[h]; if(curr==target){ result.add(Arrays.asList(nums[k],nums[i],nums[j],nums[h])); j++; while(j j++; } h--; while(j h--; } }else if(curr>target){ h--; }else { j++; } } } } return result; } } 048.四数相加Ⅱ (1) 题目描述 048#LeetCode.454.中等题目链接#Sunday2024/02/11 给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n , 请你计算有多少个元组 (i, j, k, l) 能满足: 0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 (2) 题解代码 class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { Map int res = 0; for (int num1 : nums1) { for (int num2 : nums2) { int sum = num1 + num2; map.put(sum, map.getOrDefault(sum, 0) + 1); } } for (int num3 : nums3) { for (int num4 : nums4) { int complement = -(num3 + num4); res += map.getOrDefault(complement, 0); } } return res; } } 好文推荐> threeSum(int[] nums) {
> results = new ArrayList<>();
> fourSum(int[] nums,int target){
> result=new ArrayList<>();
发表评论