leetcode热题100专题 6-10题解

leetcode热题100专题 6-10题解

           

目录

T6 10.正则表达式匹配（难）

T7 11.成最多水的容器

思路1（双指针）

 T8 15.三数之和

思路1（排序+双指针）

T9 17.电话号码的字母组合

 思路1（层次遍历）

思路2（深度遍历）

T10 19.删除链表的倒数第N个结点。（简单，可略过）

思路1

---

T6 10.正则表达式匹配

 还没有做出来，等做出来再补充。

T7 11.成最多水的容器

 题目展示：

力扣https://leetcode-cn.com/problems/container-with-most-water/

思路1

两端分别设置指针l，r，逐渐往中间进行搜索。因为往中间进行遍历，容器的长度是减小的，若想容器容量最大，因此，移动l，r中小的一端，若容量变大，则更记录最大容量的值。直到i=j，停止搜索。

class Solution {
    public int maxArea(int[] height) {
        int head = 0,tail = height.length-1;
        int max = 0;
        int min = 0;
        int square = 0;
        while(headheight[tail]){
                min = height[tail];
                tail--;
            }else
                head++;
            square = min * (tail-head+1);
            if(square>max){//更新max
                max = square;
            }
        }
        return max;
    }
}

 T8 15.三数之和

 题目展示：

力扣https://leetcode-cn.com/problems/3sum/

思路1

排序+双指针：因为题目中要求不能有重复元素，因此首先对数组进行排序。然后第一个元素i采用for循环进行遍历，后面两个元素，分别设置为j = i+1，k = len-1（一个最大，一个最小）。

• 若三数相加之和大于0，则移动k元素。（使三数之和变小）
• 若小于0，则移动j元素。（使三数之和变大）
• 若等于0，则将此三元组加入列表中，同时移动j，k两个元素。

可以采用list.contains(s）去除重复元组，但是会消耗大量时间。因此可以添加一下去重条件。

class Solution {
    public List> threeSum(int[] nums) {
        List> res  = new ArrayList>();
        int i,j,k;
        // //冒泡
        // for(i= 0;inums[j]){
        //             min = j;
        //         }
        //     }
        //     if(min!=i){
        //         int t = nums[min];
        //         nums[min] = nums[i];
        //         nums[i] = t;
        //     }
        // }
        Arrays.sort(nums);//排序函数
        for(i = 0;i0||nums[nums.length-1]<0)//如果第一个元素大于0或者最后一个元素小于0，则跳出循环。
                break;
            while(i!=0&&i s = new ArrayList();
                    s.add(nums[i]);
                    s.add(nums[j]);
                    s.add(nums[k]);
                    // if(!res.contains(s)){//用此函数可以去掉一些条件，但是会消耗大量时间
                    //     res.add(s);
                    // }
                    res.add(s);
                    j++;//后面的while条件都是为了去除重复元素。
                    while(jj && nums[k]==nums[k+1]) k--;
                }else if(nums[i]+nums[j]+nums[k]>0){
                        // if(nums[j]>0)/
                        //     break;
                        k--;
                        while(k>j && nums[k]==nums[k+1]) k--;
                }else{
                    if(nums[k]<0)/
                        break;
                    j++;
                    while(j 
 
 T9 17.电话号码的字母组合 
 
题目展示： 
 
力扣https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
 
 思路1 
         采用层次遍历。首先for循环，取digits中的数字，每当取出一个新的数字，便更新list。
 
class Solution {
    public List letterCombinations(String digits) {
        int len = digits.length();
        ArrayList s = new ArrayList();
        s.addAll(Arrays.asList("abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"));
        int i,j,k;
        List res = new ArrayList();//存储返回结果
        
        if(len==0)//如果digits为空，直接返回空
            return res;
        res.add("");
        for(i = 0;i 
思路2 
      采用深度遍历。
 
class Solution {
    String[] smap = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    List res = new ArrayList();//记录返回结果
    public List letterCombinations(String digits) {
        dfs(0,"",digits); 
        return res;
    }

    public void dfs(int depth, String letter,String digits){
        if(depth == digits.length()){
            return;
        }else{
            for(int i = 0;i 
 
 T10 19.删除链表的倒数第N个结点。 
 
题目描述
 
力扣https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
 
思路1 
首先遍历链表共有多少个结点。然后再找到倒数第n个，将其删除。
 
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head.next==null){
            return null;
        }
        int count = 1;
        ListNode p = head;
        while(p.next!=null){
            p = p.next;
            count++;
        }//遍历链表，记录总共有多少个结点。
        if(count==n){
            p = head.next;
            return p;
        }else{
            count = count - n;
            int num = 1;
            p = head;
            while(num 
欢迎分享，转载请注明来源：内存溢出
原文地址:https://www.54852.com/zaji/5690518.html