Two-Pointers

题目要求A magical string S consists of only '1' and '2' and obeys the following rules:The string S is magical because concatenating the number of contiguous occurrences of characters '1' and '2' generates the string S itself.The first few elements of string S is the following: S = "1221121221221121122……"If we group the consecutive '1's and '2's in S, it will be:1 22 11 2 1 22 1 22 11 2 11 22 ......and the occurrences of '1's or '2's in each group are:1 2 2 1 1 2 1 2 2 1 2 2 ......You can see that the occurrence sequence above is the S itself.Given an integer N as input, return the number of '1's in the first N number in the magical string S.Note: N will not exceed 100,000.Example 1:Input: 6Output: 3Explanation: The first 6 elements of magical string S is "12211" and it contains three 1's, so return 3.这题是描述了一个魔法字符串，该字符串完全由数字1和2构成。这个字符串的魔法点在于，如果将该该字符串连续的数字数量进行统计并且构成一个新的字符串，会发现新的字符串与原来的字符串完全相同。比如1 22 11 2 1 22 1 22 11 2 11 22字符串，经过统计后发现有1个1，2个2，2个1，1个2，1个1，2个2，1个1，2个2，2个1，1个2，2个1，2个2，将统计的数量合并为新的字符串，会发现新的字符串为1 22 11 2 1 22 1 22，和原字符串完全匹配。 ...

ProblemGiven a non-empty, singly linked list with head node head, return a middle node of linked list.If there are two middle nodes, return the second middle node.Example 1:Input: [1,2,3,4,5]Output: Node 3 from this list (Serialization: [3,4,5])The returned node has value 3. (The judge’s serialization of this node is [3,4,5]).Note that we returned a ListNode object ans, such that:ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.Example 2:Input: [1,2,3,4,5,6]Output: Node 4 from this list (Serialization: [4,5,6])Since the list has two middle nodes with values 3 and 4, we return the second one.Note:The number of nodes in the given list will be between 1 and 100.SolutionSOL.1class Solution { public ListNode middleNode(ListNode head) { ListNode fast = head, slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } return slow; }}SOL.2class Solution { public ListNode middleNode(ListNode head) { ListNode fast = head, slow = head; int n = 1; while (fast.next != null) { fast = fast.next; n++; } int k = n/2; while (k != 0) { slow = slow.next; k–; } return slow; }} ...

ProblemGiven an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.You may return any answer array that satisfies this condition.Example 1:Input: [3,1,2,4]Output: [2,4,3,1]The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.Note:1 <= A.length <= 50000 <= A[i] <= 5000Solutionclass Solution { public int[] sortArrayByParity(int[] A) { if (A == null || A.length < 2) return A; int i = 0, j = 0; while (j < A.length) { while (i < j && A[i]%2 == 0) i++; if (A[j]%2 == 0) { int temp = A[i]; A[i] = A[j]; A[j] = temp; i++; } j++; } return A; }} ...

ProblemGiven a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.Example 1:Input: [1,0,1,1,0]Output: 4Explanation: Flip the first zero will get the the maximum number of consecutive 1s.After flipping, the maximum number of consecutive 1s is 4.Note:The input array will only contain 0 and 1.The length of input array is a positive integer and will not exceed 10,000Follow up:What if the input numbers come in one by one as an infinite stream? In other words, you can’t store all numbers coming from the stream as it’s too large to hold in memory. Could you solve it efficiently?Solutionclass Solution { public int findMaxConsecutiveOnes(int[] nums) { int max = 0, lastZeroIndex = -1; int l = 0, r = 0; while (r < nums.length) { if (nums[r] == 0) { l = lastZeroIndex+1; lastZeroIndex = r; } max = Math.max(max, r-l+1); r++; } return max; }} ...