头像

后海不是海




离线:1小时前


最近来访(76)
用户头像
practice
用户头像
edgdcgxgbx
用户头像
凌乱之风
用户头像
Misaka_9982
用户头像
不到130不改名
用户头像
喵喵喵喵子
用户头像
735217535@qq.com
用户头像
翻滚的小浪花
用户头像
skydegree
用户头像
lxxxl
用户头像
Pipipapi
用户头像
tommy_
用户头像
琅琊
用户头像
心向远方
用户头像
时光_61
用户头像
RyanMoriarty
用户头像
anji
用户头像
春うらら
用户头像
noobcode091
用户头像
LHHHHHH

活动打卡代码 LeetCode 5909. 并行课程 III

Java 代码

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        Arrays.fill(h, 1, n + 1, -1);
        for (int[] item : relations) {
            int a = item[0], b = item[1];
            add(a, b);
            d[b]++;
        }

        int hh = 0, tt = -1;
        for (int i = 1; i <= n; i++)
            if (d[i] == 0) {
                q[++tt] = i;
                dp[i] = 0;
            }

        while (hh <= tt) {
            int t = q[hh++];

            for (int i = h[t]; i != -1; i = ne[i]) {
                int j = e[i];
                d[j]--;
                if (d[j] == 0) q[++tt] = j;

                dp[j] = Math.max(dp[j], dp[t] + time[t - 1]);
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dp[i] + time[i - 1]);
        }
        return ans;
    }

    private void add(int u, int v) {
        e[idx] = v; ne[idx] = h[u]; h[u] = idx++;
    }

    private final int N = (int) 5e4 + 10;

    // 数组模拟邻接表
    private int[] e = new int[N];
    private int[] ne = new int[N];
    private int[] h = new int[N];
    private int idx = 0;

    private int[] q = new int[N];   // 队列
    private int[] d = new int[N];   // d[i]表示编号为i的课程的入度

    private int[] dp = new int[N];  // 编号为i的课程最早开始时间(入度为0时可以开始)
}

Preference




Java 代码

class Solution {
    public int countHighestScoreNodes(int[] parents) {
        n = parents.length; cnt = 0; ans = 0;
        siz = new int[n];

        for (int i = 0; i < n; i++) {
            int p = parents[i];
            if (m.containsKey(p)) {
                List<Integer> t = m.get(p);
                t.add(i);
                m.put(p, t);
            } else {
                List<Integer> t = new ArrayList<>();
                t.add(i);
                m.put(p, t);
            }
        }

        dfs(0);
        return cnt;
    }

    private void dfs(int x) {
        long cur = 1L;  // 由于是二叉树所以节点x的分数最大约为 (1e5/3)^3,在 64 位整数范围内
        siz[x] = 1;

        if (m.containsKey(x)) {
            for (int v : m.get(x)) {
                dfs(v);
                siz[x] += siz[v];
                cur *= siz[v];  //  编号为x节点的两个子树(若存在)大小累积
            }
        }
        if (siz[x] < n) cur *= n - siz[x];  // 累积除去以x为根的子树

        if (cur > ans) {
            ans = cur;
            cnt = 0;
        }
        if (cur == ans) cnt++;
    }

    private int n, cnt;
    private long ans;   
    private int[] siz;
    private Map<Integer, List<Integer>> m = new HashMap<>();
}

Preference




class Solution {
    public int nextBeautifulNumber(int n) {
        while (true) {
            n++;
            if (check(n)) break;
        }

        return n;
    }

    private boolean check(int x) {
        Arrays.fill(cnt, 0);
        while (x > 0) {
            cnt[x % 10]++;
            x /= 10;
        }
        for (int i = 0; i < 10; i++)
            if (cnt[i] != 0 && cnt[i] != i)
                return false;

        return true;
    }

    private int[] cnt = new int[10];
}



class Solution {
    public int countValidWords(String sentence) {
        String[] strArray = sentence.split("\\s+");

        int res = 0;
        for (String s : strArray) {
            char[] ch = s.toCharArray();

            int cnt = 0;   // 统计 '-' 的个数
            boolean valid = true;
            for (int i = 0; i < ch.length; i++) {
                char c = ch[i];
                if ((i != ch.length - 1 && (c == '!' || c == '.' || c == ',')) || Character.isDigit(c) 
                    || ((i == 0 || i == ch.length - 1) && c == '-') || (c == '-' && (!Character.isAlphabetic(ch[i - 1]) || !Character.isAlphabetic(ch[i + 1])))) {
                    valid = false;
                    break;
                }
                if (c == '-') cnt++;
            }

            if (ch.length > 0 && valid && cnt < 2) {
                res++;
            }
        } 

        return res;
    }
}


活动打卡代码 AcWing 760. 字符串长度

s = str(input())
print(len(s))


活动打卡代码 AcWing 660. 零食

dic = {1 : 4.00, 2 : 4.50, 3 : 5.00, 4 : 2.00, 5 : 1.50}

x, y = [int(i) for i in input().split(' ')]
# 或者这样写
# x, y = map(int, input().split(' '))

print("Total: R$", "%.2f" % (dic[x] * y))

Preference



活动打卡代码 AcWing 670. 动物

a = str(input())
b = str(input())
c = str(input())

if a == "vertebrado":
    if b == "ave":
        if c == "carnivoro":
            print("aguia")
        else:
            print("pomba")
    else:
        if c == "onivoro":
            print("homem")
        else:
            print("vaca")
else:
    if b == "inseto":
        if c == "hematofago":
            print("pulga")
        else:
            print("lagarta")
    else:
        if c == "hematofago":
            print("sanguessuga")
        else:
            print("minhoca")


活动打卡代码 AcWing 665. 倍数

# 一行一个数字的读取方式
# a = int(input())
# b = int(input())

# 一行多个数字的读取方式(数字间空格分割)
a, b = map(int, input().split(' '))
# 或者这样写
# a, b = [int(i) for i in input().split(' ')]

if a < b:
    a, b = b, a

if a % b == 0:
    print("Sao Multiplos")
else:
    print("Nao sao Multiplos")

Preference



活动打卡代码 AcWing 608. 差

a = int(input())
b = int(input())
c = int(input())
d = int(input())
x = a * b - c * d
print("DIFERENCA =", x)     # print函数在字符串和变量输出之间自动加上了空格



class Solution {
    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
        int n1 = nums1.length, n2 = nums2.length;

        // cnt10表示nums1负数个数;cnt11表示nums1正数个数;zero0表示nums1零个数
        // 其余同理
        int cnt10 = 0, cnt11 = 0, cnt20 = 0, cnt21 = 0, zero0 = 0, zero1 = 0;

        int i = lastPos(nums1, -1), j = lastPos(nums1, 0);
        if (i == -1) cnt10 = 0;
        else cnt10 = i + 1;
        if (j == -1) zero0 = 0;
        else zero0 = j + 1 - cnt10;
        cnt11 = n1 - cnt10 - zero0;

        int m = lastPos(nums2, -1), n = lastPos(nums2, 0);
        if (m == -1) cnt20 = 0;
        else cnt20 = m + 1;
        if (n == -1) zero1 = 0;
        else zero1 = n + 1 - cnt20;
        cnt21 = n2 - cnt20 - zero1;

        long neg = 1L * cnt10 * cnt21 + 1L * cnt11 * cnt20;
        long pos = 1L * cnt10 * cnt20 + 1L * cnt11 * cnt21;
        long zero = 1L * n1 * n2 - neg - pos;
        // System.out.println(neg + " " + zero + " " + pos);
        long res = 0;
        if (k > neg) {
            k -= neg;
            if (k > zero) {     // 答案是正数,二分答案
                k -= zero;

                long l = 1, r = (long) 1e10;
                while (l <= r) {    // 二分找出大于等于k的第一个mid
                    long mid = l + (r - l >> 1);
                    if (check(nums1, j + 1, n1 - 1, nums2, n + 1, n2 - 1, mid) + check(nums1, 0, i, nums2, 0, m, mid) >= k) {
                        if (mid == 1 || check(nums1, j + 1, n1 - 1, nums2, n + 1, n2 - 1, mid - 1) + check(nums1, 0, i, nums2, 0, m, mid - 1) < k) {
                            return mid;
                        } else r = mid - 1;
                    } else l = mid + 1;
                }
            } else return 0L;
        } else {    // 答案是负数,二分答案
            int p1 = firstPos(nums1, 1), p2 = firstPos(nums2, 1);
            // System.out.println(i + " " + p1 + " " + m + " " + p2);

            long l = (long) -1e10, r = -1;
            while (l <= r) {    // 二分找出大于等于k的第一个mid
                long mid = l + (r - l >> 1);

                if (check(nums1, 0, i, nums2, p2, n2 - 1, mid) + check(nums1, p1, n1 - 1, nums2, 0, m, mid) >= k) {
                    if (mid == (long) -1e10 || check(nums1, 0, i, nums2, p2, n2 - 1, mid - 1) + check(nums1, p1, n1 - 1, nums2, 0, m, mid - 1) < k) {
                        return mid;
                    } else r = mid - 1;
                } else l = mid + 1;
            }
        }

        return -1;  // 题目保证有解,这句不会执行
    }

    // 二分查找nums数组中最后一个(最右)小于等于x的元素,返回其下标
    private int lastPos(int[] nums, int x) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = l + (r - l >> 1);
            if (nums[mid] <= x) {
                if (mid == n - 1 || nums[mid + 1] > x) {
                    return mid;
                } else l = mid + 1;
            } else r = mid - 1;
        }

        return -1;  // 返回-1表示nums数组元素均大于x
    }

    // 二分查找nums数组中第一个(最左)大于等于x的元素,返回其下标
    private int firstPos(int[] nums, int x) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = l + (r - l >> 1);
            if (nums[mid] >= x) {
                if (mid == 0 || nums[mid - 1] < x) {
                    return mid;
                } else r = mid - 1;
            } else l = mid + 1;
        }

        return -1;  // 返回-1表示nums数组元素均大于x
    }

    // 返回相乘后小于等于mid的元素个数
    private long check(int[] nums1, int s1, int e1, int[] nums2, int s2, int e2, long mid) {
        long ret = 0L;

        if (s1 != -1 && e1 != -1 && s2 != -1 && e2 != -1) {
            for (int k = s1; k <= e1; k++) {
                long val = mid / nums1[k];

                if (mid > 0) {
                    if (nums1[k] > 0) {
                        int l = s2, r = e2;
                        while (l <= r) {    // 二分找到小于等于val最右边下标
                            int t = l + (r - l >> 1);
                            if (nums2[t] <= val) {
                                if (t == e2 || nums2[t + 1] > val) {
                                    ret += t - s2 + 1L;
                                    break;
                                } else l = t + 1;
                            } else r = t - 1;
                        }
                    }

                    if (nums1[k] < 0) {
                        int l = s2, r = e2;
                        while (l <= r) {    // 二分找到大于等于val最左边下标
                            int t = l + (r - l >> 1);
                            if (nums2[t] >= val) {
                                if (t == s2 || nums2[t - 1] < val) {
                                    ret += e2 - t + 1L;
                                    break;
                                } else r = t - 1;
                            } else l = t + 1;
                        }
                    }
                }

                if (mid < 0) {
                    if (nums1[k] > 0) {
                        if (1L * nums1[k] * val != mid) val--;

                        int l = s2, r = e2;
                        while (l <= r) {    // 二分找到小于等于val最右边下标
                            int t = l + (r - l >> 1);
                            if (nums2[t] <= val) {
                                if (t == e2 || nums2[t + 1] > val) {
                                    ret += t - s2 + 1L;
                                    break;
                                } else l = t + 1;
                            } else r = t - 1;
                        }
                    }

                    if (nums1[k] < 0) {
                        if (1L * nums1[k] * val != mid) val++;

                        int l = s2, r = e2;
                        while (l <= r) {    // 二分找到大于等于val最左边下标
                            int t = l + (r - l >> 1);
                            if (nums2[t] >= val) {
                                if (t == s2 || nums2[t - 1] < val) {
                                    ret += e2 - t + 1L;
                                    break;
                                } else r = t - 1;
                            } else l = t + 1;
                        }
                    }
                }
            }
        }

        return ret;
    }
}

唯一需要注意的一点就是二分的答案不能整除时(mid != 当前两个数组元素的乘积),取整方向要根据题意变化。

Preference