数据结构与算法练习题（含答案）.docxVIP

数据结构与算法练习题（含答案）

1.数组相关问题

问题1：移除数组中的重复元素

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。

示例：

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

函数应该返回新的长度2，并且原数组nums的前两个元素被修改为1,2。

你不需要考虑数组中超出新长度后面的元素。

代码实现（Python）：

```python

defremoveDuplicates(nums):

ifnotnums:

return0

i=0

forjinrange(1,len(nums)):

ifnums[j]!=nums[i]:

i+=1

nums[i]=nums[j]

returni+1

nums=[1,1,2]

length=removeDuplicates(nums)

print(length)

print(nums[:length])

```

解释：

我们使用双指针法，一个指针`i`用于记录不重复元素的位置，另一个指针`j`用于遍历数组。当`nums[j]`与`nums[i]`不同时，说明遇到了一个新的不重复元素，将`i`指针向后移动一位，并将`nums[j]`的值赋给`nums[i]`。最后返回`i+1`即为不重复元素的个数。

问题2：旋转数组

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

示例：

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

输出:[5,6,7,1,2,3,4]

解释:

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

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

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

代码实现（Python）：

```python

defrotate(nums,k):

n=len(nums)

k=k%n

nums[:]=nums[n-k:]+nums[:n-k]

nums=[1,2,3,4,5,6,7]

k=3

rotate(nums,k)

print(nums)

```

解释：

首先，为了避免不必要的旋转，我们将`k`对数组长度`n`取模。然后，我们将数组的后`k`个元素和前`n-k`个元素拼接起来，得到旋转后的数组。

2.链表相关问题

问题1：反转链表

反转一个单链表。

示例：

输入:1-2-3-4-5-NULL

输出:5-4-3-2-1-NULL

代码实现（Python）：

```python

classListNode:

def__init__(self,val=0,next=None):

self.val=val

self.next=next

defreverseList(head):

prev=None

curr=head

whilecurr:

next_node=curr.next

curr.next=prev

prev=curr

curr=next_node

returnprev

创建链表1-2-3-4-5

head=ListNode(1)

head.next=ListNode(2)

head.next.next=ListNode(3)

head.next.next.next=ListNode(4)

head.next.next.next.next=ListNode(5)

new_head=reverseList(head)

whilenew_head:

print(new_head.val,end=-)

new_head=new_head.next

print(NULL)

```

解释：

我们使用迭代的方法，通过三个指针`prev`、`curr`和`next_node`来反转链表。`prev`指针初始化为`None`，`curr`指针指向链表的头节点。在每一次迭代中，我们先保存`curr`的下一个节点到`next_node`，然后将`curr`的`next`指针指向`prev`，接着更