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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* first = head;
        ListNode* second = head->next;
        if (second == nullptr) return head;
        while (second != nullptr) {
            int gcd = __gcd(first->val, second->val);
            ListNode* temp = new ListNode(gcd);
            first->next = temp;
            temp->next = second;
            first = second;
            second = second->next;
        }
        return head;
    }
};

# Approach 1 : Recursive - top down + memorize
        n = len(stones)
        @lru_cache(None)
        def helper(i, curr):
            if i >= n:
                return abs(curr) 
            return min(helper(i + 1, curr - stones[i]),helper(i + 1, curr + stones[i]))
        return helper(0,0)

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = Arrays.stream(stones).sum();
        int capacity = sum / 2;

        int[] dp = new int[capacity + 1];

        for (int num: stones) {
            for (int i = capacity; i >= num; i--) {
                dp[i] = Math.max(dp[i], dp[i - num] + num);
            }
        }

        return sum - 2 * dp[capacity];
    }
}

class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        if (head.next == null) return head;

        ListNode cur = head;
        ListNode t;
        
        while(cur.next != null) {
            t = new ListNode();
            t.val = findGCD(cur.val, cur.next.val);
            t.next = cur.next;
            cur.next = t;
            cur = t.next;
        }

        return head;
    }

    int findGCD(int a, int b) {
        return a * b / findLCM(a, b);
    }

    int findLCM(int a, int b) {
        int bigger = Math.max(a, b);
        int min = Math.min(a, b);

        int m = bigger;
        while(m%min != 0) {
            m += bigger;
        }

        return m;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def gcd(a, b):
            if b == 0:
                return a
            return gcd(b, a % b)
        new_head = ListNode(head.val)
        current = new_head
        while head:
            if head.next:
                current.next = ListNode(gcd(head.val, head.next.val))
                current = current.next
                current.next = ListNode(head.next.val)
            current = current.next
            head = head.next
        return new_head

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def gcd(a, b):
            while a != b:
                if a > b:
                    a = a -b
                else:
                    b = b - a

            return a

        current = head

        while current.next is not None:
            gcd_value = gcd(current.val, current.next.val)
            gcd_node = ListNode(gcd_value, current.next)
            temp = current
            current = current.next
            temp.next = gcd_node

        return head

func calculateCommonDivisor(x, y int) int{
    if y == 0 {
        return x
    }
    return calculateCommonDivisor(y, x%y)
}

func insertGreatestCommonDivisors(head *ListNode) *ListNode {
    curr := head
    currNext := curr.Next
    for currNext != nil {
        g := calculateCommonDivisor(curr.Val, currNext.Val)
        curr.Next = &ListNode{
            Val: g,
            Next: currNext,
        }
     
        curr = curr.Next.Next
        currNext = curr.Next
    }
    return head
}

class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        target = total // 2
        
        def dfs(index, half, sumSoFar, possibleSums):
            if index == len(half):
                possibleSums.add(sumSoFar)
                return
            dfs(index + 1, half, sumSoFar + half[index], possibleSums)
            dfs(index + 1, half, sumSoFar, possibleSums)

        n = len(stones)
        s1, s2 = set(), set()
        
        dfs(0, stones[:n//2], 0, s1)
        dfs(0, stones[n//2:], 0, s2)

        s2 = sorted(s2)
        ans = float('inf')

        for s in s1:
            remain = target - s

            low, high = 0, len(s2) - 1
            while low <= high:
                mid = (low + high) // 2
                if s2[mid] < remain:
                    low = mid + 1
                else:
                    high = mid - 1

            if low < len(s2):
                ans = min(ans, abs(total - 2 * (s + s2[low])))
            if high >= 0:
                ans = min(ans, abs(total - 2 * (s + s2[high])))

        return ans

class Solution:

    def lastStoneWeightII(self, stones: List[int]) -> int:
        total = sum(stones)
        target = total // 2
       
        memo = {}
        self.largestSum = 0

        def dfs(index, sumSoFar):
            if sumSoFar > target:
                return
           
            if index == len(stones):
                self.largestSum = max(self.largestSum, sumSoFar)
                return
           
            if (index, sumSoFar) in memo:
                return memo[(index, sumSoFar)]

            dfs(index + 1, sumSoFar + stones[index])
            dfs(index + 1, sumSoFar)

            memo[(index, sumSoFar)] = self.largestSum

        dfs(0, 0)

        return total - 2 * self.largestSum

impl Solution {
    pub fn insert_greatest_common_divisors(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut sentinel = Some(Box::new(ListNode::new(0)));
        let mut tail = sentinel.as_mut();

        fn gcd(a: i32, b: i32) -> i32 {
            match a {
                0 => b,
                _ => gcd(b % a, a)
            }
        }

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

            tail =
                tail.and_then(|tail| {
                    if tail.val != 0 {
                        let gcd = gcd(tail.val, node.val);
                        let mut gcd_node = ListNode::new(gcd);

                        gcd_node.next = Some(node);
                        tail.next = Some(Box::new(gcd_node));

                        tail.next.as_mut().and_then(|gcd_node| gcd_node.next.as_mut())
                    } else {
                        tail.next = Some(node);

                        tail.next.as_mut()
                    }
                });
        }

        sentinel.and_then(|mut sen| sen.next.take())
    }
}

impl Solution {
    pub fn insert_greatest_common_divisors(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        if head.is_none() {
            return None;
        }

        let mut node = head.take().unwrap();
        head = node.next.take();
        let mut sentinel = Some(node);
        let mut tail = sentinel.as_mut();

        fn gcd(a: i32, b: i32) -> i32 {
            match a {
                0 => b,
                _ => gcd(b % a, a)
            }
        }

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

            tail =
                tail.and_then(|tail| {
                    let gcd = gcd(tail.val, node.val);
                    let mut gcd_node = ListNode::new(gcd);
                    gcd_node.next = Some(node);
                    tail.next = Some(Box::new(gcd_node));
                    tail.next.as_mut().and_then(|gcd_node| gcd_node.next.as_mut())
                });
        }

        sentinel
    }
}

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] list = new ListNode[k];
        int sz = 0;
        ListNode tmp = head;

        while (tmp != null) {
            tmp = tmp.next;
            sz++;
        }

        int pos = sz / k;
        int rem = sz % k;
        tmp = head;
        ListNode prev = null;

        for (int i = 0; i < k; i++) {
            list[i] = tmp;
            int partSize = pos + (i < rem ? 1 : 0);

            for (int j = 0; j < partSize; j++) {
                prev = tmp;
                tmp = tmp.next;
            }

            if (prev != null) {
                prev.next = null;
            }
        }

        return list;
    }
}

class Solution {
    public int[][] spiralMatrix(int m, int n, ListNode head) {
        int[][] a = new int[m][n];

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                a[i][j] = -1;
            
        int top = 0, bot = m - 1;
        int lt = 0, rt = n - 1;

        while (head != null) {
            for (int i = lt; i <= rt && head != null; i++) {
                a[top][i] = head.val;
                head = head.next;
            }
            top++;

            for (int i = top; i <= bot && head != null; i++) {
                a[i][rt] = head.val;
                head = head.next;
            }
            rt--;

            for (int i = rt; i >= lt && head != null; i--) {
                a[bot][i] = head.val;
                head = head.next;
            }
            bot--;

            for (int i = bot; i >= top && head != null; i--) {
                a[i][lt] = head.val;
                head = head.next;
            }
            lt++;
        }

        return a;
    }
}

class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode ptr = head;
        if (ptr.next == null) return head;
        while (ptr.next != null) {
            int tmp = gcd(ptr.next.val, ptr.val);
            ListNode newNode = new ListNode(tmp);
            newNode.next = ptr.next;
            ptr.next = newNode;
            ptr = ptr.next.next;
        }
        return head;
    }

    public int gcd(int a, int b) {
        int g = a > b ? a : b;
        int s = a < b ? a : b;
        if (s == 0)
            return g;
        while (g > s) {
            if (g % s == 0) {
                return s;
            } else {
                g = g % s;
                if (g < s) {
                    int tmp = g;
                    g = s;
                    s = tmp;
                }
            }
        }
        return s;
    }
}

impl Solution {
    fn gcd(mut a: i32, mut b: i32) -> i32 {
        while b != 0 {
            (a, b) = (b, a % b)
        }
        a
    }

    pub fn insert_greatest_common_divisors(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut head = head;
        let mut current = &mut head;

        while let Some(node) = current {
            if node.next.is_none() {
                break;
            }
            let next = node.next.take().unwrap();
            node.next = Some(Box::new(ListNode {
                val: Self::gcd(node.val, next.val),
                next: Some(next),
            }));
            current = &mut node.next.as_mut().unwrap().next;
        }

        head
    }
}

class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode node = head;
        ListNode next = head.next;
        while(next!=null){
            node.next = new ListNode(gcd(node.val,next.val),next);
            node = next;
            next = next.next;
        }
        return head;
    }

    public int gcd(int a,int b){
        if (b==0)
            return a;
        return gcd(b,a%b);
    }
}