1. 移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
出处：
https://edu.csdn.net/practice/26880573
代码：
class Solution(object): def removeElement(self, nums, val): ls = len(nums) if ls == 0: return ls count = 0 index = 0 while index < ls - count: if nums[index] == val: nums[index] = nums[ls - 1 - count] count += 1 else: index += 1 return ls - count if __name__ == '__main__': s = Solution() print(s.removeElement([3,2,2,3], 3)) print(s.removeElement(nums = [0,1,2,2,3,0,4,2], val = 2))
输出：
2
5
2. 删除排序链表中的重复元素
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
返回同样按升序排列的结果链表。
示例 1：
输入：head = [1,1,2]
输出：[1,2]
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
提示：
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列
出处：
https://edu.csdn.net/practice/26880574
代码：
class ListNode(object): def __init__(self, x): self.val = x self.next = None class LinkList: def __init__(self): self.head=None def initList(self, data): self.head = ListNode(data[0]) r=self.head p = self.head for i in data[1:]: node = ListNode(i) p.next = node p = p.next return r def convert_list(self,head): ret = [] if head == None: return node = head while node != None: ret.append(node.val) node = node.next return ret class Solution(object): def deleteDuplicates(self, head): if head is None: return None pos = head while pos is not None and pos.next is not None: if pos.val == pos.next.val: pos.next = pos.next.next else: pos = pos.next return head # %% s = Solution() l = LinkList() list1 = [1,1,2] l1 = l.initList(list1) print(l.convert_list(s.deleteDuplicates(l1))) list2 = [1,1,2,3,3] l2 = l.initList(list2) print(l.convert_list(s.deleteDuplicates(l2)))
输出：
[1, 2]
[1, 2, 3]
3. 搜索旋转排序数组 II
已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
示例 2：
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false
提示：
1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10^4 <= target <= 10^4
进阶：
这是 搜索旋转排序数组 的 延伸题目，本题中的 nums 可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
出处：
https://edu.csdn.net/practice/26880575
代码：
class Solution(object): def search(self, nums, target): """ :type nums: List[int] :type target: int :rtype: bool """ def get(start, end): if start > end: return False mid = (start + end) / 2 mid = int(mid) while mid < end and nums[mid + 1] == nums[mid]: mid += 1 while start < mid and nums[start + 1] == nums[start]: start += 1 if nums[mid] == target: return True elif mid == end: return get(start, mid - 1) elif start == mid: return get(mid + 1, end) elif nums[mid] >= nums[start]: if target >= nums[start] and target < nums[mid]: return get(start, mid - 1) else: return get(mid + 1, end) elif nums[mid] <= nums[end]: if target > nums[mid] and target <= nums[end]: return get(mid + 1, end) else: return get(start, mid - 1) return get(0, len(nums) - 1) # %% s = Solution() print(s.search(nums = [2,5,6,0,0,1,2], target = 0)) print(s.search(nums = [2,5,6,0,0,1,2], target = 3))
输出：
True
False
