首页 > 代码库 > leetcode-18-remove

leetcode-18-remove

283. Move Zeroes

技术分享

解题思路:

从nums[0]开始,如果是零就和它后面的第一个非零数交换,不是零就下一位。不贴代码了,比较简单。


27. Remove Element

技术分享

解题思路:

这道题对结果的顺序无要求,所以显然可以想到交换。我的思路是设置两个指针i和j,j先从后往前扫一下,找到第一个不是val的位置。

i从前向后,找到第一个是val的位置,nums[i]和nums[j]交换。最后,nums[j]后面都是val,所以返回j+1即是想要的长度。需要注意

的是,交换完之后,j向前走,前面仍然可能是val,所以需要加一个循环,找到前方第一个不是val的位置作为j的新位置。

int removeElement(vector<int>& nums, int val) {
        if (nums.size() == 0)
            return 0;
        if (nums.size() == 1) {
            if (nums[0] == val)
                return 0;
            else
                return 1;
        } 
        int i,j;
        j = nums.size() - 1;
        while (nums[j] == val) {
            j --;
            if (j < 0)
                return 0;
        }
        for (i = 0; i <= j; i++) {
            if (nums[i] == val) {
                nums[i] = nums[j];
                nums[j] = val;
                j --;
                // nums[j] may be val. then move forward.
                while (nums[j] == val)
                    j--;
                continue;
            }
            
        }
        return j+1;
    }

26. Remove Duplicates from Sorted Array

技术分享

解题思路:

考虑到nums是排好序的,所以先找到第一个与nums[i]不同的位置j,nums[i+1]=nums[j],然后i继续向前扫。如果nums[i]和nums[j]不相等,

那就继续向前扫咯。以1112222233为例。当然,如果有1111这种情况,在找j的时候,j会等于nums.size()这时候,终止就可以了。

int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 2)
            return nums.size();
        int i = 0;
        int j = i + 1;
        while(i < nums.size()-1) {
            if (nums[j] == nums[i]) {
                while (nums[j] == nums[i]) {
                    j++;
                    if (j == nums.size())
                        return i+1;
                }
                nums[i+1] = nums[j];
                i++;
                continue;
            }
            else {
                i++;
                j++;
            }
        }
        return i+1;
    }  

 

203. Remove Linked List Elements

技术分享

解题思路:

这道题WA好几次。。没考虑到连续几个数都是val的情况。我的思路是先处理头部是val的情况,然后处理val在second

的位置的情况。不过写的时候一定要考虑指针为空的情况,特别是用到->next赋值的时候。

ListNode* removeElements(ListNode* head, int val) {
        if (head == NULL)
            return head;
        // if val is at head
        while (head != NULL && head->val == val) {
            head = head->next;
        }
        if (head == NULL)
            return head;
        ListNode* first = head;
        ListNode* second = head->next;
        while (second != NULL) {
            if (second->val == val) {
                // judge if second is NULL. serial val
                while(second != NULL && second->val == val) {
                    second = second->next;
                }
                if (second == NULL) {
                    first->next = NULL;
                }
                else {
                    first->next = second;
                    first = second;
                    if (first != NULL)
                        second = first->next;
                    else
                        second = NULL;
                }
                continue;
            }
            // not val
            first = second;
            second = second->next;
        }
        return head;
    }

 

leetcode-18-remove