Linked List Cycle II, Leetcode 解题笔记

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:
Can you solve it without using extra space?

接上一题,当两个指针重合时,说明有环,此时把一个指针放回head,然后两个指针同时一步一步前进,直到再次重合,这个重合点就是环开始的位置。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        
        ListNode fast = head;
        ListNode slow = head;
     
        while(fast != null && slow != null){
            fast = fast.next;
            slow = slow.next;
            if(fast != null) fast = fast.next;
            if(fast == slow) break;
        }
        if(fast == null) return null;
        slow = head;
        
        while(slow != fast){
            
            fast = fast.next;
            slow = slow.next;
            
        }
        return fast;
    }
}
Advertisements

Linked List Cycle, Leetcode 解题笔记

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

这题很经典,就是两个指针,一个每次前进一步,一个每次前进两步,如果最终两个指针重合了,那么说明有环。这个方法具体好像是可以数学证明的,因为以前见过,所以直接写code了:

/**
 * 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;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) return true;
        }
        return false;
    }
}

Word Break II, Leetcode 解题笔记

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = “catsanddog”,
dict = [“cat”, “cats”, “and”, “sand”, “dog”].

A solution is [“cats and dog”, “cat sand dog”].

这道题是上一道的变形,思路是上一题的DFS解法稍作改动,但是为了通过leetcode中的一个比较tricky的test case,要先用DP的思路判断是否有解。

public class Solution {
    ArrayList<String> wordBreak(String s, Set<String> dict) {
        int length = s.length();
        
        //create the word ending character's index list for each character
        ArrayList<ArrayList<Integer>> record = new ArrayList<ArrayList<Integer>>(length);
        for(int i = 0;i<length;i++)
            record.add(new ArrayList<Integer>());
 
        //each character can be the ending character of some word
        for(int end=length;end>=0;end--){
 
            if(end < length && record.get(end).isEmpty())
                continue;
            
            //find the starting character for the current ending character
            for(int runner = end-1;runner >= 0;runner--){
                if(dict.contains(s.substring(runner,end)))
                    record.get(runner).add(end);    //add current end to start character's list
            }
        }
        
        ArrayList<String> solutionSet = new ArrayList<String>();
        buildSolution(record,0,s,"",solutionSet);
        
        return solutionSet;
    }
 
    void buildSolution(ArrayList<ArrayList<Integer>> record, int current, String s, 
                String solution, ArrayList<String> solutionSet){
        
        //iterate on current character's word ending list
        for(Integer end : record.get(current)){
 
            String sub=s.substring(current,end);
            /*
                since the loop may have many iterations, we should keep the reference
                of "solution", rather than writing as "solution += ..."
            */
            String newSolution = solution+(current==0 ? sub : " "+sub);
            
            if(end == s.length()) 
                solutionSet.add(newSolution);
            else 
                buildSolution(record,end,s,newSolution,solutionSet);
        }
    }
 
}

Word Break, Leetcode 解题笔记

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = “leetcode”,
dict = [“leet”, “code”].

Return true because “leetcode” can be segmented as “leet code”.

首先应该想到用dfs递归来解,如下:

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        return dfs(s, dict, 0);
    }
    public boolean dfs(String s, Set<String> dict, int start){
        if(start == s.length()) return true;
        for(int i = start+1; i <= s.length(); i++){
            String cur = s.substring(start, i);
            if(dict.contains(cur)){
                if(dfs(s, dict, i)){
                    return true;
                }
            }
        }
        return false;
    }
}

但是这样比较消耗时间,所以Leetcode上通不过。

最优解应该利用DP,定义possible[i] 为S字符串上[0,i]的子串是否可以被segmented by dictionary.

那么possible[i] = true if S[0,i]在dictionary里面

= true if possible[k] == true 并且 S[k+1,j]在dictionary里面

= false if no such k exist.

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i = 1; i < s.length()+1; i++){
            for(int j = 0; j < i; j++){
                if(dp[j] && dict.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

Copy List with Random Pointer, Leetcode 解题笔记

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

思路与Clone Graph完全一样,利用hashmap来映射新旧node。

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode cur = head;
        RandomListNode newhead = new RandomListNode(0);
        RandomListNode pre = newhead;
        RandomListNode n;
        while(cur != null){
            
            n = new RandomListNode(0);
            n.label = cur.label;
            pre.next = n;
            pre = n;
            map.put(cur, n);
            cur = cur.next;
        }
        newhead = newhead.next;
        
        cur = head;
        n = newhead;
        while(cur != null){
            n.random = map.get(cur.random);
            cur = cur.next;
            n = n.next;
        }
        return newhead;
        
    }
}

Single Number II, Leetcode 解题笔记

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目中要求我们不要用额外空间来实现,也就是O(1)空间复杂度。实现的思路是基于数组的元素是整数,我们通过统计整数的每一位来得到出现次数。我们知道如果每个元素重复出现三次,那么每一位出现1的次数也会是3的倍数,如果我们统计完对每一位进行取余3,那么结果中就只剩下那个出现一次的元素。总体只需要对数组进行一次线性扫描,统计完之后每一位进行取余3并且将位数字赋给结果整数,这是一个常量操作(因为整数的位数是固定32位),所以时间复杂度是O(n)。而空间复杂度需要一个32个元素的数组,也是固定的,因而空间复杂度是O(1)。代码如下:

public int singleNumber(int[] A) {
    int[] digits = new int[32];
    for(int i=0;i<32;i++)
    {
        for(int j=0;j<A.length;j++)
        {
            digits[i] += (A[j]>>i)&1;
        }
    }
    int res = 0;
    for(int i=0;i<32;i++)
    {
        res += (digits[i]%3)<<i;
    }
    return res;
}

Single Number, Leetcode 解题笔记

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

第一反应就应该是bit操作。当然也可以用hashmap,但是会用额外空间。

复习一下XOR的性质:A XOR A = 0; A XOR B XOR A = B

public class Solution {
    public int singleNumber(int[] A) {
        int sum = 0;
        for(int i = 0; i < A.length; i++){
            sum = sum ^ A[i];
        }
        return sum;
    }
}