思路: 转换成Char数组,排序后比较数组是否相等
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()){
return false;
}
char[] ss = s.toCharArray();
char[] tt = t.toCharArray();
Arrays.sort(ss);
Arrays.sort(tt);
return Arrays.equals(ss,tt);
}
}
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] mp = new int[26];
for (char c : magazine.toCharArray()) {
mp[c - 'a']++;
}
for (char c : ransomNote.toCharArray()) {
mp[c - 'a']--;
if (mp[c - 'a'] < 0) {
return false;
}
}
return true;
}
}
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, ArrayList<String>> mp = new HashMap<>();
for (int i = 0; i < strs.length; i++) {
char[] temp = strs[i].toCharArray();
Arrays.sort(temp);
String key = new String(temp);
if(mp.containsKey(key)){
mp.get(key).add(strs[i]);
}else{
mp.put(key,new ArrayList<>());
mp.get(key).add(strs[i]);
}
}
Set<String> chars = mp.keySet();
List<List<String>> ans =new ArrayList<>( new ArrayList<>());
for(String a : chars){
ans.add(mp.get(a));
}
return ans;
}
}
思路: 可以使用滑动窗口 这里使用粗暴的匹配
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int sLen = s.length(), pLen = p.length();
if (pLen > sLen) {
return new ArrayList<>();
}
char[] charp = p.toCharArray();
Arrays.sort(charp);
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < sLen - pLen + 1; i++) {
char[] temp = s.substring(i, i + pLen).toCharArray();
Arrays.sort(temp);
if (Arrays.equals(temp, charp)) {
ans.add(i);
}
}
return ans;
}
}
思路:先将nums1的每个数压入list,再将nums2压入set2(会去重)再将list只保留set2里面有点的元素,最后压入set1(去重)再用流转成int数组
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> set = new HashSet<>();
ArrayList list = new ArrayList();
for (int i = 0; i < nums1.length; i++) {
list.add(nums1[i]);
}
HashSet<Integer> set2 = new HashSet<>();
for (int i = 0; i < nums2.length; i++) {
set2.add(nums2[i]);
}
list.retainAll(set2);
set.addAll(list);
return Arrays.stream(set.stream().toArray()).mapToInt(i-> (int) i).toArray();
}
}
思路: 跟上题区别是可以重复,前提是不能多于nums1重复的次数,所以用map记录每个值的次数,每次重复就提取并减少
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> mp = new HashMap<>();
for (int i = 0; i < nums1.length; i++) {
if(mp.containsKey(nums1[i])){
mp.put(nums1[i], mp.get(nums1[i]) + 1);
}else{
mp.put(nums1[i], 1);
}
}
int []ans = new int[nums1.length];
int index= 0;
for (int i = 0; i < nums2.length; i++) {
if(mp.containsKey(nums2[i])&&mp.get(nums2[i])>0){
ans[index++] = nums2[i];
mp.put(nums2[i],mp.get(nums2[i]) - 1);
}
}
return Arrays.copyOfRange(ans,0,index);
}
}
用set来记录出现过的数字,防止死循环
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;
}
}
用一个哈希表来记录当前有的数字和索引,遍历每个元素,如果差已经存在,即存在两数之和等于target
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> mp = new HashMap<>();
for(int i = 0 ;i < nums.length ;i ++){
if(mp.containsKey(target - nums[i])){
return new int[] {mp.get(target - nums[i]),i};
}
mp.put(nums[i],i);
}
return new int[0];
}
}
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> map = new HashMap<>();
int ans = 0;
for (int i : nums1) {
for (int j : nums2) {
int temp = i + j;
if (map.containsKey(temp)) {
map.put(temp, map.get(temp) + 1);
} else {
map.put(temp, 1);
}
}
}
for (int i : nums3) {
for (int j : nums4) {
int temp = i + j;
if (map.containsKey(0 - temp)) {
ans += map.get(0 - temp);
}
}
}
return ans;
}
}
枚举最小数,双指针找
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int len = nums.length;
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < len; i++) {
//右边全正 不可能相加为0
if (nums[i] > 0) {
return ans;
}
//排除重复值
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = len - 1;
while (right > left) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
} else {
ans.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++;
}
right--;
left++;
}
}
}
return ans;
}
}
比三数之和多一层循环
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
int len = nums.length;
for (int i = 0; i < len; i++) {
if (nums[i] > 0 && nums[i] > target) {
return ans;
}
if (i > 0 && nums[i - 1] == nums[i]) {
continue;
}
for (int j = i + 1; j < len; j++) {
if (j > i + 1 && nums[j - 1] == nums[j]) {
continue;
}
int left = j + 1;
int right = len - 1;
while (right > left) {
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
ans.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++;
}
right--;
left++;
}
}
}
}
return ans;
}
}
哈希表结束