question 1:
给定一个只有0,1的数列,和一个整数n,要求:
(1)判断是否能在这个数列中将0的地方替换成1(n次) (2)替换后要保证不能有连续的两个1出现
我的方法:
刚开始想直接找规律,但是发现给定列表的排列情况太复杂,很难全部考虑到
别的方法:
对于一个位置x,只要同时满足这三种情况 :
(1)x==0 (2)x-1 ==0 (3)x+1==0
就可以把位置x的0替换成1
question 2:
给定一个列表,只需要对列表的子列表排序,就可以使得整个列表按升序排列。求出这个子列表的最大长度
我的方法:
很简单的想法,将原列表与排序后的列表比较,找出不同的部分,就是子列表
question 3:
给定n组按升序排列的列表,求出两组列表间的最大距离(定义:两组间的最大数减最小数)
我的方法:
找到列表中的最大值和最小值(还要符合这两个值不在同一个列表中),两则的差就是结果。但是。但是这样的想法是没有依据的:
假设输入[ [0,2,5],[3,4]]
按照算法 ,不在同一列表的最大最小值为 5,3,那么距离为2
但实际上最大距离应该是4-0=4
别人的方法:
最大距离只可能出现在:两个列表间的最大值(a[-1])-最小值(b[0])或者是最小值(a[0])减去最大值(b[-1]),那么问题就转变成:
将遇到过的最大值,最小值与当前列表的最大值最小值比较,看是不是当前遇到的最大的距离,然后再更新历史最大值和最小值
这样做能够保证所有的最大值(a[-1])-最小值(b[0])或者是最小值(a[0])减去最大值(b[-1])
都被遍历一次