阶梯训练2-整数数组

171. 乱序字符串

给出一个字符串数组S，找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串，那么他存在一个字母集合相同，但顺序不同的字符串也在S中。

样例

对于字符串数组["lint","intl","inlt","code"]

返回["lint","inlt","intl"]

这题我想的是把两个字符串是变位词的代码重复利用一下，比较每两个字符串是否是变位词，结果超时了。

取字符串数组长度，设置标记位testlist，每取一个位置的字符串就设置该位置位为0。

length =len(strs)

testlist = [1forxinrange(length)]

result = []

比较每两个字符串，如果是变位词，将没有加到结果列表的字符串加进去，标记该位置已加入。

foriinrange(,length-1):

forjinrange(i+1,length):

iftestlist[j]+testlist[i]>:

ifself.isanagram(strs[i],strs[j]):

iftestlist[i]==1:

testlist[i] =

result.append(strs[i])

iftestlist[j]==1:

testlist[j] =

result.append(strs[j])

超时：

看看九章上的代码：

对每个字符串进行排序，如果排序后键不在字典中，将字符串加入该键值，如果键在字典中，该键增加该字符串。

遍历完字符串之后，再遍历字典，如果某个键元素超过一个，即为有变位词，将元素加入结果列表。

然后是整数数组：

172. 删除元素

给定一个数组和一个值，在原地删除与值相同的数字，返回新数组的长度。

元素的顺序可以改变，并且对新的数组不会有影响。

样例

给出一个数组[0,4,4,0,0,2,4,4]，和值 4

返回 4 并且4个元素的新数组为[0,0,0,2]

如果数组为空，返回0，

ifAis None:

return

如果数组中有与值相同的元素，删除并记录删除的数量。

length =len(A)

count =

whileA.count(elem) >:

A.remove(elem)

count +=1

returnlength - count

运行结果：

代码：

100. 删除排序数组中的重复数字

给定一个排序数组，在原数组中删除重复出现的数字，使得每个元素只出现一次，并且返回新的数组的长度。

不要使用额外的数组空间，必须在原地没有额外空间的条件下完成。

样例

给出数组A =[1,1,2]，你的函数应该返回长度2，此时A=[1,2]。

取数组长度length，从length-1位置到1位置，比较i与i-1位置数字是否相同，如果相同，删除i位置的数字。返回处理之后的数组长度。

length =len(nums)

foriinrange(length-1,,-1):

ifnums[i]==nums[i-1]:

delnums[i]

returnlen(nums)

运行结果：

64. 合并排序数组

合并两个排序的整数数组A和B变成一个新的数组。

样例

给出 A = , B =

合并之后 A 将变成

临时数组C保存排序结果，一个数组排序完了之后，另外一个数组剩下部分添加到结果末尾。

C = []

i =

j =

whilei

ifA[i]

C.append(A[i])

i +=1

else:

C.append(B[j])

j +=1

ifi == m:

temp = B[j:n]

C = C + temp

elifj == n:

temp = A[i:m]

C = C + temp

将结果赋值给A，

forxinrange(m+n):

A[x] = C[x]

A = A + C[m:m+n]