Category: LeetCode

Posted 2022-04-10Updated 2022-05-04LeetCode / Mediuma minute read (About 176 words)

Question

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Solution

遍历，使用哈希表保存遍历次数。
再次遍历，根据元素出现的次数将其填入优先级队列实现的大根堆。
遍历取出k个最大值。

getOrDefault()：
方便的遍历并生成哈希表。

lambda：
（）内表示传入的数值。
-> 后表示返回值。

Code

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] ans = new int[k];
        HashMap<Integer,Integer> map = new HashMap();
        for (int num : nums){
            map.put( num, map.getOrDefault(num , 0) + 1 );
        }
        PriorityQueue<Integer> pq = new PriorityQueue((a,b) -> map.get(b) - map.get(a));
        for (int key : map.keySet()){
            pq.add(key);
        }
        for (int i = 0; i < k ; i++){
            ans[i] = pq.poll();
        }
        return ans;
    }
}

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

206. Reverse Linked List

问题
Given the head of a singly linked list, reverse the list, and return the reversed list.

翻转列表，当链表长度不足时，直接返回原链表。
将头元素设置到preNode，同时将其next设置为null，作为新链表的尾。
将其余的元素设置到curNode。

当当前节点不为null时
遍历：

将curNode的next保存在temp。
将curNode的next指向preNode，作为preNode的上一个节点。
将preNode指向curNode，完成交换。
将curNode指向temp，curNode变为原来的curNode的next。

/**
 * 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 reverseList(ListNode head) {
        
        if( head == null ){   //if not enough, return head
            return head;
        }
        if ( head.next == null ){
            return head;
        }
        
        ListNode preNode = head;    //set head to preNode, it will be the last node in the end
        ListNode curNode = head.next;   //curNode move to next
        preNode.next = null;    //only preserve one head node
        ListNode temp;
        
        while( curNode != null ){
            temp = curNode.next;    //preserve nodes after curNode
            curNode.next = preNode; //cur -> pre
            preNode = curNode;  //set back reversed list to preNode
            curNode = temp; //put back preserved nodes, curNode move to the next
        }
        return preNode;
    }

}

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

203. Remove Linked List Elements

问题
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);
 */

Posted 2022-04-07Updated 2022-04-20LeetCode / Medium2 minutes read (About 235 words)

567. Permutation in String

问题
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.

将要查找的组合加入数组，数值为字符出现的次数。
滑动窗口，入窗口对应的元素数值-1，出窗口对应的元素数值+1。
每次移动窗口都检验一次数组的数值是否全部为0，如果是真，则返回真。
小技巧：直接用数组来记录字符出现的次数，用字符减去与’a’的差作为下标。

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()){
            return false;
        }
        
        int[] dic = new int[26];
        for (int i = 0; i < s1.length(); i++){
            dic[s1.charAt(i)-'a']++;
            dic[s2.charAt(i)-'a']--;
        }
 
        int i = 0;
        int j = s1.length();
        
        while( j < s2.length() ){
            if ( allZero(dic) ){
                return true;
            }
            dic[s2.charAt(i)-'a']++;
            dic[s2.charAt(j)-'a']--;
            i++;
            j++;
        }
        return allZero(dic);
    }
    
    private boolean allZero(int[] dic){
        for (int num : dic){
            if ( num != 0 ){
                return false;
            }
        }
        return true;
    }
}

Posted 2022-04-07Updated 2022-06-10LeetCode / Medium / 复习2 minutes read (About 355 words)

3. Longest Substring Without Repeating Characters

Question

Given a string s, find the length of the longest substring without repeating characters.

Solution 1

滑动窗口加数组统计。
用一个数组bin[]记录各个字符的访问情况。（数组尺寸由字符串的总数决定）

当指针j第一次遍历到一个字符时，如果该字符对应的位置为0，则将其设置为1。
否则对前面的i指针进行遍历，并将i经过的位置重新设置为0。如果i的字符与当前j字符相等，则将bin[index]设置为0，计算当前的长度j-i并更新最大值best。

Code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int best = 0, i = 0, j = 0;
        char[] word = s.toCharArray();
        int[] bin = new int[128];
        while(j < s.length()){
            int index = word[j] - ' ';
            if(bin[index] == 0){
                bin[index] = 1;
                j++;
            }
            else{
                while(i < j){
                    int temp = word[i] - ' ';
                    if(temp == index && bin[index] == 1){
                        bin[index] = 0;
                        best = Math.max(best, j - i);
                        i++;
                        break;
                    }
                    bin[temp] = 0;
                    i++;
                }
            }
            best = Math.max(best, j - i);
        }
        return best;
    }
}

Solution 2

滑动窗口，哈希表记录访问过的字符的元素。
如果重复，则放弃前一个重复的字符，更新左指针。
注意：只有在新指针大于现有指针时才更新！

Code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int best = 0;
        int i = 0;
        int j = 0;
        
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        
        while ( j < s.length() ){
            char curChar = s.charAt(j);
            if ( !map.containsKey(curChar) ){
                map.put( curChar, j );
            }
            else{
                if ( map.get(curChar) + 1 > i){
                    i = map.get(curChar) + 1;
                }

                map.put( curChar, j );
            }
            
            if ((j - i + 1) > best){
                best = (j - i + 1);
            }
            j++;
        }
        return best;
    }
}

Posted 2022-04-07Updated 2022-04-20LeetCode / Easya minute read (About 189 words)

1046. Last Stone Weight

问题
You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are destroyed, and

If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

采用PriorityQueue队列，将所有元素放入。
每次取出两个，将两者的差值放回队列。

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
        for (int stone : stones){
            pq.add(stone);
        }
        
        while ( pq.size() > 1) {
            int largeStone = pq.poll();
            int smallStone = pq.poll();
            pq.add( largeStone - smallStone );
        }
        
        return pq.poll();
    }
}

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

680. Valid Palindrome II

问题
Given a string s, return true if the s can be palindrome after deleting at most one character from it.

双指针，字符串两边对比。
如果两边字符不相等，则更新两边指针，并分别传入辅助方法再次对比。
两个结果有一个是true则返回true。

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        
        while (left < right){
            if (s.charAt(left) == s.charAt(right) ){
                left++;
                right--;
            }
            else{
                return ( checkPalindrome(s, left+1, right) || checkPalindrome(s, left, right-1));
            }
        }
        return true;
    }
    private boolean checkPalindrome(String s, int left, int right){
        while (left < right){
            if (s.charAt(left)==s.charAt(right)){
                left++;
                right--;
            }
            else{
                return false;
            }
        }
        return true;
    }    
}

Posted 2022-04-07Updated 2022-04-20LeetCode / Mediuma minute read (About 166 words)

19. Remove Nth Node From End of List

问题
Given the head of a linked list, remove the nth node from the end of the list and return its head.

双指针，同时记录前n个节点和当前节点。
当前指针到链表尾部时，删除前面的指针，注意处理edge cases。

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        ListNode preNode = null;
        ListNode removedNode = head;
        ListNode fastNode = head;
        for ( int i = 0; i < n; i++ ){
            fastNode = fastNode.next;
        }
        
        while ( fastNode != null ){
            fastNode = fastNode.next;
            preNode = removedNode;
            removedNode = removedNode.next;
        }
        
        if ( removedNode == head ){
            head = head.next;
        }
        else if ( removedNode.next == null){
            preNode.next = null;
        }
        else{
            preNode.next = removedNode.next;
        }
        
        return head;
    }
}

Posted 2022-04-07Updated 2022-04-08LeetCode / Easya minute read (About 132 words)

876. Middle of the Linked List

问题
Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

快慢指针，两个指针不同速度遍历链表。当快指针达到链表尾部时候，慢指针正好在中间。

/**
 * 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 middleNode(ListNode head) {
        
        ListNode slowNode = head;
        ListNode fastNode = head;
        
        while( fastNode != null ){
            fastNode = fastNode.next;
            if (fastNode == null){
                return slowNode;
            }
            slowNode = slowNode.next;
            fastNode = fastNode.next;
        }
        return slowNode;
    }
}

Posted 2022-04-07Updated 2022-04-18LeetCode / Mediuma minute read (About 216 words)

74. Search a 2D Matrix

问题
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.

The first integer of each row is greater than the last integer of the previous row.

二分搜索，以整个数组尺寸作为搜索范围。
每次搜索中间值，如等于target则返回。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int left = 0;
        int right = (matrix.length * matrix[0].length) - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            int row = mid / matrix[0].length;
            int col = mid % matrix[0].length;
            if(matrix[row][col] == target){
                return true;
            }
            else if(matrix[row][col] > target){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        return false;
    }
}

双指针，先搜索到合适的行。
再搜索到合适的列。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int i = 0;
        int j = 0;
        
        while(i < matrix.length){
            if(matrix[i][0] == target){
                return true;
            }
            else if(matrix[i][0] < target){
                i++;
            }
            else{
                break;
            }
        }
        if( i == 0 ){
            return false;
        }
        i--;
        while(j < matrix[0].length){
            if(matrix[i][j] == target){
                return true;
            }
            j++;
        }
        return false;
    }
}

Posted 2022-04-07Updated 2022-04-06LeetCode / Medium2 minutes read (About 239 words)

36. Valid Sudoku

问题
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.

Each column must contain the digits 1-9 without repetition.

Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.

Only the filled cells need to be validated according to the mentioned rules.

遍历并创建三组不同的哈希表，每个表内包含一组哈希集合。
如果访问的元素已在哈希集合内，则返回false

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashMap<Integer,HashSet<Character>> rowMap = new HashMap<Integer,HashSet<Character>>();
        HashMap<Integer,HashSet<Character>> colMap = new HashMap<Integer,HashSet<Character>>();
        HashMap<Integer,HashSet<Character>> blockMap = new HashMap<Integer,HashSet<Character>>();

        for (int i = 0; i < board[0].length; i++ ){
            for (int j = 0; j < board.length; j++ ){
                char curChar = board[i][j];
                if (curChar == '.'){
                    continue;
                }
                if (!rowMap.containsKey(i)){
                    rowMap.put(i, new HashSet<Character>());
                }
                if (!colMap.containsKey(j)){
                    colMap.put(j, new HashSet<Character>());
                }
                if (!blockMap.containsKey(j/3*3+i/3)){
                    blockMap.put(j/3*3+i/3, new HashSet<Character>());
                }
                HashSet<Character> curRow = rowMap.get(i);
                HashSet<Character> curCol = colMap.get(j);
                HashSet<Character> curBlock = blockMap.get(j/3*3+i/3);
                
                if ( !curRow.contains(curChar) && !curCol.contains(curChar) && !curBlock.contains(curChar) ){
                    curRow.add(curChar);
                    curCol.add(curChar);
                    curBlock.add(curChar);
                }
                else{
                    return false;
                }   
            }
        }
        return true;
    }
}

Question

Solution

Code

Question

Solution 1

Code

Solution 2

Code

Recents

Archives

Links