LeetCode寒假刷题 Day03

文章目录

  • 前言
  • 一、011 盛最多水的容器
    • 1. 题目描述
    • 2. 解题思路
    • 3. 代码实现
  • 二、014 最长公共前缀
    • 1. 题目描述
    • 2. 解题思路
    • 3. 代码实现
  • 三、015 三数之和
    • 1. 题目描述
    • 2. 解题思路
    • 3. 代码实现
  • 总结


前言

LeetCode寒假刷题打卡的第三天了,我感觉是我自己的问题,对双指针等问题不够熟练,感觉今天的题目偏难。没有关系,找到自己的薄弱项才能进步。本文将今天的三道题的解题过程记录下来,供大家参考!

一、011 盛最多水的容器

1. 题目描述

题号:11
难度:中等
https://leetcode-cn.com/problems/container-with-most-water/
给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例:

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

2. 解题思路

要知道,水能够装多少,是由

1)最短的那个板子的长度;

2)两个板子之间的距离

两个因素共同决定的。因此,我们设置双指针,然后只需要移动两个板子中较短的那个,然后与现在的值进行比较即可。

3. 代码实现

class Solution {
     
    public int maxArea(int[] height) {
     
        if(height.length<2)
            return 0;
        int i=0,j=height.length-1;
        int max=Math.min(height[i],height[j])*(j-i);
        while(i<j)
        {
     
            if(height[j]<height[i])
                --j;
            else
                ++i;
            max=Math.max(max,Math.min(height[i],height[j])*(j-i));
        }
        return max;
    }
}

二、014 最长公共前缀

1. 题目描述

题号:14
难度:简单
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 “”。

示例 1:

输入: [“flower”,“flow”,“flight”]
输出: “fl”

示例 2:

输入: [“dog”,“racecar”,“car”]
输出: “”
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z。

2. 解题思路

假设有N个字符串,则:
LCP(S1 …Sn )=LCP(LCP(LCP(S 1 ,S 2​),S3),…Sn)

3. 代码实现

class Solution {
     
    public String longestCommonPrefix(String[] strs) {
     
       if(strs.length==0)
            return "";
        int min_length=Integer.MAX_VALUE;
        String str=strs[0];
        for(int i=1;i< strs.length;i++)
        {
     
            str=longestString(str,strs[i]);
        }
        return str;
    }
    public String longestString(String s1,String s2)
    {
     
        int min=Math.min(s1.length(),s2.length());
        for(int i=0;i<min;i++)
        {
     
            if(s1.charAt(i)!=s2.charAt(i))
            {
     
                return s1.substring(0,i);
            }
        }
        return s1.substring(0,min);
    }
}

三、015 三数之和

1. 题目描述

题号:15
难度:中等
015 三数之和
给定一个包含n个整数的数组nums,判断nums中是否存在三个元素a,b,c,使得a + b + c = 0?找出所有满足条件且不重复的三元组。

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

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]

2. 解题思路

做这道题我承认我想的时候偷懒了,但是排序+双指针的双重循环算法,并利用哈希set去重,通不过LeetCode中java的AC,我也是没想到的,我还天真的以为这道题只有三重循环才会超时。。。哎,天真。但是后面也是偷懒,依然是利用hashset来去重,前面加了一点判断条件,勉强通过了AC。若要得到更高的分数,可以将代码中的–i和++k的执行条件改为当与上一个相等时不执行。

3. 代码实现

class Solution {
     
    public List<List<Integer>> threeSum(int[] nums) {
     
       if(nums.length<3)
            return new LinkedList<List<Integer>>();
        int i;

        List<List<Integer>> list = new LinkedList<List<Integer>>();

        HashSet<List<Integer>> set = new HashSet<List<Integer>>();

        Arrays.sort(nums);
        i=0;
        int j=1,k=2;
        int value=Integer.MAX_VALUE;
        while(j<nums.length-1)
        {
     
            if(j>1&&nums[j]==nums[j-1]&&nums[j-1]==nums[j-2])
            {
     
                ++j;
                i=j-1;
                k=j+1;
                continue;
            }

            while (i>=0&&k<nums.length&&(value=nums[i]+nums[j]+nums[k])!=0)
            {
     

                if(value<0)
                {
     
                    ++k;
                }
                else
                {
     
                    --i;
                }
            }
            if(value==0)
            {
     
                LinkedList<Integer> list2=new LinkedList<Integer>();
                list2.add(nums[i]);
                list2.add(nums[j]);
                list2.add(nums[k]);
                set.add(list2);
                if(k<nums.length-1&&i>0)
                {
     
                    ++k;
                    --i;
                }
                else
                {
     
                    ++j;
                    i=j-1;
                    k=j+1;
                }
                continue;
            }
            ++j;
            i=j-1;
            k=j+1;
        }

        for(List lis:set)
        {
     
            new LinkedList<List<Integer>>(lis);
            list.add(lis);
        }
        return list;
    }
}

总结

以上就是今天LeetCode寒假刷题的第三天所做的三道题。若有任何疑问,欢迎私信Call我鸭!

你可能感兴趣的