4ier's Blog

Solution for Count and Say

12 Aug 2018

Count and Say

题目定义的比较难懂，查看下列序列的规律：

 1.     1
 2.     11
 3.     21
 4.     1211
 5.     111221 
 6.     312211
 7.     13112221
 8.     1113213211
 9.     31131211131221
10.     13211311123113112211

Solution for Remove Element

10 Aug 2018

Remove Element

给出的数组nums和数值val，在满足o(1)空间复杂度的前提下，计算出删除val后剩余数组的长度len，要求处理后的数组前len个元素不包含val

题目比较简单，但是有些隐藏的陷阱：

  • 遍历数组的同时删除元素，不能采用for循环进行，否则如果出现两个以上相等的元素，遍历时会跳过删除后前移的元素，如
for i,n in enumerate(nums):
    if n == val:
        del nums[i] #删除元素后，数组后面列表元素自动前移，如果删除前nums[i+1] == val，那么删除后这个val自动移动到了nums[i]的位置，但是循环已经认为这个位置的元素处理过了不会再重复处理
return len(nums)
  • 解决方案1：使用while循环和下标，控制遍历过程：
i = 0
while(i < len(nums)):
    if nums[i] == val:
        del nums[i]
    else:
        i = i + 1
return len(nums)

在遍历时使用下标i控制遍历过程，如果匹配到了要删除的元素，下标i的值不自增，可以解决上面描述的遍历问题

Implement strStr()

10 Aug 2018

Implement strStr()

给定两个字符串strA / strB，计算后者在前者第一次出现的首字母位置（java的indexOf()和C的strStr()）

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not needle:
            return 0
        if haystack == needle:
            return 0

        for i in range(len(haystack)):
            subStr = ''.join(haystack[i : i + len(needle)])
            if len(needle) > len(subStr): #在输入的两个字符很长的情况下，有可能存在资源消耗过大，因此先用长度做简单判断
                return -1

            if subStr == needle:
                return i
        return  -1

Solution for Remove Duplicates from Sorted Array

09 Aug 2018

题目要求不使用额外的空间进行去重，并且不要求指定长度后的数组元素结果

解决方案：把指针前面的子集可以作为新的数组使用即可

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        if len(nums) < 2:
            return 1
        
        index = 0
        for i in range(1, len(nums)):
            if nums[i] != nums[index]:
                index = index + 1
                nums[index] = nums[i]

        return index + 1

Solution for Merge Two Sorted Lists

09 Aug 2018

Merge Two Sorted Lists

问题是两个单向有序链表A / B合并，解题思路有两个

  • 递归

比较A和B的第一个元素a1 / b1，假设a1 < b1，那么A.next和B先合并，合并后的第一个链表节点赋值给A.next，反之亦然，直到两个链表其中一个完成遍历，将剩余的节点挂在最后一个合并节点上即可完成合并

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

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1:
            return l2
        if not l2:
            return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2