索鸟网

  1. 首页
  2. 剑指offer之Python练习二

剑指offer之Python练习二


1.输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if len(tinput)<k:
            return []
        tinput.sort()
        return tinput[:k]

2.连续子数组的最大和;例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。

class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        s=0
        maxl=[]
        for i in array:
            s+=i
            if s > 0:
                maxl.append(s)
            else:
                s=0
        if not maxl:
            return -1
        return max(maxl)
3.求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count=0
        m=1
        while m<=n:
            count+=(n // m + 8) // 10 * m + (n // m % 10 == 1) * (n % m + 1)
            m*=10
        return count

4.统计一个数字在排序数组中出现的次数。

class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        return data.count(k)

class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        l = len(data)
        c = 0
        for j in range(l):
            if data[j] == k:
                s += 1
        return s

5.一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        tmp=[]
        for i in array:
            if i not in tmp:
                tmp.append(i)
            else:
                tmp.remove(i)
        return tmp
6.他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?

class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        tmp=[]
        t=[i for i in range(tsum)]
        for i in range(1,tsum/2+1):
            for j in range(i+1,tsum):
                if sum(t[i:j+1]) == tsum:
                    tmp.append(t[i:j+1])
        return tmp
7.输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        tmp=[]
        for i in array:
            if tsum-i in array:
                tmp.append([i,(tsum-i)])
        if tmp:
            return tmp[0]
        else:
            return tmp
8.汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S,请你把其循环左移K位后的序列输出。例如,字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!

class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        c=0
        if n>len(s):
            return ""
        while c<n:
            s=s+s[c]
            c+=1
        return s[n:]
9.Fish每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?

class Solution:
    def ReverseSentence(self, s):
        # write code here
        s1=s.split(" ")
        s1.reverse()
        return " ".join(s1)
10.求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

class Solution:
    def Sum_Solution(self, n):
        # write code here
        def f(x,y):
            return x+y
        return reduce(f,range(n+1))
11.写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。

class Solution:
    def Add(self, num1, num2):
        # write code here
        s=[]
        s.append(num1)
        s.append(num2)
        return sum(s)

12.给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。

class Solution:
    def multiply(self, A):
        # write code here
        s=1
        B=[]
        for i in range(len(A)):
            arr = A[:i] + A[i+1:]
            for j in arr:
                s*=j
            B.append(s)
            s=1
        return B









来源地址:http://blog.csdn.net/haoze999/article/details/78229909 版权归作者所有!

相关教程

  • 剑指offer之Python练习三

    1.用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。 class Solution: def __init__(self): self.stack1=[] self.stack2=[] def push(self, node): # write code here self.sta
  • 剑指offer之Python练习一

    1.在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 # -*- coding:utf-8 -*- class Solution: # array 二维列表 def Find(self, target, array): # write code
  • 剑指Offer

    数组 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。 请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 public static boolean Solution(int target, int[][] a){ if(a == null || a.length
  • 剑指offer系列算法

    1 . Reverse Linked List /** 1. Definition for singly-linked list. 2. function ListNode(val) { 3. this.val = val; 4. this.next = null; 5. } */ /** 6. @param {ListNo
  • 剑指offer 34 丑数

    题目描述 把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。 思路 按照顺序生成丑数。把数组中每个数依次乘以2,3,5,得到的最小的数作为下一个丑数,同时记录下来下次开始遍历的index。 代码 # -*- coding:utf-8 -*- class
  • 剑指offer第三题Java

    虽然很多都实现过了,不过还是记录下自己的实现吧/** *    public class ListNode { *        int val; *        ListNode next = null; * *    &nbs
  • 剑指offer之旋转数组的最小数字

    题目描述:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 思路:对于旋转数组,使用二分法来查找最小元素。取中间mid元素,如果array[mid]>array[end],说明最小元素应该在m
  • 剑指offer:构建乘积数组

    题目描述 给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…A[i-1]*A[i+1]…*A[n-1]。不能使用除法。 分析 重点在于不能用除法,其实我觉得如果不说这一条的话,我们可能直接想到的就是用除法,算出A中所有元素的乘积除以A[i]直接就可以获得B[i]了,现在不能用,那就一个一个乘吧,跳过A[i]。代码如下: