头像

xsinx


访客:10948

离线:14小时前



xsinx
3天前


1.如果两个数组有序的话,那么必然采用方法二
2.如果两个数组的大小差距很大采用方法一,首先将小的放入HashMap这样会节约Map的空间,其次如果一个
数组过大的话,进行排序NlogN的时间太大
3.如果 nums2 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,那么必然
不能采用费内存的方法一,要先在外部进行排序再读取两个文件

方法一:利用HashMap实现计数

  • 时间复杂度O(N+M),N是nums1的长度,M是nums2的长度
  • 空间复杂度是 O(Math.min(N,M)),两个数组的交集最大就是最小值
public int[] intersect(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length) {
        return intersect(nums2, nums1);
    }
    HashMap<Integer, Integer> m = new HashMap<>();
    for (int n : nums1) {
        m.put(n, m.getOrDefault(n, 0) + 1);
    }
    int k = 0;
    for (int n : nums2) {
        int cnt = m.getOrDefault(n, 0);
        if (cnt > 0) {
            nums1[k++] = n;
            m.put(n, cnt - 1);
        }
    }
    return Arrays.copyOfRange(nums1, 0, k);
}

方法二:双指针

  • 时间复杂度首选是两个数组的排序,一个是O(NlogN),一个是O(MlogM),遍历的时间复杂度是N+M
    这样的话就是三者的一个最大值,就和具体的N和M有关系了
  • 空间复杂度是O(1),不需要额外的空间
public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        LinkedList<Integer> list=new LinkedList<>();
        int p1=0,p2=0;
        while(p1<nums1.length && p2<nums2.length)
        {
            if(nums1[p1]<nums2[p2]) p1++;
            else if(nums1[p1]>nums2[p2]) p2++;
            else{
                list.add(nums1[p1]);
                p1++;
                p2++;
            }
        }
        int res[]=new int[list.size()];
        int index=0;
        for(int i:list) res[index++]=i;
        return res;
    }



xsinx
3天前

介绍几道LC上双指针排序的问题

面试题21题

  • index指向的是奇数的最后一个位置,那么index+1指向的是偶数的第一个位置
  • 假设现在的序列是 1 3 2 4 5,那么index指向的是3,i指向的是5。所以现在要将2和5来交换
  • 先将index的下标加1,再和5交换
 void swap(int nums[],int i,int j)
    {
        if(i==j) return;
        nums[i]=nums[i]^nums[j];
        nums[j]=nums[i]^nums[j];
        nums[i]=nums[i]^nums[j];
    }

    public int[] exchange(int[] nums) {
        int index=-1;
        for(int i=0;i<nums.length;i++)
            if(nums[i]%2==1) swap(nums,i,++index);
        return nums;
    }

LC 283

  • index是第一个不为0的数字,剩下的和上面的一样
 void swap(int arr[],int i,int j)
    {
        if(i==j) return;
        arr[i]=arr[i]^arr[j];
        arr[j]=arr[i]^arr[j];
        arr[i]=arr[i]^arr[j];
    }

    public void moveZeroes(int[] nums) {
        int index=-1;
        for(int i=0;i<nums.length;i++)
            if(nums[i]!=0) swap(nums,++index,i);
    }

LC75

  • l指向0的最后一个,所以要将初始值设置为-1,当cur=0时,先将l加一再交换和cur的值。由于交换过来的值必然是1,所以将cur++
  • r指向的是2的最前面一个值,所以初始值设置为nums.length,当cur=2时,先将r减一再交换
  • 由于r指向的是2最前面的元素,所以小于r就可以终止了
void swap(int nums[],int i,int j)
    {
        if(i==j) return;
        nums[i]=nums[i]^nums[j];
        nums[j]=nums[i]^nums[j];
        nums[i]=nums[i]^nums[j];
    }

 public void sortColors(int[] nums) {
     int cur=0,r=nums.length,l=-1;
     while(cur<r){
         if(nums[cur]==0) swap(nums,++l,cur++);
         else if(nums[cur]==1) cur++;
         else swap(nums,cur,--r);
     }
  }


活动打卡代码 AcWing 86. 构建乘积数组

xsinx
10天前

方法一:2遍扫描+长度为N的数组,正向求左边元素,逆向求右边元素

class Solution {
    public int[] multiply(int[] a) {
        if(a==null||a.length==0) return new int[]{};
        int res[]=new int[a.length];
        res[0]=1;
        //从左向右遍历
        for(int i=1;i<a.length;i++)
            if(i==1) res[i]=a[0];
            else res[i]=res[i-1]*a[i-1];
        int temp=a[a.length-1];
        //从右向左遍历
        for(int i=a.length-2;i>=0;i--)
        {
            res[i]*=temp;
            temp*=a[i];
        }
        return res;
    }
}

自然可以开3个数组,一个数组放左边元素的乘积和,一个数组放右边元素的成绩和。再将对应位置上的元素相乘
这样就会扫三遍,开三个数组




xsinx
16天前

方法一:二分查找

class Solution {
    public int mySqrt(int x) {
        long l=0,r=x;
        while(l<r)
        {
            //从右向左第一个满足mid*mid<=x的值
            //如果是从左向右的话,只能找第一个mid*mid>=x的值,那么就不是下取整,而是上取整了
            //两个整数相加存在溢出的问题
            long mid=l+r+1>>1;
            if(mid*mid<=x) l=mid;
            else r=mid-1;
        }
        return (int)l;
    }
}

方法二:牛顿迭代法

class Solution {
    public int mySqrt(int x) {
        double cur=x;
        double p=(x+1)/2;
        //利用切线不断逼近的过程中,前者和后者之间的差距小于1e-7就可以跳出循环
        while(Math.abs(p-cur)>1e-7){
            cur=p;
            p=(cur+x/cur)/2;
        }
        return cur>0?(int)cur:-(int)cur;
    }
}



xsinx
1个月前

1.最优解问题

  • 有限集合:DP、贪心、DFS
  • 无限集合:数学方法或二分

2.数据范围是:10^5,可推断时间复杂度为$O(nlogn)$

import java.util.*;
public class Main{
    static int arr[];
    public static boolean check(int val)
    {
        for(int i=0;i<arr.length;i++) 
        {
            val=2*val-arr[i];
            if(val>=100000) return true;
            if(val<0) return false;
        }
        return true;
    }

    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        int len=sc.nextInt();
        arr=new int[len];
        for(int i=0;i<len;i++) arr[i]=sc.nextInt();
        int l=1,r=100000;
        while(l<r)
        {
            int mid=l+r>>1;
            if(check(mid)) r=mid;
            else l=mid+1;
        }
        System.out.print(l);
    }
}


活动打卡代码 AcWing 1048. 鸡蛋的硬度

xsinx
1个月前
import java.util.*;
public class Main{
static int N=110,M=11;
static int f[][]=new int[N][M];
public static void main(String args[])
{
    for(int i=1;i<N;i++) f[i][1]=i;
    for(int i=1;i<M;i++) f[1][i]=1;
    Scanner sc=new Scanner(System.in);
    while(sc.hasNext())
    {
        int n=sc.nextInt();
        int m=sc.nextInt();

        for(int i=2;i<=n;i++)
            for(int j=2;j<=m;j++)
            {
                f[i][j]=f[i][j-1];
                for(int k=1;k<=i;k++)
                    f[i][j]=Math.min(f[i][j],Math.max(f[k-1][j-1],f[i-k][j])+1);
            }
        System.out.println(f[n][m]);
    }
}
}


活动打卡代码 AcWing 1259. 二叉树遍历

xsinx
2个月前
import java.util.*;
public class Main{
    static String level=null;
    public static int find(char c)
    {
        for(int i=0;i<level.length();i++)
            if(level.charAt(i)==c) return i;
        return -1;
    }

    public static String fun(String s)
    {
        if(s.length()<=1) return s;
        int index=find(s.charAt(0));
        int j=0;
        for(int i=1;i<s.length();i++)
        {
            int val=find(s.charAt(i));
            if(val<index)
            {
                index=val;
                j=i;
            }
        }

        String root=s.charAt(j)+"";
        String l=fun(s.substring(0,j));
        String r=fun(s.substring(j+1,s.length()));
        return root+l+r;
    }

    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        String in=sc.nextLine();
        level=sc.nextLine();
        System.out.print(fun(in));
    }
}


活动打卡代码 AcWing 1490. 最长上升子串

xsinx
2个月前
public class Main{
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        int len=sc.nextInt();
        int arr[]=new int[len];
        for(int i=0;i<len;i++) arr[i]=sc.nextInt();
        int f[]=new int[len];//以i开头的最长上升子串
        int g[]=new int[len];//以i结尾的最长上升子串
        Arrays.fill(f,1);
        Arrays.fill(g,1);
        for(int i=1;i<len;i++) 
            if(arr[i]>arr[i-1]) g[i]=g[i-1]+1;
        for(int i=len-2;i>=0;i--) 
            if(arr[i]<arr[i+1]) f[i]=f[i+1]+1;
        int res=1;
        //注意特判
        for(int i=0;i<len;i++)
            if(i==0) res=Math.max(res,f[i+1]);
            else if(i==len-1) res=Math.max(res,g[i-1]);
            else if(arr[i-1]<arr[i+1]) res=Math.max(res,g[i-1]+f[i+1]);
            else res=Math.max(res,Math.max(g[i-1],f[i+1]));
        System.out.println(res);
    }
}



xsinx
2个月前
// The query API is defined in the parent class Getvalue:
// int query(int x, int y);
// return int means matrix[x][y].

class Solution extends Getvalue {
    public int[] getMinimumValue(int n) {
        int l=0,r=n-1;
        while(l<r)
        {
            int mid=l+r>>1;
            int k=0;
            int val=Integer.MAX_VALUE;
            //找到对应的行
            for(int i=0;i<n;i++)
            {
                int value=query(i,mid);
                if(value<val)
                {
                    val=value;
                    k=i;
                }
            }
            //判断是否越界
            int left=mid==0?-1:mid-1;
            int right=mid==n-1?-1:mid+1;

            int lval=query(k,left);
            int rval=query(k,right);
            //如果两侧都小于当前值就直接返回
            if(val<lval && val<rval) return new int[]{k,mid};
            else if(lval<val) r=mid-1;
            else l=mid+1;
        }
        //再计算当前列中的最小值,这时l=r
        int res=Integer.MAX_VALUE;
        int k=0;
        for(int i=0;i<n;i++)
        {
            int val=query(i,l);
            if(val<res)
            {
                k=i;
                res=val;
            }
        }
        return new int[]{k,r};
    }
}



xsinx
2个月前

两个栈

class MinStack {
    Stack<Integer> stack;
    Stack<Integer> min;
    /** initialize your data structure here. */
    public MinStack() {
        stack=new Stack<>();
        min=new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if(min.isEmpty()) min.push(x);
        else if(x>=min.peek()) min.push(min.peek());
        else min.push(x);
    }

    public void pop() {
        stack.pop();
        min.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min.peek();
    }
}

一个栈

class MinStack {
    Stack<Integer> stack;
    int min=Integer.MAX_VALUE;
    /** initialize your data structure here. */
    public MinStack() {
        stack=new Stack<>();
    }

    public void push(int x) {
        if(x<=min)
        {
            stack.push(min);
            min=x;
        }
        stack.push(x);
    }

    public void pop() {
        if(min==stack.pop()) min=stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }
}