two_pointer

11、Container With Most Water

给定n个数，a1,a2,...,an.在坐标上的位置为（i,ai）,求其中两个点到X轴的线段与x轴围成的面积最大。

思路：
1、暴力法：用两个for循环，超时了，看来还是得动脑子。
2、贪心法，从两边向中间夹逼，两个指针指向列表两端，当左边高度＜右边时，制约在左边，右边往左移肯定找不到更大的，应该左边往右移，反之也成立。
但注意到，每次都会比较一次，但是当右移或左移的数比原来小时，没有必要进行计算，因为肯定会比原来结果小，如何优化代码。

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        length = len(height) 
        if length < 2:
            return -1
        
        left = 0
        right = length - 1
        max_contain = 0
        while left < right:
            max_contain = max(max_contain, min(height[left] , height[right]) * (right - left))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1                                     
        return max_contain
                    
            
if __name__ == '__main__':
    solution = Solution()
    print solution.maxArea([1,3,56,57,8])

优化后，

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        length = len(height) 
        if length < 2:
            return -1
        
        left = 0
        right = length - 1
        max_contain = 0
        while left < right:
            max_contain = max(max_contain, min(height[left] , height[right]) * (right - left))
            if height[left] < height[right]:
                j = left
                left += 1
                
                while height[left] <= height[j] and left < right: #若＜原来的数，直接下一个，算都不用算
                    left += 1
            else:
                j = right
                right -= 1
                
                while height[right] <= height[j] and left < right:
                    right -= 1                                       
        return max_contain                               
if __name__ == '__main__':
    solution = Solution()
    print solution.maxArea([1,2])

two sum,three sum 见unckassify文件

19、Remove Nth Node From End of List

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.

这个算是很基本的链表删除问题，换了个提法，就是删除倒数第几个，下面的程序还有很多不足，为最一般写法，一是判断是否为只有一个元素，二是判断删除的是否是链表首元素

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        p = head
        length = 0
        while p != None:
            length += 1
            p = p.next
        if length == 1:
            return None
        p = head
        current = head.next
        if length - n != 0:
            for i in range(length - n -1):
                current = current.next
                p = p.next
            p.next = current.next
        else:
            head = head.next
        return head

class Solution:
    # @return a ListNode
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(-1)
        dummy.next = head
        slow, fast = dummy, dummy
        
        for i in xrange(n):
            fast = fast.next
            
        while fast.next:
            slow, fast = slow.next, fast.next            
        slow.next = slow.next.next        
        return dummy.next

上面程序比较简单明了，引入一个虚拟头节点，避免了判断删除首元素，而且只遍历一次链表。

61. Rotate List

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        p = q = head
        length = 0
        while q:
            length += 1
            q = q.next
        k %= length
        if k == 0:
            return head
        slow, fast = head, head
        for i in xrange(k):
            fast = fast.next
        while fast.next is not None:
            slow, fast = slow.next, fast.next
        head = slow.next
        slow.next, fast.next = None, p
        return head

上面的思路完全是根据19题出发，当对列表从后往前计算N个数时，都可以采用slow，fast两个指针方式。但是，这道题以这种思路出发需要考虑的问题有：1、k大于链表总长度，只能取余，则需要计算链表长度；2、一些特殊情况考虑，比如，链表为空，或者只含一个元素。3、k为0.
另一种较简单方法：

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        n, p = 1, head
        while p.next:
            n += 1
            p = p.next
        p.next = head
        for i in xrange(n - k % n):
            p = p.next
        head = p.next
        p.next = None
        return head

80. Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) < 3:
            return len(nums)
        count = 2
        for i in xrange(2, len(nums)):
            if nums[i] != nums[count-2]:
                nums[count] = nums[i]
                count += 1

        return count

这道题不是简单计算个数，还要求数组in place移动。

86. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        dummy1, dummy2 = ListNode(-1), ListNode(-1)
        small, big = dummy1, dummy2
        while head is not None:
            if head.val < x:
                small.next = head
                small, head = small.next, head.next
            else:
                big.next = head
                big, head = big.next, head.next
                
        small.next = dummy2.next
        big.next = None
        return dummy1.next

125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

class Solution(object):
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        left, right = 0, len(s) - 1
        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            if s[left].lower() != s[right].lower():
                return False
            left, right = left + 1, right - 1
        return True

283. Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        count, length = 0, len(nums)
        for i in xrange(length):
            if nums[i]:
                nums[count] = nums[i]
                count += 1
        while count <= length - 1:
            nums[count] = 0
            count += 1

下面方法更为简洁，不断交换位置。

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        pos = 0
        for i in xrange(len(nums)):
            if nums[i]:
                nums[i], nums[pos] = nums[pos], nums[i]
                pos += 1

234. Palindrome Linked List

判断是不是回文链表，要求空间复杂度o(1),因为空间复杂度限制，不能转换为数组或者栈的操作，所以在链表本身操作。分为几个步骤，一是找到中点位置，可以使用快慢指针，二是对后半部分链表进行反转，链表反转操作比较简单，用两个指针循环前移即可。三是比较val.

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None or head.next is None:
            return True
        if head.next.next is None:
            return head.val == head.next.val
        if head.next.next.next is None:
            return head.val == head.next.next.val
        fast, slow = head.next, head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
        newHead = slow.next
        slow.next = None
        p = newHead.next
        newHead.next = None
        while p is not None:
            temp = p.next
            p.next = newHead
            newHead, p = p, temp
        while newHead:
            if newHead.val != head.val:
                return False
            newHead, head = newHead.next, head.next
        return True

整体还是比较复杂点。