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 < na、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 < nnums1[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;
}
}
