Leetcode 1721

this is a two pointer question, it uses slow fast pointer technique to get pointer to the kth node from the end, then find the front node !!

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        // locate the end node 
        ListNode slow = head;
        ListNode fast = head;
        int k1 = k;
        while(fast != null && k1 > 0){
            fast = fast.next;
            k1 --;
        }
        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        ListNode p = head;
        while(p != null && k > 1){
            p = p.next;
            k --;
        }
        // make the swap 
        int temp = p.val;
        p.val = slow.val;
        slow.val = temp;
        return head;
    }
}

265. Paint House II

This is a classic dp problem, but also little like advance graph apporach! Be sure to review this problem again tomorrow!

class Solution {
    public int minCostII(int[][] costs) {
        if(costs.length == 0) return 0; // nothing to paint
        int k = costs[0].length; // the k color we are looking for
        int n = costs.length;
        int[] previousRow = costs[0];

        for(int house = 1; house < n; house++){
            // we going to look at curr costs
            int[] currRow = new int[k];
            for(int color = 0; color < k; color ++){
                int min = Integer.MAX_VALUE;
                // locate the cheapest solution from last row, we want the cheapest cost so far
                for(int previousColor = 0; previousColor < k; previousColor ++){
                    if(color == previousColor){
                        // we can't print two adjusent color same
                        continue;
                    }
                    min = Math.min(min, previousRow[previousColor]);
                }
                // if we would paint curr house curr color, then we add cost from min previous house and cost of curr house 
                currRow[color] += costs[house][color] += min;
            }
            // now we want to change previousRow = curr
            previousRow = currRow;
        }
        // now we have the final row, find return the res
        int res = Integer.MAX_VALUE;
        for(int cost : previousRow){
            res = Math.min(res,cost);
        }
        return res;
    }
}