本文共 10960 字，大约阅读时间需要 36 分钟。
# 函数调用格式如下def main(): array = [11, 7, 45, 67, 134, 5, 83, 55, 106, 33, 57, 82, 6, 24, 87, 61, 3, 39, 6, 26] target_number = 13 result, a, b = hasSum(array, target_number) if result == 1: print('YES, %d + %d = %d' % (a, b, target_number)) else: print('NO')# 代码1：使用哈希表，适用于不含重复元素的数组，时间复杂度N,def hasSum(a, target_number): hashset = set(a) print(hashset) for i in a: if (target_number-i) in hashset: print(target_number, i) return 1, i, target_number-i return None,None,None# 代码2：使用排序后的列表，双指针法；由于要先进行数组排序，# 复杂度为NlogNdef hasSum2(a, target_number): a_sorted = sort(a) i, j = 0, len(a)-1 while i target_number: j -= 1 elif a[i] + a[j] < target_number: i += 1 else: return 1, a[i], a[j] return None, None, Noneif __name__ == '__main__': main() 示例: 输入price = [12, 15, 14, 8, 11, 10, 12], 则输出最大利润是4。
# 函数调用格式如下def main(): price = [12, 15, 14, 8, 11, 10, 12] result = get_max_profit(price) print(result) """差最大， 元素最小的问题先定义最大差和最小元素遍历列表，让元素与最小元素做差，找差最大"""def get_max_profit(a): max_val = 0 min_num = a[0] for num in a: if num < min_num: min_num = num elif num - min_num > max_val: max_val = num-min_num return max_valif __name__ == '__main__': main()
示例: head -> 3 -> 8 -> 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> 1, 则返回5
# 链表的类定义如下:class ListNode(object): def __init__(self, value=0): self.value = value self.next_node = None
from ListModel import ListNodedef lengthOfCircle(head):# 如果头节点就是空的if head == None: return "不是环结构"s = list()indx = 0while head.next: indx += 1 if id(head) in s: return indx - s.index(id(head)) s.append(id(head)) head = head.nextreturn "不是环结构"def main(): # 下面完成构造链表的代码 head = ListNode(3) p1 = ListNode(8) p2 = ListNode(7) p3 = ListNode(1) p4 = ListNode(2) p5 = ListNode(3) p6 = ListNode(4) p7 = ListNode(5) head.next_node = p1 p1.next_node = p2 p2.next_node = p3 p3.next_node = p4 p4.next_node = p5 p5.next_node = p6 p6.next_node = p7 p5.next_node = p3 # 调用你编写的代码函数, 唯一的参数是头指针head res = lengthOfCircle(head) print('result length:', res)#实现方法2：def lengthOfCircle(head): p1 = p2 = head i = 0 while p2 and p2.next_node: i += 1 p1 = p1.next_node p2 = p2.next_node.next_node if p1 == p2: return i + 2 return 0if __name__ == '__main__': main() 示例: 输入"10112", 输出"1.0.1.12", “1.0.11.2”, “10.1.1.2”, 共有3个合法ip地址。
# 函数调用格式如下def main(): s = '10112' res = get_ip(s) for i in res: # 每个i代表一个合法的ip字符串 print(i)def get_ip(s): # r存储结果 r = [] n = len(s) def helper(tmp): """辅助函数，判断是否满足ip条件 循环解析；从第一个ip段开始查询，将符合条件的存放到结果中 Args: tmp ([type]): 输入的ip段 """ if not tmp or (tmp[0] == '0' and len(tmp) > 1) or int(tmp) > 255: return False return True for i in range(3): for j in range(i+1, i+4): for k in range(j+1, j+4): if i < n and j < n and k
# 函数调用格式如下def main(): price = [12, 15, 14, 8, 11, 10, 12] result = get_max_profit(price) print(result)def get_max_profit(price): # 查找最大的两个差值，而且有先后顺序 # 分段查找，加和 # 定义一个字典，存储先后两个最大值 max_value = { } length = len(price) max_profit = 0 for i in range(1,length-1): prices1 = price[:i+1] # 当 prices2 = price[i:] min_price1 = 10000 min_price2 = 10000 max_profit1 = 0 max_profit2 = 0 for price1 in prices1: min_price1 = min(price1, min_price1) max_profit1 = max(max_profit1, price1 - min_price1) for price2 in prices2: min_price2 = min(price2, min_price2) max_profit2 = max(max_profit2, price2 - min_price2) max_profit = max(max_profit, max_profit1+max_profit2) return max_profitif __name__ == '__main__': main() 示例: 输入数组 A = [2, 1, 3, 1, 1], 输出2
# 函数调用格式如下def main(): a = [2, 1, 3, 1, 1] res = frog_jump(a) print(res)def frog_jump(a): # 跳跃次数 jump_num = 0 # 最远距离 max_jump = 0 # 每次跳跃能跳到的边界 end = 0 for i, num in enumerate(a): # num+i表示i位置上能够到的最远距离， 每次找路径上的最大数值 max_jump = max(max_jump, num + i) if end==i: end = max_jump jump_num += 1 return jump_numif __name__ == '__main__': main()
示例: 输入数组为[5, 3, 4, 0, 1, 4, 1], 则最大下标距离产生于A[i]=3, i=1和A[j]=4, j=5的时候, 此时j - i = 4, 这个4就是满足条件的最大下标距离。
算法思路: 记录从数组第一个元素开始的下降序列descent_seq, 然后使用指针从尾部开始逆向扫描, 求出满足要求的下标的最大距离。
反证法: 假设存在最大下标距离的两个下标i和j, 满足i<j, A[i]<A[j], 并且A[i]不在descent_seq中。
如果上述假设情况发生, 那么我们一定还能找到一个k, 满足k<i, A[k]<A[i], 那么此时最大下标距离应该是j-k, 而不是j-i, 矛盾! 因此假设不成立! 得出结论: 满足要求的A[i]一定在descent_seq中, 也就是一定在从数组第一个元素开始的下降序列中。# 函数调用格式如下def main(): array = [5, 3, 4, 0 ,1, 4, 1] dis = maxDistance(array) print("dis=%d," % dis)def maxDistance_baseline(array): max_length = 0 for i, num in enumerate(array): for j in range(i): if (i - j > max_length) & (num-array[j] > 0): max_length = i-j print (max_length) return max_length def maxDistance(array): descent_array = [] max_number = array[0] for i in range(len(array)): if i == 0: descent_array.append('O') else: if array[i] < max_number: descent_array.append('O') max_number = array[i] else: descent_array.append('X') print(descent_array) i = j = len(descent_array) - 1 max_distance = 0 max_i = -1 max_j = -1 while i >= 0: if descent_array[i] == 'X': i -= 1 continue while array[j] <= array[i] and i < j: j -= 1 if i < j and j - i > max_distance: max_distance = j - i max_i = i max_j = j i -= 1 return max_distance, max_i, max_j if __name__ == '__main__': main() 另外一种实现方法：最大索引距离在极值的时后出现
def maxDistance(a): length = len(a) min_num = a[0] min_flag = [0]*length max_flag = [0]*length # 遍历列表，查找极大极小值， 并将极大极小值标记 for i in range(1, length): if a[i] >= a[i-1]: max_flag[i] = 1 max_flag[i-1] = 0 if a[i-1] > a[i]: min_flag[i] = 1 min_flag[i-1] = 0 # 遍历列表，当到极大极小值的时，进行比较，如果极小小于极大，那么返回差值 left = 0 # 设置遍历方向 left_go = True right_go = False right = length-1 max_length = 0 while left < right: # 左边递增，且没到极小时，继续下一个 if min_flag[left] != 1 and left_go: left += 1 # 到极小，判断左右两个极值之间的关系，如果满足，返回距离，如果不满足，从 # 右边进行遍历，左边遍历停止，left_go设置为False elif min_flag[left] == 1 and left_go: if a[left] < a[right]: return right - left left_go = False right_go = True # 如果右边不是极大值，而且是从右边遍历， 继续前一个 if max_flag[right] != 1 and right_go: right -= 1 # 如果是极大，而且是从右边遍历，满足条件，返回距离，否则从左边再开始进行遍历 elif max_flag[right] == 1 and right_go: if a[left] < a[right]: return right - left left_go = True right_go = False # 如果没有符合条件的结果，返回0 return 0
示例: 给定数组 A = [2, 35, 8, 16, 8, 2, 7, 35], 返回唯一只出现了一次的7
# 函数调用格式如下def main(): array = [2, 35, 8, 16, 8, 2, 7, 35] num = onlyOneTimeNumber(array) print("num=%d," % num)# ----------------------------------------------------- def onlyOneTimeNumber(array): used_dict = { } has_set = set() for i, num in enumerate(array): if num in has_set: used_dict[num] = 2 if num not in has_set: has_set.add(num) used_dict[num] = 1 # print(used_dict) for key, values in used_dict.items(): if values == 1: return key# ---------------------------------------------------------------if __name__ == '__main__': main() 示例:
# 函数调用格式如下def main(): a = [2, 1, 3, 1, 1] b = [3, 2, 1, 0, 1] res = frog_jump(b) print(res) res = frog_jump(a) print(res) def frog_jump(list_): last = list_[0] length = len(list_) # end_num = list[length-1] for i, num in enumerate(list_): if i == last: last += num # 如果是刚好到达结尾就是等，如果是能跳出就是>= if last >= length: return True return Falseif __name__ == '__main__': main()
示例: 输入[1, 2, 3, 4]和[2, 4, 1, 0], 返回[2, 4, 1, 3] or ‘2413’
# 函数调用格式如下def main(): x = [1, 2, 3, 4] y = [2, 4, 1, 0] res = getclosenumber(x, y) print("res=%s" % res) def getclosenumber(x,y): x = sorted(x) res = [] for i in y: for j in x: if j>=i: res.append(j) x.remove(j) break return resif __name__ == '__main__': main() def get_min_value(a): left = 0 right = len(a) - 1 min_value = a[left] while left < right: mid = int(left + (right - left) / 2) min_value = min(a[left], min_value) if (a[mid] == a[left]) and (a[mid] == a[right]): left += 1 elif a[mid] >= a[left]: left = mid + 1 min_value = min(a[left], min_value) else: min_value = min(a[mid], min_value) right = mid - 1 return min_valuedef main(): a = [3, 4, 5, 6, 1, 2] res = get_min_value(a) print('res=%d' % res)if __name__ == '__main__': main() # 从左向右扫描一遍, 记录任意位置i的数字a[i]是否满足左边的所有数字都小于等于它, # 满足的话用flag标记。再从右向左扫描一遍, 记录任意位置i的数字a[i]是否满足右边 # 的所有数字都大于等于它, 满足的话最后判断一下刚才的flag标记是都等于1, 这样的i就是解。def get_point_number(a): length = len(a) result = [] flag = [0] * length first_max = a[0] for i in range(0, length): if a[i] >= first_max: first_max = a[i] flag[i] = 1 second_min = a[-1] for i in range(length - 1, -1, -1): if a[i] <= second_min: second_min = a[i] if flag[i] == 1: result.append(i) return resultdef main(): a = [1, 0, 1, 0, 1, 2, 3] res = get_point_number(a) print(res)if __name__ == '__main__': main()
转载地址：http://ivnws.baihongyu.com/