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 / 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;
    }
}
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 / 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。

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
/**
 * 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 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 / 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 / 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 / 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;
    }
}
242. Valid Anagram
Posted Updated LeetCode / Easya minute read (About 163 words)

242. Valid Anagram

Problem

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Solution

两数组相等时，直接遍历两个数组并记录各个字符出现的数量。
一个数组遍历时用做加法，另一个做减法。
如果最后每个字符出现的数量均为0，则返回真。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length()!=t.length()){
            return false;
        }
        int[] dic = new int[26];
        for (int i = 0; i < s.length(); i++){
            dic[s.charAt(i)-'a']++;
            dic[t.charAt(i)-'a']--;
        }
        
        for(int num : dic){
            if ( num != 0 ){
                return false;
            }
        }
        return true;
    }
}
387. First Unique Character in a String
Posted Updated LeetCode / Easy2 minutes read (About 240 words)

387. First Unique Character in a String

Problems

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Solution

遍历，数组统计记录出现次数。
如果数组未记录过，则将其index添加进列表中保存。

遍历列表，如果数组统计结果为1，则返回对应的index。
否则返回-1。

Code 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int firstUniqChar(String s) {
        List<Integer> arr = new ArrayList<>();
        int[] bin = new int[26];
        
        for(int i = 0; i < s.length(); i++){
            if(bin[s.charAt(i) - 'a'] == 0) arr.add(i);
            bin[s.charAt(i) - 'a']++;
        }
        
        for(int i = 0; i < arr.size(); i++){
            if(bin[s.charAt(arr.get(i)) - 'a'] == 1) return arr.get(i);  
        }
        
        return -1;
    }
}

Solution

遍历，建立哈希表，记录出现次数。
再次遍历，如果出现次数为1，则返回下标。

Code 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int firstUniqChar(String s) {
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();
        for ( int i = 0; i < s.length(); i++ ){
            char curChar = s.charAt(i);
            if ( !map.containsKey(curChar) ){
                map.put(curChar, 1);
            }
            else{
                map.put(curChar, map.get(curChar)+1);
            }
        }
        
        for ( int i = 0; i < s.length(); i++ ){
            char curChar = s.charAt(i);
            if ( map.get(curChar) == 1 ){
                return i;
            }
        }
        return -1;
    }
}
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

×