首页 > 代码库 > 软件工程大作业
软件工程大作业
实验一：
实验题目：跳跃游戏 II
问题描述：
给出一个非负整数数组，你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
数据输入：[13,52,42,21,58]
数据输出：1
涉及的数据类型：int型的列表，整型（int）
解题思路：由于每层最多可以跳A[i]步，也可以跳0或1步，因此如果能到达最高层，则说明每一层都可以到达,有了这个条件，可以使用贪心算法
易错点（需要考虑的特殊情况）：贪心策略是每步前进的地方是下一步能达到的地方最远。切记这一点规则。
主要算法描述（伪代码）：
由于每层最多可以跳A[i]步，也可以跳0或1步，因此如果能到达最高层，则说明每一层都可以到达。从0出发，一层一层往上，看最后能否超过最高层，能超过，说明可以，否则不能。
1 # Time: O(n) 2 # Space: O(1) 3 # 4 # Given an array of non-negative integers, you are initially positioned at the first index of the array. 5 # 6 # Each element in the array represents your maximum jump length at that position. 7 # 8 # Your goal is to reach the last index in the minimum number of jumps. 9 # 10 # For example: 11 # Given array A = [2,3,1,1,4] 12 # 13 # The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.) 14 # 15 16 class Solution: 17 # @param A, a list of integers 18 # @return an integer 19 def jump(self, A): 20 jump_count = 0 21 reachable = 0 22 curr_reachable = 0 23 for i, length in enumerate(A): 24 if i > reachable: 25 return -1 26 if i > curr_reachable: 27 curr_reachable = reachable 28 jump_count += 1 29 reachable = max(reachable, i + length) 30 return jump_count 31 32 # Time: O(n^2) 33 # Space: O(1) 34 class Solution2: 35 # @param A, a list of integers 36 # @return an integer 37 def jump(self, A): 38 result, prev_reachable, reachable = 0, -1, 0 39 while reachable > prev_reachable: 40 if reachable >= len(A) - 1: 41 return result 42 result += 1 43 prev_reachable = reachable 44 for i, length in enumerate(A[:reachable + 1]): 45 reachable = max(reachable, i + length) 46 return -1 47 48 if __name__ == "__main__": 49 print Solution().jump([2,3,1,1,4]) 50 print Solution().jump([3,2,1,0,4])
实验二：
实验题目：加油站
问题描述：
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油gas[i]，并且从第_i_个加油站前往第_i_+1个加油站需要消耗汽cost[i]。你有一辆油箱容量无限大的汽车，现在要从某一个加油站出发绕环路一周，一开始油箱为空。
数据输入：[4], [5]
数据输出：-1
涉及的数据类型：两个int型列表，整型（int）
解题思路：
最暴力的O(n2)的算法就是从起点开始检查是否可以绕一圈，碰到不足以走到下一个加油站的则从起点+1继续检查，直到检查完n个加油站。
当然这题是有O(n)的解法的，不用那么暴力。我们知道，从起点start开始走，当我们走到第i个加油站发现不足以走到i+1个加油站时我们不需要从start+1开始查找，因为既然从start开始到不了i+1那么从start到i中间的任意一节点开始都是到不了i+1的，所以下一个我们就可以从i+1开始检查，直到发现满足条件的。
易错点（需要考虑的特殊情况）：
1 如果从一个加油站不能到达下一个加油站，那么之后的所有加油站都不能到
2 如果能走一圈，那么所有的gas之和肯定大于等于所有cost之和
3 时间复杂度不能太高
主要算法描述（伪代码）：设置两个变量，sum判断当前的指针的有效性；total则判断整个数组是否有解，如果有解就返回通过sum得到的下标，没有则返回-1
1 # Time: O(n) 2 # Space: O(1) 3 # 4 # There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. 5 # 6 # You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). 7 # You begin the journey with an empty tank at one of the gas stations. 8 # 9 # Return the starting gas station‘s index if you can travel around the circuit once, otherwise return -1. 10 # 11 # Note: 12 # The solution is guaranteed to be unique. 13 # 14 15 class Solution: 16 # @param gas, a list of integers 17 # @param cost, a list of integers 18 # @return an integer 19 def canCompleteCircuit(self, gas, cost): 20 start, total_sum, current_sum = 0, 0, 0 21 for i in xrange(len(gas)): 22 diff = gas[i] - cost[i] 23 current_sum += diff 24 total_sum += diff 25 if current_sum < 0: 26 start = i + 1 27 current_sum = 0 28 if total_sum >= 0: 29 return start 30 31 return -1 32 33 if __name__ == "__main__": 34 print Solution().canCompleteCircuit([1, 2, 3], [3, 2, 1]) 35 print Solution().canCompleteCircuit([1, 2, 3], [2, 2, 2]) 36 print Solution().canCompleteCircuit([1, 2, 3], [1, 2, 3]) 37 print Solution().canCompleteCircuit([1, 2, 3], [1, 2, 4])
实验三：
实验题目：落单的数II
问题描述：
给出3*n + 1 个的数字，除其中一个数字之外其他每个数字均出现三次，找到这个数字。
数据输入：[1,1,2,3,3,3,2,2,4,1]
数据输出：4
涉及的数据类型：
解题思路：题目的挑战还是在于一次遍历，常数级的额外空间复杂度。当有2 * n + 1 个数的时候的我觉得应该用的是位运算的异或（参考了网页上提交的代码方法和博文）
主要算法描述（伪代码）：
对应位的0,1相加，最后对3取余。得到的结果就是那个落单的数的二进制表示。然后恢复成整数即可
1 class Solution: 2 """ 3 @param A : An integer array 4 @return : An integer 5 """ 6 def singleNumberII(self, A): 7 result = 0 8 record = [0 for i in range(32)] 9 for i in A: 10 11 # 瀵?32浣嶄簩杩涘埗涓蹭粠鍙冲線宸︽壂鎻? 12 for index in range(-1, -32, -1): 13 # temp涓烘瘡涓€浣嶄唬琛ㄧ殑鏁板瓧锛?0鎴?1锛? 14 temp = (i & 1) 15 record[index] += temp 16 record[index] %= 3 17 i = i >> 1 18 19 # 姝ゆ椂鐨剅ecord鏄竴涓敱鏁存暟0鎴?1缁勬垚鐨勬暟缁勶紝浠ｈ〃缁撴灉鐨勪簩杩涘埗琛ㄧず 20 # 灏嗘暟缁勬仮澶嶆垚鏁存暟 21 for i in range(32): 22 result += record[31 - i] * pow(2, i) 23 return result 24 # write your code here
实验四：
实验题目：报数
问题描述：
报数指的是，按照其中的整数的顺序进行报数，然后得到下一个数。如下所示：
1, 11, 21, 1211, 111221, ...
1 读作 "one 1" -> 11.
11 读作 "two 1s" -> 21.
21 读作 "one 2, then one 1" -> 1211.
给定一个整数 n, 返回 第 n 个顺序。
数据输入：5
数据输出：111221
涉及的数据类型：
解题思路：这道题基本上就是一个模拟的题目,不断遍历字符串，每一次遍历一个新的字符的时候看后面有多少字符是跟前面的一样的。 这样相当于按照相同的字符一层一层的遍历而不是一个字符一个字符的遍历。
易错点（需要考虑的特殊情况）
整数的顺序将表示为一个字符串。
主要算法描述（伪代码）：
后一个字符串是前一个字符串每个连续出现的数字的个数＋该数字拼凑而成，用count记录连续数字的个数，然后用key记录当前最新的数字，每次遇到不同的数字就把count+key拼接到结果当中，但注意如果遍历到最后一位时，无论是否遇到新的字符都要把当前count+key加入结果中
1 class Solution: 2 def countAndSay(self, n): 3 beforeSeq=‘1‘;afterSeq=‘‘ 4 if n==1: return ‘1‘ 5 while n>1: 6 curLength=len(beforeSeq) 7 key=beforeSeq[0]; 8 count=0 9 afterSeq=‘‘ 10 for i in range(curLength): 11 if beforeSeq[i]==key: 12 count+=1 13 if i==curLength-1: 14 afterSeq+=(str(count)+key) 15 else: 16 afterSeq+=(str(count)+key) 17 key=beforeSeq[i] 18 count=1 19 if i==curLength-1: 20 afterSeq+=(str(count)+key) 21 beforeSeq=afterSeq 22 n-=1 23 return afterSeq
实验五：
实验题目：最接近的三数之和
问题描述：
给一个包含 n 个整数的数组 S, 找到和与给定整数 target 最接近的三元组，返回这三个数的和
数据输入：
[2,7,11,15], 3
数据输出：
20
涉及的数据类型：
解题思路：
这道题让我们返回这个最接近于给定值的值，即我们要保证当前三数和跟给定值之间的差的绝对值最小，所以我们需要定义一个变量diff用来记录差的绝对值，然后我们还是要先将数组排个序，然后开始遍历数组
易错点（需要考虑的特殊情况）
主要算法描述（伪代码）：
对输入的数组进行排序
使用左右加逼
1 # Time: O(n^2) 2 # Space: O(1) 3 # 4 # Given an array S of n integers, 5 # find three integers in S such that the sum is closest to a given number, target. 6 # Return the sum of the three integers. 7 # You may assume that each input would have exactly one solution. 8 # 9 # For example, given array S = {-1 2 1 -4}, and target = 1. 10 # 11 # The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). 12 # 13 14 class Solution(object): 15 def threeSumClosest(self, nums, target): 16 """ 17 :type nums: List[int] 18 :type target: int 19 :rtype: int 20 """ 21 nums, result, min_diff, i = sorted(nums), float("inf"), float("inf"), 0 22 while i < len(nums) - 2: 23 if i == 0 or nums[i] != nums[i - 1]: 24 j, k = i + 1, len(nums) - 1 25 while j < k: 26 diff = nums[i] + nums[j] + nums[k] - target 27 if abs(diff) < min_diff: 28 min_diff = abs(diff) 29 result = nums[i] + nums[j] + nums[k] 30 if diff < 0: 31 j += 1 32 elif diff > 0: 33 k -= 1 34 else: 35 return target 36 i += 1 37 return result 38 39 if __name__ == ‘__main__‘: 40 result = Solution().threeSumClosest([-1, 2, 1, -4], 1) 41 print result
实验六：
实验题目：三数之和
问题描述：
给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。
和
数据输入：
[2,7,11,15]
数据输出：
[]
涉及的数据类型：
解题思路：
先对数组排序，排序后的数组，定义其实节点i，然后对i+1 到len内的所有节点进行两端遍历，这里利用二分查找的思想
易错点（需要考虑的特殊情况）
在三元组(a, b, c)，要求a <= b <= c。
结果不能包含重复的三元组。
主要算法描述（伪代码）：
设两端的两个下标是left 和right ，显然 sum=nums[i] + nums[left] + nums[right] >0时候 ，right--,小于0的时候left++,等于0的时候就是答案。时间复杂度O(NlogN)
1 class Solution: 2 """ 3 @param numbersbers : Give an array numbersbers of n integer 4 @return : Find all unique triplets in the array which gives the sum of zero. 5 """ 6 def threeSum(self, numbers): 7 # write your code here 8 result = [] 9 if numbers == None or len(numbers) < 3: 10 return result 11 numbers.sort() 12 numlen = len(numbers) 13 for i in range(numlen): 14 left = i + 1 15 right = numlen - 1 16 while left < right: 17 sum = numbers[i] + numbers[left] + numbers[right] 18 if sum==0: 19 path = [numbers[i],numbers[left],numbers[right]] 20 if path not in result: 21 result.append(path) 22 left +=1 23 right -=1 24 elif sum>0: 25 right -=1 26 else: 27 left +=1 28 29 return result
实验七：
实验题目：两数之和
问题描述：
给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。
你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 1 到 n，不是以 0 开头。
数据输入：[2,7,11,15], 9
数据输出：[1,2]
涉及的数据类型：
解题思路：为了降低时间复杂度只能用哈希法
易错点（需要考虑的特殊情况）：
在原来数组中找下标时，需要一个从头找，一个从尾找，要不无法通过。
主要算法描述（伪代码）：
1，由于要找到符合题意的数组元素的下标，所以先要将原来的数组深拷贝一份，然后排序。
2，然后在排序后的数组中找两个数使它们相加为target。这个思路比较明显：使用两个指针，一个指向头，一个指向尾，两个指针向中间移动并检查两个指针指向的数的和是否为target。如果找到了这两个数，再将这两个数在原数组中的位置找出来就可以了。
1 class Solution: 2 # @return a tuple, (index1, index2) 3 def twoSum(self, num, target): 4 dict = {} 5 for i in xrange(len(num)): 6 x = num[i] 7 if target-x in dict: 8 return (dict[target-x]+1, i+1) 9 dict[x] = i
实验八：
用递归打印数字
问题描述：
用递归的方法找到从1到最大的N位整数。
数据输入：1
数据输出：[1,2,3,4,5,6,7,8,9]
涉及的数据类型：
解题思路：题目已经非常明确给出了递归二字。N = i 和 N = i + 1时，返回的这个结果列表时怎样转化的。找到“升级”的方式，是递归算法最难的一环。
易错点（需要考虑的特殊情况）：
主要算法描述（伪代码）：
拿 N = 1 和 N = 2为例，我们可以总结出这样的规律：N = 2时，返回的数都是两位数，所以如果用1~9分别乘10^1，就得到了10, 20, 30, ..., 90，这些数中，我们给每个数分别加上N = 1时返回的列表中的数，就构成了10, 11, 12, ..., 99，当然，再给这个新构成的序列前头附上N = 1时的序列，就是N = 2时的序列。如果再尝试一下N = 3时与N = 2时的升级过程也是这样的。
而这个递归算法“触底”的条件显而易见：N = 1时，返回列表[1, 2, ..., 9
1 class Solution: 2 # @param n: An integer. 3 # return : A list of integer storing 1 to the largest number with n digits. 4 def numbersByRecursion(self, n): 5 6 # 瑙﹀簳鏉′欢 7 if n == 1: 8 return [i for i in range(1, 10)] 9 10 # 鍒濆鍖栧垪琛? 11 result = [] 12 13 if n >= 2: 14 temp = self.numbersByRecursion(n - 1) 15 # i: 1~9 16 for i in range(1, 10): 17 result.append(i * pow(10, n - 1)) 18 for j in temp: 19 result.append(j + i * pow(10, n - 1)) 20 result = temp + result 21 return result
实验九：
实验题目：丑数
问题描述：
写一个程序来检测一个整数是不是丑数。
丑数的定义是，只包含质因子 2, 3, 5 的正整数。比如 6, 8 就是丑数，但是 14 不是丑数以为他包含了质因子 7。
数据输入：8
数据输出：true
涉及的数据类型：
解题思路：主要是找出丑数的定义，根据规律与定律编写循环
易错点（需要考虑的特殊情况）：对丑数的定义一定不能出错
主要算法描述（伪代码）：
根据定义，丑数是只包含质因子2,3,5的正整数。那么不妨可以由以下4步来判定一个整数是不是丑数：
1. 判断正负：若是负数，可直接返回False
2. 不断除2，直到商还是整数的一次为最后一次
3. 对2步结束后的值，不断除3，直到商还是整数的一次为最后一次
4. 对3步结束后的值，不断除5，直到商还是整数的一次为最后一次
此时，我们看4步结束后的值是不是1：是1，则说明是丑数；不是1，则说明不是丑数。
1 class Solution: 2 # @param {int} num an integer 3 # @return {boolean} true if num is an ugly number or false 4 def isUgly(self, num): 5 if num <= 0: 6 return False 7 while num % 2 == 0: 8 num = num / 2 9 while num % 3 == 0: 10 num = num / 3 11 while num % 5 == 0: 12 num = num / 5 13 if num == 1: 14 return True 15 else: 16 return False
实验十：
实验题目：丑数II
问题描述：
设计一个算法，找出只含素因子2，3，5 的第 n 大的数。
符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
数据输入：9
数据输出：1
涉及的数据类型：
解题思路：之前，做过一道类似的题目：丑数。题目的要求是判别一个整数是不是丑数。而本题的目的是计算第n个丑数是多少。所以，一种朴素的思路是这样：设定一个计数器，初始为0. 然后从1开始，遍历正整数，每遍历到一个，就用上题（详情查看前面链接）中判断丑数的函数判断，是丑数，对计数器加1，知道计数器为n为止。但是效率不高，因为每次对遍历到的正整数都要进行那样一个时间复杂度偏高的算法。如果我们把所有的丑数依次按升序存储到一个列表里面，那么这个列表后面的某个元素，一定是前面的某个元素乘2、乘3、或乘5得到的。所以，假设现在我们已知这样一个列表的一部分，想要往列表里面添加新元素，从而要找出新元素的方法。
易错点（需要考虑的特殊情况）：
主要算法描述（伪代码）：
列表的下一个要添加元素可以这样计算：
1. 依次遍历现在列表中的元素，并计算这些元素乘2的结果，直到遇到第一个比现在列表中最后一个元素（也就是最大的那个）大的元素，我们将这个元素乘2的结果记为M2
2. 与1步同理，处理这些元素乘3的结果，找到第一个乘3比最后元素大的元素，把他乘3的结果记为M5
3. 与2步同理，可得到相应的M5
4. 最后，将min(M2, M3, M5)添加到列表最后，作为新元素即可。
其实，效率还可以再高一点。因为这个列表已经是排好序的，所以我们可以设定三个指针index2, index3, index5，他们所指向的元素，乘2，乘3，乘5分别为此时的M2, M3, M5，每次遍历结束之后，只需要从这三个指针的位置（含）开始向后扫描即可。
1 class Solution: 2 """ 3 @param {int} n an integer. 4 @return {int} the nth prime number as description. 5 """ 6 def nthUglyNumber(self, n): 7 record = [1] 8 if n == 1: 9 return record[0] 10 11 index2, index3, index5 = 0, 0, 0 12 M2, M3, M5 = record[index2] * 2, record[index3] * 3, record[index5] * 5 13 14 while len(record) == n: 15 16 while M2 <= record[-1]: 17 index2 += 1 18 M2 = record[index2] * 2 19 while M3 <= record[-1]: 20 index3 += 1 21 M3 = record[index3] * 3 22 while M5 <= record[-1]: 23 index5 += 1 24 M2 = record[index5] * 5 25 26 record.append(min(M2, M3, M5)) 27 return record[-1]
软件工程大作业