目录
136.只出现一次的数字
137.只出现一次的数字 ||
217.存在重复元素
219.存在重复元素 ||
771.宝石与石头
旧键盘(牛客)
首先需要导包 import java.utli.*;
表中常用的是前两个,时间复杂度低。O(1)
Set<E> set = new HashSet<>();
set.contains(E);
set.add(E);
set.remove(E);
返回值都为boolean
Map<K,V> map = new HashMap<>(); 键值对 (key , value)
map.put(K,V);
map.get(K); 返回值为V
背后 | 时间复杂度 | 常用方法 | |
HashSet | 哈希表 | O(1) | add() remove() contains() |
HashMap | 哈希表 | O(1) | put() get() |
TreeSet | 二叉搜索树 | O(logn) | |
TreeMap | 二叉搜索树 | O(logn) |
136.只出现一次的数字
使用异或的特点或HashSet的特点都行
0^A=A ; A^A=0
算法代码
class Solution {
public int singleNumber(int[] nums) {
// 1 使用异或 0^A=A A^A=0
/*int tmp = 0;
for(int i=0;i<nums.length;i++) {
tmp = tmp^nums[i];
}
return tmp;*/
// 2 使用HashSet的特点 不重复
Set<Integer> set = new HashSet<>();
for(int i=0;i<nums.length;i++) {
if(set.contains(nums[i])) {
set.remove(nums[i]);
}else {
set.add(nums[i]);
}
}
for(int i=0;i<nums.length;i++) {
if(set.contains(nums[i])) {
return nums[i];
}
}
return -1;
}
}
137.只出现一次的数字 ||
依旧是用 HashSet 或 异或 也能做
class Solution {
public int singleNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int i=0;i<nums.length;i++) {
if(set.contains(nums[i])) {
set.remove(nums[i]);
}else {
set.add(nums[i]);
}
}
for(int i=0;i<nums.length;i++) {
if(set.contains(nums[i])) {
return nums[i];
}
}
return -1;
}
}
217.存在重复元素
首先想到HashSet,HashMap都可以做,但时间复杂度上HashSet更适合。O(1)
class Solution {
public boolean containsDuplicate(int[] nums) {
/*Map<Integer,Integer> map = new HashMap<>();
for(int i:nums) {
if(map.get(i) == null) {
map.put(i,1);
}else{
return true;
}
}
return false;*/
Set<Integer> set = new HashSet<>();
for(int i:nums) {
if(!set.add(i)) {
return true;
}
}
return false;
}
}
219.存在重复元素 ||
首先想到HashSet,HashMap,但不同的是
这道题由于与元素和索引都有关,故 MapSet 更适合。
import java.util.*;
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++) {
if(map.get(nums[i]) == null) {
map.put(nums[i],i);
}else {
if(Math.abs(i-map.get(nums[i])) <= k) {
return true;
}else{
map.put(nums[i],i);
}
}
}
return false;
}
}
771.宝石与石头
使用 HashSet 或 TreeSet 都行,
不过 HashSet 背后是二叉搜索树,时间复杂度是O(logn)。
而 TreeSet 背后是哈希表,时间复杂度是O(1)。
相同点都是存储的值是不重复的。
故以后刷题就用 HashSet 和 HashMap,背后都是哈希表,时间复杂度低。
jewels都是唯一的。
class Solution {
public int numJewelsInStones(String jewels, String stones) {
int count = 0;
HashSet<Character> hash = new HashSet<>();
//TreeSet<Character> hash = new TreeSet<>();
for(int i=0;i<jewels.length();i++) {
hash.add(jewels.charAt(i));
}
for(int i=0;i<stones.length();i++) {
if(hash.contains(stones.charAt(i))) {
count++;
}
}
return count;
}
}
旧键盘(牛客)
依旧使用hashSet
题目要求字母是大写输出,故先变为大写,再把少的存入HashSet。再用方法contains()进行比较。
import java.util.Scanner;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String a = in.nextLine();
String b = in.nextLine();
func(a,b);
}
}
public static void func(String s1,String s2) {
HashSet<Character> hash1 = new HashSet<>();
//HashSet<Character> hash2 = new HashSet<>();
for(char ch:s2.toUpperCase().toCharArray()) {
hash1.add(ch);
}
for(char ch:s1.toUpperCase().toCharArray()) {
if(!hash1.contains(ch)) {
hash1.add(ch);
System.out.print(ch);
}
}
}
}