Posted Updated LeetCode / Easy / 复习2 minutes read (About 247 words)

617. Merge Two Binary Trees

问题
You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

递归。将root1和root2合并到root1。
如果一个节点为null，则返回另一个节点。
否则root1的值为root1 + root2的值。
root1.left递归root1和root2的left。
root2.right递归root1和root2的right。
返回root1。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if( root1 == null ){
            return root2;
        }
        if( root2 == null ){
            return root1;
        }
        
        root1.val = root1.val + root2.val;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        
        return root1;
    }
}
Posted Updated LeetCode / Easya minute read (About 167 words)

83. Remove Duplicates from Sorted List

问题
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

设置前一个节点和当前节点两个指针。
由于是有数的链表，遍历时可以直接比较两个节点。
如相等则前一个节点的next指向当前节点的next。

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
/**
 * 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 deleteDuplicates(ListNode head) {
        
        if ( head == null){
            return head;
        }
        if ( head.next == null){
            return head;
        }
        ListNode prev = head;
        ListNode curr = head.next;
        
        while(curr != null){
            if(prev.val != curr.val){
                curr = curr.next;
                prev = prev.next;
            }
            else{
                prev.next = curr.next;
                curr = curr.next;
            }
        }
        return head;
    }
}
695. Max Area of Island
Posted Updated LeetCode / Medium / 复习2 minutes read (About 292 words)

695. Max Area of Island

Question

You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Solution

DFS搜索, 维护一个变量count，为连续执行DFS搜索的次数。
遍历地图上所有为1的位置。

运行BFS时每次将全局变量count增加1。
执行完毕后BFS时将全局变量count清零。

遍历每个等于1的地图块。
递归周围四个地图块，当超越数组范围，或者当前位置不为1时返回。
进行搜索时将搜索过的地图块标记为0，不再重复搜索。

Code

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
class Solution {
    int[][] visited, directions;
    int count;
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for(int x = 0; x < grid.length; x++){
            for(int y = 0; y < grid[0].length; y++){
                if(grid[x][y] == 1){
                    count = 0;
                    dfs(grid, x, y);
                    res = Math.max(res, count);
                }
            }
        }
        return res;
    }
    
    private void dfs(int[][] grid, int x, int y){
        if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0) return;
        grid[x][y] = 0;
        count++;
        for(int[] direction : directions){
            int i = x + direction[0];
            int j = y + direction[1];
            dfs(grid, i, j);
        }
    }
}
Posted Updated LeetCode / Mediuma minute read (About 176 words)

347. Top K Frequent Elements

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

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

  1. 将curNode的next保存在temp。
  2. 将curNode的next指向preNode，作为preNode的上一个节点。
  3. 将preNode指向curNode，完成交换。
  4. 将curNode指向temp，curNode变为原来的curNode的next。
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
/**
 * 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;
    }

}
Follow

Recents

Archives

Links

×