【大数据】Spark优化经验&案例--数据倾斜 《Mysql必知必会》读书笔记 jar包名中自动添加git commit id PyCharm教学视频学习笔记 《SQL基础教程》简要总结 《设计师要懂心理学》读书笔记 MySQL与MariaDB学习笔记 WDT (Folly) 安装指南 -- CentOS 7 [solved]Page build failed(Jekyll) 数据包过滤及分析实例 tshark tcpdump Scala Tour 学习总结 “Docker容器和容器云”读书笔记(1) “Docker Practice”读书笔记 “图解基础设施设计模式”小结 “图解服务器端网络架构”小结 Python网络安全编程 数据包解析笔记 华为挑战赛(1) DDoS攻击防御与云服务 基于网络回溯分析技术的异常行为分析 “Linux程序设计”小结(进程间通信) C语言编程规范(华为软件精英挑战赛) 2017阿里在线编程题--单源最短路径问题 2017年阿里在线编程题-- 数串分组 Uinx/Linux上的帮助查询命令 你懂C,所以C++不在话下 一篇特别长的总结(C专家编程) 程序员面试金典--笔记(精华篇) C陷阱与缺陷--笔记 半小时搭建电子商务网站--opencart linux网络知识和工具(持续更新) 网卡参数查询及设置工具ethtool 高性能流量生成工具trafgen(DDoS模拟) Linux流量控制工具TC 流量控制工具TC详细说明 tcpdump过滤数据包,结果不对? Lecture 网络攻击与防御技术笔记 gotgit-git权威指南 高效使用MacOS所要知道的 shell内置字符串处理 配置ntp(知其所以然) 360黑客攻防技术分享会--记录 中毒U盘恢复--快捷键病毒 Tor--anonymity network介绍(PPT) IBM bluemix 再读《Linux Shell脚本攻略》 linux shell 学习摘记(9) linux shell 学习摘记(8) linux shell 学习摘记(7) linux shell 学习摘记(6) linux shell 学习摘记(5) linux shell 学习摘记(4) linux shell 学习摘记(3) linux shell 学习摘记(2) linux shell 学习摘记(1) firefox vim 插件 vimperator A Byte of Vim 笔记 windows注册表小知识 安全测试工具篇(开源&商业) 安全及性能测试工具(网站收集) 性能测试工具 屡试不爽的“3个”iPad使用技巧 Shell Shortcuts(和Tab键一样实用) vim--自动添加jekyll post信息头 vim 自动给文件添加头部信息 GitHub Tips (很实用,值得收藏) Linux路由、防火墙、NAT命令

2017年阿里在线编程题-- 数串分组

2017年03月04日

博客链接: http://codeshold.com/2017/03/alialgorithm.html

题目

2017年3月阿里在线编程题(实习内推)

给定一串数字
判断是否存在这三个元素,它们将数字串分为四个子串,其中每个子串的数字之和均相同(该3个元素不纳入计算)
要求时间复杂度和空间复杂度均不能超过O(n)

实现

python 写的
代码不够优美,欢迎留言指正!

注:添加了测试代码,所以比较冗长!

# -*- encoding:utf-8 -*-

class StrSplit(object):
    def __init__(self,  srclist):
        self.srclist = srclist
        self.sumA = [0] * len(self.srclist) # 保存从左到右依次累积统计的sum
        self.sumB = [0] * len(self.srclist) # 保存从右到左依次累积统计的sum
        self.dictA = {}                     # 保存sumA中具有某个值的索引号
                                            # 如dictA[100]为[1,12],即表示sumA[1]和sum[12]都是100
        self.dictB = {}                     # 保存sumB中具有某个相同索引号
        self.result = [0, 0, 0]             # 保存统计结果,即需要删除的三个元素的索引
        self.initstrsplit()


    def initstrsplit(self):
        sum = 0
        for i in range(0, len(self.srclist)):
            sum += self.srclist[i]
            self.sumA[i] = sum
            if self.sumA[i] in self.dictA:
                self.dictA[self.sumA[i]].append(i)
            else:
                self.dictA[self.sumA[i]] = [i]
        sum = 0
        for i in range(len(self.srclist)-1, -1, -1):
            sum += self.srclist[i]
            self.sumB[i] = sum
            if self.sumB[i] in self.dictB:
                self.dictB[self.sumB[i]].append(i)
            else:
                self.dictB[self.sumB[i]] = [i]


    def getmidpivot(self, left, right, partsum):
        if not (1 < left < right < len(self.srclist)-2 and left < right - 1):
            return False
        #print "left:%d, right:%d, partsum:%d" %(left, right, partsum)

        mid = self.sumA[left-1] + partsum # left-1为要删除的第一个元素
        if mid in self.dictA:
            for i in self.dictA[mid]: # i+1 为要删除的中间元素
                if left-1 < i < right-1:
                    #print self.sumA[right], self.sumA[i]
                    if self.sumA[right] - self.sumA[i+1] == partsum:
                        return i+1
                else:
                    continue
        return False


    def getresult(self):
        if len(self.srclist) < 7:
            return False

        for i in range(0, len(self.sumA)-4):
            if self.sumA[i] in self.dictB:
                index = self.dictB[self.sumA[i]] # index is list type
                for j in index:
                    if j > i+3:
                        # 删除元素i+1 和 j-1后, 判断是否存在中间元素
                        m = self.getmidpivot(i+2, j-2, self.sumA[i])
                        if m:
                            self.result = [i+1, m, j-1]
                            return True
        return False


    def checkresult(self):
        sum1, sum2, sum3, sum4 = 0, 0, 0, 0
        left, mid, right = tuple(self.result)

        for i in range(0, left):
            sum1 += self.srclist[i];

        for i in range(left+1, mid):
            sum2 += self.srclist[i];
        if sum2 != sum1: return False

        for i in range(mid+1, right):
            sum3 += self.srclist[i];
        if sum3 != sum1: return False

        for i in range(right+1, len(self.srclist)):
            sum4 += self.srclist[i];
        if sum4 != sum1: return False

        return True


if __name__ == "__main__":
    import random

    a = [1,2,3,4,5,6,7,8,9,10,1,2,3,24,3,4,1,3,4,5,3,2,1,2,3,4,5,6,7]
    b = [1,1,1,9,1,2,3,-3,4,1,2,5,1,2,-100,100,2,3,-5]
    c = [1,1,1,1,1,1,1]
    d = []
    e = [0,0,0,0,0,0,0,0,0,0]
    all = [a, b, c, d, e]

    for i in range(0, 100):    # 列表数
        tmp = []
        for j in range(0, random.randint(1, 1000)):     # 元素的个数
            tmp.append(random.randint(-10, 10))     # 元素的范围
        all.append(tmp)

    okcount = 0
    failcount = 0
    errorcount = 0

    for i in all:
        swf = StrSplit(i)
        # print swf.srclist
        ret = swf.getresult()
        if ret:
            okcount += 1
            if not swf.checkresult(): errorcount += 1
            print "     StrSplit: True "
            print "     Result: ", swf.result
            print "     Check result: ", swf.checkresult()
        else:
            failcount += 1

    print " SUCCESS COUNT: ", okcount
    print " FAILED COUNT: ", failcount
    print " ERROR COUNT: ", errorcount

知识共享许可协议
SWF's Hacking Dreamonephone 创作,采用 知识共享 署名-非商业性使用 4.0 国际 许可协议进行许可。
© 2011-2024. All rights reserved by onephone. Powerd by Jekyll.