头像

visionrl


访客:1730

离线:1天前



题目描述

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

样例

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。


算法1

时间复杂度 $O(n)$

双指针算法,遍历数组一遍,若当前位不等于val,对数组进行更新;
始终保证指针 i 在指针 idx 之前。

Java 代码

class Solution {
    public int removeElement(int[] nums, int val) {
        int n=nums.length;
        int idx=0;
        for(int i=0;i<n;i++){
            if(nums[i]==val)
                continue;
            nums[idx++]=nums[i];
        }
        return idx;
    }
}



题目描述

给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

注意:

答案中不可以包含重复的四元组。

样例

给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。

满足要求的四元组集合为:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]


算法1

时间复杂度 $O(n^3)$

Java 代码

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res=new ArrayList<>();
        Arrays.sort(nums);
        int n=nums.length;
        for(int i=0;i<n;i++){
            while(i!=0&&i<n&&nums[i]==nums[i-1])
                i++;
            for(int j=i+1;j<n;j++){
                while(j!=i+1&&j<n&&nums[j]==nums[j-1])
                    j++;
                int l=j+1,r=n-1;
                while(l<r){
                    int val=nums[i]+nums[j]+nums[l]+nums[r];
                    if(val==target){
                        List<Integer> path=
                        new ArrayList(Arrays.asList(nums[i],nums[j],nums[l],nums[r]));
                        res.add(path);
                        do{l++;}while(l<r&&nums[l]==nums[l-1]);
                        do{r--;}while(l<r&&nums[r]==nums[r+1]);
                    }else if(val<target){
                         do{l++;}while(l<r&&nums[l]==nums[l-1]);
                    }else{
                        do{r--;}while(l<r&&nums[r]==nums[r+1]);
                    }
                }
            }
        }
        return res;
    }
}



题目描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

样例

输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

算法1

时间复杂度 $O(n^2)$

排序O(nlogn)
枚举O(n^2)

排序后i从0开始遍历, l=i+1, r=n-1;
计算 nums[i] + nums[l] + nums[r] 更新结果;
枚举 i , l , r 时循环去重。

Java 代码

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int n=nums.length;
        Arrays.sort(nums);
        int ans=0x3f3f3f3f;
        for(int i=0;i<n;i++){
            while(i!=0&&i<n&&nums[i]==nums[i-1])
                i++;
            int l=i+1,r=n-1;
            while(l<r){
                int val=nums[i]+nums[l]+nums[r];
                if(val==target)
                    return target;
                else if(val<target){
                    ans=(Math.abs(target-val)<Math.abs(ans-target))?val:ans;
                    do{l++;}while(l<r&&nums[l]==nums[l-1]);
                }else if(val>target){
                    ans=(Math.abs(target-val)<Math.abs(ans-target))?val:ans;
                    do{r--;}while(l<r&&nums[r]==nums[r+1]);
                }
            }
        }
        return ans;
    }
}


活动打卡代码 AcWing 831. KMP字符串

visionrl
30天前
import java.util.*;
import java.io.*;
class Main{
    static int N=100010,M=1000010;
    static int n,m;
    static int[] ne=new int[N];
    //p[] 用于匹配的模板串 s[] 模式串
    static char[] p=new char[N],s=new char[M];
    public static void main(String[] args) throws IOException{
        Scanner sc=new Scanner(System.in);
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        n=sc.nextInt();
        String str1=sc.next();
        for(int i=1;i<=n;i++)
            p[i]=str1.charAt(i-1);
        m=sc.nextInt();
        String str2=sc.next();
        for(int i=1;i<=m;i++)
            s[i]=str2.charAt(i-1);
        for(int i=2,j=0;i<=n;i++){
            while(j!=0&&p[i]!=p[j+1]) j=ne[j];
            if(p[i]==p[j+1]) j++;
            ne[i]=j;
        }
        for(int i=1,j=0;i<=m;i++){
            while(j!=0&&s[i]!=p[j+1]) j=ne[j];
            if(s[i]==p[j+1]) j++;
            if(j==n){
                bw.write(i-n+" ");
                j=ne[j];
            }
        }
        bw.flush();
    }
}


活动打卡代码 AcWing 143. 最大异或对

visionrl
30天前
import java.util.*;
class Main{
    static int N=100010,M=31*N;
    static int[][] son=new int[M][2];
    static int idx;
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        int ans=0;
        while(t-->0){
            int n=sc.nextInt();
            insert(n);
            int u=query(n);
            ans=Math.max(ans,n^u);
        }
        System.out.println(ans);
    }
    public static void insert(int n){
        int p=0;
        for(int i=30;i>=0;i--){
            int u=n>>i&1;
            if(son[p][u]==0) son[p][u]=++idx;
            p=son[p][u];
        }
    }
    public static int query(int n){
        int p=0,res=0;
        for(int i=30;i>=0;i--){
            int u=n>>i&1;
            if(son[p][1-u]!=0){
                res=res*2+(1-u);
                p=son[p][1-u];
            }else{
                res=res*2+u;
                p=son[p][u];
            }
        }
        return res;
    }
}



visionrl
30天前
import java.util.*;
class Main{
    static int N=100010;
    static int[] p=new int[N],size=new int[N];
    public static int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        for(int i=1;i<=n;i++){
            p[i]=i;
            size[i]=1;
        }
        while(m-->0){
            String ops=sc.next();
            if(ops.equals("C")){
                int a=sc.nextInt(),b=sc.nextInt();
                a=find(a);b=find(b);
                if(a==b) continue;
                p[a]=b;
                size[b]+=size[a];
            }else if(ops.equals("Q1")){
                int a=sc.nextInt(),b=sc.nextInt();
                a=find(a);b=find(b);
                if(a==b) 
                    System.out.println("Yes");
                else
                    System.out.println("No");
            }else{
                int a=sc.nextInt();
                System.out.println(size[find(a)]);
            }
        }
    }
}


活动打卡代码 AcWing 836. 合并集合

visionrl
30天前
import java.util.*;
class Main{
    static int N=100010;
    //p[] 并查集数组 p[i]为i的祖宗节点 若p[i]=i则i为根节点
    static int[] p=new int[N];
    //返回x的祖宗节点+状态压缩(将路径上所有点的父节点都指向根节点)
    public static int find(int x){
        if(p[x]!=x) p[x]=find(p[x]);
        return p[x];
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        for(int i=1;i<=n;i++)
            p[i]=i;
        while(m-->0){
            char ops=sc.next().charAt(0);
            int a=sc.nextInt(),b=sc.nextInt();
            if(ops=='M')
                //判断a,b各自的祖宗节点放入一个集合
                p[find(a)]=find(b);
            else if(ops=='Q'){
                //判断a,b各自的祖宗节点是否为同一节点
                if(find(a)==find(b))
                    System.out.println("Yes");
                else
                    System.out.println("No");
            }
        }
    }
}


活动打卡代码 AcWing 835. Trie字符串统计

visionrl
1个月前
import java.util.*;
class Main{
    static int N=20010;
    static int[][] son=new int[N][26];
    static int[] cnt=new int[N];
    static int idx;
    public static void insert(String s){
        int p=0;
        for(int i=0;i<s.length();i++){
            int u=s.charAt(i)-'a';
            if(son[p][u]==0) son[p][u]=++idx;
            p=son[p][u];
        }
        cnt[p]++;
    }
    public static int query(String s){
        int p=0;
        for(int i=0;i<s.length();i++){
            int u=s.charAt(i)-'a';
            if(son[p][u]==0) return 0;
            p=son[p][u];
        }
        return cnt[p];
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int T=sc.nextInt();
        while(T-->0){
            char c=sc.next().charAt(0);
            String s=sc.next();
            if(c=='I')
                insert(s);
            else if(c=='Q')
                System.out.println(query(s));
        }
    }
}


活动打卡代码 AcWing 830. 单调栈

visionrl
1个月前
import java.util.*;
class Main{
    static int N=100010;
    static int n;
    static int[] h=new int[N];
    static int[] res=new int[N];
    static Stack<Integer> stack=new Stack<>();
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        h[0]=h[n+1]=-1;
        for(int i=1;i<=n;i++)
            h[i]=sc.nextInt();
        stack.push(0);
        for(int i=1;i<=n;i++){
            while(h[stack.peek()]>=h[i])
                stack.pop();
            res[i]=h[stack.peek()];
            stack.push(i);
        }
        for(int i=1;i<=n;i++)
            System.out.print(res[i]+" ");
    }
}


活动打卡代码 AcWing 154. 滑动窗口

visionrl
1个月前
import java.util.*;
import java.io.*;
class Main{
    public static void main(String[] args) throws IOException{
        Scanner sc=new Scanner(System.in);
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int n=sc.nextInt(),k=sc.nextInt();
        int[] a=new int[n];
        for(int i=0;i<n;i++)
            a[i]=sc.nextInt();
        Deque<Integer> d1=new LinkedList<>();
        Deque<Integer> d2=new LinkedList<>();
        int[] r1=new int[n-k+1];
        int[] r2=new int[n-k+1];
        for(int i=0;i<n;i++){
            while(!d1.isEmpty()&&d1.getFirst()<=i-k)
                d1.removeFirst();
            while(!d2.isEmpty()&&d2.getFirst()<=i-k)
                d2.removeFirst();
            while(!d1.isEmpty()&&a[d1.getLast()]<a[i])
                d1.removeLast();
            while(!d2.isEmpty()&&a[d2.getLast()]>a[i])
                d2.removeLast();
            d1.offer(i);
            d2.offer(i);
            if(i-k+1>=0){
                r1[i-k+1]=a[d1.getFirst()];
                r2[i-k+1]=a[d2.getFirst()];
            }
        }
        for(int i=0;i<r2.length;i++)
            bw.write(r2[i]+" ");
        bw.write("\n");
        for(int i=0;i<r1.length;i++)
            bw.write(r1[i]+" ");
        bw.flush();
    }
}