Posted Updated LeetCode / 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队列，将所有元素放入。
每次取出两个，将两者的差值放回队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 Updated LeetCode / 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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 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 Updated LeetCode / 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.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 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 Updated LeetCode / 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:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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;
    }
}

Posted Updated LeetCode / Easy / 复习a few seconds read (About 86 words)

118. Pascal's Triangle

Given an integer numRows, return the first numRows of Pascal’s triangle.

动态规划，直接按照杨辉三角形的定义计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<Integer>> generate(int numRows) {
        ArrayList<List<Integer>> ans = new ArrayList<List<Integer>>(numRows);

        for (int i = 0; i < numRows ; i++){
            List<Integer> arr = new ArrayList<Integer>(i+1);
  
            for (int j = 0; j <= i; j++){
                if ( j == 0 || j == i ){
                    arr.add(1);
                }
                else{
                    arr.add(ans.get(i-1).get(j-1)+ans.get(i-1).get(j));
                }
            }
            ans.add(arr);
        }
        return ans;
    }
}

Follow

Recents

Archives

Links

×