thảo luận Leetcode mỗi ngày

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
        first_i = -1
        max_dis = 0
        min_dis = float('inf')
        last_i = -1
        i = 1
        while head.next and head.next.next:
            if (head.next.val > head.val and head.next.val > head.next.next.val) or (head.next.val < head.val  and head.next.val < head.next.next.val):
                if first_i == -1:
                     first_i = i
                else:
                    min_dis = min(i - last_i, min_dis)
                last_i = i

            i += 1
            head = head.next
        max_dis = last_i - first_i

        if first_i == last_i:
            return [-1, -1]
        return [min_dis, max_dis

public class Solution
{
    public int[] NodesBetweenCriticalPoints(ListNode head)
    {
        ListNode prev = head;
        ListNode pointer = head.next;
        int minDist = int.MaxValue;
        int maxDist = 0;
        int leftMost = int.MaxValue;
        int rightMost = int.MaxValue;

        int index = 1;
        while (pointer.next != null)
        {
            if (IsCriticalNode(prev, pointer))
            {
                if (rightMost != int.MaxValue)
                {
                    minDist = Math.Min(index - rightMost, minDist);
                }
                rightMost = index;

                if (leftMost == int.MaxValue)
                {
                    leftMost = index;
                }
                maxDist = Math.Max(index - leftMost, maxDist);
            }
            index++;
            prev = pointer;
            pointer = pointer.next;
        }

        if (minDist == int.MaxValue)
        {
            return [-1, -1];
        }
        return [minDist, maxDist];
    }

    private bool IsCriticalNode(ListNode prev, ListNode current)
    {
        return prev.val < current.val && current.next.val < current.val
            || current.val < prev.val && current.val < current.next.val;
    }
}

// Problem: https://leetcode.com/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/
class Solution {
    func nodesBetweenCriticalPoints(_ head: ListNode?) -> [Int] {
        var current = head
        var index = 0
        var minDis = Int.max
       
        var first = -1
        var last = -1
        while current != nil && current?.next != nil && current?.next?.next != nil {
            let left = current?.val ?? 0
            let mid = current?.next?.val ?? 0
            let right = current?.next?.next?.val ?? 0
           
            // find the critical point
            if (mid > left && mid > right) || (mid < left && mid < right) {
                if first == -1 {
                    first = index
                    last = index
                } else {
                    minDis = min(minDis, index - last)
                    last = index
                }
            }
            index += 1
            current = current?.next
        }
       
        return first == last ? [-1, -1] : [minDis, last - first]
    }
}

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @return Integer[]
     */
    function nodesBetweenCriticalPoints($head) {
        if (!$head->next->next) return [-1, -1];

        $critPoints = [];
        $min = PHP_INT_MAX;
        $cur = $head->next;
        $index = 1;
        while ($cur->next) {
            if ($head->val > $cur->val && $cur->val < $cur->next->val || $head->val < $cur->val && $cur->val > $cur->next->val) {
                $critPoints[] = $index;

                if (count($critPoints) > 1) {
                    $mod = $critPoints[count($critPoints)-1] - $critPoints[count($critPoints)-2];
                    $min = ($mod < $min) ? $mod : $min;
                }
            }

            $index++;
            $head = $cur;
            $cur = $cur->next;
        }

        if (count($critPoints) < 2) return [-1, -1];

        $max = $critPoints[count($critPoints)-1] - $critPoints[0];
        return [$min, $max];
    }
}

function nodesBetweenCriticalPoints(head: ListNode | null): number[] {
    let cur = head, first = -1, idx = 0, min = Infinity, max = -1, prev = -1;
    if (!cur) return [-1, -1];
    while (cur && cur.next && cur.next.next) {
        const next1 = cur.next;
        const next2 = cur.next.next;
        idx++;
        if ((next1.val < cur.val && next1.val < next2.val) || (next1.val > cur.val && next1.val > next2.val)) {
            if (first < 0) first = idx, prev = idx;
            else {
                min = Math.min(min, idx - prev)
                prev = idx;
            }
        }
        cur = next1;
    }
    if (prev === first) return [-1, -1];
    return [min, prev - first]
};

class Solution {
    public int[] nodesBetweenCriticalPoints(ListNode head) {
        int firstPoint = -1;
        int lastPoint = -1;
        int[] res= new int[2];
        Arrays.fill(res,-1);
        ListNode node = head.next;
        ListNode preNode = head;
        int index = 1;
        while (node != null) {
            if (node.next != null) {
                if ((node.val > preNode.val && node.val > node.next.val) ||
                    (node.val < preNode.val && node.val < node.next.val)) {
                    if (firstPoint == -1) {
                        firstPoint = index;
                    }
                    if(lastPoint != -1){
                        if(res[0]==-1){
                            res[0]= index - firstPoint;
                        }
                        res[0] = Math.min(res[0],index- lastPoint);
                    }
                    lastPoint = index;
                }
            }
            preNode = node;
            node = node.next;
            index++;
        }
        if(lastPoint != firstPoint){
            res[1]= lastPoint - firstPoint;
        }
        return res;
    }
}

impl Solution {
    pub fn nodes_between_critical_points(head: Option<Box<ListNode>>) -> Vec<i32> {
        let mut prev_node = unsafe { head.as_ref().unwrap_unchecked() };
        let mut node = unsafe { prev_node.next.as_ref().unwrap_unchecked() };

        let (mut first_cp, mut prev_cp, mut current_cp) = (None, None, None);
        let mut min_dist = i32::MAX;

        let mut i = 0;
        while let Some(ref a_node) = node.next {
            let inc = prev_node.val <= node.val && node.val <= a_node.val;
            let dec = prev_node.val >= node.val && node.val >= a_node.val;
            if !inc && !dec {
                prev_cp = current_cp;
                current_cp = Some(i);
                match (prev_cp, current_cp) {
                    (Some(prev), Some(curr)) => {
                        min_dist = i32::min(min_dist, curr - prev);
                    }
                    _ => {}
                }

                if first_cp.is_none() {
                    first_cp = current_cp;
                }
            }

            i += 1;
            prev_node = node;
            node = a_node;
        }

        match (prev_cp, current_cp) {
            (Some(_), Some(curr)) => {
                let first = unsafe { first_cp.unwrap_unchecked() };
                vec![min_dist, curr - first]
            }

            _ => vec![-1, -1],
        }
    }
}

impl Solution {
    pub fn nodes_between_critical_points(head: Option<Box<ListNode>>) -> Vec<i32> {
        let (mut prev, mut next) = (None, head);
        let (mut first_crit, mut last_crit) = (None, None);
        let (mut min_dist, mut max_dist, mut i): (Option<usize>, Option<usize>, usize) = (None, None, 0);

        while let Some(mut node) = next {
            next = node.next.take();

            prev.as_ref().zip(next.as_ref()).map(|(&prev_val, next_node)| {
                if (next_node.val < node.val && node.val > prev_val) || (next_node.val > node.val && node.val < prev_val) {
                    let new_dist = last_crit.as_ref().map(|&k| i - k);
                    min_dist = min_dist.map_or(new_dist, |dist| new_dist.map(|other_dist| dist.min(other_dist)));

                    first_crit = first_crit.map_or(Some(i), |k| Some(k));
                    last_crit = Some(i);
                }
            });

            prev = Some(node.val);
            i += 1;
        }

        let max_dist =
            last_crit.zip(first_crit).
                map(|(i, j)| {
                    if i != j {
                        (i - j) as i32
                    } else {
                        -1
                    }
                }).
                unwrap_or(-1);

        let min_dist = min_dist.map(|dist| dist as i32).unwrap_or(-1);

        vec![min_dist, max_dist]
    }
}

class Solution {
    func nodesBetweenCriticalPoints(_ head: ListNode?) -> [Int] {
        guard let head else { return [-1, -1] }

        var minDistance = -1
        var maxDistance = -1

        var firstPos = 0
        var prePos = 0
        var currPos = 1

        func dfs(node1: ListNode?, node2: ListNode?, node3: ListNode?) {
            guard let node1, let node2, let node3 else { return }
            currPos += 1
            let isDistinct = (node2.val > node1.val && node2.val > node3.val) ||
                            (node2.val < node1.val && node2.val < node3.val)
            if isDistinct {
                if firstPos != 0 {
                    minDistance = minDistance != -1 ? min(minDistance, currPos - prePos) : currPos - prePos
                    maxDistance = max(maxDistance, currPos - firstPos)
                    prePos = currPos
                } else {
                    firstPos = currPos
                    prePos = currPos
                }
            }

            dfs(node1: node2, node2: node3, node3: node3.next)
        }

        dfs(node1: head, node2: head.next, node3: head.next?.next)

        return [minDistance, maxDistance]
    }
}

var nodesBetweenCriticalPoints = function(head) {
    let min = Infinity;
    let max = -1;
    let node = head;
    let prev = null;
    let minimaIndex = -1;
    let maximaIndex = -1;
    let i = 1;
    while (node && node.next) {
        if (prev) {
            if ((node.val > prev.val && node.val > node.next.val) ||
                (node.val < prev.val && node.val < node.next.val)) {
                if (maximaIndex != -1) {
                    max = Math.max(max, i - maximaIndex);
                } else {
                    maximaIndex = i;
                }

                if (minimaIndex != -1) {
                    min = Math.min(min, i - minimaIndex);
                }

                minimaIndex = i;
            }
        }

        prev = node;
        node = node.next;
        i++;
    }

    if (min == Infinity) min = -1;

    return [min, max];
};

var nodesBetweenCriticalPoints = function (head) {
  let ids = [], id = 0
  let one = head, two = one.next, three = two.next
  while (three) {
    if (two.val > one.val && two.val > three.val) {
      ids.push(id)
    } else if (two.val < one.val && two.val < three.val) {
      ids.push(id)
    }
    id++
    one = one.next
    two = one.next
    three = two.next
  }
  if (ids.length < 2) return [-1, -1]
  let max = ids[ids.length - 1] - ids[0], min = Infinity
  for (let i = 1; i < ids.length; i++) {
    min = Math.min(min, ids[i] - [ids[i - 1]])
  }
  return [min, max]
};

class Solution {
    public int[] nodesBetweenCriticalPoints(ListNode head) {
        ListNode prev = head;
        ListNode temp = head.next;
        ListNode next = temp.next;
        int index = 2;
        int firstIndex = 0;
        int prevIndex = 0;
        int currIndex = 0;
        int min = Integer.MAX_VALUE;
        if (next ==null) return new int[]{-1,-1};
        while(next!=null){
            if(temp.val<next.val && temp.val<prev.val||
                temp.val>next.val && temp.val>prev.val){
                    if(firstIndex ==0) firstIndex = index;
                    currIndex = index;
                    if(prevIndex!=0) min = Math.min(currIndex-prevIndex,min);
                    prevIndex = index;
                }
            index++;
            prev = prev.next;
            temp = temp.next;
            next = next.next;
        }
        if(currIndex==firstIndex) return new int[]{-1,-1};
        int max = currIndex - firstIndex;
        return new int[]{min,max};
    }
}

class Solution {
    public int[] nodesBetweenCriticalPoints(ListNode head) {
        int[] ans = new int[2];
        ans[0] = Integer.MAX_VALUE;
        ans[1] = -1;
        ListNode pointer = head;
        int prevVal = head.val, nextVal = head.val;
        int idx = 0, lastCriticalIdx = -1, fistCriticalIdx = -1;
        while (pointer != null) {
            nextVal = pointer.next == null ? pointer.val : pointer.next.val;
            int curVal = pointer.val;
            if ((curVal > prevVal && curVal > nextVal) || (curVal < prevVal && curVal < nextVal)) {
                ans[0] = lastCriticalIdx > 0 ? Math.min(ans[0], idx - lastCriticalIdx) : ans[0];
                ans[1] = fistCriticalIdx > 0 ? idx - fistCriticalIdx : ans[1];
                if (fistCriticalIdx < 0) fistCriticalIdx = idx;
                lastCriticalIdx = idx;
            }
            prevVal = curVal;
            idx++;
            pointer = pointer.next;
        }
        if (ans[0] == Integer.MAX_VALUE) ans[0] = -1;
        return ans;
    }
}

class Solution:
    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
        minDist = math.inf
        firstCrit = lastCrit = -math.inf
        i, prevNode, curNode = 0, head, head.next
        
        while curNode.next:
            if (prevNode.val < curNode.val > curNode.next.val
                or prevNode.val > curNode.val < curNode.next.val):
                firstCrit = i if firstCrit == -math.inf else firstCrit
                minDist = min(minDist, i - lastCrit)
                lastCrit = i
            i, prevNode, curNode = i + 1, curNode, curNode.next
        
        return [minDist, lastCrit - firstCrit] if lastCrit > firstCrit else [-1, -1]