剑指Offer-python实现（四）

34. 第一个只出现一次的字符

python3.6可运行
在python3.5及以下版本中字典是乱序的
def FirstNotRepeatingChar(self, s):
  res = {}
      for i, v in enumerate(s):
          res[v] = (res.get(v, (0, i))[0] + 1, i)
      for v in res.values():
          if v[0] == 1:
              return v[1]
      else:
          return -1

修改后
# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        if not s:
            return -1
        res = {}
        for i, v in enumerate(s):
            if v not in res:
                res[v] = i
            else:
                res[v] = -1
        min_index=[]
        for k,v in res.items():
            if v != -1:
                min_index.append(v)
        return min(min_index)

35.数组中的逆序对
直观的遍历数组每一项，再与其后面的数作比较
但是很明显时间复杂度为O(n^2)提交直接报超时了

def InversePairs(self, data):
        # write code here
        n = 0
        length = len(data)
        for i in range(length):
            for j in range(i+1,length):
                if data[i] > data[j]:
                    n += 1
        return n%1000000007

改进后的方法，首先拷贝一份源数组，对拷贝数组排序，然后从最小数开始查看其在源数组的索引位置，可以看出索引左边的数与当前最小数都成逆序对，索引数就是逆序对数，记录下来。然后删除当前最小数，重复查看即可
时间复杂度为n(logn)
牛客网关于这道题使用python通不过……

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        sortData = sorted(data)
        count = 0
        for i in sortData:
            pos = data.index(i)
            count += pos
            data.pop(pos)
        return count

    def quick_sort(self, data):
        if len(data) < 2:
            return data
        left = self.quick_sort([i for i in data[1:] if i <= data[0]])
        right = self.quick_sort([j for j in data[1:] if j > data[0]])
        return left + [data[0]] + right

36. 两个链表的第一个公共结点

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
  
class Solution:
    def FindFirstCommonNode(self, head1, head2):
        # write code here
        list1 = []
        list2 = []
        node1 = head1
        node2 = head2
        while node1:
            list1.append(node1.val)
            node1 = node1.next
        while node2:
            if node2.val in list1:
                return node2
            else:
                node2 = node2.next

37. 统计一个数字在排序数组中出现的次数
用list.count()很简单
不过看见有序数组还是用二分查找吧

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        def BiSearch(data, k):
            L = len(data)
            if L == 0:
                return 0
            if L == 1 and data[0] == k:
                return 1
            mid = L >> 1
            if data[mid] == k:
                return 1 + BiSearch(data[:mid],k) + BiSearch(data[mid+1:],k)
            elif data[mid] < k:
                return BiSearch(data[mid+1:],k)
            elif data[mid] > k:
                return BiSearch(data[:mid],k)
        return BiSearch(data,k)

38.二叉树的深度

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if pRoot == None:
            return 0
        nLeft = self.TreeDepth(pRoot.left)
        nRight = self.TreeDepth(pRoot.right)
        return (nLeft+1 if nLeft > nRight else nRight +1)

39. 平衡二叉树

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if not pRoot:
            return True
        l  = r = 0
        lRoot = pRoot.left
        rRoot = pRoot.right
        while lRoot:
            l+=1
            lRoot=lRoot.left
        while rRoot:
            r+=1
            rRoot=rRoot.right
        if  l==r:
            return True

40. 数组只出现一次的数字

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        #tmp = set()
        tmp = []
        for a in array:
            if a in tmp:
                tmp.remove(a)
            else:
                tmp.append(a)
        return tmp

41. 和为S的连续正数序列
双指针

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        l_num = [i for i in range(1, tsum + 1)]
        start = 0
        end = 2
        res = []
        while end - start >= 2 and end < tsum:
            a = sum(l_num[start:end])
            if a < tsum:
                end += 1
            elif a > tsum:
                start += 1
            else:
                res.append(l_num[start:end])
                start += 1
        return res

42. 和为S的两个数
还是用双指针，因为是递增数列，所以指针从两边取

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        start = 0
        end = len(array)-1
        while end - start >=2:
            if array[start]+array[end] > tsum:
                end -= 1
            elif array[start]+array[end] < tsum:
                start += 1
            else:
                return [array[start],array[end]]
        return[]

43. 左旋转字符串

# -*- coding:utf-8 -*-
class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        return s[n:]+s[:n]

可以用切片做，更科学的是使用多次翻转

# -*- coding:utf-8 -*-
class Solution:
    def LeftRotateString(self, s, n):
        if not s: return s
        s = list(s)
        self.reverse(s, 0, n - 1)
        self.reverse(s, n, len(s) - 1)
        self.reverse(s, 0, len(s) - 1)
        return ''.join(s)

    def reverse(self, s, start, end):
        while start < end:
            s[start], s[end] = s[end], s[start]
            start += 1
            end -= 1

44. 翻转单词顺序列

# -*- coding:utf-8 -*-
class Solution:
    def ReverseSentence(self, s):
        # write code here
        if not s.strip():
            return s
        res = " ".join(reversed(s.split()))
        return res

剑指Offer-python实现（四）

推荐阅读更多精彩内容