LeetCode刷题笔记 7月

Posted on By Guanzhou Song

Go to Leetcode

2019-07-01

394. Decode String

Description

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

Solution

class Solution {
	//there are four situations:
	//1. digits: should count all the possible number and add to stack.
	//2. letter: just add to res.
	//3. [: should first put all the words before to resStk, then set res to empty.
	//4. ]: should start wrapping up. first get a count from countStk, then pop a string from resStk, which is the result after the [ and number.
	// then add current res, which is the result in the [], for cout times. then make the current string as res.
    public String decodeString(String s) {
        String res = "";
        Stack<Integer> countStk = new Stack();
        Stack<String> resStk = new Stack();
        int idx = 0;
        while(idx < s.length()){
            if(Character.isDigit(s.charAt(idx))){
                int count = 0;
                while(Character.isDigit(s.charAt(idx))){
                    count = count * 10 + (s.charAt(idx)-'0');
                    idx++;
                }
                countStk.push(count);
            }else if(s.charAt(idx) == '['){
                resStk.push(res);
                res = "";
                idx++;
            }else if(s.charAt(idx) == ']'){
                StringBuilder sb = new StringBuilder(resStk.pop());
                int count = countStk.pop();
                for(int i=0;i<count;i++){
                    sb.append(res);
                }
                res = sb.toString();
                idx++;
            }else{
                res += s.charAt(idx++);
            }
        }
        return res;
    }

    // use maxHeap. Put entry into maxHeap so we can always poll a number with largest frequency
    public List<Integer> topKFrequent2(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap();
        for(int n: nums){
            map.put(n,map.getOrDefault(n,0)+1);
        }

        //PriorityQueue
        PriorityQueue<Map.Entry<Integer,Integer>> maxHeap =
            new PriorityQueue<>((a,b)->(b.getValue()-a.getValue()));

        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            maxHeap.add(entry);
        }
        List<Integer> res = new LinkedList();
        while(res.size()<k){
            Map.Entry<Integer,Integer> entry = maxHeap.poll();
            res.add(entry.getKey());
        }
        return res;
    }

	// use treeMap. Use freqncy as the key so we can get all freqencies in order
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int n: nums){
            map.put(n, map.getOrDefault(n,0)+1);
        }

        TreeMap<Integer,List<Integer>> freqMap = new TreeMap();
        for(int num: map.keySet()){
            int freq=  map.get(num);
            if(!freqMap.containsKey(freq)){
                freqMap.put(freq,new LinkedList());
            }
            freqMap.get(freq).add(num);
        }

        List<Integer> res = new LinkedList();
        while(res.size()<k){
            Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();
            res.addAll(entry.getValue());
        }
        return res;
    }
}

#2019-07-11

56. Merge Intervals

Desc

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Solution

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length < 2){
            return intervals;
        }
        //remember to sort in order of first element.
        //normal order as increasing, should first minus second.
        Arrays.sort(intervals,(a,b)->(a[0]-b[0]));
        List<int[]> res = new ArrayList();
        //record the current interval.
        int[] pre = intervals[0];
        for(int i =1;i<intervals.length;i++){
            int[] cur = intervals[i];
            //if not overlap, then add to res and start a new record.
            if(pre[1] < cur[0]){
                res.add(pre);
                pre = cur;
            }else{
                pre[1] = Math.max(cur[1],pre[1]);
            }
        }

        res.add(pre);
        return res.toArray(new int[res.size()][]);
    }
}

253. Meeting Rooms II

Desc

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2
Example 2:

Input: [[7,10],[2,4]]
Output: 1

Solution

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if(intervals==null || intervals.length == 0){
            return 0;
        }
        int max = 0;
        //sort start time.
        Arrays.sort(intervals,(a,b)->(a[0]-b[0]));
        //max heap for end time.
        PriorityQueue<int[]> pq = new PriorityQueue<>(intervals.length,(a,b)->(a[1]-b[1]));
        for(int i = 0;i<intervals.length;i++){
            while(!pq.isEmpty() && intervals[i][0] >= pq.peek()[1])
                //remove all not overlaped previous meeting.
                pq.poll();
            pq.offer(intervals[i]);
            //count the current overlaped meetings.
            max = Math.max(max,pq.size());
        }
        return max;
    }
}

2019-07-17

15. 3Sum

Desc

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        //if length is smaller than 3, than it cannot be valid.
        if(nums == null || nums.length < 3){
            return res;
        }
        //sort only take O(n·logn)
        Arrays.sort(nums);
        for(int i = 0;i<nums.length-2;i++){
        	//prevent duplication
            if(i == 0 || (i>0 && nums[i-1]!= nums[i])){
	            int start = i+1;
	            int end = nums.length - 1;
	            int sum = 0 - nums[i];
	            //should not stop when found one result, should keep looking.
	            while(start < end){
	            	//once found a result.
	                if(nums[start]+nums[end] == sum){
	                    res.add(Arrays.asList(nums[i],nums[start],nums[end]));
	                    //prevent duplication.
	                    while(start < end && nums[start]==nums[start+1]) start++;
	                    while(start < end && nums[end]==nums[end-1]) end--;
	                    //don't forget to move forward for next search;
	                    start++;
	                    end--;
	                }else if(nums[start]+nums[end] < sum) {
	                	//if the result is too small, than moving start to right by one will increase the sum.
	                	start++;
	                }else end--;
	            }
        }
    }
        return res;
    }
}

937. Reorder Log Files

Desc

You have an array of logs. Each log is a space delimited string of words.

For each log, the first word in each log is an alphanumeric identifier. Then, either:

Each word after the identifier will consist only of lowercase letters, or; Each word after the identifier will consist only of digits. We will call these two varieties of logs letter-logs and digit-logs. It is guaranteed that each log has at least one word after its identifier.

Reorder the logs so that all of the letter-logs come before any digit-log. The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties. The digit-logs should be put in their original order.

Return the final order of the logs.

Example 1:

Input: ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
Output: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]


Note:

0 <= logs.length <= 100
3 <= logs[i].length <= 100
logs[i] is guaranteed to have an identifier, and a word after the identifier.

Solution

class Solution {
    public String[] reorderLogFiles(String[] logs) {
    	//the main idea is to create your own compare rules.
        Comparator<String> comp = new Comparator<String>(){
            @Override
            public int compare(String s1, String s2){
                String[] split1 = s1.split(" ",2);
                String[] split2 = s2.split(" ",2);
                boolean isDigit1 = Character.isDigit(split1[1].charAt(0));
                boolean isDigit2 = Character.isDigit(split2[1].charAt(0));
                //situation 1: both are letter.
                if(!isDigit1 && !isDigit2){
                    int com = split1[1].compareTo(split2[1]);
                    if(com == 0){
                    	//if ties, than compare first.
                        return split1[0].compareTo(split2[0]);
                    }else{
                    	//if not, just return.
                        return com;
                    }
                }else{
                	//if one of them is digit, than letter should be larger.
                    return isDigit1 ? (isDigit2 ? 0 : 1) : -1;
                }
            }
        };

        Arrays.sort(logs,comp);
        return logs;
    }
}

5. Longest Palindromic Substring

Desc

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

Solution

public class Solution {
private int lo, maxLen;

public String longestPalindrome(String s) {
	int len = s.length();
	if (len < 2)
		return s;

    for (int i = 0; i < len-1; i++) {
     	extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
     	extendPalindrome(s, i, i+1); //assume even length.
    }
    return s.substring(lo, lo + maxLen);
}

private void extendPalindrome(String s, int j, int k) {
	while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
		j--;
		k++;
	}
	if (maxLen < k - j - 1) {
		lo = j + 1;
		maxLen = k - j - 1;
	}
}}

2019-07-21

2. Add Two Numbers

Desc

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode c1 = l1;
        ListNode c2 = l2;
        ListNode sentinel = new ListNode(0);
        ListNode d = sentinel;
        int sum = 0;
        while (c1 != null || c2 != null) {
            sum /= 10;
            if (c1 != null) {
                sum += c1.val;
                c1 = c1.next;
            }
            if (c2 != null) {
                sum += c2.val;
                c2 = c2.next;
            }
            d.next = new ListNode(sum % 10);
            d = d.next;
        }
        if (sum / 10 >= 1) {
            d.next = new ListNode(sum/10);
        }
        return sentinel.next;
    }
}

200. Number of Islands

Desc

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1
Example 2:

Input:
11000
11000
00100
00011

Output: 3

Solution

class Solution {
    //main idea is that whenever an island was found, use recursion to set all island to 0, so the island will only be counted once.
    public int numIslands(char[][] grid) {
        int count = 0;
        if(grid.length == 0){
            return 0;
        }
        //iterate through all nodes to find all possible island.
        for(int  i = 0;i<grid[0].length;i++){
            for(int j = 0; j<grid.length;j++){
                if(grid[j][i] == '1'){
                    count++;
                    helper(grid,i,j);
                }
            }
        }
        return count;
    }

    //the function is to use recursion to set whole island to 0.
    private void helper(char[][] grid, int x, int y){
        //invalid cord will simply return.
        if(x<0 || y<0 || x>=grid[0].length || y>= grid.length){
            return;
        }
        //set to 0.
        grid[y][x] = 0;
        //remember to check validation before check grid[y][x].
        if(x > 0 && grid[y][x-1] == '1'){
            helper(grid,x-1,y);
        }
        if(x < grid[0].length-1 && grid[y][x+1] == '1'){
            helper(grid,x+1,y);
        }
        if(y> 0 && grid[y-1][x] == '1'){
            helper(grid,x,y-1);
        }
        if(y<grid.length-1 && grid[y+1][x] == '1'){
            helper(grid,x,y+1);
        }

    }
}

2019-07-24

3. Longest Substring Without Repeating Characters

Desc

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

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution

//the basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string , and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Note that the two pointers can only move forward.
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s==null || s.length()==0){
            return 0;
        }
        HashMap<Character,Integer> map = new HashMap();
        int max = 0;
        for(int i = 0,j = 0;i<s.length();i++){
            if(map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }
}

21. Merge Two Sorted Lists

Desc

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        if(l1.val > l2.val){
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }else{
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }
    }
}

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null && l2==null){
            return null;
        }
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        while(l1 !=null && l2 != null){
            if(l1.val <= l2.val){
                prev.next = l1;
                l1 = l1.next;
            }else{
                prev.next = l2;
                l2 = l2.next;
            }
            //don't forget to move prev to next.
            prev = prev.next;
        }
        if(l1 != null){
            prev.next = l1;
        }
        if(l2 != null){
            prev.next = l2;
        }
        return dummy.next;
    }
}

2019-07-29

206. Reverse Linked List

Desc

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution

```java class Solution { public ListNode reverseList(ListNode head) { if(head == null){ return null; } ListNode dummy = new ListNode(0); dummy.next = head; ListNode pre = dummy; ListNode cur = dummy.next;; ListNode than = cur.next; //pre->cur->than // 3 -> 1 -> 2 while(than != null){ cur.next = than.next; than.next = pre.next; pre.next = than; than = cur.next; } return dummy.next;

} }

class Solution { public ListNode reverseList(ListNode head) { return helper(head,null); }

private ListNode helper(ListNode head, ListNode newHead){
    if(head == null){
        return newHead;
    }
    ListNode next = head.next;
    head.next = newHead;
    return helper(next,head);