Given an array and a value, remove all instances of that value in place and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example: Given input array nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.
Hint:
Try two pointers.
Did you use the property of "the order of elements can be changed"?
What happens when the elements to remove are rare?
class Solution(object):
def removeElement(self, nums, val):
"""
:type nums: List[int]
:type val: int
:rtype: int
"""
i, j, n = 0, 0, len(nums)
while j < n:
if nums[j] != val:
nums[i] = nums[j]
i += 1
j += 1
return i
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.
借助两个数组已经排序完成的特性，从后往前排，这样就不需要进行对nums1的移动操作了。
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: void Do not return anything, modify nums1 in-place instead.
"""
while m > 0 and n > 0:
if nums1[m-1] > nums2[n-1]:
nums1[m+n-1] = nums1[m-1]
m -= 1
else:
nums1[m+n-1] = nums2[n-1]
n -= 1
if n > 0:
nums1[:n] = nums2[:n]
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
思路还是比较简单的，准备一个数组来标记一个正整数是否出现过。
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = [0] * (len(nums) + 1)
for i in nums:
if i > 0 and i < len(nums)+1:
l[i] = 1
for i in range(1,len(nums)+1):
if l[i] == 0:
return i
return len(nums)+1
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up: Could you do this in-place?
注意数学个性，顺时针转90度，等于先轴对称转再翻转。
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
for i in range(n):
for j in range(i+1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for i in range(n):
for j in range(n/2):
matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
这里将三者之和化为两者之和等于第三者的方法很不错。
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums = sorted(nums)
sol = {}
n = 0
while n < len(nums) - 2:
i = n + 1
j = len(nums) - 1
s = -1 * nums[n]
while i < j:
if nums[i] + nums[j] < s:
i += 1
elif nums[i] + nums[j] > s:
j -= 1
else:
sol[str([nums[n], nums[i], nums[j]])] = [nums[n], nums[i], nums[j]]
i += 1
n += 1
return sol.values()
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
这里使用记录的方法，记录下了需要变0的行和列。
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
row=set([])
col=set([])
i,j=0,0
n,m=len(matrix), len(matrix[0])
for i in range(n):
for j in range(m):
if matrix[i][j]==0:
row.add(i)
col.add(j)
for i in range(n):
if i in row:
for j in range(m):
matrix[i][j]=0
for j in range(m):
if j in col:
for i in range(n):
matrix[i][j]=0
Follow up for "Remove Duplicates": What if duplicates are allowed at most twice?
For example, Given sorted array nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.
使用 count做标记，分类处理。
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0 or len(nums) == 1:
return len(nums)
i, j = 0, 1
count = 0
while j < len(nums):
if nums[i] == nums[j] and count == 0:
nums[i+1] = nums[j]
i += 1
j += 1
count = 1
elif nums[i] == nums[j] and count == 1:
j += 1
else:
nums[i+1] = nums[j]
i += 1
j += 1
count = 0
return i + 1
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library's sort function for this problem.
click to show follow up.
Follow up: A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?
用l,r来标记0和2的位置。
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
n = len(nums)
l, r, i = 0, n - 1, 0
while l < r and i <= r:
while nums[i] == 2 and i <= r:
nums[r], nums[i] = nums[i], nums[r]
r -= 1
while nums[i] == 0 and i >= l:
nums[l], nums[i] = nums[i], nums[l]
l += 1
i += 1