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

232. Implement Queue using Stacks

问题
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

  • void push(int x) Pushes element x to the back of the queue.

  • int pop() Removes the element from the front of the queue and returns it.

  • int peek() Returns the element at the front of the queue.

  • boolean empty() Returns true if the queue is empty, false otherwise.
    Notes:

  • You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.

  • Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.

创建两个栈。
当入队列时，将元素压入第一个栈。
当出队列或进行其他操作时，如第二个栈为空，则将第一个栈的元素倒出到第二个栈。
此时第二个栈内的内容为顺序。

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
40
41
42
43
44
45
46
47
48
49
50
51
class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
        
    public MyQueue() {
        s1 = new Stack();
        s2 = new Stack();
    }
    
    public void push(int x) {
        s1.add(x);
    }
    
    public int pop() {
        if (s2.isEmpty()){
            while (!s1.isEmpty()){
                s2.add(s1.pop());
            }
            return s2.pop();
        }
        else{
            return s2.pop();
        }
        
    }
    
    public int peek() {
        if (s2.isEmpty()){
            while (!s1.isEmpty()){
                s2.add(s1.pop());
            }
            return s2.peek();
        }
        else{
            return s2.peek();
        }
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */
Posted Updated LeetCode / Easy / 复习2 minutes read (About 319 words)

542. 01 Matrix

问题
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.

由于是搜索最近的距离，因此可以采用BFS搜索。
首先创建一个距离矩阵，将所有原矩阵为0的位置填上距离0，将其他位置填上无穷大。
使用BFS搜索，将所有0的坐标放入队列。
取出队列头元素，将其周围的距离矩阵的元素与自身距离矩阵的元素+1比较，将较小的值设置在周围的距离矩阵上。
同时，将改变数值的坐标再次放入队列。

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
40
41
42
43
44
45
class Solution{
    public int[][] updateMatrix(int[][] mat) {

        Queue<Integer> q = new LinkedList();
        int row = mat.length;
        int col = mat[0].length;
        int[][] ans = new int[row][col];
                                   
        for ( int i = 0; i < row; i++ ){
            for (int j = 0; j < col; j++){
                if (mat[i][j] == 0){
                    ans[i][j] = 0;
                    q.add(i*col + j);
                }
                else{
                    ans[i][j] = Integer.MAX_VALUE;
                }
            }
        }

            
        while(!q.isEmpty()){
            int i = q.peek() / col;
            int j = q.poll() % col;
            
            if(i-1 >= 0 && ans[i][j]+1 < ans[i-1][j]){
                ans[i-1][j] = ans[i][j]+1;
                q.add((i-1)*col + j);
            }
            if(i+1 < row && ans[i][j]+1 < ans[i+1][j]){
                ans[i+1][j] = ans[i][j]+1;
                q.add((i+1)*col + j);
            }
            if(j-1 >= 0 && ans[i][j]+1 < ans[i][j-1]){
                ans[i][j-1] = ans[i][j]+1;
                q.add(i*col + (j-1));
            }
            if(j+1 < col && ans[i][j]+1 < ans[i][j+1]){
                ans[i][j+1] = ans[i][j]+1;
                q.add(i*col + (j+1));
            }
        }
        return ans;
    }
}
Posted Updated LeetCode / Easy / 复习a minute read (About 170 words)

20. Valid Parentheses

问题
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

用栈储存遍历中的字符。
如果是“（”，“{”或“[”，则入栈。
如果是其他字符，且不与栈顶的字符成对，则返回false。
其他情况需要pop掉栈顶。

  • toCharArray(): 将字符串转换为字符数组，便于遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack();
        
        for (char c : s.toCharArray()){
            if ( c == '(' || c == '{' || c == '[' ){
                stack.push(c);
            }
            else if ( stack.size() == 0 || 
                     c == ')' && stack.peek() != '(' || 
                     c == '}' && stack.peek() != '{' || 
                     c == ']' && stack.peek() != '[') {
                return false;
            }
            else{
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}
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 / 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;
    }

}
Posted Updated LeetCode / 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.

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

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 { 
    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 Updated LeetCode / 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.

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

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
40
/**
 * 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 Updated LeetCode / 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.

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

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
/**
 * 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 Updated LeetCode / 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掉前面的元素。

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
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 Updated LeetCode / 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。

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 {
    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 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

×