Minimum Size Subarray Sum leetcode

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

用滑动窗口的做法

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int left = 0;
        int right = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        while (right < nums.length) {
            sum += nums[right];
            while (sum >= s) {
                sum -= nums[left];
                min = Math.min(min, right - left + 1);
                left++;
            }
            right++;
        }
        if (min == Integer.MAX_VALUE) {
            return 0;
        } else {
            return min;
        }
        
    }
}

Two Sum II - Input array is sorted leetcode

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

时间 O(n) space O(1)

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        int[] res = new int[2];
        while (left < right) {
            if (numbers[left] + numbers[right] == target) {
                res[0] = left + 1;
                res[1] = right + 1;
                return res;
            } else if (numbers[left] + numbers[right] > target) {
                right--;
            } else {
                left++;
            }
        }
        return null;
    }
}

Rotate List leetcode

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

k的值可以大于链表长度, 大于的话用k对length取莫. 用快慢指针方法 快指针先走k步 然后一起走.

 最后快指针停在最后面的位置 (null之前),慢指针停在要翻转的前一个位置.

记录slow.next就是newhead结点, fast,next 指向原来的head, slow.next指向null

public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = head;
        ListNode slow = head;
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            cur = cur.next;
            len++;
        }
        k = k%len;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        fast.next = head;
        dummy.next = slow.next;
        slow.next = null;
        return dummy.next;
    }
    
}

Minimum Window Substring leetcode

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

这道题是字符串处理的题目，和Substring with Concatenation of All Words思路非常类似，同样是建立一个字典，然后维护一个窗口。区别是在这道题目中，因为可以跳过没在字典里面的字符（也就是这个串不需要包含且仅仅包含字典里面的字符，有一些不在字典的仍然可以满足要求），所以遇到没在字典里面的字符可以继续移动窗口右端，而移动窗口左端的条件是当找到满足条件的串之后，一直移动窗口左端直到有字典里的字符不再在窗口里。在实现中就是维护一个HashMap，一开始key包含字典中所有字符，value就是该字符的数量，然后遇到字典中字符时就将对应字符的数量减一。算法的时间复杂度是O(n),其中n是字符串的长度，因为每个字符再维护窗口的过程中不会被访问多于两次。空间复杂度则是O(字典的大小)，也就是代码中T的长度。

public class Solution {
    public String minWindow(String s, String t) {
        int m = s.length();
        int n = t.length();
        if (m == 0 || n == 0 || s == null || t == null) {
            return "";
        }
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < n; i++) {
            if (!map.containsKey(t.charAt(i))) {
                map.put(t.charAt(i), 1);
            } else {
                map.put(t.charAt(i), map.get(t.charAt(i)) + 1);
            }
        }
        int minL = m+1;
        int count = 0;
        int minstart = 0;
        int left = 0;
        for (int i = 0; i < m; i++) {
           if (map.containsKey(s.charAt(i))) {
               map.put(s.charAt(i), map.get(s.charAt(i)) - 1);
               if (map.get(s.charAt(i)) >= 0) {
                   count++;
               }
               while (count == n) {
                   if (i - left + 1 < minL) {
                       minL = i - left + 1;
                       minstart = left;
                   }
                   if (map.containsKey(s.charAt(left))) {
                       map.put(s.charAt(left), map.get(s.charAt(left)) + 1);
                       if (map.get(s.charAt(left)) > 0) {
                           count--;
                       }
                   }
                   left++;
               }
           } 
        }
        if (minL > m) {
            return "";
        }
        return s.substring(minstart, minstart + minL);
    }
}

Substring with Concatenation of All Words (hard) leetcode

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in wordsexactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].

题意：给定一个字符串S和一个字符串数组L，L中的字符串长度都相等，找出S中所有的子串恰好包含L中所有字符各一次，返回子串的起始位置。

用一个hashmap把words里面所有单词放入, 出现次数为单词的value 作为字典

再用另一个hashmap 记录当前单词

因为每个单词长度一样，外层循序只许循环wordLen次，每次指针挪一次，每一次循环遍历整个字符串。

内层循环每次遍历一个单词，把整个S字符串遍历检查。

需要在每次大循环维护一个count，看是不是达到了给的字典字符串数量，同时维护一个index，是每个符合条件的字符串的起始index，需要存到返回结果中。

为了能够检查是不是合格字符串，在这里维护一个curDict的HashMap。



首先检查一个单词是不是在原始字典中出现，没出现的话说明这个单词肯定不符合标准，index指针指向下一个单词的起始点，计数器和curDict都要清零。


如果这个单词在原始字典里出现过，用更新原始字典的方法更新curDict，如果这个单词出现的次数没有超过原始字典里记录的次数，那么count++，如果超过了，就需要挪动指针，并把超过的从curDict删掉。


最后，如果count达到了L的length，说明找到了一个合格的字符串，那么将index存入返回结果res中，再把index挪到下一个单词处，更新curDict即可。

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int m = words.length;
        int n = words[0].length();
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return result;
        }
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for (int i = 0; i < m; i++) {//把words所有单词放入map里
            if (map.containsKey(words[i])) {
                map.put(words[i], map.get(words[i]) + 1);
            } else {
                map.put(words[i], 1);
            }
        }
        for (int i = 0; i < n; i++) {
            int count = 0;
            int left = i;
            HashMap<String, Integer> curmap = new HashMap<String, Integer>();
            for (int j = i; j <= s.length() - n; j += n) {
                String str = s.substring(j, j + n);
                if (!map.containsKey(str)) {
                    left = j + n;
                    curmap.clear();
                    count = 0;
                } else {
                    if (!curmap.containsKey(str)) {
                        curmap.put(str, 1);
                    } else {
                        curmap.put(str, curmap.get(str) + 1); 
                    }
                    if (curmap.get(str) <= map.get(str)) {//如果当前和map中都有这个单词 count++
                        count++;
                    } else {//如果这个单词出现次数>map中出现的次数
                        while (curmap.get(str) > map.get(str)) {
                            String tem = s.substring(left, left + n);

                            curmap.put(tem, curmap.get(tem) - 1);
                            if(curmap.get(tem)<map.get(tem)) {//如果是= 说明tem就是str 对于str并没有在count中+
                                count--;
                            } 
                            
                            left = left + n;
                        }
                    }
                    if (count == m) {
                        result.add(left);
                        String tem = s.substring(left, left + n);
                        curmap.put(tem, curmap.get(tem) - 1);
                        count--;
                        left += n;
                    }
                }
            }
        }
        return result;
    }
}

Longest Substring Without Repeating Characters leetcode

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

基本思路是维护一个窗口，每次关注窗口中的字符串，在每次判断中，左窗口和右窗口选择其一向前移动。同样是维护一个HashSet, 正常情况下移动右窗口，如果没有出现重复则继续移动右窗口，如果发现重复字符，则说明当前窗口中的串已经不满足要求，继续移动有窗口不可能得到更好的结果，此时移动左窗口，直到不再有重复字符为止，中间跳过的这些串中不会有更好的结果，因为他们不是重复就是更短。因为左窗口和右窗口都只向前，所以两个窗口都对每个元素访问不超过一遍，因此时间复杂度为O(2*n)=O(n),是线性算法。空间复杂度为HashSet的size,也是O(n).

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int walker = 0;
        int runner = 0;
        int max = 0;
        HashSet<Character> set = new HashSet<Character>();
        while (runner < s.length()) {
            if (set.contains(s.charAt(runner))) {
                max = Math.max(max, runner - walker);
                while (s.charAt(walker) != s.charAt(runner)) {
                    set.remove(s.charAt(walker));
                    walker++;
                }
                set.remove(s.charAt(walker));
                walker++;
            } else {
                set.add(s.charAt(runner));
                runner++;
            }
        }
        return Math.max(max, runner - walker);
    }
}

Linked List Cycle II leetcode

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

题解：(转自http://www.cnblogs.com/springfor/p/3862125.html) 

这个连同I都是很经典的题啦，刷CC150时候就折磨了半天。

其实就推几个递推公式就好。。首先看图（图引用自CC150）：

 

从链表起始处到环入口长度为：a，从环入口到Faster和Slower相遇点长度为：x，整个环长为：c。

明确了以上信息，就可以开始做运算了。。

 假设从开始到相遇，Slower走过的路程长为s，由于Faster的步速是Slower的2倍，那么Faster在这段时间走的路程长为2s。

 而对于Faster来说，他走的路程还等于之前绕整个环跑的n圈的路程nc，加上最后这一次遇见Slower的路程s。

 所以我们有：

                   2s = nc + s 

 对于Slower来说，他走的路程长度s还等于他从链表起始处到相遇点的距离，所以有：

                    s = a + x 

 通过以上两个式子代入化简有：

                    a + x = nc

                    a = nc - x

                    a = (n-1)c + c-x

                    a = kc + (c-x)

那么可以看出，c-x，就是从相遇点继续走回到环入口的距离。上面整个式子可以看出，如果此时有个pointer1从起始点出发并且同时还有个pointer2从相遇点出发继续往前走（都只迈一步），那么绕过k圈以后， pointer2会和pointer1在环入口相遇。这样，换入口就找到了。

时间复杂度 O(n)

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null){//必须包含head.next的判定
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast!= null && fast.next != null){//注意此处的判定
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast){
                break;
            }
        }
        if (fast != slow){
            return null;
        }
        fast = head;
        while (fast != slow){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
        
    }
}

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?

用双指针法， 如果faster 和slower最后遇到了则有环

时间O(n) 空间O(1)

对于是否相遇的参考：转自http://www.cnblogs.com/springfor/p/3862102.html

假设Faster确实把Slower超了而且他俩还没相遇（类似Faster一下迈了2步，Slower一下迈了一步，Faster超了Slower，但是俩人并没遇上）。那么就假设Faster现在在 i+1 位置而Slower在 i 位置。那么前一时刻，Slower肯定是在 i-1 位置，而Faster肯定在(i+1)-2位置，所以前一时刻，俩人都在 i-1 位置，相遇了。

还有一种情况就是Faster在i+2位置而slower在i位置，那么前一时刻，Faster在i位置，而Slower在 i-1位置。这样问题又回归到上面那种情况了（再往前一时刻，Faster在i-2位置，Slower在i-1-1位置，相遇）。

所以，这就证明Runner和Faster在有环的链表中肯定会相遇。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null){
            return false;
        }
        ListNode faster = head, slower = head;
        while (faster.next != null && faster.next.next != null){
            faster = faster.next.next;
            slower = slower.next;
            if (faster == slower){
                return true;
            }
        }
        return false;
    }
}

Remove Nth Node From End of List leetcode

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

首先先让faster从起始点往后跑n步。

然后再让slower和faster一起跑，直到faster==null时候，slower所指向的node就是需要删除的节点。

注意：慢指针要在dummy上而不是head上 因为可能head位的数值被删除
return也要return dummy.next 因为head可能被删除

时间O(n) 空间O(1)

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (n <= 0){
            return null;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode faster = head;
        ListNode slower = dummy;
        for (int i = 0; i < n; i++){
            if (faster == null){
                return null;
            }
            faster = faster.next;
        }
        while (faster!= null){
            faster = faster.next;
            slower = slower.next;
        }
        slower.next = slower.next.next;
        return dummy.next;
        
    }
}