1.请写出冒泡排序。
#冒泡排序:n*n def bubbleSort(array): maxindex = len(array)-1 maxValue = array[maxindex] k=0 while maxindex: for i in range(1,maxindex): if array[i-1]>array[i]: temp = array[i] array[i] = array[i-1] array[i-1] = temp k+=1 maxindex -=1 print(k) return array
2.1~9999数列中数字3出现的次数。用递推方法解出。
def count_digit(number): return len(str(number)) def countThree(digit): if not isinstance(digit,int): raise TypeError('number is not int') # digit = len(str(number)) if(digit <=0): return 0 if(digit ==1): return 1 return 10*countThree(digit-1) + 10 **(digit-1) print(countThree(count_digit(9999)))
3.从一个数组中找出前4个最大的数,用最优解。
#快速排序:最快的n*logN def qiuckSort(list): if len(list)<2: return list mid = list[0] left = [i for i in list[1:] if i <= mid] right = [i for i in list[1:] if i > mid] finallyList = qiuckSort(left)+[mid] + qiuckSort(right) return finallyList array = [3, 0, 1, 832,23,45, 5, 5, 6,46, 9, 56, 897] print(qiuckSort(array)[-4:])
4.写一段程序,删除字符串a中包含的字符串b,举例 输入a = "asdw",b = "sd" 返回 字符串 “aw”,并且测试这个程序。
def delBString(a,b): if not isinstance(a,str): raise TypeError("a is not str") if not isinstance(b,str): raise TypeError("b is not str") if len(a) < len(b): raise Exception('a length must large to b length') result = [] flag = False i=0 la = len(a) lb = len(b) while i <la: j = 0 while j < lb: if i+j < la and a[i+j] == b[j]: j += 1 else : j += 1 flag = False break flag = True if flag: i += lb else: result.append(a[i]) i += 1 return "".join(result)
测试用例: class TestdelInnerStringFunctions(): def setUp(self): pass def tearDown(self): pass def test_nomorl1(self): assert delBString('asdqwe','we') == 'asdq' def test_nomorl2(self): assert delBString('asdqwe','0') == 'asdqwe' def test_nomorl3(self): assert delBString('测试asdqwe','we') == '测试asdq' def test_nomorl4(self): assert delBString('测试asdqwe','测试') == 'asdqwe' def test_nomorl5(self): assert delBString('asdqwe','') == 'asdqwe' def test_nomorl6(self): with pytest.raises(TypeError): delBString('', 0) def test_nomorl7(self): with pytest.raises(TypeError): delBString(0, 'as') def test_nomorl8(self): with pytest.raises(TypeError): delBString(True) def test_nomorl9(self): with pytest.raises(Exception) as excinfo: delBString('acd','acde') assert "a length must large to b length" in str(excinfo.value) assert excinfo.type == Exception
5.写一个方法,把字符串转为数字,比如 str="1234",变成 int 1234。并且测试这个程序。
def StrToInt(a): res ,mult,flag = 0,1,1 if not isinstance(a,str): raise TypeError("a is not str") if a[0] =='-' or a[0] == '+': if a[0] == '-': flag = -1 a = a[1:] for i in range(len(a)-1,-1,-1): if '9' >=a[i] >= '0': res +=(ord(a[i]) -48) * mult mult = mult *10 else : return 0 return res * flag def test_strToInt2(self): with pytest.raises(TypeError): StrToInt(34)
测试用例: def test_strToInt3(self): assert StrToInt('测试赛') == 0 def test_strToInt4(self): assert StrToInt('+2147689') == 2147689 def test_strToInt5(self): assert StrToInt('45') == 45 def test_strToInt6(self): assert StrToInt('1a33') == 0 def test_strToInt7(self): assert StrToInt('-5') == -5
6.给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
# Python def TargetSum(nums,target): if len(nums) < 2: return 0 for i in range(0,len(nums)-1): for j in range (i+1,len(nums)): if nums[i] + nums[j] == target: return [i,j]
# 测试用例 def test_TargetSum1(self): assert TargetSum([1,1,3,6,0,2],2) == [0,1] def test_TargetSum2(self): assert TargetSum([1],1) == 0 def test_TargetSum3(self): assert TargetSum([6,2,4,3,1,2],4) == [1,5] def test_TargetSum4(self): assert TargetSum([2, 7, 11, 15],9) == [0,1]
// Java public int[] TargetSum(int nums[],int target){ Map<Integer, Integer> map = new HashMap<>(); for(int i=0;i<nums.length;i++){ int temp = target - nums[i]; if(map.containsKey(temp)){ return new int[] { map.get(temp), i }; } map.put(nums[i],i); } return null; }
7.给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2,其中 index1 必须小于 index2。
''' 说明: 返回的下标值(index1 和 index2)不是从零开始的。 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。 示例: 输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。 ''' ## python class Solution(object): def twoSum(self, numbers, target): l=0 r=len(numbers)-1 while(l<r): if(numbers[l]+numbers[r]== target): return [l+1,r+1] if(numbers[l]+numbers[r] <target): l += 1 else: r -= 1 ## 测试用例: def test_towSum1(self): assert towSum([0,1, 1, 2, 3, 6,8], 2) == [1, 4] def test_towSum2(self): assert towSum([1,2,5,6,12], 13) == [1, 5] def test_towSum3(self): assert towSum([2, 7, 11, 15], 9) == [1, 2]
## Java public int[] twoSum(int[] numbers, int target) { int left = 0; int right = numbers.length - 1; while (left < right) { if (numbers[left] + numbers[right] == target) { return new int[]{left + 1, right + 1}; } if (numbers[left] + numbers[right] < target) { left += 1; } else { right -= 1; } } return null; }
8.假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数。
''' 示例 1: 输入:2 输出:2 解释:有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 示例 2: 输入:3 输出:3 解释:有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶 ''' Python ## 不推荐 效率极低 ## def setpMethod(num): if(n == 1 or n == 2): return n else: return self.setpMethod(num-1)+self.setpMethod(num-2) ## 推荐写法 ## def climbStairs(self, n): if(n == 1 or n == 2): return n num1=1 num2=2 while(n >= 3): result = num1 + num2 num1 = num2 num2 = result n -=1 return result ## Java ## public int setpMethod(int n){ if(n ==1 || n ==2){ return n; } int result = 0,n1 = 1,n2 = 2; while (n>=3){ result = n1 + n2; n1 = n2; n2 = result; n--; } return result; }
9.给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
''' 示例 1: 输入: [2,3,1,1,4] 输出: true 解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。 示例 2: 输入: [3,2,1,0,4] 输出: false 解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。 ''' ## python ## class Solution(object): def canJump(self, nums): need = 1 if(len(nums) ==1): return True if(nums[0] == 0): return False for i in range(len(nums)-2,-1,-1): if(nums[i] == 0 or nums[i] < need): need += 1 else: need = 1 if(need == 1) : return True else: return False ## java ## public boolean canJump(int[] nums) { int n = 1; if(nums.length ==1){ return true; } if(nums[0] == 0){ return false; } for(int i=nums.length-2; i>=0; i--){ if(nums[i] >= n){ n=1; }else{ n++; } } if(n == 1){ return true; }else{ return false; } }
10.以 Unix 风格给出一个文件的绝对路径,你需要简化它。或者换句话说,将其转换为规范路径。
在 Unix 风格的文件系统中,一个点(.)表示当前目录本身;此外,两个点 (..) 表示将目录切换到上一级(指向父目录);两者都可以是复杂相对路径的组成部分。
更多信息请参阅:Linux / Unix中的绝对路径 vs 相对路径.
请注意,返回的规范路径必须始终以斜杠 / 开头,并且两个目录名之间必须只有一个斜杠 /。最后一个目录名(如果存在)不能以 / 结尾。此外,规范路径必须是表示绝对路径的最短字符串。
示例 1: 输入:"/home/" 输出:"/home" 解释:注意,最后一个目录名后面没有斜杠。 示例 2: 输入:"/../" 输出:"/" 解释:从根目录向上一级是不可行的,因为根是你可以到达的最高级。 示例 3: 输入:"/home//foo/" 输出:"/home/foo" 解释:在规范路径中,多个连续斜杠需要用一个斜杠替换。 示例 4: 输入:"/a/./b/../../c/" 输出:"/c" 示例 5: 输入:"/a/../../b/../c//.//" 输出:"/c" 示例 6: 输入:"/a//bc/d//././/.." 输出:"/a/b/c"
##python## def simplifyPath(self, path): """ :type path: str :rtype: str """ paths = path.split('/') str = '' pathlist = [i for i in paths if I] result = [] for j in range(len(pathlist)): print(j) if(pathlist[j] == ".."): if(result): result.pop() elif(pathlist[j] == "."): continue else : result.append(pathlist[j]) if not result: return '/' for k in range(len(result)): str = str + '/' + result[k] return str
11.给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?' 和 '' 的通配符匹配。'?' 可以匹配任何单个字符。'' 可以匹配任意字符串(包括空字符串)。两个字符串完全匹配才算匹配成功。
说明: s 可能为空,且只包含从 a-z 的小写字母。 p 可能为空,且只包含从 a-z 的小写字母,以及字符 ? 和 *。 示例 1: 输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。 示例 2: 输入: s = "aa" p = "*" 输出: true 解释: '*' 可以匹配任意字符串。 示例 3: 输入: s = "cb" p = "?a" 输出: false 解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。 示例 4: 输入: s = "adceb" p = "*a*b" 输出: true 解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce". 示例 5: 输入: s = "acdcb" p = "a*c?b" 输入: false
##python## def isMatch(self, s, p): si, pi, pj, sj = 0, 0, -1, -1 while si < len(s): if pi < len(p) and p[pi] == '*': pi += 1 pj = pi sj = si elif pi < len(p) and (p[pi] == '?' or p[pi] == s[si]): pi += 1 si += 1 elif pj != -1: pi = pj sj += 1 si = sj else: return False while (pi < len(p) and p[pi] == '*'): pi += 1 return pi == len(p)
12.给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例: 输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807
## python ## class Solution(object): def addTwoNumbers(self, l1, l2): n =l1.val + l2.val l3 = ListNode(n%10) l3.next = ListNode(n//10) p1 = l1.next p2 = l2.next p3 = l3 while True: if p1 and p2: sum = p1.val+ p2.val + p3.next.val p3.next.val = sum % 10 p3.next.next = ListNode(sum//10) p1 = p1.next p2 = p2.next p3 = p3.next elif p1 and not p2: sum = p1.val + p3.next.val p3.next.val = sum %10 p3.next.next = ListNode(sum // 10) p1 = p1.next p3 = p3.next elif not p1 and p2: sum = p2.val +p3.next.val p3.next.val = sum % 10 p3.next.next = ListNode(sum // 10) p2 = p2.next p3 = p3.next else : if p3.next.val == 0: p3.next = None break return 13