头像

wyyang




离线:30天前


最近来访(19)
用户头像
微微_3
用户头像
努力ing
用户头像
pukka
用户头像
changyou1009
用户头像
rouse
用户头像
Derrick_Xu
用户头像
zombotany
用户头像
Ac_c0mpany丶
用户头像
就玩
用户头像
INnoVation
用户头像
ilovethiscitya
用户头像
qwerxyz


wyyang
2个月前
class Solution {
    List<Integer> res = new ArrayList<>();
    Map<TreeNode, List<TreeNode>> map = new HashMap<>();
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        // 1 先dfs遍历,将有向树转换为无向树。使用邻接表,java中可以用map来存,key : 节点指针,value:相邻的节点列表(父和子)
        // 2 再以target为根遍历,找到所有距离为k的点,注意的是无向树中防止反向遍历,需要判断遍历点的父亲节点是否与当前的相同,若是则忽略。
        dfs1(root);
        // 3 以target为根遍历无向树,第二个参数为父指针,根的父为null
        dfs2(target, null, k);
        return res;
    }
    // 将有向树转换为无向树
    void dfs1(TreeNode root) {
        if (root == null) return;
        if (root.left != null) {
            map.computeIfAbsent(root, elm -> new ArrayList<>()).add(root.left);
            map.computeIfAbsent(root.left, elm -> new ArrayList<>()).add(root);
            dfs1(root.left);
        }
        if (root.right != null) {
            map.computeIfAbsent(root, elm -> new ArrayList<>()).add(root.right);
            map.computeIfAbsent(root.right, elm -> new ArrayList<>()).add(root);
            dfs1(root.right);
        }
    }
    void dfs2(TreeNode root, TreeNode parent, int k) {
        if (k == 0) {
            res.add(root.val);
            return;
        }
        if (!map.containsKey(root)) return;
        for (TreeNode son : map.get(root)) {
            if (son != parent) {
                dfs2(son, root, k - 1);
            }
        }
    }
}



wyyang
2个月前
class Solution {
    int n;
    int[] p;
    int find(int x) {
        if (x != p[x]) p[x] = find(p[x]);
        return p[x];
    }
    public int regionsBySlashes(String[] grid) {
        // 1 这题有很强的技巧性,将每个格子再根据对角线划分为四块用0,1,2,3来标识。
        // 2 并查集求连通区域,关键是找到点和边。点可以看成1分解的每个四小块,边:根据上面的切分则当前点0与四个方向的2连通,1和3连通。
        // 3 若grid[i][j]为\,则0和1,2和3连通。否则为/则0和3,1和2连通
        n = grid.length;
        p = new int[n * n * 4];
        for (int i = 0; i < p.length; i++) p[i] = i;
        // 初始时先将所有内部的合并到一个连通块中。遍历所有格子,四个方向。每个小格子坐标为(i*n+j)*4+k
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                        // 将小格子坐标转换为1维
                        p[find(get(i, j, k))] = find(get(nx, ny, k ^ 2));
                    }                   
                }
                if (grid[i].charAt(j) != '/') {
                    p[find(get(i, j, 0))] = find(get(i, j, 1));
                    p[find(get(i, j, 2))] = find(get(i, j, 3));
                }
                if (grid[i].charAt(j) != '\\') {
                    p[find(get(i, j, 0))] = find(get(i, j, 3));
                    p[find(get(i, j, 2))] = find(get(i, j, 1));
                }                 
            }
        }
        // 返回parent的数量即连通的区域数量
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n * n * 4; i++) set.add(find(i));
        return set.size();
    }
    int get(int x, int y, int k) {
        return (x * n + y) * 4 + k;
    }
}


活动打卡代码 AcWing 3734. 求和

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

public class Main{
    static List<Long> list = new ArrayList<>();
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int l = s.nextInt();
        int r = s.nextInt();
        // 1 可以先用dfs求出所有 满足条件数放到list中。
        // 2 对于 l,r区间,看list中有多少区间落入其中。
        dfs(0, 0L);
        Collections.sort(list);
        long res = 0;
        for (int i = 1; i < list.size(); i++) {
            long a = list.get(i - 1) + 1;
            long b = list.get(i);
            res += list.get(i) * Math.max(0, Math.min(r, b) - Math.max(l, a) + 1);
        }

        System.out.print(res);
    }
    // dfs求只有4,7的所有数,根据题意最大为10位数
    static void dfs(int idx, long n) {
        list.add(n);
        if (idx >= 10) return;
        dfs(idx + 1, n * 10 + 4);
        dfs(idx + 1, n * 10 + 7);
    }
}



wyyang
2个月前
class Solution {
    public int[] diStringMatch(String s) {
        // 思维题,对于0-n 若遇到为I则将最小的值0填入,后面的数填什么都 可以 1-n
        // 若为D则填入n,则后面的数填什么都可以0-n-1。 所以这两种情况可以递归去处理后面的情况。
        // 这里使用l,r两个指针,每次缩小区间即可。
        int j = 0;
        int l = 0; 
        int r = s.length();
        int[] res = new int[r + 1];
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == 'I') res[j++] = l++;
            else res[j++] = r--;
        }
        res[j] = r;
        return res;
    }
}



wyyang
2个月前
class Solution {
    public boolean canReorderDoubled(int[] arr) {
        //1 使用TreeMap计数,这里要将正数和负数区分开,否则-4会排到-2前面。这里使用了技巧将正数和负数分开处理。
        //2 然后从小到大遍历,对x 在map中找是否有2x的数出现过。即可。要注意的是在遍历过程中删除列表中的元素,不能直接for来处理。判断list长度遍历剩余元素。
        return check(arr, 1) && check(arr, -1);
    }
    boolean check(int[] arr, int t) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int a : arr) {
            if (a * t > 0) map.put(a * t, map.getOrDefault(a * t, 0) + 1);
        }
        List<Integer> list = new ArrayList<>(map.keySet());
        while (list.size() > 0) { // 注意:遍历长度
            int a = list.get(0);
            if (!map.containsKey(2 * a) || map.get(2 * a) < map.get(a)) return false; // 若x的出现次数大于2x则返回false
            map.put(2 * a, map.get(2 * a) - map.get(a));
            if (map.get(2 * a) == 0) {
                map.remove(2 * a);
                list.remove(Integer.valueOf(2 * a));  // 列表中同步清除指定的元素,这里注意要用Integer.valueOf否则则删除对应下标索引的元素了。
            }
            map.remove(a);  
            list.remove(Integer.valueOf(a)); // 列表中同步清除指定的元素,这里注意要用Integer.valueOf否则则删除对应下标索引的元素了。
            if (map.isEmpty()) return true;
        }
        return map.isEmpty() ? true : false;
    }
}



wyyang
2个月前
class Solution {
    public int countGoodNumbers(long n) {
        // 1 偶数位能取5个位,奇数位可以取4个位。长度为n的数偶数位有(n+1)/2位,奇数位有n/2位。
        // 2 所以转换为求 5的(n+1)/2次幂 * 4的n/2 次幂的积 对mod取模。。
        // 3 a的b次幂对p取模可以用快速幂模板快速求得,见基础 课
        int mod = 1000000007;
        return (int)(qmi(5, (n + 1) / 2, mod) * qmi(4, n / 2, mod) % mod);
    }
    long qmi(long a, long b, long p) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = res * a % p;
            b >>= 1;
            a = a * a % p;
        }
        return res;
    }
}



wyyang
2个月前
class Solution {
    public int eliminateMaximum(int[] dist, int[] speed) {
        // 计算所有 怪物到达中心所需要的时间
        int[] t = new int[dist.length];
        for (int i = 0; i < dist.length; i++) {
            t[i] = (dist[i] + speed[i] - 1) / speed[i];
        }
        Arrays.sort(t);
        int res = 0;
        int time = 0;
        for (int i = 0; i < dist.length; i++) {
            if (t[i] > time++) res++;
            else break;
        }

        return res;
    }
}



wyyang
2个月前
class Solution {
    public int[] buildArray(int[] nums) {
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res[i] = nums[nums[i]];
        }
        return res;
    }
}



wyyang
2个月前
class Solution {
    Map<Character, Integer> map = new HashMap<>();
    public boolean isAlienSorted(String[] words, String order) {
        for (int i = 0; i < order.length(); i++) map.put(order.charAt(i), i);
        for (int i = 0; i < words.length; i++) {
            String w1 = words[i];
            for (int j = i + 1; j < words.length; j++) {
                String w2 = words[j];
                if (!check(w1, w2)) return false;
            }
        }
        return true;
    }
    boolean check(String w1, String w2) {
        int n = w1.length();
        int m = w2.length();
        for (int i = 0, j = 0; i < n && j < m; ) {
            if (map.get(w1.charAt(i)) < map.get(w2.charAt(j))) return true;
            else if (map.get(w1.charAt(i)) > map.get(w2.charAt(j))) return false;
            i++;
            j++;
        }
        return n <= m;
    }
}


活动打卡代码 LeetCode 934. 最短的桥

wyyang
3个月前
class Solution {
    int n;
    int m;
    int[][] a;
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    LinkedList<List<Integer>> q = new LinkedList<>();
    Map<List<Integer>, Integer> dist = new HashMap<>();

    public int shortestBridge(int[][] grid) {
        // 1、多源bfs求最短路问题,a岛可以看作源,b岛看作目的,从a岛中可以有多个点到达b岛,这类问题可以将a中所有点(x,y)先加到队列中(dfs)。
        // 2、然后出队,并更新dist值(取最小的),直到到达b岛中任一一个节点,返回最短的路径即可(变换的0的数目为dist - 1)。
        // 3 dist使用map, key:坐标list, value到该坐标的距离。
        n = grid.length;
        m = grid[0].length;
        a = grid;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    dfs(i, j);
                    return bfs();
                }
            }
        }
        return -1;
    }
    void dfs(int x, int y) {
        a[x][y] = 0;
        q.offer(Arrays.asList(x, y));
        dist.put(Arrays.asList(x, y), 0);
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && a[nx][ny] == 1) dfs(nx, ny);
        }
    }
    int bfs() {
        while (q.size() > 0) {
            List<Integer> list = q.poll();
            int x = list.get(0);
            int y = list.get(1);
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !dist.containsKey(Arrays.asList(nx, ny))) {
                    dist.put(Arrays.asList(nx, ny), dist.get(list) + 1);
                    q.offer(Arrays.asList(nx, ny));
                    if (a[nx][ny] == 1) return dist.get(Arrays.asList(nx, ny)) - 1;
                }
            }
        }
        return -1;
    }
}