thích thì thoát loop sớm cũng dc mà, nhưng mà bài này n bé cứ cho chạy hết loop cũng chả sao, có khi còn nhanh hơn mỗi lần + 1 phép tính kiểm tra điều kiệnXem tệp đính kèm 2670259
Xem tệp đính kèm 2670256
cho e hoir, tại sao ko return luôn n=0 đi ta, tại =0 là thỏa điều kiện đặt được n vào trong flowerbed rồi mà. Câu easy gì mà khó vãi
bafi này em coi của ông neetcode hướng giải thôi chứ em có giải ra đâu thím. K hiểu return n <=0 làm sao nó biết được true hay false ta ? theo e hiểu là n=0 là thỏa đk cần rồi chứ đâu cần, hay là ổng tính kiểu edge case tức trong flowerbed có nhiều chỗ đặt hơn n ta ?
thì chư cũng đã nói như ở trên r. n==0 thoát loop sớm cũng dc thôi,
e làm ko ra mới lên hỏi đó thím, thấy bài easy mà 30p k ra thôi coi giải rồi giải lại cho rồi.thì chư cũng đã nói như ở trên r. n==0 thoát loop sớm cũng dc thôi,
sao fen ko tự modify code chạy thử đi mà lại mang lên hỏi.submit nếu mà có wrong answer là thấy edge case liền.
xài chat gpt với coi solution có khácgì nhau đâu nhỉfen yếu quá như v thì xem kênh này học cách khứa lày cách đặt câu hỏi cho chat gpt để hỗ trợ nhé.
còn mình thì mình ko xài chat gpt đâu. mấy đại ka phải tin ethề chưa bao h xài
class Solution {
public:
bool isSubPath(ListNode* head, TreeNode* root) {
if (root == nullptr) return false;
return isFullPath(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);
}
bool isFullPath(ListNode* head, TreeNode* root) {
if (head == nullptr) return true;
if (root == nullptr || head->val != root->val) return false;
return isFullPath(head->next, root->left) || isFullPath(head->next, root->right);
}
};
public class Solution
{
public bool IsSubPath(ListNode head, TreeNode root)
{
if (root == null)
{
return false;
}
return DFS(head, root) || IsSubPath(head, root.left) || IsSubPath(head, root.right);
}
private bool DFS(ListNode listCurrent, TreeNode node)
{
if (listCurrent == null)
{
return true;
}
if (node == null)
{
return false;
}
if (listCurrent.val == node.val)
{
return DFS(listCurrent.next, node.left) || DFS(listCurrent.next, node.right);
}
return false;
}
}Bài này dfs + memoi implement thẳng tắp, medium thôi chứ hard hơi ảo.dfs thì không cần care về indegree, có dùng stack nhưng thay stack bằng O(1) được
Thím ăn thử cơm này thử khô không.
Sau này đừng xúi rau hẹ khác chui vào contest nữa nhé
Tuần này có nên làm quả contest nữa không ta, lỡ xuống tiếp 1300 chắc có nước bỏ nick voz cho đỡ nhục
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def isSubPath(self, head, root):
"""
:type head: ListNode
:type root: TreeNode
:rtype: bool
"""
self.res = False
def search(r, h):
if not h:
return True
if not r:
return False
if r.val == h.val:
return search(r.left, h.next) or search(r.right, h.next)
return False
def inOrder(r):
if self.res:
return
if not r:
return
if r.val == head.val and search(r, head):
self.res = True
return
inOrder(r.left)
inOrder(r.right)
inOrder(root)
return self.res
class Solution {
List<TreeNode> list;
ListNode head;
boolean res;
public boolean isSubPath(ListNode head, TreeNode root) {
this.list = new ArrayList<>();
this.head = head;
this.res = false;
traverseTree(root);
return res;
}
private boolean checkSubPath(TreeNode node, ListNode head) {
if (head == null) {
return true;
}
if (node == null) {
return false;
}
if (node.val != head.val) {
return false;
}
return checkSubPath(node.left, head.next) || checkSubPath(node.right, head.next);
}
private void traverseTree(TreeNode root) {
if (res) {
return;
}
if (root == null) {
return;
}
if (head.val == root.val) {
res = checkSubPath(root, head);
if (res) {
return;
}
}
traverseTree(root.left);
traverseTree(root.right);
}
}
var isSubPath = function (head, root) {
const B = 1995, M = 1e9 + 7;
let H = 0, n = 0;
const Bpow = n => {
const memo = (Bpow._memo ??= [1]);
return memo[n] ??= Bpow(n - 1) * B % M;
};
for (let h = head; h !== null; h = h.next) {
H = H * B + h.val;
H %= M;
n++;
}
function* traverse(node, stack, h) {
stack.push(node.val);
h = (h * B + node.val) % M;
if (stack.length > n) {
h = (h - Bpow(n) * stack[stack.length - n - 1] + M * 42) % M;
}
if (stack.length >= n) {
yield h;
}
for (const child of [node.left, node.right].filter(Boolean)) {
yield* traverse(child, stack, h);
}
stack.pop();
}
for (const hash of traverse(root, [], 0)) {
if (hash === H) {
return true;
}
}
return false;
};
Tks thím chỉ cách làm, em mới luyện nên thấy nó khó
em cũng mới bác ơi, ý e là xếp nó vào hard thì hơi sai chứ nhiều bài medium khó lòi kèn ra mà bài kia để hard ^^Tks thím chỉ cách làm, em mới luyện nên thấy nó khó
/**
function isSubPath(head: ListNode | null, root: TreeNode | null): boolean {
if (head.val == root.val && dfs(head, root)) {
return true
}
const left = root.left ? isSubPath(head, root.left) : false;
const right = root.right ? isSubPath(head, root.right) : false;
return left || right;
};
function dfs(head: ListNode | null, root: TreeNode | null) {
if (root.val !== head.val) return false;
if (!head.next) {
return true;
}
const left = root.left ? dfs(head.next, root.left) : false;
const right = root.right ? dfs(head.next, root.right) : false;
return left || right
}ko biết nhưng mà bài tập sql free của leetcode cũng có 50 câu, mức độ khó cũng ko ổn lắm, sql qua hackerrank làm khó, đa dạng hơn,
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isSubPath(ListNode head, TreeNode root) {
if (root == null) {
return false;
}
boolean ans = dfs(head, root);
ans = ans || isSubPath(head, root.left) || isSubPath(head, root.right);
return ans;
}
private boolean dfs(ListNode head, TreeNode root) {
if (head == null) return true;
if (root == null) return false;
boolean ans = false;
if (root.val == head.val) {
ans = dfs(head.next, root.left) || dfs(head.next, root.right);
}
return ans;
}
}
use std::collections::HashSet;
impl Solution {
pub fn modified_list(nums: Vec<i32>, mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let nums: HashSet<i32> = nums.into_iter().collect();
let mut sentinel = Some(Box::new(ListNode::new(0)));
let mut tail = sentinel.as_mut();
while let Some(mut node) = head {
head = node.next.take();
if nums.contains(&node.val) {
continue;
}
tail =
tail.map(|mut tail| {
tail.next = Some(node);
tail
});
tail = tail.and_then(|tail| tail.next.as_mut());
}
sentinel.and_then(|mut sen| sen.next.take())
}
}use std::rc::Rc;
use std::cell::RefCell;
type LNode = Box<ListNode>;
type TNode = Rc<RefCell<TreeNode>>;
impl Solution {
pub fn is_sub_path(head: Option<LNode>, root: Option<TNode>) -> bool {
fn check_subtree(head: Option<&LNode>, tree_node: Option<TNode>) -> bool {
if head.is_some() && tree_node.is_none() || head.is_none() && tree_node.is_some() {
return false;
}
if dfs(head, tree_node.as_ref().map(|tree_node| tree_node.clone())) {
return true;
}
let tree_node = tree_node.unwrap();
let tree_node = tree_node.borrow();
check_subtree(head, tree_node.left.clone()) || check_subtree(head, tree_node.right.clone())
}
fn dfs(list_node: Option<&LNode>, tree_node: Option<TNode>) -> bool {
match (list_node, tree_node) {
(None, _) => true,
(Some(_), None) => false,
(Some(list_node), Some(tree_node)) => {
let list_node_next = list_node.next.as_ref();
let tree_node = tree_node.borrow();
if list_node.val != tree_node.val {
return false;
}
dfs(list_node_next, tree_node.left.clone()) || dfs(list_node_next, tree_node.right.clone())
}
}
}
check_subtree(head.as_ref(), root)
}
}
