头像

秀策




离线:19小时前


最近来访(102)
用户头像
csgirl2021
用户头像
codeboy2006
用户头像
江浔浔
用户头像
奔跑的小怪兽
用户头像
在南极找不到南
用户头像
yxc
用户头像
_6
用户头像
xinwang
用户头像
小镇做梦家
用户头像
ikaros_
用户头像
可爱林林林
用户头像
OnjoujiToki
用户头像
馨意
用户头像
皮皮闪
用户头像
itdef
用户头像
小金鑫呀
用户头像
Lims
用户头像
ky2074
用户头像
zhuzuojun
用户头像
rushhhhh

活动打卡代码 AcWing 2013. 三条线

秀策
19小时前
# java
import java.util.*;


public class Main {

    static int N = 50010;
    static int[][] q = new int[N][2];
    static int n;
    static HashSet<Integer> row = new HashSet<>();
    static HashSet<Integer> col = new HashSet<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i = 0; i < n; i ++){
            q[i][0] = sc.nextInt();
            q[i][1] = sc.nextInt();
        }

        System.out.println(dfs(0, 0) ? 1: 0);
    }


    public static boolean dfs(int u, int cnt){
        if (cnt > 3) return false;
        if (u == n) return true;

        if (row.contains(q[u][1]) || col.contains(q[u][0])) return dfs(u + 1, cnt);

        row.add(q[u][1]);
        if (dfs(u + 1, cnt + 1)) return true;
        row.remove(q[u][1]);

        col.add(q[u][0]);
        if (dfs(u + 1, cnt + 1)) return true;
        col.remove(q[u][0]);

        return false;
    }

}


# python


# Segmentation Fault   

import sys
sys.setrecursionlimit(10**8)
row, col = set(), set()
n = int(input())


def dfs(u, cnt):
    if cnt > 3:
        return 0

    if u == n:
        return 1

    if q[u][1] in row or q[u][0] in col:
        return dfs(u + 1, cnt)

    row.add(q[u][1])
    if dfs(u + 1, cnt + 1):
        return 1
    row.remove(q[u][1])

    col.add(q[u][0])
    if dfs(u + 1, cnt + 1):
        return 1
    col.remove(q[u][0])

    return 0


def main():
    global q
    q = []
    for _ in range(n):
        q.append(list(map(int, input().split())))

    print(dfs(0, 0))

main()




新鲜事 原文

秀策
3天前
AcWing《Web应用课》拼团优惠!https://www.acwing.com/activity/content/introduction/1150/group_buy/68316/


新鲜事 原文

秀策
27天前
AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/65255/


新鲜事 原文

秀策
27天前
AcWing《春季每日一题2022》拼团优惠!https://www.acwing.com/activity/content/introduction/1238/group_buy/65240/



秀策
1个月前
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        P, Q = 131, 159
        MOD = 1e7 + 7
        T = -1
        res = False

        def dfs(root):
            nonlocal res
            if not root:
                return 12345
            left = dfs(root.left)
            right = dfs(root.right)
            x = root.val % MOD
            if left == T or right == T:
                res = True
            return (x + left * P % MOD + right * Q) % MOD
        T = -1
        T = dfs(subRoot)
        if T == dfs(root):
            res = True
        return res


活动打卡代码 LeetCode 785. 判断二分图

秀策
1个月前
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        def dfs(u, c):
            color[u] = c
            for v in graph[u]:
                if color[v] != -1:
                    if color[v] == c:
                        return False
                elif not dfs(v, c ^ 1):
                    return False
            return True

        n = len(graph)
        color = [-1] * n
        for i in range(n):
            if color[i] == -1:
                if not dfs(i, 0):
                    return False
        return True


活动打卡代码 LeetCode 463. 岛屿的周长

秀策
1个月前
class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        res = 0
        dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
        for i in range(n):
            for j in range(m):
                if grid[i][j]:
                    for k in range(4):
                        a, b = i + dx[k], j + dy[k]
                        if not (0 <= a < n and 0 <= b < m):
                            res += 1
                        elif grid[a][b] == 0:
                            res += 1
        return res


活动打卡代码 LeetCode 896. 单调数列

秀策
1个月前
class Solution:
    def isMonotonic(self, nums: List[int]) -> bool:
        dec = True
        inc = True
        for i in range(1, len(nums)):
            if nums[i - 1] < nums[i]:
                dec = False
            if nums[i - 1] > nums[i]:
                inc = False
        return dec or inc



秀策
1个月前
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
        def dfs(root):
            if not root:
                return None, 0
            left, left_depth = dfs(root.left)
            right, right_depth = dfs(root.right)
            if left_depth == right_depth:
                return root, left_depth + 1
            if left_depth > right_depth:
                return left, left_depth + 1
            return right, right_depth + 1

        return dfs(root)[0]



秀策
1个月前
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        # n: number of nodes
        # p: index of last node
        n = p = 0
        def dfs(root, k):
            nonlocal n, p
            if not root:
                return True
            if n > 100:
                return False
            n += 1
            p = max(p, k)
            return dfs(root.left, k * 2) and dfs(root.right, k * 2 + 1)

        if not dfs(root, 1):
            return False
        return n == p