发表于 | 分类于

Remove Duplicates from Sorted List

从排序链表中删除重复元素。
Description

解题思路：
依次比较相邻的两个链表元素，若值相等，则将前一个节点的next引用为后一个节点的后一个节点。使用cur来依次向下遍历元素，最后返回head。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur = head
        
        while cur:
            while cur.next and cur.next.val==cur.val:
                cur.next = cur.next.next
            cur = cur.next
        return head

发表于 | 分类于

给定一个排序数组，将数组中的重复元素去除，并返回修改后的数组长度。
Description
解题思路：
题目要求不能分配额外空间，由于python中列表是传引用，因此可以对传入的列表进行原地修改。由于数组已经排序，因此可以通过新建一个下标两两比较删除重复的元素。
注意：
题目中 It doesn’t matter what you leave beyond the new length，因此超出长度部分的重复元素不需要考虑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        
        newIndex = 0
        for i in range(1, len(nums)):
            if nums[i] != nums[newIndex]:        
                newIndex += 1
                nums[newIndex] = nums[i]
                
        return newIndex+1

发表于 | 分类于

Merge Two Sorted Lists

合并两个有序链表。
Description

解题思路：
此题比较简单，采用迭代的方式。由于链表已经是有序的，所以依次比较两个链表当前元素的大小，然后将较小的元素加入到新的链表中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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
        """
        result = cur = ListNode(1)       # 第一个节点可以任取
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 or l2
        return result.next

发表于 | 分类于

Maximum Subarray

最大子串和问题：从一个数组中找出一个子串使其和最大。
Description

tips:
子串是指数组中连续的若干个元素，而子序列只要求各元素的顺序与其在数组中一致，而没有连续的要求。

解题思路：
自己没有想出来，直接借鉴了网上的动态规划思路，我觉得下面是一些解决的关键点：

  • 对于array[1…n]，如果array[i…j]就是满足和最大的子串，那么对于任何k(i<=k<=j)，我们有array[i…k]的和大于0。具体证明
  • 假设已知0, .., k的最大和sum[k]以后，则0, …, k+1的最大和sum[k+1]分为以下两种情况：
    1）若sum[k]>=0，则sum[k+1]=sum[k]+A[k+1]。代码中即curSum = curSum+nums[i]。
    2）若sum[k]<0，另起一个SubArray，令sum[k+1]=A[k+1]。代码中即curSum = nums[i]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return 0
    
    curSum = maxSum = nums[0]
    for i in range(1, len(nums)):
        curSum = max(nums[i], curSum+nums[i])
        maxSum = max(maxSum, curSum)
        
    return maxSum

发表于 | 分类于

Longest Common Prefix

最长相同前缀：给定一个字符串数组，找出其中最长的共同前缀。这里leetcode并没有说明共同前缀是指两两之间的前缀还是所有字符串的前缀，实际题意是指采用所有字符串的共同前缀。
Description

解题思路：
若字符串数组为空则返回空字符串；
否则从所有字符串中找出最短的字符串，依次将最短字符串的每个元素和所有字符串对应位置上的元素进行比较，若不同则停止比较并返回；
若全部相同，则返回最短字符串。

1
2
3
4
5
6
7
8
9
10
11
if not strs:
    return ""

shortest = min(strs, key=len)

for i in range(len(shortest)):
    for string in strs:
        if shortest[i] != string[i]:
            return shortest[:i]
        
return shortest

改进：
将字符串数组进行排序(注意，这里是按照字母表顺序排序，而不是根据长度排序），排序后实际只要比较第一个和最后一个字符串的共同前缀即可，因此大大提升了运行时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
if not strs:
          return ""
      
      strs.sort()
      first = strs[0]
      last = strs[-1]
      minlen = min(len(first), len(last))
                  
      for i in range(minlen):
          if first[i]!=last[i]:
              return first[:i]
              
      return first[:minlen]

发表于 | 分类于

Linked List Cycle

判断单链表是否存在环。
Description

解题思路：
一个单链表如果不存在环，则最后一个元素的下一个节点必然为null.
如果单链表存在环，则：
设置两个指针，一个慢指针和一个快指针。将链表的环想象成是一个圆形操场，两个人在同一起跑线开始绕着操场无限循环跑，那么快的人必然会再一次和慢的人相遇，即快指针的元素和慢指针的元素相同时，即说明存在环。
在代码中，慢指针设置为每次走一步，即slow=slow.next,快指针设置为每次走两步，即fast=fast.next.next。实际步数设置是可以任取的，只是循环次数不同，如可以设置fast=fast.next.next.next。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head==None:
            return False
        
        slow = head
        fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
            if slow==fast:
                return True
        return False

改进：
由于每次循环都要判断是否到达最后一个节点，因此leetcode上提供了另一种思路，即采取异常的方式。

“Easier to ask for forgiveness than permission.”

1
2
3
4
5
6
7
8
9
10
def hasCycle(self, head):
    try:
        slow = head
        fast = head.next
        while slow is not fast:
            slow = slow.next
            fast = fast.next.next
        return True
    except:
        return False

发表于 | 分类于

Intersection of Two Linked Lists

寻找两个无环链表的交点。
Description

解题思路：

  1. 如果两个链长度相同的话，那么对应的一个个比下去就能找到；
  2. 如果两个链长度不相同，分别计算出两个链表的长度，计算出长度差值，然后让长度更长的那个链表从头节点先遍历长度差的步数，这样以后两个链表按尾部对齐。接着长链表和短链表同步往下走，遇到的第一个相同的节点就是最早的公共节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        lenA = lenB = 0
        curA, curB = headA, headB 
        while curA is not None:
            lenA += 1
            curA = curA.next
        while curB is not None:
            lenB += 1
            curB = curB.next
        if lenA>lenB:
            for i in range(lenA-lenB):
                headA = headA.next
        else:
            for i in range(lenB-lenA):
                headB = headB.next
        while headA != headB:
            headA = headA.next
            headB = headB.next
        return headA

发表于 | 分类于

Intersection of Two Arrays

查找两个数组的共有元素。
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
Description

解题思路：
本来是想做关于排序的题目的，然后这道题的标签中就是含sort的，但我觉得用集合的方式会更简明些。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        set1 = set(nums1)
        set2 = set(nums2)
        return list(set1.intersection(set2))

tip：
set求交集函数返回的是set,因此需要通过list进行转换。

发表于 | 分类于

Implement strStr()

从字符串中找出给定子字符串的索引，若不存在则返回-1。
Description

解题思路：
用python解决这道题很简单，因为python字符串自带的find的方法可以直接实现。

1
2
3
4
5
6
7
def strStr(self, haystack, needle):
    """
    :type haystack: str
    :type needle: str
    :rtype: int
    """
    return haystack.find(needle)

不采用find()方法的解题思路：
采用brute force方式，即依次从字符串的每个位置开始，截取和子字符串相同长度的字符串，与给定的子字符串进行比较。

1
2
3
4
5
6
7
8
9
10
def strStr(self, haystack, needle):
    """
    :type haystack: str
    :type needle: str
    :rtype: int
    """ 
    for i in range(len(haystack)-len(needle)+1):
        if haystack[i:i+len(needle)] == needle:
            return i
    return -1

改进：http://blog.csdn.net/linhuanmars/article/details/20276833
提出了一种rolling hash的方式。

发表于 | 分类于

House Robber

打家劫舍。问题本质就是从数组中找出一个或多个不相邻的数，使其和最大。

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Description

解题思路：

  1. 如果选择了抢劫上一个屋子，那么就不能抢劫当前的屋子，所以最大收益就是抢劫上一个屋子的收益；
  2. 如果选择抢劫当前屋子，就不能抢劫上一个屋子，所以最大收益是到上一个屋子的上一个屋子为止的最大收益，加上当前屋子里有的钱。

令dp[i]表示从[0, …, i]数组中能够得到的最大收益，显然，dp[0]=nums[0], dp[1]=max(dp[0],dp[1]), 现在计算dp[i+1]:

dp[i+1]=max(dp[i], dp[i-1]+nums[i+1])

其中，上式包含了如下隐含信息：
若dp[i]不包含nums[i], 所以nums[i+1]可以和dp[i]相加，但此时dp[i]=dp[i-1],所以dp[i-1]+nums[i+1]与dp[i]+nums[i+1]的值相等；
若dp[i]包含nums[i]，则nums[i+1]不可以和dp[i]相加，所以只存在nums[i+1]+dp[i-1]。

实际计算时只需要保存两个变量即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums)<=1:
            return 0 if len(nums)==0 else nums[0]
        # 保存上一次的收益
        last = nums[0]
        # 保存当前收益
        cur = max(nums[0], nums[1])
        for i in range(2, len(nums)) :
            tmp = cur
            cur = max(last+nums[i], cur)
            last = tmp
        return cur

tip:
python中的三目运算符不像其他语言, 其他的一般都是:

判定条件?为真时的结果:为假时的结果

而在python中的格式为:

为真时的结果 if 判定条件 else 为假时的结果