LeetCode每周记录-4

给出一个目标数字和一个数组，在这个数组里面找三个相加起来最接近目标数字的组合。用的方法其实和找三个数相加起来是0那道题一样，先排序，然后按顺序固定一个数，用两个指针搜索的形式，注意避免重复搜索即可。代码：

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        totalLength = len(nums)
        if totalLength <= 3: return sum(nums)
        nums = sorted(nums)
        currClosest = sum([nums[0], nums[1], nums[-1]])
        for i in xrange(totalLength - 2):
            if i > 0 and nums[i] == nums[i - 1]: continue
            l, r = i + 1, totalLength - 1
            while(l < r):
                sumRet = nums[i] + nums[l] + nums[r]
                if sumRet == target:
                    return target
                elif abs(currClosest - target) > abs(sumRet - target):
                    currClosest = sumRet
                else:
                    if sumRet > target:
                        r -= 1
                    else:
                        l += 1
        return currClosest

2-9的数字能代表的字母如图所示，给出一串数字号码，列出数字转换成字母后的所有可能性。题目比较简单，把所有可能性列出来即可。

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        digitToLetter = {
            '2': ['a', 'b', 'c'],
            '3': ['d', 'e', 'f'],
            '4': ['g', 'h', 'i'],
            '5': ['j', 'k', 'l'],
            '6': ['m', 'n', 'o'],
            '7': ['p', 'q', 'r', 's'],
            '8': ['t', 'u', 'v'],
            '9': ['w', 'x', 'y', 'z']
        }
        currCombinations = []
        for digit in digits:
            if digit in digitToLetter:
                if len(currCombinations) == 0:
                    currCombinations = digitToLetter[digit]
                else:
                    _currCombinations = []
                    for letter in digitToLetter[digit]:
                        _currCombinations += map(lambda x:x+letter, currCombinations)
                    currCombinations = _currCombinations
        return currCombinations

 3Sum的升级版，从数组里面找出所有相加为0的四个数组合。我这里沿用了3Sum的办法，固定两个数，然后两个指针从这两个数右侧的两端开始找可能性，跑下来发现时间用了很多，看了别人的解法，主要在固定两个数的时候加了几步筛选步骤，避免了两个活动指针不必要的寻找。我的代码：

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        allPossibilities = []
        totalLength = len(nums)
        if totalLength < 4: return allPossibilities
        nums = sorted(nums)
        for i in xrange(totalLength - 3):
            if i >= 1 and nums[i] == nums[i - 1]: continue　　# 这里可以继续优化
            for _i in xrange(i + 1, totalLength - 2):
                if _i > (i + 1) and nums[_i] == nums[_i - 1]: continue　　# 这里可以继续优化
                l, r = _i + 1, totalLength - 1
                while(l < r):
                    sumRet = sum([nums[i], nums[_i], nums[l], nums[r]])
                    if sumRet == target:
                        allPossibilities.append([nums[i], nums[_i], nums[l], nums[r]])
                        l += 1
                        while(nums[l] == nums[l - 1] and l < r): l += 1
                    elif sumRet < target:
                        l += 1
                    else:
                        r -= 1
        return allPossibilities

 

给出一个数字n和一串链表，把这个链表的倒数第n个节点删除（只能对链表进行一次遍历）。我的做法是一边遍历链表一边把链表的节点存到一个数组里面，最后根据数组的长度找到第n个节点，然后利用数组存下来的节点直接进行链表节点的切割。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        nodeList = []
        p = head
        while(p):
            nodeList.append(p)
            p = p.next
        if n == len(nodeList):
            head = head.next
        else:
            preNode = nodeList[-(n+1)]
            preNode.next = None if n == 1 else nodeList[-(n-1)]
        return head
        

 检查给出的括号字符串是否正确（对称），利用栈可以简单的处理这道题。遇到左括号压栈，遇到右括号弹栈并检查这对括号是否匹配，不匹配直接返回False，直到字符串遍历完毕，最后栈里面是空的，则是一个正确的括号字符串。

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        pre = ['(', '{', '[']
        suf = [')', '}', ']']
        sufToPre = {')': '(', '}': '{', ']': '['}
        q = []
        for letter in s:
            if letter in pre:
                q.append(letter)
            elif letter in suf:
                if q == [] or q.pop() != sufToPre[letter]:
                    return False
            else:
                return False
        return True if q == [] else False