LeetCode开心刷题二十二天——41. First Missing Positive42. Trapping Rain Water

本是古典何须时尚 2023-08-17 15:14 71阅读 0赞

41. First Missing Positive

Hard

1825606FavoriteShare

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
    Output: 3

Example 2:

Input: [3,4,-1,1]
    Output: 2

Example 3:

Input: [7,8,9,11,12]
    Output: 1

Note:

Your algorithm should run in *O*(*n*) time and uses constant extra space.

ATTENTION：

we need to find the relationship between subscripts and array value.

Correct order is the subscripts i corresponding i+1,which means arr\[i\]=i+1;

So if you find this value is not the correct corresponding just swap it to the right place.

if(arr[i]!=i+1&&arr[i]>=1&&arr[i]<=n&&arr[arr[i]-1]!=arr[i])
    This code is the most important one,but you need to pay attention that if arr[i]-1<0
    the arr will outrange so when we dealing with arrays we need to pay attention to its
    subscripts

#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;
    //solve function
    class Solution
    {
    public:
        int firstMissingPositive(vector<int>& arr)
        {
            int res,n=arr.size();
            for(int i=0;i<n;)
            {
                if(arr[i]!=i+1&&arr[i]>=1&&arr[i]<=n&&arr[arr[i]-1]!=arr[i])
                {
                    swap(arr[i],arr[arr[i]-1]);
                }
                else
                {
                    i++;
                }
            }
            for(int i=0;i<n;i++)
            {
                if(arr[i]!=i+1)
                {
                    res=i+1;
                    return res;
                }
    
            }
            res=n+1;
            return res;
        }
    };
    int main()
    {
        Solution s;
        vector<int> arr={
         0,0,2};
        int res;
        res=s.firstMissingPositive(arr);
        cout<<res<<endl;
        return 0;
    }

The main progress is to use python,in face the thoughts are similar,so we need to operate skillfully

In fact,python has such difference with C,the main part is it needn't main function

Now paste the solution below,including main function,and we use class so we need to let b=solution()

class Solution(object):
        def firstMissingPositive(self, nums):
            for i in range(0,len(nums)):
                while nums[i]>0 and nums[i]<=len(nums) and nums[i]!=i+1 and nums[nums[i]-1]!=nums[i]:
                    nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
    
            for i in range(0, len(nums)):
                if nums[i] != (i+1):
                    return i+1
    
            return len(nums)+1
    
    nums=[3,4,-1,1]
    b=Solution()
    print(b.firstMissingPositive(nums))

42. Trapping Rain Water

Hard

388672FavoriteShare

Given *n* non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

![rainwatertrap.png][]  
The above elevation map is represented by array \[0,1,0,2,1,0,1,3,2,1,2,1\]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
    Output: 6

Accepted

312,934

Submissions

714,173

IDEA ATTENTION:

The first consensus to be agree is not to waste time on a problem more than 15mins believe me darling,you need to have a clear perceive to you situation.which also as you known ,dilemma!!You are racing with time

Now you must totally clear that time only can be used to deeper the right way instead of thinking useless method you are not strong enough to pave the new road.

The first solution mainly solve by layer.But it cost too much time.Also my own method,but not recommend

#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;
    class Solution {
    public:
        int trap(vector<int>& height) {
        int n=height.size(),res=0,cnt=1,global=0;
        if(n==0||n==1) return 0;
        int start=-1,ends=0,flag=0;
        while(1)
        {
            cnt=0;start=-1,ends=-1;
            for(int i=1;i<n-1;i++)
            {
                if(height[i]==0) flag=1;
                if(i+1>=n) break;
                if(height[i]==0&&(height[i+1]>height[i])&&(height[i-1]>height[i]))
                {
                    cnt++;
                }
                if(height[i]==0&&height[i+1]==0&&height[i-1]>0)
                {
                    start=i;
                }
                if(height[i]==0&&height[i-1]==0&&height[i+1]>0)
                {
                    ends=i;
                }
                if(start!=-1&&ends!=-1&&ends!=n-1&&(ends>start))
                {
    //                cout<<"cntb"<<cnt<<endl;
    //                cout<<ends<<"::"<<start<<endl;
                    cnt+=(ends-start+1);
    //                cout<<"cntA"<<cnt<<endl;
                    start=-1,ends=-1;
                }
                global=i;
            }
    //        cout<<"cnt"<<cnt<<endl;
            res+=cnt;
            for(int i=0;i<n;i++)
            {
               if(height[i]>0)
               height[i]--;
            }
            int flag0=0;
            for(int i=0;i<n;i++)
            {
               if(height[i]!=0)
                    flag0=1;
            }
            if(flag0==0) break;
        }
            return res;
        }
    };
    int main()
    {
        Solution s;
        vector<int> arr={
         4,9,4,5,3,2};
        int res;
        res=s.trap(arr);
        cout<<res<<endl;
        return 0;
    }

This is the correct way use two pointer:

#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;
    class Solution
    {
    public:
        int findWater(vector<int>& height)
        {
            int n=height.size(),left_max=0,right_max=0;
            if(n==0||n==1) return 0;
            int res=0,left=0,right=n-1;
            //we need to find this situation one less value between two high value
            
            while(left<right)
            {
                //if left's height already less than right,it means we get min value between left and right
                //then we can directly use this to minus
                if(height[left]<height[right])
                {
                    (left_max<height[left])?(left_max=height[left]):res+=left_max-height[left];
                    left++;
                }
                else
                {
                    (right_max<height[right])?(right_max=height[right]):res+=right_max-height[right];
                    right--;
                }
            }
            return res;
        }
    };
    int main()
    {
        Solution s;
        vector<int> height={
         0,1,0,2,1,0,1,3,2,1,2,1};
        int res;
        res=s.findWater(height);
        cout<<res<<endl;
        return 0;
    }

Python Version:

Special Assignment：

just put variable inorder between = left and right

left,right=0,len(height)-1

In python we make class Instantiation like this:

solu = Solution()

Python Code:

class Solution(object):
        def trap(self, height):
            """
            :type height: List[int]
            :rtype: int
            """
            if not height:return 0
            left_max=right_max=res=0
            left,right=0,len(height)-1
    
            while left<right:
                if height[left]<height[right]:
                    if left_max>height[left]:
                        res+=left_max-height[left]
                    else:
                        left_max=height[left]
                    left+=1
                else:
                    if right_max>height[right]:
                        res+=right_max-height[right]
                    else:
                        right_max=height[right]
                    right-=1
    
            return  res
    
    if __name__ == '__main__':
        height=[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
        solu = Solution()
        print(solu.trap(height))

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

[rainwatertrap.png]: https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png