头像

wyyang




离线:3小时前



wyyang
1天前

算法1

使用双端队列 Deque

时间复杂度

参考文献

Java 代码

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int k = s.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = s.nextInt();
        Deque<Integer> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (!q.isEmpty() && i - q.peekFirst() + 1 > k) q.pollFirst();
            while (!q.isEmpty() && a[i] <= a[q.peekLast()]) q.pollLast();

            q.offer(i);
            if (i >= k - 1) sb.append(a[q.peekFirst()]).append(" ");
        }
        System.out.println(sb.toString());
        q.clear();
        sb.setLength(0);
        for (int i = 0; i < n; i++) {
            if (!q.isEmpty() && i - q.peekFirst() + 1 > k) q.pollFirst();
            while (!q.isEmpty() && a[i] >= a[q.peekLast()]) q.pollLast();

            q.offer(i);
            if (i >= k - 1) sb.append(a[q.peekFirst()]).append(" ");
        }
        System.out.print(sb.toString());
    }
}



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

wyyang
1天前
import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int k = s.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = s.nextInt();
        // 1 由于n比较大,nlgn也会超时,所以需要找到on做法,能快速求出窗口中的最值。
        // 2 可以用单调队列来维护窗口,求最小值,则保证队列是单调递增的,每次取队头。
        // 3 同理求最大值,则保证队列是单调递减的,每次取队头。
        // 4 java中可以使用双端队列来维护,可以在队头,队尾操作。
        // 5 和单调栈的区别在于1)要维护窗口大小为k,若超出,则移除队头元素。2)队列中存储下标,3)维护队列的单调性同单调栈
        Deque<Integer> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (q.size() > 0 && i - q.peekFirst() + 1 > k) q.pollFirst();
            while (q.size() > 0 && a[q.peekLast()] >= a[i]) q.pollLast();

            q.offer(i);
            if (i >= k - 1) sb.append(a[q.peekFirst()]).append(" ");
        }
        System.out.print(sb.toString());
        // q.clear();
        System.out.println();
        StringBuilder sb2 = new StringBuilder();
        Deque<Integer> q2 = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (q2.size() > 0 && i - q2.peekFirst() + 1 > k) q2.pollFirst();
            while (q2.size() > 0 && a[q2.peekLast()] <= a[i]) q2.pollLast();

            q2.offer(i);
            if (i >= k - 1) sb2.append(a[q2.peekFirst()]).append(" ");
        }
        System.out.print(sb2.toString());
    }
}


活动打卡代码 AcWing 841. 字符串哈希

wyyang
2天前
import java.util.*;
public class Main{
    static int C = 131; // 常量
    static long[] h; // 存储前缀hash值 i表示串 0-i对应的hash值
    static long[] p; // 缓存p进制的值,即131的 i次方
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int m = s.nextInt();
        String str = s.next();
        h = new long[n + 1];
        p = new long[n + 1];
        p[0] = 1; // ###注意初始化
        // 计算字符串前缀hash
        hash(str);
        for (int i = 0; i < m; i++) {
            int l1 = s.nextInt();
            int r1 = s.nextInt();
            int l2 = s.nextInt();
            int r2 = s.nextInt();
            if (check(l1, r1, l2, r2)) {
                System.out.println("Yes");
            } else System.out.println("No");
        }
    }

    static void hash(String str) {
        int len = str.length();
        for (int i = 1; i <= len; i++) {
            h[i] = h[i - 1] * C + str.charAt(i - 1);  // ### C进制数,*c
            p[i] = p[i - 1] * C;
        }
    }

    static boolean check(int l1, int r1, int l2, int r2) {
        long s1 = h[r1] - h[l1 - 1] * p[r1 - l1 + 1];
        long s2 = h[r2] - h[l2 - 1] * p[r2 - l2 + 1];
        //System.out.print(" s1 " + s1 + " s2 " + s2);
        return s1 == s2;
    }
}



wyyang
5天前
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        // 求满足条件 的K个数要想到用堆,根据条件堆里最终存的是满足两个条件的数,若超过K个数,则将最大的数(与x的绝对值差最大 或数最大)删除
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {
            int v1 = Math.abs(x - o1);
            int v2 = Math.abs(x - o2);
            if (v1 == v2) return o2 - o1;

            return v2 - v1;
        });
        for (int i = 0; i < arr.length; i++) {
            pq.offer(arr[i]);
            if (pq.size() > k) pq.poll();
        }

        List<Integer> res = new ArrayList<>();
        int i = 0;
        while (pq.size() > 0) {
            res.add(pq.poll());
        }
        Collections.sort(res);
        return res;
    }
}



wyyang
5天前
class Solution {
    public boolean judgeCircle(String moves) { 
        int x = 0;
        int y = 0;
        for (int i = 0; i < moves.length(); i++) {
            char ch = moves.charAt(i);
            if (ch == 'R') y++;
            else if (ch == 'L') y--;
            else if (ch == 'U') x--;
            else if (ch == 'D') x++;
        }

        return x == 0 && y == 0;
    }
}



wyyang
1个月前
class SummaryRanges {
    TreeSet<int[]> set;
    int INF;
    /** Initialize your data structure here. */
    public SummaryRanges() {
        set = new TreeSet<>((o1, o2) -> {
            if (o1[0] != o2[0]) return o1[0] - o2[0];
            return o1[1] - o2[1];
        });

        INF = (int)1e8;
        // 先添加 左右两个哨兵区间,方便统一处理
        set.add(new int[]{-INF, -INF});
        set.add(new int[]{INF, INF});
    }
    // 根据题意:要求每次能快速 找到x要插入的区间或区间范围。若区间有序(根据左右点从小到大排序),则可以快速查找。
    // 可以使用TreeSet自定义排序算法,每次搜索x所在的区间范围(找到小于等于x的最大区间和大于等于x的最小区间。可以简单看作 紧贴x的左右两个数)。然后判断,分五种:
    // 1、x在现有区间范围内,则直接返回。2、x-1] x [x + 1,则合并左右两个区间,并删除左右区间。3、x-1] x 只合并左区间,并删除左区间。
    // 4、x [x + 1 只合并右区间,并删除右区间。 5、新添加区间[x,x]
    public void addNum(int x) {
        // 找到x的左右区间,因为有哨兵存在,所以肯定能找到,不用再考虑null情形
        int[] left = set.floor(new int[]{x, INF});
        int[] right = set.ceiling(new int[]{x, INF});
        if (left[1] >= x) return;
        if (left[1] + 1 == x && right[0] - 1 == x) {
            set.add(new int[]{left[0], right[1]});
            set.remove(left);
            set.remove(right);
        } else if (left[1] + 1 == x) {
            set.add(new int[]{left[0], x});
            set.remove(left);
        } else if (right[0] - 1 == x) {
            set.add(new int[]{x, right[1]});
            set.remove(right); 
        } else {
            set.add(new int[]{x, x});
        }
    }

    public int[][] getIntervals() {
        int[][] res = new int[set.size() - 2][2]; // 要去除哨兵
        int i = 0;
        for (int[] arr : set) {
            if (arr[0] != -INF && arr[0] != INF) res[i++] = new int[]{arr[0], arr[1]};
        }

        return res;
    }
}


活动打卡代码 AcWing 898. 数字三角形

wyyang
1个月前
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int[][] m = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                m[i][j] = s.nextInt();
            }
        }

        // dp[i][j] 表示走到第i层第j个位置的最大路径和,求max(dp[n][j]),这里从下至上求,避免各种边界 问题
        // 状态方程: dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) 
        int[][] dp = new int[n + 1][n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j + 1]) + m[i][j];
            }
        }

        System.out.print(dp[0][0]);
    }
}


活动打卡代码 LeetCode 525. 连续数组

wyyang
1个月前
class Solution {
    public int findMaxLength(int[] nums) {
        // 最简单是枚举每个区间尾结点,统计从0,1,2..。到i区间0和1的数量。取最长的。由于范围在数组长度超过1W两重循环爆int
        // 考虑优化:1、每次遍历时统计0,1的个数,然后hash中缓存,key:1-0的差, value:最小下标。2、由于要求最小下标,若当前差值在hash表中不存在时才缓存。
        // 3、根据前缀和的原理:si表示从1-i区间 1-0的差。 找到sj使得si - sj = 0,用到2的hash表来解决。
        Map<Integer, Integer> map = new HashMap<>();
        int one = 0;
        int zero = 0;
        map.put(0, 0);// 差值为0的下标为0
        int res = 0;
        for (int i = 1; i <= nums.length; i++) { // 类似计算前缀和,这里s表示从1到i区间1-0的差。
            if (nums[i - 1] == 0) zero++;
            else one++;
            int s = one - zero;
            if (map.containsKey(s)) res = Math.max(res, i - map.get(s));
            else map.put(s, i);
        }

        return res;
    }
}


活动打卡代码 LeetCode 504. 七进制数

wyyang
1个月前
class Solution {
    public String convertToBase7(int num) {
        if (num == 0) return "0"; // 0直接输出0
        StringBuilder sb = new StringBuilder();
        boolean flag = false;
        if (num < 0) {
            flag = true;
            num = -num;  // 负数的话先转换为正数然后求
        }
        while (num > 0) {
            sb.append(num % 7);
            num /= 7;
        }

        if (flag) return "-" + sb.reverse().toString();
        return sb.reverse().toString();
    }
}


活动打卡代码 LeetCode 491. 递增子序列

wyyang
1个月前
class Solution {
    List<List<Integer>> res = new ArrayList<>();

    List<Integer> path = new ArrayList<>();
    // 使用set去重处理,保证相同的数出现不超过两次
    Set<List<Integer>> set = new HashSet<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        // Arrays.sort(nums);
        dfs(nums, 0);

        return res;
    }

    void dfs(int[] nums, int start) {
        if (path.size() >= 2 && path.size() <= nums.length) {
            if (set.add(new ArrayList<>(path))) res.add(new ArrayList<>(path));
        }

        if (path.size() > nums.length) return;

        for (int i = start; i < nums.length; i++) {
            // 重复的不能超过两个。。。所以不能这样判断。
            // if (i > start && nums[i] == nums[i - 1]) continue; 
            if (path.size() >= 1 && nums[i] < path.get(path.size() - 1)) continue;
            path.add(nums[i]);
            dfs(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}