第一个只出现一次的字符位置
//思路一：
public int FirstNotRepeatingChar(String str) {
int[] freq = new int[256];
for(char c:str.toCharArray()){
freq[c]++;
}
for(int i=0;i<str.length();i++){
if(freq[str.charAt(i)]==1){
return i;
}
}
return -1;
}//思路二：
// 需要优化空间复杂度，可以使用 BitSet
// BitSet 按位操作，每一位的值只有两种 0 或者 1，来表示某个值是否出现过。
// 如果字符出现的次数 >= 2，则表示未多个
// 所以只需要 2 位就可表示字符出现的次数，即 0次(00)、1次(01)或者多次(11)
public int FirstNotRepeatingChar(String str) {
BitSet bitSet = new BitSet(256);
BitSet bitSet2 = new BitSet(256);
for(char c:str.toCharArray()){
if(!bitSet.get(c) && !bitSet2.get(c)){ //00
// c 原来出现次数 0次，加入 c 后出现次数为 1
bitSet2.set(c);
}
else if(!bitSet.get(c) && bitSet2.get(c)){ //01
// c 原来出现次数 1 次，加入 c 后出现次数为 3 (3 表示多次)
bitSet.set(c);
}
}
for(int i=0;i<str.length();i++){
char c= str.charAt(i);
if(!bitSet.get(c) && bitSet2.get(c)){
return i;
}
}
return -1;
}单词规律
public boolean wordPattern(String pattern, String str) {
if(pattern.length()==0 || str.length()==0){
return false;
}
String[] strs=str.trim().split(" ");
if(pattern.length()!=strs.length){
return false;
}
Map<Character,String> records=new HashMap<>();
for(int i=0;i<pattern.length();i++){
char c=pattern.charAt(i);
String s=strs[i];
if(records.containsKey(c)){
//如果已经包含了 c
String oldStr=records.get(c); // 当前的 s 必须要和 oldStr 相同
if(!s.equals(oldStr)){
return false;
}
}else{
//TODO:注意 value 是否相同
//pattern = "abba", str = "dog dog dog dog"
//不存在 b, 但是 records 中存在 <a,dog> 则 <b,dog> 就是错误的
if(records.containsValue(s)){
return false;
}
records.put(c,s);
}
}
return true;
}两个数组的交集
public int[] intersection(int[] nums1, int[] nums2) {
if(nums1==null || nums2==null){
return new int[]{};
}
HashSet<Integer> record=new HashSet<>();
for(int num:nums1){
record.add(num);
}
HashSet<Integer> resRecord=new HashSet<>();
for(int num:nums2){
if(record.contains(num)){
resRecord.add(num);
}
}
int[] res=new int[resRecord.size()];
int index=0;
for(int num:resRecord){
res[index++]=num;
}
return res;
}两个数组的交集 II
public int[] intersect(int[] nums1, int[] nums2) {
if(nums1==null || nums2==null){
return new int[]{};
}
//统计 nums1 中数字出现的次数
HashMap<Integer,Integer> record=new HashMap<>();
for(int num:nums1){
int freq=record.getOrDefault(num,0);
record.put(num,++freq);
}
ArrayList<Integer> resRecord=new ArrayList<>();
for(int num:nums2){
int freq=record.getOrDefault(num,0); //获取 num 的出现次数
if(freq>0){
resRecord.add(num);
record.put(num,--freq);
}
}
int[] res=new int[resRecord.size()];
int index=0;
for(int num:resRecord){
res[index++]=num;
}
return res;
}两数之和
public int[] twoSum(int[] nums, int target) {
//record <key,value> : key 记录元素值，value 记录元素出现的下标
HashMap<Integer,Integer> record=new HashMap<>();
for(int i=0;i<nums.length;i++){
int v=target-nums[i];
if(record.containsKey(v)){
return new int[]{i,record.get(v)};
}
//注意元素，相同的下标会覆盖掉，这样就不用担心重复利用这个数组中同样的元素了。
record.put(nums[i],i);
}
return new int[]{};
}四数相加 II
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
//record <key,value> key 记录数字，value 记录该数字出现次数
HashMap<Integer,Integer> record=new HashMap<>();
for(int k=0;k<C.length;k++){
for(int l=0;l<D.length;l++){
int freq=record.getOrDefault(C[k]+D[l],0);
record.put(C[k]+D[l],++freq);
}
}
int res=0;
for(int i=0;i<A.length;i++){
for(int j=0;j<B.length;j++){
if(record.containsKey(-A[i]-B[j])){
res+=record.get(-A[i]-B[j]);
}
}
}
return res;
}回旋镖的数量
public int numberOfBoomerangs(int[][] points) {
int res=0;
for(int i=0;i<points.length;i++){
//<k,v> k 记录距离的平方 v 记录出现的次数
HashMap<Integer,Integer> record=new HashMap<>();
for(int j=0;j<points.length;j++){
if(j!=i){
int freq=record.getOrDefault(distance(points,i,j),0);
record.put(distance(points,i,j),++freq);
}
}
//map 记录 i->到其他点的距离出现的次数
//如果到点i的距离相等的点 >=2（假设为n）,则有n*(n-1)种可能
for(Integer key:record.keySet()){
int freq=record.getOrDefault(key,0);
if(freq>=2){
res+=freq*(freq-1);
}
}
}
return res;
}
//计算点 i 和 点 j 之间的距离的平方
private int distance(int[][] points,int i,int j){
int x1=points[i][0],y1=points[i][1];
int x2=points[j][0],y2=points[j][1];
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}存在重复元素 II
//思路：
// 滑动窗口和 set 的综合使用:
// 维持一个长度为k的滑动窗口，只要在该窗口查找是否有两个相等的元素。
// 同时窗口不断向前滑行。
public boolean containsNearbyDuplicate(int[] nums, int k) {
//维护一个长度为 k 的窗口，set.size()长度为滑动窗口
HashSet<Integer> set=new HashSet<>();
for(int i=0;i<nums.length;i++){
int num=nums[i];
if(set.contains(num)){ // num 出现在滑动窗口中,最大绝对值差为 k
return true;
}
set.add(num);
if(set.size()==k+1){ //滑动窗口大小必须维持为 k，则需要删除最左边的元素
//i-x+1=k+1 ==> x=i-k
set.remove(nums[i-k]); //删除该滑动窗口最左边元素
}
}
return false;
}存在重复元素 III
//思路：
//nums [i] 和 nums [j] 的差的绝对值最大为 |nums[i]-nums[j]|<=t
//则对 nums[j] 有 (nums[i]-t) <= nums[j]<= (nums[i]+t)
//维持一个长度为k的滑动窗口，只要在该窗口查找是否存在元素在[nums[i]-t,nums[i]+t] 之间。
//同时窗口不断向前滑行。
//注意 k 和 t 的值，显然 k<1 或者 t<0，可以直接返回 false
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (k < 1 || t < 0){
return false;
}
//维护一个长度为 k 的有序的滑动窗口
//这里使用 Long 类型，以为 nums[i]+t 有可能超过 int 范围
SortedSet<Long> set=new TreeSet<>();
for(int i=0;i<nums.length;i++){
//使用 subSet 判断是否有元素存在与 [nums[i]-t,nums[i]+t] 之间
Set<Long> subSet=set.subSet((long)(nums[i]-t),(long)(nums[i]+t+1));
//nums[i]+t+1 因为是左闭右开的
if(!subSet.isEmpty()){
return true;
}
set.add((long)nums[i]);
if(set.size()==k+1){
set.remove((long)nums[i-k]);
}
}
return false;
}