备战秋招day4

算法

242. 有效的字母异位词

class Solution {public boolean isAnagram(String s, String t) {int[] count = new int[26];for(int i = 0;i<s.length();i++){count[s.charAt(i)-'a']++;}for(int i = 0;i<t.length();i++){count[t.charAt(i)-'a']--;if(count[t.charAt(i)-'a']<0){return false;}}for(int i = 0;i<26;i++){if(count[i]!=0){return false;}}return true;}
}

349. 两个数组的交集

class Solution {public int[] intersection(int[] nums1, int[] nums2) {if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {return new int[0];}Set<Integer> set1 = new HashSet<>();Set<Integer> set2 = new HashSet<>();for(int i : nums1){set1.add(i);}//拿2出来判断for(int i : nums2){if(set1.contains(i)){set2.add(i);}}int[] res = new int[set2.size()];int index = 0;for(int i : set2){res[index++] = i;}return res;}
}

202. 快乐数

class Solution {public boolean isHappy(int n) {//题干说了可能会无限循环：//结果一旦出现重复，说明结果集已经确定，直到重复都没有true说明不是快乐数Set<Integer> set = new HashSet<>();while(n!=1 && !set.contains(n)){set.add(n);n = newNumber(n);}return n==1;}public int newNumber(int n){//做新数字的计算int res = 0;while(n > 0){//取出每一位int tmp = n%10;res += tmp*tmp;n/=10;}return res;}
}

1. 两数之和

class Solution {//我们可以使用map来解决public int[] twoSum(int[] nums, int target) {int res[] = new int[2];if(nums == null || nums.length < 2){return new int[]{0,0};}HashMap<Integer, Integer> map = new HashMap<>();for(int i = 0;i<nums.length;i++){int tmp = target - nums[i];if(map.get(tmp)!=null){res[0] = i;res[1] = map.get(tmp);}else{map.put(nums[i],i);}}return res;}
}

454. 四数相加 II

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res = 0;//题目中给出的用例可以发现，允许重复情况出现HashMap<Integer,Integer> map1 = new HashMap<>();for(int i:nums1){for(int j:nums2){int sum = i+j;map1.put(sum,map1.getOrDefault(sum,0)+1);}}for(int i:nums3){for(int j:nums4){//找对应值即可res+=map1.getOrDefault(0-i-j,0);}}return res;}
}

383. 赎金信

class Solution {public boolean canConstruct(String ransomNote, String magazine) {//先统计magazineint[] m = new int[26];for(char a:magazine.toCharArray()){m[a-'a']++;}for(char a:ransomNote.toCharArray()){m[a-'a']--;if(m[a-'a']<0){return false;}}return true;}
}

15. 三数之和

class Solution {public List<List<Integer>> threeSum(int[] nums) {//双指针来做，先排序List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums);//隐藏条件for(int i = 0;i<nums.length;i++){//如果当前已经大于0，则后面一定没有符合条件if(nums[i]>0){break;}//去重if(i>0 && nums[i] == nums[i-1]){continue;}//找集合-双指针做法int left = i+1;int right = nums.length-1;while(left<right){int sum = nums[i]+nums[left]+nums[right];if(sum<0){left++;}else if(sum>0){right--;}else{res.add(Arrays.asList(nums[i],nums[left],nums[right]));//去重while(right>left && nums[right]==nums[right-1]){right--;}while(right>left && nums[left]==nums[left+1]){left++;}//再走一步//如：2223,最后一步只会走到2，而不是3left++;right--;}}}return res;}
}

18. 四数之和

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> res = new ArrayList<>();//和三数之和是一样的道理，再套一层--我们通过双指针最多可以同时操作两个数int len = nums.length;//排序，因为不在乎顺序Arrays.sort(nums);for(int i = 0;i<len;i++){//排序如果首位大于tar并且当前位置大于等于0，那么后面怎么加减都无法凑到tarif(nums[i]>target && nums[i]>=0){break;}//对i去重if(i>0 && nums[i]==nums[i-1]){continue;}//开始遍历后面三个，其实就是三数之和for(int j = i+1;j<len;j++){//对j去重if(nums[i]+nums[j] > target && nums[i]+nums[j]>=0){break;}//去重if(j>i+1 && nums[j]==nums[j-1]){continue;}int left = j+1;int right = len-1;while(left<right){int sum = nums[i]+nums[j]+nums[left]+nums[right];if(sum>target){right--;}else if(sum<target){left++;}else{res.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));while(right>left && nums[right]==nums[right-1]){right--;}while(right>left && nums[left]==nums[left+1]){left++;}left++;right--;}}}}return res;}
}