1、二分查找:
class Solution: def search(self, nums, target): right = len(nums) - 1 left = 0 while left <= right: middle = (left + right)//2 if nums[middle] < target: left = middle + 1 elif nums[middle] > target: right = middle - 1 else: return middle return -1 nums = [1,3,5,6,7,9,12] target = 3 a = Solution().search(nums,target) print(a)
2、使用双指针法移除元素
class Solution: def remove(self,nums,val): fast = slow = 0 while fast < len(nums): if nums[fast] != val: nums[slow] = nums[fast] slow += 1 fast += 1 return slow nums = [1,3,5,3,7,9,12] target = 3 a = Solution().remove(nums,target) print(a)
3、有序数组的平方:
class Solution: def sortedSquares(self, nums): for i in range(len(nums)): nums[i] = nums[i]**2 nums.sort() return nums nums = [-1,3,-5,7,9,12] a = Solution().sortedSquares(nums) print(a) #使用双指针法 class Solution: def sortedSquares(self, nums): n = len(nums) i = 0 j = n-1 k = n-1 ans = [-1]*n print(ans) while i <= j: lm = nums[i]**2 rm = nums[j]**2 if lm > rm: ans[k] = lm i += 1 else: ans[k] = rm j -= 1 k -= 1 return ans nums = [-1,3,-5,7,9,12] a = Solution().sortedSquares(nums) print(a)
4、长度最小的子数组:
class Solution: def minSubArrayLen(self, nums, target): if not nums: return 0 n = len(nums) ans = n + 1 start = 0 end = 0 sum = 0 while end < n: sum += nums[end] while sum >= target: ans = min(ans, end - start + 1) sum -= nums[start] start += 1 end += 1 return 0 if ans == n+1 else ans nums = [2,3,1,2,4,3] a = Solution().minSubArrayLen(nums,7) print(a)
5、螺旋矩阵
class Solution: def generateMatrix(self, n): matrix = [[0]*n for _ in range(n)] #空矩阵表示方法 print(matrix) left, right, up, down = 0, n-1, 0, n-1 number = 1 while left < right and up < down: for x in range(left, right): matrix[up][x] = number number += 1 for y in range(up, down): matrix[y][right] = number number += 1 for x in range(right, left, -1): matrix[down][x] = number number += 1 for y in range(down, up, -1): matrix[y][left] = number number += 1 left += 1 right -= 1 up += 1 down -= 1 if n % 2: matrix[n//2][n//2] = number return matrix a = Solution().generateMatrix(4) print(a)