LeetCode中等题(二)

朴灿烈づ我的快乐病毒、 2021-10-19 09:12 375阅读 0赞

题目一：

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = \[-1, 0, 1, 2, -1, -4\]，

满足要求的三元组集合为：  
\[  
\[-1, 0, 1\],  
\[-1, -1, 2\]  
\]

分析：这是一道三元组求和问题

1、首先定义返回的元组类型，List<List<Integer>> ans=new ArrayList<>()；

2、对刚开始的数组进行排序，Arrays.sort(nums)；

3、通过一个指针遍历整个数组for(int i=0;i<num.lenght;i++)

4、再设置两个指针，分别是l=i+1，r=len-1；

5、接下来开始求和进行判断；if(nums\[i\]+nums\[l\]+nums\[r\]==0)将l++,r--；

6、当然应该存入到ans.add(Arrays.asList(nums\[i\],nums\[l\],nums\[r\]))；

7、在这个过程可能产生重复，if(nums\[i\]>0) break，if(i>&&nums\[i\]==nums\[i-1\]) continue；while(nums\[l\]==nums\[l+1\]) l++; r同样；

8、如果和不同sum<0，l++;sum>0，r--;

9、返回ans；

具体代码：

class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            
            List<List<Integer>> ans=new ArrayList<>();
            int len=nums.length;        
            if(nums==null||len<3) return ans;
            
            Arrays.sort(nums);
            
            for(int i=0;i<len;i++)
            {
                int l=i+1,r=len-1;
                if(nums[i]>0) break;
                if(i>0&&nums[i]==nums[i-1]) continue;
                while(l<r)
                {
                    int sum=nums[i]+nums[l]+nums[r];
                    if(sum==0)
                    {
                        ans.add(Arrays.asList(nums[i],nums[l],nums[r]));
                        while(l<r&&nums[l]==nums[l+1]) l++;
                        while(l<r&&nums[r]==nums[r-1]) r--;
                        l++;
                        r--;
                    }
                    else if(sum<0) l++;
                    else if(sum>0) r--;                    
                }
            }        
            return ans;
        }        
    }

题目二：

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

\[  
"((()))",  
"(()())",  
"(())()",  
"()(())",  
"()()()"  
\]

方法一：

1、首先产生所有括号的情况；

2、采用递归算法，先定义一个函数实现所有括号的情况，其等于‘(’+n-1的序列和‘）’+n-1的序列和

3、进行判断所产生的序列是否有效，设置一个balance=0，if(c=='(') balance++；否则balance--；

4、如果balance<0 返回false；

具体代码：

class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> result=new ArrayList();
            
            GenerateAll(new char[2*n],0,result);
            return result;       
        }
        
        public void GenerateAll(char[] current,int pos,List<String> res)
        {
            if(current.length==pos)
            {
                if(Valid(current))
                {
                    res.add(new String(current));
                }
            }
            else {
                current[pos]='(';
                GenerateAll(current,pos+1,res);
                current[pos]=')';
                GenerateAll(current,pos+1,res);
            }
        }
        
        public boolean Valid(char[] current)
        {
            int balance=0;
            for(char c:current)
            {
                if(c=='(') balance++;
                else {
                    balance--;
                }
                
                if(balance<0) return false;
            }
            
            return (balance==0);
        }
    }

题目三：

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

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

方法一：

1、采用暴力法，双循环遍历出所有的情况；

2、进行逐个比较取最大值，计算公式为数组最小值和两个数组值之间的距离进行相乘；

具体代码：

class Solution {
        public int maxArea(int[] height) {
            
            int ans=0;
            int result=0;
            int minVal=0;
            for(int i=0;i<height.length;i++)
                for(int j=i+1;j<height.length;j++)
                {
                    minVal=Math.min(height[i], height[j]);
                    result=minVal*(j-i);
                    ans=Math.max(ans, result);
                }
            
            return ans;
        }
    }

方法二：

1、使用双指针，一个数组第一位开始，另一个从数组的最后一位开始；

2、保持数组最大值不动，移动最小的值；

具体代码：

class Solution {
        public int maxArea(int[] height) {
            
            int p=0,q=height.length-1;
            int ans=0;
            int minVal=0;
            int result=0;
            
            while(p<q)
            {
                int distance=q-p;
                
                minVal=Math.min(height[p], height[q])
                if(height[p]<height[q])
                {
                    minVal=height[p];
                    p++;
                }
                else {
                    minVal=height[q];
                    q--;
                }
                result=minVal*distance;
                ans=Math.max(ans, result);
            }        
            return ans;
        }
    }

题目四：

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

方法一：

1、递归实现，如果是两两反转递归应该是swapPairse(next.next)；

2、head.next=swapPairse(next.next)，next.next=head；

3、返回next:

4、递归一定要有递归出口，递归出口，递归出口，if(head==null||head.next==null) return head；

具体代码：

class Solution {
        public ListNode swapPairs(ListNode head) {
            
            if(head==null||head.next==null)
                return head;
            
            ListNode next=head.next;
            head.next=swapPairs(next.next);
            next.next=head;
            
            return next;
        }
    }

方法二：

非递归算法

具体代码：

class Solution {
        public ListNode swapPairs(ListNode head) {
            
            ListNode dummy=new ListNode(0);
            dummy.next=head;
            
            ListNode curr=dummy;
            
            while(curr.next!=null&&curr.next.next!=null)
            {
                ListNode start=curr.next;
                ListNode end=curr.next.next;
                curr.next=end;
                start.next=end.next;
                end.next=start;
                curr=start;
            }
            return dummy.next;
        }
    }

题目五：

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

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

方法一：

1、现对原始数组排序，Arrays.sort(nums)；

2、返回return nums\[nums.leght-k\]，这种方式较为简单；

方法二：

1、使用大顶堆获取最大的k个数；

2、java中使用优先队列PriorityQueue类定义了最小堆的实现，PriorityQueue<Integer> heap=new PriorityQueue<>()，通过这个函数得到的是最小堆；

3、对数组元素进行遍历，for(i：nums)  heap.add(i)，值得注意的是当一个元素加入到堆当中，系统自动将最小的元素放到堆顶排序好；

4、if(heap.size()>k) heap.poll()；将堆顶元素删除，并且又最后一个元素覆盖，再次进行建立最小堆；

5、最后得到k个元素的最小堆，因为本地要输出第k个大小的值，刚好输出堆顶元素；

具体代码：

class Solution {
        public int findKthLargest(int[] nums, int k) {
            
            PriorityQueue<Integer> pQueue=new PriorityQueue<>();        
            for(int i:nums)
            {
                pQueue.add(i);
                
                if(pQueue.size()>k)
                    pQueue.poll();
            }
            
            return pQueue.poll();
      }
    }

题目六：

给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)

方法：

1、这里关键是有正数，负数，0的区别；

2、如果是三个正数直接求前三个最大值就是最后的结果；

3、如果负数刚开始不太容易想到，求数组中最小的两个负数，再和最大值乘积就是最大值；

4、如何得到 前三个正数，每次进行判断if(nums\[i\]>max1) max3=max2,max2=max1,max1=nums\[i\]采用这种循序渐进的方式求出；

5、同样求最小的两个负数也类似；

6、值得注意的是，本地如果是 Int类型并不能通过，需要long类型；

具体代码：

public class Main{
            public static long MaxProduct(int n,long[] arr)
        {
            long max1=0,max2=0,max3=0,min1=0,min2=0;
            for(int i=0;i<n;i++)
            {
                if(arr[i]!=0)
                {
                    if(arr[i]>max1)
                    {
                        max3=max2;
                        max2=max1;
                        max1=arr[i];
                    }
                    else if(arr[i]>max2)
                    {
                        max3=max2;
                        max2=arr[i];
                    }
                    else if(arr[i]>max3) 
                    {
                        max3=arr[i];
                    }
                    else if(arr[i]<min1) 
                    {
                        min2=min1;
                        min1=arr[i];
                    }
                    else if (arr[i]<min2) {
                        min2=arr[i];
                    }
                }
                else {
                    continue;
                }
            }
            
            return Math.max(max1*max2*max3,max1*min1*min2);
        }
        
        public static void main(String[] arg)
        {
            Scanner input=new Scanner(System.in);
            int n=input.nextInt();
            long[] arr=new long[n];
            for(int i=0;i<n;i++)
            {
                arr[i]=input.nextLong();
            }
            
            System.out.println(MaxProduct(n,arr));
            
        }
    }

题目七：

有序数组进行查找目标元素

1、最简单查找

l=0,r=lengh-1，while(l<=r)，左右值的变化都为l=mid+1，r=mid-1；

具体代码：

class Solution {
        public static void main(String[] args)
        {
            int[] nums= {1,2,3,4,5};
            int target=10;
            
            System.out.println(TwoDisv(nums,target));
        }
        
        public static int TwoDisv(int[] nums,int target)
        {
            int l=0,r=nums.length-1;
            
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(nums[mid]==target)
                    return mid;
                else if (nums[mid]<target) {
                    l=mid+1;
                }
                else if (nums[mid]>target) {
                    r=mid+1;
                }
            }        
            return -1;
        }
    }

2、查找目标值左边界

l=0，r=length，while(l<r)，if(l<target) l=mid+1，if(r>target) r=mid;，因为这是一个左闭右开区间；

最关键的点在if(nums\[mid\]==target) 并不是直接的返回，而是r=mid，逐步向左移动，直到最左边；

具体代码：

class Solution {
        public static void main(String[] args)
        {
            int[] nums= {1,2,3,3,5};
            int target=3;
            
            System.out.println(TwoDisv(nums,target));
        }
        
        public static int TwoDisv(int[] nums,int target)
        {
            int l=0,r=nums.length;
            
            while(l<r)
            {
                int mid=(l+r)/2;
                if(nums[mid]==target)
                    r=mid;
                else if (nums[mid]<target) {
                    l=mid+1;
                }
                else if (nums[mid]>target) {
                    r=mid;
                }
            }    
            return r;
        }
    }

3、查找目标元素的右边界

l=0，r=length，while(l<r) if(nums\[mid\]==target) l=mid-1，最后返回也需要修改return l-1；

具体代码：

class Solution {
        public static void main(String[] args)
        {
            int[] nums= {1,2,3,3,3};
            int target=3;
            
            System.out.println(TwoDisv(nums,target));
        }
        
        public static int TwoDisv(int[] nums,int target)
        {
            int l=0,r=nums.length;
            
            while(l<r)
            {
                int mid=(l+r)/2;
                if(nums[mid]==target)
                    l=mid+1;
                else if (nums[mid]<target) {
                    l=mid+1;
                }
                else if (nums[mid]>target) {
                    r=mid;
                }
            }    
            return r-1;
        }
    }

4、得出左右集合代码：

class Solution {
        public int[] searchRange(int[] nums, int target) {
                   
            return new int[]{left(nums,target),right(nums,target)};
        }
        
        public int left(int[] nums,int target)
        {
            int l=0,r=nums.length;
            
            while(l<r)
            {
                int mid=(l+r)/2;
                if(nums[mid]==target)
                {
                    r=mid;
                }
                else if (nums[mid]<target) {
                    l=mid+1;
                }
                else if (nums[mid]>target) {
                    r=mid;
                }
            }
            
            return r;
        }
        public int right(int[] nums,int target)
        {
            int l=0,r=nums.length;
            
            while(l<r)
            {
                int mid=(l+r)/2;
                if(nums[mid]==target)
                {
                    l=mid-1;
                }
                else if (nums[mid]<target) {
                    l=mid+1;
                }
                else if (nums[mid]>target) {
                    r=mid;
                }
            }
            
            return l-1;
        }
    }

转载于:https://www.cnblogs.com/Optimism/p/11327405.html