本文共 9675 字，大约阅读时间需要 32 分钟。

笔试刷题必备------ 数组

买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: [7,1,5,3,6,4]

输出: 7 1 2 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5]

输出: 4 1 2 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。 因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]

输出: 0 1 2 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

class Solution(object):    def max_profit(self,prices):        if prices==None or len(prices)<=1:            return 0        buy = 0        sell = 0        tag=0        profit = 0        length = len(prices)        for i in range(0,length-1):            if tag ==0 and prices[i] < prices[i+1]:                buy = prices[i]                tag = 1            elif tag == 1 and prices[i] > prices[i+1]:                sell = prices[i]                tag =0                profit += (sell-buy)        #从未买入过        if tag == 0 and sell == 0:            return 0        # 用来解决[1,2,3,4,5]这种一直没有卖出的情况        elif tag == 1 :            profit += (prices[length-1]-buy)        return profitif __name__ == "__main__":    solu = Solution()    print(solu.max_profit([1,2,3,4,5]))

旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3

输出: [5,6,7,1,2,3,4] 1 2 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2

输出: [3,99,-1,-100] 1 2 解释: 向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100] 说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。

要求使用空间复杂度为 O(1) 的 原地 算法。

class Solution(object):    def rotate(self,nums,k):        l = len(nums)        nums[:] = nums[l-k:]+nums[:l-k]        return numsif __name__ == "__main__":    solu = Solution()    print(solu.rotate([1,2,3,4,5,6,7],3))

存在重复

给定一个整数数组，判断是否存在重复元素。

如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例 1:

输入: [1,2,3,1]输出: true

示例 2:

输入: [1,2,3,4]输出: false

示例 3:

输入: [1,1,1,3,3,4,3,2,4,2]输出: true

class Solution(object):	def containsDuplicate(self,nums):		num_dict = {
   }		for i in nums:			if i not in num_dict:				my_dict[i] = 0			else:				return True		return False

利用python的set

class Solution(object):	def containsDuplicate(self,nums):		return len(nums) == len(set(nums))

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

y_ 示例 1:

输入: [2,2,1]输出: 1

示例 2:

输入: [4,1,2,1,2]输出: 4

class Solution(object):	def singleNumber(self,nums):		my_dict = {
   }		for i in nums:			if i not in my_dict:				my_dict[i] = 1			else:				my_dict[i] += 1		for k in my_dict.keys():			if my_dict[k] == 1:				return k

利用异或的技巧

class Solution(object):  def singleNumber(self,nums):        res = 0        for i in nums:            res ^= i        return res

两个数组的交集 II

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]输出: [2,2]

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出: [4,9]

说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。

我们可以不考虑输出结果的顺序。 进阶:

如果给定的数组已经排好序呢？你将如何优化你的算法？

如果 nums1 的大小比 nums2 小很多，哪种方法更优？ 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

class Solution(object):    def intersect(self,nums1,nums2):        nums1 = sorted(nums1)        nums2 = sorted(nums2)        new_list = []        i=0        j=0        while i < len(nums1) and j < len(nums2):            if nums1[i] == nums2[j]:                new_list.append(nums1[i])                i += 1                j += 1            elif nums1[i] < nums2[j]:                i += 1            else:                j += 1                         return new_list

加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

输入: [1,2,3]输出: [1,2,4]

解释: 输入数组表示数字 123。

示例 2:

输入: [4,3,2,1]输出: [4,3,2,2]

解释: 输入数组表示数字 4321。

class Solution(object):    def plus_one(self,nums_str):        nums = 0        t = 1        for i in range(len(nums_str)-1,-1,-1):            nums+=nums_str[i]*t            t *= 10        res = nums + 1        res_arr = []        for i in str(res):            res_arr.append(int(i))        return res_arrif __name__ == "__main__":    solu = Solution()    print(solu.plus_one([4,3,2,1]))

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]输出: [1,3,12,0,0]

说明:

必须在原数组上操作，不能拷贝额外的数组。

尽量减少操作次数。

class Solution(object):	def move_zero(self,nums):		for i in range(len(nums)-1):			for j in range(len(nums)-1-i):				if nums[j] == 0:					nums[j],nums[j+1] = nums[j+1],nums[j]		return numsif __name__ == "__main__":    solu = Solution()    print(solu.move_zero([0,1,0,5,65,0,3,12]))

两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

class Solution(object):    def two_sum(self,nums,target):        for i in range(len(nums)-1):            for j in range(i+1,len(nums)):                if nums[i] + nums[j] == target:                    return [i,j]        return None    if __name__ == "__main__":    solu = Solution()    print(solu.two_sum([2,7,11,15],9))

三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：

[ [-1, 0, 1], [-1, -1, 2] ]

class Solution(object):	def three_sum(self,nums):		res = []		nums.sort()		for cur in range(len(nums)):			#如果排序后的第一个元素都大于零就直接跳出			if nums[cur] > 0:				break			#跳过相邻相等的元素			if cur > 0 and nums[cur] == nums[cur-1]:				continue						nxt = cur + 1			last = len(nums)-1			while nxt < last:				if nums[nxt] + nums[last] == -nums[cur]:					res.append([nums[cur],nums[nxt],nums[last]])					#判断与nxt相等的相邻元素，并跳过它 					while nxt < last and nums[nxt] == nums[nxt+1]:						nxt += 1					#判断与last相等的相邻元素，并跳过它					while nxt < last and nums[last] == nums[last-1]:						last -= 1					#没有相等元素继续缩小范围					nxt += 1					last -= 1				elif nums[nxt] + nums[last] < nums[cur]:					nxt += 1				else:					last -= 1		return res

旋转图像

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明：

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:

给定 matrix =

[ [1,2,3], [4,5,6], [7,8,9] ],

原地旋转输入矩阵，使其变为:

[ [7,4,1], [8,5,2], [9,6,3] ] 示例 2:

给定 matrix =

[ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ],

原地旋转输入矩阵，使其变为:

[ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ] 常规解法：

class Solution(object):    def rotate(self,matrix):        tR = 0        tC = 0        dR = len(matrix)-1        dC = len(matrix[0])-1        while tR < dR and tC < dC:            self.rotate_edge(matrix,tR,tC,dR,dC)            tR += 1            tC += 1            dR -= 1            dC -= 1        return matrix    def rotate_edge(self,matrix,tR,tC,dR,dC):        times = dR-tR        for i in range(times):            temp = matrix[tR][tC+i]            matrix[tR][tC+i] = matrix[dR-i][tC]            matrix[dR-i][tC] = matrix[dR][dC-i]            matrix[dR][dC-i] = matrix[tR+i][dC]            matrix[tR+i][dC] = tempif __name__ == "__main__":    matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]    print(matrix)    solu = Solution()    print(solu.rotate(matrix))

Python解法：

def rotate(self, matrix):        """        :type matrix: List[List[int]]        :rtype: None Do not return anything, modify matrix in-place instead.        """        length = len(matrix)        for i in range(length):            for j in range(i+1,length):                temp = matrix[i][j]                matrix[i][j] = matrix[j][i]                matrix[j][i] = temp        for i in range(length):#把每一行逆序            matrix[i] = matrix[i][::-1]        return matrix

矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1:

输入:

[ [1,1,1], [1,0,1], [1,1,1] ] 输出: [ [1,0,1], [0,0,0], [1,0,1] ] 示例 2:

输入:

[ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] 输出: [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ] 进阶:

一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。

一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。 你能想出一个常数空间的解决方案吗？

class Solution(object):    def set_zeros(self,matrix):        row_list = []        col_list = []        for i in range(len(matrix)):            for j in range(len(matrix[0])):                if matrix[i][j] == 0:                    row_list.append(i)                    col_list.append(j)        while len(row_list) != 0 and len(col_list) != 0:            r = row_list.pop()            c = col_list.pop()            for i in range(len(matrix)):                for j in range(len(matrix[0])):                    if i == r or j == c:                        matrix[i][j] = 0        return matrixif __name__ == "__main__":    matrix = [  [0,1,2,0],  [3,4,5,2],  [1,3,1,5]]    print(matrix)    solu = Solution()    print(solu.set_zeros(matrix))

字谜分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],

输出: [ [“ate”,“eat”,“tea”], [“nat”,“tan”], [“bat”] ] 说明：

所有输入均为小写字母。

不考虑答案输出的顺序。

class Solution(object):	def group_anagrams(self,strs):		res_dict = {
   }		for s in strs:			sorted_s = ''.join(sorted(s))			if sorted_s not in res_dict.keys():				res_dict[sorted_s] = [s]			else:				res_dict[sorted_s].append(s)		return list(res_dict.values())

递增的三元子序列

给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。

数学表达式如下:

如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1，

使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。 说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。

示例 1:

输入: [1,2,3,4,5]

输出: true 示例 2:

输入: [5,4,3,2,1]

输出: false

class Solution(object):	def increasing_triplet(self,nums):		if len(nums) < 3:			return False		first = float('inf')		second = float('inf')		for i in nums:			if i < first:				first = i			elif i > first and i < second:				second = i			elif i > second:				return True		return False

转载地址：http://cluib.baihongyu.com/