SouthLeetCode-打卡24年02月第2周

SouthLeetCode-打卡24年02月第2周

// Date : 2024/02/05 ~ 2024/02/11

039.有效的字母异位词

(1) 题目描述

039	#LeetCode.242.	简单	题目链接	#Monday	2024/02/05

给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。

**注意：**若 *s* 和 *t* 中每个字符出现的次数都相同，则称 *s* 和 *t* 互为字母异位词。

(2) 题解代码

Version1.0

class Solution {class Box{String str;int len;HashMap<Character,Integer> map;Box(String str){this.str = str;this.len = str.length();this.map = new HashMap();}// 这段代码可以优化// 优化后HashMap<Character,Integer> initMap(){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<Character,Integer> initMap(){char curChar;int curVal;for(int i=0 ; i<len ; 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<Character,Integer> map;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.	简单	题目链接	#Tuesday	2024/02/06

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。

返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。

可以不考虑输出结果的顺序。

(2) 题解代码

class Solution {int[] listToArray(HashSet<Integer> set){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<Integer,Integer> map = new HashMap();HashSet<Integer> resSet = new 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.	简单	题目链接	#Tuesday	2024/02/06

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。

返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。

可以不考虑输出结果的顺序。

(2) 题解代码

class Solution {class Box{int len;Map<Integer, Integer> map;Box(int[] nums){len = nums.length;map = new HashMap<Integer, Integer>();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.	简单	题目链接	#Wednesday	2024/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<Integer> seen = new HashSet<>();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<size ; i++){boolean flag = (i == 0 || s.charAt(i - 1) == ' ') && s.charAt(i) != ' ';if(flag){res++;}}return res;}
}

044.两数之和

(1) 题目描述

044	#LeetCode.001.	简单	题目链接	#Thursday	2024/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<nums.length ; i++){for(int j=i+1 ; j<nums.length ; 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<Integer, Integer> map = new HashMap<Integer, Integer>();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.	简单	题目链接	#Thursday	2024/02/08

(2) 题解代码

class Solution {static boolean isSubsetOf(Map<Character, Integer> subset,Map<Character, Integer> parent){// 遍历子集的所有键值对for (Map.Entry<Character, Integer> entry : subset.entrySet()) {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<Character,Integer> map = new HashMap<>();Box(String str){int len = str.length();for(int i=0 ; i<len ; 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.	中等	题目链接	#Friday	2024/02/09

(2) 题解代码

class Solution {public List<List<Integer>> threeSum(int[] nums) {int length = nums.length;int sum = -1;int left = 0;int right = length-1;List<List<Integer>> results = new ArrayList<>();if(nums == null || length < 3) return results;Arrays.sort(nums);for(int i=0; i<length-2 ; 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<Integer> array = new ArrayList<>();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.	中等	题目链接	#Saturday	2024/02/10

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

(2) 题解代码

class Solution {
public List<List<Integer>> fourSum(int[] nums,int target){List<List<Integer>> result=new ArrayList<>();if(nums==null||nums.length<4){return result;}Arrays.sort(nums);int length=nums.length;for(int k=0;k<length-3;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<target){continue;}for(int i=k+1;i<length-2;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<target){continue;}while (j<h){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<h&&nums[j]==nums[j-1]){j++;}h--;while(j<h&&i<h&&nums[h]==nums[h+1]){h--;}}else if(curr>target){h--;}else {j++;}}}}return result;}
}

048.四数相加Ⅱ

(1) 题目描述

048	#LeetCode.454.	中等	题目链接	#Sunday	2024/02/11

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，

请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

(2) 题解代码

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {Map<Integer, Integer> map = new HashMap<>();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;}
}