DS相关题目

DS相关题目

题目一：消失的数字

• 拿到这道题目之后，首先可以想到的一个解题方法就是，我们可以先排序，排完序之后，这个数组其实就是一个有序的数组了，那只用比较数组中的每一个元素和他对应的下标是不是相等的，如果是相等的，那么就说明对应的数字其实是存在的，如果是不相等的，那么就说明对应的数字其实就是不存在的了，但是如果要排序的话，使用sort方法就不符合题目中说的时间复杂度为O(n)了，但是在leetcode上还是可以通过编译的，代码如下

class Solution {
public:
    int missingNumber(vector<int>& nums) 
    {
        int i=0;
        sort(nums.begin(),nums.end());
        for(i=0;i<nums.size();)
        {
            if(nums[i]==i)
                i++;
            else
                break;
        }
        //return i;
        return i;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 解决这道题目的第二个思路其实就是位运算里面的异或，数组中有n个数，在这n个数的后面添加从0到n的每个整数，则添加了n+1个整数，共有2n+1个整数，在2n+1个整数中，消失的数字只在后面n+1个整数中出现一次，其余的数字在前 n个整数中（即数组中）和后面n+1个整数中各出现一次，即其余的数字都出现了两次。根据出现的次数的奇偶性，可以使用按位异或运算得到消失的数字。0和任何数字异或都是那个数字本身。由于2n+1个整数中，消失的数字出现了一次，其余的数字都出现了两次，因此对上述 2n+1个整数进行按位异或运算，结果就是消失的数字

class Solution {
public:
    int missingNumber(vector<int>& nums) 
    {
        int ret=0;
        for(int i=0;i<nums.size();i++)
        {
            ret^=nums[i];
        }
        for(int i=0;i<=nums.size();i++)
        {
            ret^=i;
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 第三种思路就是进行两个数字的做差，就可以求出来那个消失的数字

class Solution {
public:
    int missingNumber(vector<int>& nums) 
    {
        //第三种方式其实就是利用两个数组求和然后做剑法的方式，找到那个缺失的数字
        int a=0;
        int b=0;
        int n=nums.size();
        for(int i=0;i<nums.size();i++)
        {
            a+=nums[i];
        }
        b=(1+n)*n/2;
        return b-a;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

题目二:轮转数组

• 拿到这个题目之后，最先能想到的思路其实就是可以创建一个额外的数组，用n表示数组的长度，我们遍历原数组，将原数组下标为i的元素放至新数组下标为 (i+k) mod n 的位置，最后将新数组拷贝至原数组即可，代码如下所示

class Solution {
public:
    void rotate(vector<int>& nums, int k) 
    {
        int size=nums.size();
        vector<int> newarray(size);
        for(int i=0;i<size;i++)
        {
            newarray[(i+k)%size]=nums[i];
        }
        nums.assign(newarray.begin(),newarray.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

• 还有一种思路，就是分段对数组进行翻转的操作，其实用几个reverse操作就可以完成对这个题目的解答, 当nums长度为1，或者k=0时，不做处理;当nums长度≥k时，k除以nums长度取余数作为k。;第一段数组起止范围(nums.begin(), nums.begin() + k)，第二段数组起止范围(nums.begin() + k, nums.end())。

class Solution {
public:
    void rotate(vector<int>& nums, int k) 
    {
        if (nums.size() == 1 || k == 0) {
        }
        else {
            if (nums.size() >= k) 
            {
            
            }
            else 
            {
                k = k % nums.size();
            }
            reverse(nums.begin(), nums.end());
            reverse(nums.begin(), nums.begin() + k);
            reverse(nums.begin() + k, nums.end());
        }
    }
    vector<int> nums;
    int k;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

题目三:移除元素

• 这个题目首先会想到的思路其实就是暴力解法，可以依次遍历，遇到了符合的数字之后就进行移动覆盖其实就好了，但是这种解法的时间复杂度太高了，并不符合题目的要求，所以暂时不考虑这种解题思路
• 由于题目要求删除数组中等于 val 的元素，因此输出数组的长度一定小于等于输入数组的长度，我们可以把输出的数组直接写在输入数组上。可以使用双指针：右指针 right指向当前将要处理的元素，左指针 left指向下一个将要赋值的位置,如果右指针指向的元素不等于 val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移，如果右指针指向的元素等于val，它不能在输出数组里，此时左指针不动，右指针右移一位；整个过程保持不变的性质是：区间 [0,left)中的元素都不等于val。当左右指针遍历完输入数组以后，left的值就是输出数组的长度

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

题目四：删除有序数组中的重复项

• 这道题目的要求是：对给定的有序数组nums删除重复元素，在删除重复元素之后，每个元素只出现一次，并返回新的长度，上述操作必须通过原地修改数组的方法，使用 O(1)的空间复杂度完成
• 由于给定的数组nums是有序的，因此对于任意i
• 如果数组 nums的长度为0，则数组不包含任何元素，因此返回 0.当数组 nums的长度大于0时，数组中至少包含一个元素，在删除重复元素之后也至少剩下一个元素，因此 nums[0]保持原状即可，从下标1开始删除重复元素
• 定义两个指针fast和slow分别为快指针和慢指针，快指针表示遍历数组到达的下标位置，慢指针表示下一个不同元素要填入的下标位置，初始时两个指针都指向下标1
• 假设数组 nums 的长度为n。将快指针fast 依次遍历从1到n−1的每个位置，对于每个位置，如果 nums[fast]≠nums[fast−1]，说明 nums[fast]和之前的元素都不同，因此将 nums[fast]的值复制到 nums[slow]，然后将 slow 的值加1，即指向下一个位置

class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        //利用快慢指针进行求解
        int fast=1;
        int slow=1;
        int n=nums.size();
        if(nums.size()==0)
            return 0;
        while(fast<n)
        {
            if(nums[fast]!=nums[fast-1])
            {
                nums[slow]=nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

题目六：合并有序数组

• 从这个题目的描述中可以看出，题目给出来的两个数组都是有序的数组，而且是非递减的数组，那么拿到这个题目之后，首先最先想到的一个思路其实就是，直接把第二个数组合并到第一个数组上面，然后直接用C++的sort方法，进行排序，最终就可以合成一个有序的数组了，代码如下所示(暴力求解法)

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) 
    {
        for(int i=0;i<n;i++)
        {
            nums1[m+i]=nums2[i];
        }
        sort(nums1.begin(),nums1.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11

• 但是上面的代码效率没有那么高，还有一种解法就是依次去比较两个数组中的元素，把小的数字进行一个数组的尾插其实就可以了，但是这个题目又要求在原地进行一个求解，但是这种解法要创建一个额外的空间，也不符合题目的要求，那么怎么才能不利用第三个数字来对问题进行求解呢？—其实可以从后往前比，大的元素一定就是最大的那个元素(讲)

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) 
    {
        int i=m-1,j=n-1,k=m+n-1;
        while(i>=0&&j>=0)
        {
            nums1[k--]=nums1[i]>=nums2[j]?nums1[i--]:nums2[j--];
        }
        while(i>=0)
        {
            nums1[k--]=nums1[i--];
        }
        while(j>=0)
        {
            nums1[k--]=nums2[j--];
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

题目七:数组中数字出现的次数

• 拿到这个题目其实首先考虑先排序，然后顺序比较，将两项不同的数数字插入到一个新的数组中进行返回，但是这种做法不符合题目对于时间复杂度的要求，所以我们暂时先不考虑使用这中方法来进行求解

题目八：移除链表元素

• 拿到这个题目之后的思路，首先就是遍历链表，找到要删除的元素，然后利用链表删除的方式把对应的元素删除掉，这样的话，是需要两个指针的，因为链表删除的话，首先还是要记住要删除的那个元素的前一个元素，然后进行删除的操作，但是这个时候用两个指针有一个特殊的情况，就是链表的头节点就是要删除的元素的话，就没法取prev所存储的元素了，这样的话，其实也是很好处理的，单独处理一下头删的场景其实就是可以的了(讲)；还有另一种思路是把所有不是要删除的元素全部都拿出来进行尾插其实就可以了

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 typedef ListNode Node;
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) 
    {
        while(head!=NULL&&head->val==val)
        {
            head=head->next;
        }
        if(head==NULL)
            return head;
        else
        {
            Node *prev=head;
        while(prev->next)
        {
            if(prev->next->val==val)
            {
                prev->next=prev->next->next;
            }
            else
            {
                prev=prev->next;
            }
        }
        return head;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

题目九：链表的中间结点

• 这个题目其实很简单，找链表的中间结点，只需要先计算出链表中所拥有的元素的个数，然后就可以直接找到链表的中间结点了，但是这个思路其实有一个不太好的点就是这个思路需要遍历两次链表，如果题目中附带要求了只能遍历一次链表的话，那么这个方法就不适用了，但是这种思路也是可行的，代码如下所示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 typedef ListNode Node;
class Solution {
public:
    ListNode* middleNode(ListNode* head) 
    {
        int n=0;
        Node *cur=head;
        while(cur)
        {
            cur=cur->next;
            n++;
        }
        int k=0;
        cur=head;
        //求链表元素的个数
        while(k<n/2)
        {
            cur=cur->next;
            k++;
        }
        return cur;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

• 上面题目其实还有一种解提思路其实就是使用快慢指针的方式来对题目进行求解，慢的指针一次走一步，快的指针一次走两步

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 typedef ListNode Node;
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        Node* slow = head;
        Node* fast = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

题目十：链表的倒数第K个结点

• 这个题目也需要用到快慢指针的思想

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode *fast=pListHead;
        ListNode *slow=pListHead;
        while(k--){
            if(fast)
                fast=fast->next;
            else
                return NULL;
        }
        while(fast){
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

题目十一：合并两个有序链表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* preHead = new ListNode(0);

        ListNode* prev = preHead;
        while (l1 != nullptr && l2 != nullptr) 
        {
            if (l1->val < l2->val) 
            {
                prev->next = l1;
                l1 = l1->next;
            } 
            else 
            {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev->next = l1 == nullptr ? l2 : l1;

        return preHead->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

题目十二：反转链表

• 拿到这个题目首先想到的思路，其实是修改链表中指针的指向，在遍历链表时，将当前节点的next指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用，相关代码如下所示：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 typedef ListNode Node;
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        Node *prev=NULL;
        Node *cur=head;
        Node *next=NULL;
        while(cur)
        {
            next=cur->next;
            cur->next=prev;
            prev=cur;
            cur=next;
        }
        return prev;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

• 还有一种思路就是使用头插的思路，代码如下

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 typedef ListNode Node;
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        Node *cur=head;
        Node *pNewHead=NULL;
        while(cur)
        {
            Node *next=cur->next;
            cur->next=pNewHead;
            pNewHead=cur;
            cur=next;
        }
        return pNewHead;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

题目十二：链表的倒数第K个结点

• 找到链表的倒数第K个结点，一个很经典的思路就是使用快慢指针的方法进行求解

class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        ListNode *fast=pListHead;
        ListNode *slow=pListHead;
        while(k--){
            if(fast)
                fast=fast->next;
            else
                return NULL;
        }
        while(fast){
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

题目十三：链表分割

/*struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        //大体思路：创建两个链表，一个存储小于x的值，一个存储大于x的值，遍历原链表进行尾插。
        //创建哨兵卫
        struct ListNode* greatHead, *greattail, *lessHead, *lesstail, *cur;
        greatHead = greattail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lessHead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
        cur = pHead;
        
        //遍历原链表进行尾插
        while(cur)
        {
            if(cur->val < x)
            {
                lesstail->next = cur;  //链接原链表头节点
                lesstail = cur;    //更新less链表尾节点
                cur = cur->next;  //原链表中cur继续更新往下走
            }
            else
            {
                greattail->next = cur;
                greattail = cur;
                cur = cur->next;
            }
        }
        
        lesstail->next = greatHead->next;  //链接less链表和geart链表
        greattail->next = NULL;   //注意处理最后一个节点的原链接关系
        
        return lessHead->next;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40