LeetCode开心刷题十五天——26. Remove Duplicates from Sorted Array27. Remove Element28. Implement strStr()...

旧城等待， 2023-08-17 15:14 62阅读 0赞

26. Remove Duplicates from Sorted Array

Easy

15913410FavoriteShare

Given a sorted array *nums*, remove the duplicates [in-place][] such that each element appear only *once* and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array [in-place][] with O(1) extra memory.

Example 1:

Given nums = [1,1,2],
    
    Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
    
    It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],
    
    Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
    
    It doesn't matter what values are set beyond the returned length.
    
    Main Problem is to correctly understand the problem ,when I first saw this function I see int is the return type.
    I only think it's need return the number of sum,but actually it also need to move vector variable
    The most unimaginable thing is this problem only see first-N variable.You needn't see the last of array,You 
    even needn't delete them from your vector.Unimaginable
    But it also reflect that I'm not familiar with the method to delete from STL vector.
    Special Remind,In myfunction main function fo not watch(不配套) with the solution part.Main use to see the vector's constitute

#include <iostream>
    #include<vector>
    #include<iostream>
    #include<string>
    #include<stdio.h>
    #include<string.h>
    #include<iomanip>
    #include<vector>
    #include<list>
    #include<queue>
    #include<algorithm>
    #include<stack>
    #include<map>
    using namespace std;
    struct ListNode {
          int val;
          ListNode *next;
          ListNode(int x) : val(x), next(NULL) {}
      };
    
    class Solution {
    public:
        int removeDuplicates(vector<int>& nums) {
            const int n=nums.size();
            //special case
            if(n<=1) return n;
            //int res=0,keep=nums[0];
            int ans=0,j;
            for(int i=0;i<n;)
            {
                nums[ans++]=nums[i];
                j=i+1;
                while(j<n&&nums[j-1]==nums[j])
                    j++;
                i=j;
            }
    
            return ans;
        }
    };
    //class Solution {
    //public:
    //  vector<int>& removeDuplicates(vector<int>& nums) {
    //    const int n = nums.size();
    //    //if (n <= 1) return n;
    //    int ans = 0;
    //    int i = 0;
    //    while (i < n) {
    //      nums[ans++] = nums[i];
    //      int j = i + 1;
    //      while (j < n && nums[j] == nums[j - 1]) ++j;
    //      i = j;
    //    }
    //    return nums;
    //  }
    //};
    int main()
    {
    
        ListNode a(1);
        ListNode b(2);
        ListNode c(3);
        ListNode d(4);
        ListNode e(5);
        Solution s;
        a.next=&b;
        b.next=&c;
        c.next=&d;
        d.next=&e;
        ListNode *head=&a;
    //    while(head)
    //    {
    //        cout<<head->val<<endl;
    //        head=head->next;
    //    }
        //ListNode* res=NULL;
    
        vector<int> nums;
        vector<int> res;
        nums.push_back(1);
        nums.push_back(1);
        nums.push_back(2);
        res=s.removeDuplicates(nums);
        //ShowVec(res);
        //cout<<res<<endl;
    //    res=s.reverseKGroup(head, k);
        for(auto v:res)
        {
            cout<<v<<endl;
        }
        return 0;
    }

27. Remove Element

Easy

8731853FavoriteShare

Given an array *nums* and a value *val*, 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 by modifying the input array [in-place][] with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,
    
    Your function should return length = 2, with the first two elements of nums being 2.
    
    It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,
    
    Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
    
    Note that the order of those five elements can be arbitrary.
    
    It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
    int len = removeElement(nums, val);
    
    // any modification to nums in your function would be known by the caller.
    // using the length returned by your function, it prints the first len elements.
    for (int i = 0; i < len; i++) {
        print(nums[i]);
    }
    
    
    Total same with previous one,one interesting thing to mention is that the method we used to handle special case

in the previous one.can be a stumbling stone to success.Because the different of these two is,one need to eliminate 
    duplicate,another is to eliminate all one kinds of number.It means in the first method it will be kept once
    but in the second we hope it never to appear again.
    As more and more subjects are studied ,we will have this feeling,some questions are similar,Find similarity is a good 
    thing,But the most important is to find to difference to clarify them
    (当感到某些题目相似时，切记，找不同就成了新的难点，到底之前的方法能不能照搬过来，问题的关键点区别在哪，请万望不要掉以轻心)

#include <iostream>
    #include<vector>
    #include<iostream>
    #include<string>
    #include<stdio.h>
    #include<string.h>
    #include<iomanip>
    #include<vector>
    #include<list>
    #include<queue>
    #include<algorithm>
    #include<stack>
    #include<map>
    using namespace std;
    struct ListNode {
          int val;
          ListNode *next;
          ListNode(int x) : val(x), next(NULL) {}
      };
    
    class Solution {
    public:
        int removeElement(vector<int>& nums, int val) {
            const int n=nums.size();
            //special case
            //if(n<=1) return n;
            //int res=0,keep=nums[0];
            int ans=0,j;
            for(int i=0;i<n;)
            {
                while(i<n&&nums[i]==val) i++;
                if(i<n)
                    nums[ans++]=nums[i++];
            }
    
            return ans;
        }
        int removeDuplicates(vector<int>& nums) {
            const int n=nums.size();
            //special case
            if(n<=1) return n;
            //int res=0,keep=nums[0];
            int ans=0,j;
            for(int i=0;i<n;)
            {
                nums[ans++]=nums[i];
                j=i+1;
                while(j<n&&nums[j-1]==nums[j])
                    j++;
                i=j;
            }
    
            return ans;
        }
    };
    //class Solution {
    //public:
    //  vector<int>& removeDuplicates(vector<int>& nums) {
    //    const int n = nums.size();
    //    //if (n <= 1) return n;
    //    int ans = 0;
    //    int i = 0;
    //    while (i < n) {
    //      nums[ans++] = nums[i];
    //      int j = i + 1;
    //      while (j < n && nums[j] == nums[j - 1]) ++j;
    //      i = j;
    //    }
    //    return nums;
    //  }
    //};
    int main()
    {
    
        ListNode a(1);
        ListNode b(2);
        ListNode c(3);
        ListNode d(4);
        ListNode e(5);
        Solution s;
        a.next=&b;
        b.next=&c;
        c.next=&d;
        d.next=&e;
        ListNode *head=&a;
    //    while(head)
    //    {
    //        cout<<head->val<<endl;
    //        head=head->next;
    //    }
        //ListNode* res=NULL;
    
        vector<int> nums;
        //vector<int> res;
        nums.push_back(1);
    //    nums.push_back(1);
    //    nums.push_back(2);
        int res=s.removeElement(nums,1);
        //res=s.removeDuplicates(nums);
        //ShowVec(res);
        //cout<<res<<endl;
    //    res=s.reverseKGroup(head, k);
    //    for(auto v:res)
    //    {
    //        cout<<v<<endl;
    //    }
    //    return 0;
        cout<<res<<endl;
    }

28. Implement strStr()

Easy

9251363FavoriteShare

Implement [strStr()][strStr].

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
    Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
    Output: -1

Clarification:

What should we return when `needle` is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when `needle` is an empty string. This is consistent to C's [strstr()][strStr] and Java's [indexOf()][indexOf].

Main idea:
    1.Attention:this solve method is totally different with LCS(最长公共子序列)It's looks very similar
    But this question can be solved easier
    2.My fault,Firstly,I want to iterate through the string once,But it has problem
    eg:

mississipii
        issip

we can observe that for the reason that "issi" part repeated twice,if we only traversal once.we will miss this problem ,but LCS is too complex,add a lot of extra space.So we can tranverse haystack n-m times, minus m is very important point!!!!!!!!! it can greatly improve the running speed.

The question metioned that if needle ==" " return 0;

At first I deal with this separately.But in fact we can combine it,because if needle = =" "，it means length=0,if after loop j=0,j==length,these are same situation,this makes code clean and neat.

if(j==m)
       return i;

Code Time:

转载于:https://www.cnblogs.com/Marigolci/p/11149555.html

[in-place]: https://en.wikipedia.org/wiki/In-place_algorithm
[strStr]: http://www.cplusplus.com/reference/cstring/strstr/
[indexOf]: https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#indexOf%28java.lang.String%29