1.存在重复元素
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> judge = new HashSet();
for(Integer num:nums){
if(judge.contains(num)){
return true;
}
judge.add(num);
}
return false;
}
}
2.只出现一次的数字
class Solution {
public int singleNumber(int[] nums) {
Set<Integer> judge = new HashSet();
for(Integer num:nums){
if(!judge.add(num)){
judge.remove(num);
}
}
return judge.iterator().next();
}
}
class Solution {
public int singleNumber(int[] nums) {
int sum = 0;
for(Integer num: nums){
sum = sum^num;
}
return sum;
}
}
3.两个数组的交集
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> set1 = new HashSet<Integer>();
for (Integer n : nums1) set1.add(n);
HashSet<Integer> set2 = new HashSet<Integer>();
for (Integer n : nums2) set2.add(n);
set1.retainAll(set2);
int [] output = new int[set1.size()];
int idx = 0;
for (int s : set1) output[idx++] = s;
return output;
}
}
4.快乐数
class Solution {
public boolean isHappy(int n) {
Set<Integer> judge = new HashSet<>();
int sum =0;
while (true){
while (n>0){
int temp = n%10;
sum += temp*temp;
n = n/10;
}
if (sum==1) return true;
if (!judge.contains(sum)){
judge.add(sum);
}
else return false;
n = sum;
sum = 0;
}
}
}
5.同构字符串
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character,Character> que = new HashMap<>();
Map<Character,Character> antiQue = new HashMap<>();
char[] ss = s.toCharArray();
char[] tt = t.toCharArray();
for (int i = 0;i<ss.length;i++){
if (que.containsKey(ss[i])){
if (!antiQue.containsKey(tt[i])){
return false;
}else {
if (antiQue.get(tt[i])!=ss[i]) return false;
}
}else{
if (antiQue.containsKey(tt[i])){
return false;
}
else {
que.put(ss[i],tt[i]);
antiQue.put(tt[i],ss[i]);
}
}
}
return true;
}
}
6.字符串中的第一个唯一字符
答题思路：首先将每个字符出现及其出现的次数存入hashMap，然后遍历hashMap，将其次数为1的字符存入到set中，然后遍历字符数组，按照顺序查看当前字符是否在set中，从而查找第一个出现次数为1的字符。
class Solution {
public int firstUniqChar(String s) {
char[] temp = s.toCharArray();
Map<Character,Integer> hashMap = new HashMap<>();
Set<Character> set = new HashSet<>();
for (int i = 0;i<s.length();i++){
if (hashMap.containsKey(temp[i])){
int num = hashMap.get(temp[i]);
hashMap.put(temp[i],num+1 );
}else {
hashMap.put(temp[i],1);
}
}
for (Map.Entry<Character,Integer> entry:hashMap.entrySet()){
if (entry.getValue()==1) {
set.add(entry.getKey());
}
}
return set.size()==0?-1:find(temp, set);
}
private int find(char[] temp, Set<Character> key) {
for (int i =0;i<temp.length;i++){
if (key.contains(temp[i])){
return i;
}
}
return 0;
}
}
class Solution {
public int firstUniqChar(String s) {
char[] temp = s.toCharArray();
Map<Character, Integer> hashMap = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
hashMap.put(temp[i],hashMap.getOrDefault(temp[i],0)+1);
}
for (int i =0 ; i<s.length();i++){
if (hashMap.get(temp[i])==1) return i;
}
return -1;
}
}
7.存在重复元素 II
解题思路：hashMap中存入数字及其在数组中最后出现的索引，当前数字在hashMap中时，判断当前索引值与上一次该数字的索引值的差值与k的大小关系，小于等于k则返回true，否则更新索引值，循环结束时返回false
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer,Integer> hashMap = new HashMap<>();
for (int i = 0;i<nums.length;i++){
if (hashMap.containsKey(nums[i])){
if (k>=i-hashMap.get(nums[i])) return true;
}
hashMap.put(nums[i],i );
}
return false;
}
}
8.两个数组的交集 II
解题思路：将一个数组中的数字按照<数字，频率>键值对的形式存入hashMap，然后遍历数组2，如果当前数字存在于hashMap且对应的频率大于等于1，则说明该数字在数组1，2中都存在，且个数符合要求。
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
HashMap<Integer,Integer> hashMap = new HashMap<>();
for (int i =0 ;i<nums1.length;i++){
hashMap.put(nums1[i],hashMap.getOrDefault(nums1[i],0)+1);
}
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0;i<nums2.length;i++){
if (hashMap.containsKey(nums2[i])&&hashMap.get(nums2[i])-1>=0){
hashMap.put(nums2[i],hashMap.get(nums2[i])-1);
res.add(nums2[i]);
}
}
int[] ans = new int[res.size()];
int sum = 0;
for (int i:res){
ans[sum++] = i;
}
return ans;
}
}
9.两个列表的最小索引总和
解题思路：使用hashMap1存储字符数组list1，遍历字符数组list2，利用containKey函数来判断list2数组中的值是否在list2中，并利用minsum不断更新索引之和的最小值，并将其存入hashMap2中，然后根据最终的minsum值，去hashmap寻找相应的地点。
class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
HashMap<String, Integer> s1 = new HashMap<>();
HashMap<String, Integer> ss = new HashMap<>();
for (int i = 0; i < list1.length; i++) {
s1.put(list1[i], i);
}
int minsum = Integer.MAX_VALUE;
for (int i = 0; i < list2.length; i++) {
if (s1.containsKey(list2[i]) && s1.get(list2[i]) + i <= minsum) {
minsum = s1.get(list2[i]) + i;
ss.put(list2[i],minsum);
}
}
ArrayList<String> temp = new ArrayList<>();
for (Map.Entry<String, Integer> entry:ss.entrySet()){
if (entry.getValue()==minsum){
temp.add(entry.getKey());
}
}
if (temp.size()==0) return null;
String[] ans = new String[temp.size()];
int count = 0;
for (String s:temp){
ans[count++] = s;
}
return ans;
}
}
10.字母异位词分组
解题思路：遍历字符数组strs，对其中的每一个元素排序，然后将排序后一样的元素存在同一key值中。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> temp = new HashMap<>();
List<List<String>> ans = new LinkedList<>();
for (int i =0 ; i<strs.length;i++){
char[] res = strs[i].toCharArray();
Arrays.sort(res);
String s = new String(res, 0, res.length);
if (temp.containsKey(s)){
List<String> strings = temp.get(s);
strings.add(strs[i]);
temp.put(s,strings);
}else {
List<String> strings = new LinkedList<>();
strings.add(strs[i]);
temp.put(s,strings);
}
}
ans.addAll(temp.values());
return ans;
}
}
11.有效的数独
解题思路：有一说一太菜了。
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
那就分别创建三个哈希表，存储相应相应的行、列、子格及其相应的出现的数字，当有重复的数字时，即为无效数独。
class Solution {
public boolean isValidSudoku(char[][] board) {
HashMap<Integer, List<Integer>> col = new HashMap<>();
HashMap<Integer, List<Integer>> row = new HashMap<>();
HashMap<Integer, List<Integer>> block = new HashMap<>();
List<Integer> temp = new LinkedList<>();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int num = board[i][j] - '0';
int blockNum = i / 3 * 3 + j / 3;
if (col.getOrDefault(i, temp).contains(num) || row.getOrDefault(j, temp).contains(num) || block.getOrDefault(blockNum, temp).contains(num)) {
return false;
}
if (col.get(i) == null) {
List<Integer> list = new LinkedList<>();
list.add(num);
col.put(i, list);
}
if (row.get(j) == null) {
List<Integer> list = new LinkedList<>();
list.add(num);
row.put(j, list);
}
if (block.get(blockNum) == null) {
List<Integer> list = new LinkedList<>();
list.add(num);
block.put(blockNum, list);
}
col.get(i).add(num);
row.get(j).add(num);
block.get(blockNum).add(num);
}
}
}
return true;
}
}
class Solution {
public boolean isValidSudoku(char[][] board) {
boolean[][] row = new boolean[9][9];
boolean[][] col = new boolean[9][9];
boolean[][] block = new boolean[9][9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int num = board[i][j] - '1';
int blockIndex = i / 3 * 3 + j / 3;
if (row[i][num] || col[j][num] || block[blockIndex][num]) {
return false;
} else {
row[i][num] = true;
col[j][num] = true;
block[blockIndex][num] = true;
}
}
}
}
return true;
}
}
12.寻找重复的子树
解题思路：将二叉树序列化，依次存入到hashMap中，如果有重复的，则加入到ans中。注意：只需要加入一次，所以要设置加入条件temp.containsKey(s)&&temp.get(s)==1。
class Solution {
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
List<TreeNode> ans = new LinkedList<>();
HashMap<String,Integer> temp = new HashMap<>();
Serialization(root,temp,ans);
return ans;
}
private String Serialization(TreeNode root, HashMap<String, Integer> temp, List<TreeNode> ans) {
if (root==null) return" ";
String s = root.val+"{"+ Serialization(root.left, temp, ans)+"}"+
"{"+ Serialization(root.right, temp, ans)+"}";
if (temp.containsKey(s)&&temp.get(s)==1){
ans.add(root);
}
temp.put(s, temp.getOrDefault(s, 0)+1);
return s;
}
}
13.宝石与石头
解题思路：遍历S，经其中的石头类型和次数存入HashMap中，然后遍历J，取出宝石的次数。
class Solution {
public int numJewelsInStones(String J, String S) {
HashMap<Character,Integer> res = new HashMap<>();
int ans = 0;
for (int i =0;i<S.length();i++){
res.put(S.charAt(i), res.getOrDefault(S.charAt(i), 0)+1);
}
for (int i = 0;i<J.length();i++){
ans+=res.getOrDefault(J.charAt(i), 0);
}
return ans;
}
}
14.最小覆盖子串
解题思路：滑动窗口，用两个HashMap分别存储t中字符出现的次数和窗口中字符出现的次数
注意：Integer的比较需要使用equals
class Solution {
public String minWindow(String s, String t) {
HashMap<Character,Integer> needs = new HashMap<>();
HashMap<Character,Integer> window = new HashMap<>();
for (int i =0;i<t.length();i++){
needs.put(t.charAt(i), needs.getOrDefault(t.charAt(i), 0)+1);
}
int left = 0, right = 0,valid = 0;
int begin = 0,len=Integer.MAX_VALUE,end = 0;
while (right<s.length()){
Character c = s.charAt(right);
right++;
if (needs.containsKey(c)){
window.put(c, window.getOrDefault(c, 0)+1);
if (needs.get(c).equals(window.get(c))){
valid++;
}
}
while (valid==needs.size()){
if (right-left<len){
begin=left;
len = right-left;
end = right;
}
Character d = s.charAt(left);
left++;
if (needs.containsKey(d)){
if (needs.get(d).equals(window.get(d))){
valid--;
}
window.put(d, window.get(d)-1);
}
}
}
return len==Integer.MAX_VALUE?"":s.substring(begin, end);
}
}
15.字符串的排列
解题思路：滑动窗口，用两个HashMap分别存储t中字符出现的次数和窗口中字符出现的次数
class Solution {
public boolean checkInclusion(String s1, String s2) {
HashMap<Character,Integer> needs = new HashMap<>();
HashMap<Character,Integer> window = new HashMap<>();
for (int i = 0;i<s1.length();i++){
needs.put(s1.charAt(i), needs.getOrDefault(s1.charAt(i), 0)+1);
}
int left = 0,right = 0,valid = 0;
while (right<s2.length()){
Character c = s2.charAt(right);
right++;
if (needs.containsKey(c)){
window.put(c, window.getOrDefault(c, 0)+1);
if (window.get(c).equals(needs.get(c))){
valid++;
}
}
while (right-left>=s1.length()){
if (valid==needs.size()){
return true;
}
Character d = s2.charAt(left);
left++;
if (needs.containsKey(d)){
if (window.get(d).equals(needs.get(d))){
valid--;
}
window.put(d, window.get(d)-1);
}
}
}
return false;
}
}
16.找到字符串中所有字母异位词
解题思路：滑动窗口，用两个HashMap分别存储t中字符出现的次数和窗口中字符出现的次数
class Solution {
public List<Integer> findAnagrams(String s, String p) {
HashMap<Character,Integer> needs = new HashMap<>();
HashMap<Character,Integer> window = new HashMap<>();
for (int i = 0;i<p.length();i++){
needs.put(p.charAt(i),needs.getOrDefault(p.charAt(i), 0)+1);
}
int left = 0,right = 0,valid = 0;
List<Integer> ans = new LinkedList<>();
while (right<s.length()){
Character c = s.charAt(right);
right++;
if (needs.containsKey(c)){
window.put(c, window.getOrDefault(c,0 )+1);
if (window.get(c).equals(needs.get(c))){
valid++;
}
}
while (right-left>=p.length()){
if (valid==needs.size()){
ans.add(left);
}
Character d = s.charAt(left);
left++;
if (needs.containsKey(d)){
if (window.get(d).equals(needs.get(d))){
valid--;
}
window.put(d, window.get(d)-1);
}
}
}
return ans;
}
}
17.无重复字符的最长子串
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character,Integer> window = new HashMap<>();
int left = 0,right = 0;
int ans = 0;
while (right<s.length()){
Character c = s.charAt(right);
right++;
window.put(c, window.getOrDefault(c, 0)+1);
while (window.get(c)>1){
Character d = s.charAt(left);
left++;
window.put(d, window.get(d)-1);
}
ans = Integer.max(ans, right-left);
}
return ans;
}
}
18.四数相加 II
解题思路：相加为0，则将两个数组的所有数字组合之和存入HashMap中，然后遍历c,d，寻找是否有他们的相反数，并取出相应的值。
class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
HashMap<Integer,Integer> ans = new HashMap<>();
int res= 0;
for (int a:A){
for (int b:B){
ans.put(a+b,ans.getOrDefault(a+b,0)+1);
}
}
for (int c:C){
for (int d:D){
if (ans.containsKey(-(c+d))){
res += ans.get(-(c+d));
}
}
}
return res;
}
}
19.前 K 个高频元素
class Solution {
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> ans = new HashMap<>();
int[] temp = new int[k];
for (int i =0;i<nums.length;i++){
ans.put(nums[i],ans.getOrDefault(nums[i],0)+1);
}
ArrayList<Map.Entry<Integer,Integer>> res = new ArrayList<>(ans.entrySet());
res.sort(((o1, o2) -> o2.getValue()-o1.getValue()));
for (int i=0;i<k;i++){
temp[i] = res.get(i).getKey();
}
return temp;
}
}
Processed:
0.009, SQL:
8
