头像

Archer

BJUT


访客:1143

离线:1天前


活动打卡代码 LeetCode 7. 整数反转

Archer
2天前
class Solution {
    public int reverse(int x) {
        int res = 0;
        while (x != 0) {
            int pop = x % 10;
            x = x / 10;
            if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && pop > Integer.MAX_VALUE % 10)) {
                res = 0;
                break;
            } 
            else if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10  && pop < Integer.MIN_VALUE % 10 )) {
                res = 0;
                break;
            }
            res = res * 10 + pop;
        }
        return res;
    }
}



Archer
2天前
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int i = 0, j = 0, k = 0;
        int n = nums1.length + nums2.length;
        int[] num = new int[n];
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] <= nums2[j]) num[k++] = nums1[i++];
            else num[k++] = nums2[j++];
        }
        while (i < nums1.length) num[k++] = nums1[i++];
        while (j < nums2.length) num[k++] = nums2[j++];
        if (n % 2 == 1) return (double) num[n >> 1];
        return (double) (num[n >> 1] + num[(n >> 1) - 1]) / 2.0;
    }
}



Archer
5天前
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int res = 0;
        for (int i = 0, j = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) map.put(c, map.get(c) + 1);
            else map.put(c, 1);

            while (map.get(c) > 1) {
                map.put(s.charAt(j), map.get(s.charAt(j)) - 1);
                j++;
            }
            res = Math.max(res, i - j + 1);
        }
        return res; 
    }
}


活动打卡代码 LeetCode 2. 两数相加

Archer
6天前
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode d = new ListNode(-1);
        ListNode node = d;
        int t = 0;
        while (l1 != null || l2 != null || t != 0) {
            int v1 = l1 != null ? l1.val : 0;
            int v2 = l2 != null ? l2.val : 0;
            int sum = v1 + v2 + t;
            t = sum / 10;
            node.next = new ListNode(sum % 10);
            node = node.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return d.next;
    }
}


活动打卡代码 AcWing 1. 两数之和

Archer
6天前
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] + nums[j] == target) return new int[] {j, i};
            }
        }
        return new int[]{};
    }
}


活动打卡代码 AcWing 847. 图中点的层次

Archer
7天前
import java.io.*;
import java.util.*;
class Main {
    static int n, m, idx;
    static int N = 100010;
    static int[] d = new int[N];
    static int[] e = new int[N], h = new int[N], ne = new int[N];
    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    static void bfs() {
        d[1] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        while (!q.isEmpty()) {
            int t = q.poll();
            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                if (d[j] == -1) {
                    d[j] = d[t] + 1;
                    q.offer(j);
                }
            }
        }
        System.out.println(d[n]);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        Arrays.fill(h, -1);
        Arrays.fill(d, -1);
        while (m-- > 0) {
            s = cin.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            add(a, b);
        }
        bfs();
    }
}



Archer
7天前
import java.io.*;
import java.util.*;
class Main {
    static int n, m, idx;
    static int N = 100010;
    static int[] d = new int[N];
    static int[] e = new int[N], h = new int[N], ne = new int[N];
    static int[] q = new int[N];
    static int hh, tt = -1;
    static void add(int a, int b) {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    static boolean topSort() {
        for (int i = 1; i <= n; i++) {
            if (d[i] == 0) q[++tt] = i;;
        }
        while (hh <= tt) {
            int ver = q[hh++];
            for (int i = h[ver]; i != -1; i = ne[i]) {
                int j = e[i];
                d[j] --;
                if (d[j] == 0) q[++tt] = j;
            }
        }
        return tt == n - 1;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        for (int i = 0; i < N; i++) h[i] = -1;
        while (m-- > 0) {
            s = cin.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            add(a, b);
            d[b]++;
        }
        if (topSort()) {
            for (int i = 0; i < n; i++) {
                System.out.print(q[i] + " ");
            }
        } else {
            System.out.println("-1");
        }
    }
}



Archer
7天前
import java.io.*;
import java.util.*;
class Main {
    static int n, m, k;
    static int INF = 0x3f3f3f3f;
    static int N = 510, M = 10010;
    static int[] dist = new int[N];
    static int[] backup = new int[N];
    static Edge[] edges = new Edge[M];
    static class Edge {
        int a, b, w;
        Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }
    static int bellmanFord() {
        Arrays.fill(dist, INF);
        dist[1] = 0;
        for (int i = 0; i < k; i++) {
            backup = Arrays.copyOf(dist, n + 1);
            for (int j = 0; j < m; j++) {
                int a = edges[j].a, b = edges[j].b, w = edges[j].w;
                dist[b] = Math.min(dist[b], backup[a] + w);
            }
        }
        if (dist[n] > (INF >> 1)) return -1;
        return dist[n];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        k = Integer.parseInt(s[2]);

        for (int i = 0; i < m; i++) {
            s = cin.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            edges[i] = new Edge(a, b, c);
        }
        int t = bellmanFord();
        if (t == -1) System.out.println("impossible");
        else System.out.println(t);

    }
}



Archer
8天前
import java.io.*;
import java.util.*;
class Main {
    static int n, m;
    static int N = 150010;
    static int[] h = new int[N], e = new int[N], ne = new int[N], w = new int[N];
    static int idx, INF = 0x3f3f3f3f;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static class Place implements Comparable<Place> {
        int x, y;
        Place(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo (Place o) {
            return y - o.y;
        }
    }
    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    static int dijkstra() {
        dist[1] = 0;
        PriorityQueue<Place> q = new PriorityQueue<>(n);
        q.offer(new Place(1, 0));
        while (!q.isEmpty()) {
            Place p = q.poll();
            int ver = p.x, distance = p.y;
            if (st[ver]) continue;
            st[ver] = true;
            for (int i = h[ver]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > w[i] + distance) {
                    dist[j] = w[i] + distance;
                    q.offer(new Place(j ,dist[j]));
                }
            }

        }
        if (dist[n] == INF) return -1;
        return dist[n];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        for (int i = 0; i < N; i++) {
            dist[i] = INF;
            h[i] = -1;
        }

        while (m -- > 0) {
            s = cin.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            add(a, b, c);
        }
        System.out.println(dijkstra());
    }
}



Archer
8天前
import java.io.*;
class Main {
    static int n, m;
    static int N = 510;
    static int INF = 0x3f3f3f3f;
    static int[] dist = new int[N];
    static int[][] g = new int[N][N];
    static boolean[] st = new boolean[N];
    static int dijkstra() {
        dist[1] = 0;
        for (int i = 0; i < n; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
            }
            st[t] = true;
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], g[t][j] + dist[t]);
            }

        }
        if (dist[n] == INF) return -1;
        return dist[n];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        for (int i = 0; i < N; i++) {
            dist[i] = INF;
            for (int j = 0; j < N; j++) g[i][j] = INF;
        }
        while (m-- > 0) {
            s = cin.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            g[a][b] =Math.min(g[a][b], c);
        }
        System.out.println(dijkstra());
    }
}