Hexo

Posted 2022-04-09Updated 2022-04-08LeetCode / Easya minute read (About 224 words)

问题
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

设置哨兵节点，将其next指向头部。
设置前节点，将其指向哨兵节点。
设置尾部节点，并指向头部。
移动当前节点尾部，如尾部的val等于需要删去的val，则将前节点的next指向尾部的next。
尾部的next如为null，则前节点的next指向null。

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null){
            return head;
        }
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        
        ListNode preNode = dummyHead;
        ListNode tail = dummyHead.next;
        
        while( tail != null ){
            if ( tail.next == null && tail.val == val ){
                preNode.next = null;
                break;
            }
            else if (tail.val == val){
                preNode.next = tail.next;
                tail = preNode.next;
            }
            else{
                preNode = preNode.next;
                tail = tail.next;
            }
        }
        
        return dummyHead.next;
    }
}

Posted 2022-04-09Updated 2022-04-20LeetCode / Easy / 复习2 minutes read (About 246 words)

733. Flood Fill

答案
An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and newColor. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with newColor.

Return the modified image after performing the flood fill.

深度优先搜索。
如果当前像素颜色等于最初的颜色，则变更为新颜色。
然后继续递归四个周围的像素。

class Solution { 
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int oldColor = image[sr][sc];
        if (oldColor != newColor){
            dfs(image,sr,sc,oldColor,newColor);
        }

        return image;
    }
    
    private void dfs(int[][] image, int r, int c, int oldColor, int newColor){
        if (image[r][c] == oldColor){
            image[r][c] = newColor;
            
            if (r>=1){
                dfs(image,r-1,c,oldColor,newColor);
            }
            if (c>=1){
                dfs(image,r,c-1,oldColor,newColor);
            }
            if (r<image.length-1){
                dfs(image,r+1,c,oldColor,newColor);
            }
            if (c<image[0].length-1){
                dfs(image,r,c+1,oldColor,newColor);
            }
        }
    }
}

Posted 2022-04-09Updated 2022-04-20LeetCode / Easy / 复习a minute read (About 217 words)

21. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

先设置空的哨兵节点，然后将尾部指针指向这个节点。
遍历两个链表，将尾部节点的下一个值指向两个节点中值较小的一个。
然后将指针移动到下一个值。
最后返回哨兵节点的下一个节点。

/**
 * 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; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode();
        ListNode tail = dummyHead;

        
        while ( list1 != null && list2 !=null ){
            if (list1.val < list2.val){
                tail.next = list1;
                list1 = list1.next;
                tail = tail.next;
            }
            else{
                tail.next = list2;
                list2 = list2.next;
                tail = tail.next;
            }
 
        }
        
        if ( list1 == null){
            tail.next = list2;
        }
        else {
            tail.next = list1;
        }
        
        return dummyHead.next;
    }
}

Posted 2022-04-09Updated 2022-04-08LeetCode / Easy / 复习a minute read (About 201 words)

141. Linked List Cycle

问题
Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

遍历并移动快慢指针。
如两个指针最终相遇，则链表中有循环。
如快指针移动到链表尾部，则链表无循环。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        if ( head == null){
            return false;
        }
        else if ( fast.next == null){
            return false;
        }
        
        while( fast != null && fast.next != null ){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast){
                return true;
            }
        }
        return false;
    }
}

Posted 2022-04-09Updated 2022-04-08LeetCode / Easy / 复习a minute read (About 175 words)

703. Kth Largest Element in a Stream

问题
Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.

int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

优先级队列，插入所有元素，小元素在前。
当队列长度大于k时，poll掉前面的元素。

class KthLargest {
    PriorityQueue<Integer> pq;
    int kth;
    public KthLargest(int k, int[] nums) {
        pq = new PriorityQueue<Integer>();
        kth = k;
        for (int num : nums){
            pq.add(num);
        }
    }
    
    public int add(int val) {
        pq.add(val);
        while (pq.size() > kth){
            pq.poll();
        }  
        return pq.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

Recents

Archives

Links