Algorithm

NGINX typically supports two scenarios for configuring multiple certificates:

问题： 给定一个整数数组，编写一个函数，返回从左到右读取数组时出现多次的第一个整数。数组元素取值范围是整数1到n， 数组长度为n. 比较特殊情况 [2,3,4,2,3,5] 返回2 [2,3,4,4,2,5] 返回4， 虽然2也是重复数字但是再2之后。 解答： 遍历查找， 两次嵌套循环，同时标注最小索引。 1 2 3 4 5 6 7 8 9 10 11 def firstDuplicateValue(array): # Write your code here. max = len(array) value = -1 for i in range(len(array)): for j in range(len(array)): if (j > i and array[j] == array[i]): if (j < max): max = j value = array[i] return value 使用哈希表 ...

问题： Given an array arr[] of n integers, construct a Product Array prod[] (of the same size) such that prod[i] is equal to the product of all the elements of arr[] except arr[i]. 解答: 遍历数组循环跳过当前元素，需要两层循环， 时间复杂度O(n^2),空间复杂度O(n) 1 2 3 4 5 6 7 8 9 def arrayOfProducts(array): products = [1 for _ in range(len(array))] for i in range(len(array)): runningProduct = 1 for j in range(len(array)): if i != j: runningProduct = runningProduct * array[j] products[i] = runningProduct return products ...

Given an array arr with N elements, the task is to find out the longest sub-array which has the shape of a mountain

问题： Given an m x n matrix, return all elements of the matrix in spiral order.Input: 1 2 3 4 5 array = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16 ] ] Output: [1,2,3,4,8,12,11,10,9,5,6,7] 解答: 首先确定行列的边界值， startRow，endRow，startCol，endCol 按照题目的要求进行螺旋便利 ， 分别向右， 向下， 向左， 向上移动，对应四个循环。 特殊情况检查， 当出现单行或者单列的情况，在向左或向上遍历前， 分别检查行或列的边界值是否相等， startRow == endRow 或 startCol == endCol ， 相等则停止遍历。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 def spiralTraverse(array): # Write your code here. result = [] startRow , endRow = 0, len(array) - 1 startCol, endCol = 0, len(array[0]) - 1 while startRow <= endRow and startCol <= endCol: # right col for col in range(startCol, endCol + 1): result.append(array[startRow][col]) # down row for row in range(startRow + 1, endRow + 1): result.append(array[row][endCol]) # left col reversed for col in reversed(range(startCol, endCol)): if startRow == endRow: break; result.append(array[endRow][col]) # up row reversed for row in reversed(range(startRow+1, endRow)): if startCol == endCol: break; result.append(array[row][startCol]) startRow = startRow + 1 endRow = endRow -1 startCol = startCol + 1 endCol = endCol - 1 return result ...

问题： An array is monotonic if it is either monotone increasing or monotone decreasing. An array nums is monotone increasing if for all i <= j, nums[i] <= nums[j]. An array nums is monotone decreasing if for all i <= j, nums[i] >= nums[j]. Given an integer array nums, return true if the given array is monotonic, or false otherwise. 解答: 单调数组，当数组个数大于2时， 遍历数组， 通过比较当当前值与前一个值的，确定其是递增还是递减， 遍历过程中，如果有变化那么则不满足单调性。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 def isMonotonic(array): if len(array) <= 2: return True direction = array[1] - array[0] for i in range(2, len(array)): if direction == 0: direction = array[i] - array[i-1] continue if breakDirection(direction , array[i], array[i-1]): return False; return True; def breakDirection (direction, val, preval): diff = val - preval if direction > 0: return diff < 0 else: return diff > 0 ...

问题： 给定一系列正整数，代表硬币的面值，找到无法从这些整数组连续组合成的最小值。比如 coins=[1,2,5], 最小不能组合成的值为4. 解答： 如果下一个整数大于前面所有值的累积和 + 1，那么就知道最小值，如果能被组合范围[0, sum], 下一个数据为y， 如果能构造出联系数据 sum+1 要在 [y，sum+y]范围内。也就是y<=sum+1<=sum+y。 由于排序数组 y>=1, 也就是满足y>sum+1。就可以找到最小组合值。 1 2 3 4 5 6 7 8 9 10 11 def nonConstructibleChange(coins): # Write your code here. coins.sort() currentChangeCreated = 0 for coin in coins: if coin > currentChangeCreated + 1: return currentChangeCreated + 1 currentChangeCreated += coin return currentChangeCreated + 1 ...

问题 循环赛每个队对战所有其他对手， 胜利者记3分， 失败者记1分. 两个数组做为输入， competitions，存放主场队和客场队， results存放结果， 1表示主队获胜， 0表示客队获胜。返回分数最高的队伍。 解答 使用一个hash表，key为队伍名称， 值为累计分数。时间复杂度O(n) 循环赛的数量， 空间复杂度O(k), 参赛队数量。对应hash表需要的容量。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 def tournamentWinner(competitions, results): currentBestTeam = "" scores = {currentBestTeam: 0} for idx, competition in enumerate(competitions): result = results[idx] homeTeam, awayTeam = competition winningTeam = homeTeam if result == 1 else awayTeam updateScores(winningTeam, 3 , scores) if scores[winningTeam] > scores[currentBestTeam]: currentBestTeam = winningTeam return currentBestTeam def updateScores(team, points, scores): if team not in scores: scores[team] = 0 scores[team] += points 参考及引用 图片from Akihito Ichiyama

Given an integer array nums sorted in non-decreasing order, return _an array of the squares of each number sorted in non-decreasing order

Given two strings s and t, check if s is a subsequence of t