凌动魅力

Tag: 数据结构

考研日记D62

这篇日记是第二天补的,当时在微博上说:

愉快地错过了考试,人都惬意了。先前跟课跟得很辛苦,上课的示范语言和俺之前学的不一样,虽然也能听懂,但是实践起来由于语言特性不同,老师教的内容没有办法用上,一道题愣半天也不知道该咋办。俺决定调整下计划,只听思路,用自己的方法实现。十天换个及格没有意义,半年换个优秀才是俺想要的

之后又谈了下方法论,就忘记更新日记了,俺也直接援引过来:

步入到艰深的学科后,越发认识到方法论的重要性。尽管“方法论”这个词在高中政治书上被无数次提及,但作为系统的学习技巧,仍不为多数大学生所知悉。俺再次上传这两张图,有志于成为各个领域专家的小伙伴们,学校里传授的知识极为有限,更多的内容还需要下来自学,那一定得清楚如何体系化地学习。

俺正处于文学艺术学科到工程学科的转变期,这段时期比较痛苦,就像量子物理革新经典物理一样,旧有的知识体系与新的知识体系有冲突。哪怕俺计算机基础、计算思维导论等课程都是95分以上的优秀成绩,开学数据结构和算法分析以后一样茫然。从应用深入到原理,比俺想象的要艰难得多,难度不在一个数量级。

这种感觉就像翻开一本书后发现,要看懂这本书得先看懂另外3本书,而要看懂另外3本书还得有其他9本书作为铺垫[抓狂]难度瞬间从O(n)变成了O(n^3)。当然,如果只是作为一个应用型的人才,不用对自己提这么高的要求,会用就可以了,无须理解底层。但会用和用得好是两个不同的层面。

考研日记 俩月

今天继续被数据结构虐,课程以C语言为例,俺学的是面向对象编程语言,指针过去指针过来,听着一直迷糊,实现起来更迷糊,每条语句都得自己摸索。

凌晨一个电话闪了两下,,也不知道是谁的~

凌晨偷刷一下朋友圈就发现她1分钟前刚发了条朋友圈,说零食和奶茶吃多了呕吐不舒服,俺没在她身边也只能拿语言安慰下,不过也熟络了些,这就是进步嘛!

有进步就有价值,虽然算法题还是没有刷出来,但好歹也熟悉了编程嘛!

困,睡。

《数据结构》作业题01部分

01-1

给定K个整数组成的序列{ N1, N2, …, NK },“连续子列”被定义为{ Ni, Ni+1, …, Nj },其中 1 <= i <= j <= K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 },其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序,计算给定整数序列的最大子列和。

输入格式:

输入第1行给出正整数 K (<= 100000);第2行给出K个整数,其间以空格分隔。

输出格式:

在一行中输出最大子列和。如果序列中所有整数皆为负数,则输出0。

输入样例:6
-2 11 -4 13 -5 -2

输出样例:20

01-2

Given a sequence of K integers { N1, N2, …, NK }. A continuous subsequence is defined to be { Ni, Ni+1, …, Nj } where 1 <= i <= j <= K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (<= 10000). The second line contains K numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:10
-10 1 2 3 4 -5 -23 3 7 -21

Sample Output:10 1 4

俺的作答如下,Python实现


#01-1
def MaxSubseqSum4():
    K=int(input())
    A=raw_input().split(' ')
    ThisSum=0
    MaxSum=0

    for i in range(K):
        ThisSum+=int(A[i])

        if ThisSum>MaxSum:
           MaxSum=ThisSum
        elif ThisSum<0:
           ThisSum=0

    print MaxSum

MaxSubseqSum4()
#01-2
def MaxSubseqSum5():
    K=int(input())
    A=raw_input().split(' ')
    ThisSum=0
    MaxSum=0
    start=0
    temp=0
    end=K-1
    for i in range(K):
        ThisSum+=int(A[i])

        if ThisSum<0:
           ThisSum=0
           temp=i+1
        elif ThisSum>MaxSum:
           MaxSum=ThisSum
           start=temp
           end=i
        elif MaxSum==0:
             A[start]=0
             A[end]=0
    print MaxSum,A[start],A[end]

MaxSubseqSum5()

考验日记D59

学了3个小时MOOC上的数据结构课程,浙大出品,教程中以C语言为例子讲,俺只会Python,用Python实现后提交作业死活不正确…擦!修改了7次都不行,想不通为什么。

浙大的数据结构题居然是英语命题,好高大上!就是看得迷迷糊糊~

错过量子物理的测验时间了……当时期末考试周,没办法,只有报名参加下次课程了,这个寒假好生把计算机和数学捣腾两下。

Copyright © 2017 凌动魅力

蜀ICP备15003767号-1 Up ↑