首页 > 其他分享 >DAY4-力扣刷题

DAY4-力扣刷题

时间:2024-06-17 17:59:52浏览次数:25  
标签:ListNode val nums int DAY4 next 力扣 length 刷题

1.四数之和

18. 四数之和 - 力扣(LeetCode)

给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

  • 0 <= a, b, c, d < n
  • abc 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1:

输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2:

输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]

//同样是排序+双指针 

Arrays.asList() 详解-CSDN博客

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 4) {
            return list;
        }
        // 同样是对数组进行排序
        Arrays.sort(nums);
        int length = nums.length;
        for (int i = 0; i < length - 3; i++) {// 第一层
            // 同样是进行判断
            // 遇到相同的就向后
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 因为排序是从小到大的
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            // 此时就是该层最大的时刻
            // 若仍是小于target
            // 就continue
            if ((long) nums[i] + nums[length - 1] + nums[length - 2] + nums[length - 3] < target) {
                continue;
            }
            // 第二个数字
            for (int j = i + 1; j < length - 2; j++) {
                if (j > i + 1 && nums[j ] == nums[j - 1]) {
                    continue;
                }
                if ((long) nums[j] + nums[j + 1] + nums[j + 2] + nums[i] > target) {
                    break;
                    // 跳出本层循环
                }
                if ((long) nums[j - 1] + nums[j] + nums[length - 1] + nums[length - 2] < target) {
                    continue;
                }
                // 左右指针
                int left = j + 1;
                int right = length - 1;
                while (left < right) {// 循环的条件
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        List<Integer> lsi = new ArrayList<>();
                        lsi.add(nums[i]);
                        lsi.add(nums[j]);
                        lsi.add(nums[left]);
                        lsi.add(nums[right]);
                        list.add(lsi);
                        // 同时可能存在a,b,c,d都是相同的
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        left++;
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }

                }
            }
        }

        return list;
    }
}

2.删除链表的倒数第N个结点

19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (n <= 0 || head == null) {
            return null;
        }
        ListNode temp = head;
        int count = 0;
        // 判断有几个结点
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        if (n == count) {
            return head.next;
        }
        // 需要删除第几个结点
        int c = count - n;
        // 头节点
        temp = head;
        // 需要找到它的前一个节点
        for (int i = 0; i < c - 1; i++) {
            temp = temp.next;
        } // 找到该节点
        temp.next = temp.next.next;
        return head;
    }
}

 3.有效的括号

20. 有效的括号 - 力扣(LeetCode)

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

//栈

//左括号入栈

//右括号出栈

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '[' || ch == '{') {
                // 左括号入栈,因为左括号一定是符号最开始的部分
                stack.push(ch);
            } else {// 是右括号的情况
                if (stack.empty()) {
                    return false;
                } else {
                    char tmp = stack.peek();
                    if ((tmp == '(' && ch == ')') || (tmp == '[' && ch == ']') || (tmp == '{' && ch == '}')) {
                        // 括号匹配成功
                        stack.pop();
                    } else {
                        return false;
                    }
                }

            }
        }
        if (!stack.empty()) {
            return false;
        }
        return true;
    }
}

4.合并两个有序链表

21. 合并两个有序链表 - 力扣(LeetCode)

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode();// 建立一个新的链表,作为头节点
        ListNode tmH = newHead;
        // 遍历两个链表
        // 当一个链表为空的时候,循环就结束
        // 接着就遍历后一个循环
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {// 有序的判断
                tmH.next = list1;
                //tmH.next才是真正的头节点,但是它是替代比,最终return的应该是newHead.next;
                //遍历下一个节点
                tmH = tmH.next;
                list1 = list1.next;
            } else {//另外的情况
                tmH.next = list2;
                tmH = tmH.next;
                list2 = list2.next;
            }
        }
        if (list1 != null) {
            tmH.next = list1;
        }
        if (list2 != null) {
            tmH.next = list2;
        }
        return newHead.next;
    }
}

 5.括号生成

22. 括号生成 - 力扣(LeetCode)

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:

输入:n = 1
输出:["()"]

方法一:暴力法 

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> combinations=new ArrayList<String>();
        generateAll(new char[2*n],0,combinations);
        return combinations;
    }
    public void generateAll(char[] current,int pos,List<String> result){
        if(pos == current.length){
            if(valid(current)){
                result.add(new String(current));
            }
        }else{
            current[pos]='(';
            generateAll(current,pos+1,result);
            current[pos]=')';
            generateAll(current,pos+1,result);
        }
    }

    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;
    }
}

 方法二:回溯法

思路和算法

【算法思想:回溯法】回溯算法入门级详解_回溯法算法-CSDN博客

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans=new ArrayList<String>();
        backtrack(ans,new StringBuffer(),0,0,n);
        return ans;
    }
    public void backtrack(List<String> ans,StringBuffer cur,int open,int close,int max){
        if(cur.length()==max*2){
            ans.add(cur.toString());
            return;
        }
        if(open<max){
            cur.append('(');
            backtrack(ans,cur,open+1,close,max);
            cur.deleteCharAt(cur.length()-1);
        }
        if(close<open){
            cur.append(')');
            backtrack(ans,cur,open,close+1,max);
            cur.deleteCharAt(cur.length()-1);
        }
    }
}

5.1 电话号码的字母组合(类似的习题)

首先使用哈希表存储每个数字对应的所有可能的字母,然后进行回溯操作

回溯过程中维护一个字符串,表示已有的字母排列(如果未遍历完电话号码的所有数字,则已有的字母排列是不完整的)。该字符串初始为空。每次取电话号码的一位数字,从哈希表中获得该数字对应的所有可能的字母,并将其中的一个字母插入到已有的字母排列后面,然后继续处理电话号码的后一位数字,直到处理完电话号码中的所有数字,即得到一个完整的字母排列。然后进行回退操作,遍历其余的字母排列。

回溯算法用于寻找所有的可行解,如果发现一个解不可行,则会舍弃不可行的解。在这道题中,由于每个数字对应的每个字母都可能进入字母组合,因此不存在不可行的解,直接穷举所有的解即可。 

class Solution11 {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        //若字符串的长度为0,就直接返回即可
        if (digits.length() == 0) {
            return combinations;
        }
        //hashmap
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        //如果是"23"
        //其实本质就是“abc”和“def”进行组合
        //一共有9种可能性
        //回溯法
        //递归
        StringBuffer stringBuffer=new StringBuffer();
        //backtrack(需要返回的队列,hashmap存储的值,数字字符串23,从数组0的位置开始的,可以改变的字符串)
        backtrack(combinations, phoneMap, digits, 0, stringBuffer);
        return combinations;
    }

    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
        if (index == digits.length()) {//digit的长度就是将来组合的字符串的大小,所以我们是以index为分割的
            combinations.add(combination.toString());//将“ad”加入队列中
        } else {
            char digit = digits.charAt(index);//第一个需要遍历的数字2//3
            String letters = phoneMap.get(digit);//得到了对应的字符串"abc"//"def"
            int lettersCount = letters.length();//字符串的大小
            for (int i = 0; i < lettersCount; i++) {
                combination.append(letters.charAt(i));//i=0,得到了a//"ad"
                backtrack(combinations, phoneMap, digits, index + 1, combination);//a:进行遍历1//index=2进行遍历
                combination.deleteCharAt(index);//a之后还没有完,此时index=1,删除了d,现在是"a"
            }
        }
    }
}

标签:ListNode,val,nums,int,DAY4,next,力扣,length,刷题
From: https://blog.csdn.net/m0_47017197/article/details/139716324

相关文章

  • 蓝桥杯备考冲刺必刷题(C++) | 3792 小蓝的礼物
    学习C++从娃娃抓起!记录下蓝桥杯备考比赛学习过程中的题目,记录每一个瞬间。附上汇总贴:蓝桥杯备考冲刺必刷题(C++)|汇总-CSDN博客【题目描述】小蓝想要给她的女朋友小桥买一份生日礼物,她来到了一家礼品店。在店里,她看中了N......
  • 最实用的 LeetCode 刷题指南
    暑期实习基本结束了,校招即将开启。当前就业环境已不再是那个双向奔赴时代了。求职者在变多,岗位在变少,要求还更高了,最近社群又开始活跃起来了,各种讨论、各种卷。为方便大家快手入手、节省时间,我整理了一份算法指南:汇总合集:内容不仅仅是大模型,也包括LeetCode刷题技巧《......
  • 代码随想录刷题记录(7)| 字符串(344.反转字符串,541. 反转字符串II,卡码网:54.替换数字)
    目录(一)反转字符串1.题目描述2.思路3.解题过程(二)反转字符串Ⅱ1.题目描述2.思路3.解题过程(三)替换数字1.题目描述2.思路3.解题过程(一)反转字符串344.反转字符串-力扣(LeetCode)1.题目描述        编写一个函数,其作用是将输入的字符串反转过......
  • 代码随想录刷题记录(8)| 字符串(151.反转字符串里的单词,卡码网:55.右旋转字符串,28. 找出字
    目录(四)反转字符串里的单词1. 题目描述2.思路3.解题过程(1)使用额外空间存储(2)原地反转 (五)右旋转字符串1.题目描述2.思路3.解题过程 (六)找出字符串中第一个匹配项的下标1.题目描述2.思路3.解题思路(七)重复的子字符串1.题目描述2.思路3.解题过程(八)......
  • 洛谷 P4343 自动刷题机
    题目链接:自动刷题机思路    二分典题,两个二分判断出可能的最大值和最小值。需要注意当删掉y行代码后,当前代码行数小于0时需要将代码行数重新赋值为0,然后需要注意二分的n最大值的边界,因为x[i]的最大值为1e9,日志最多有1e5行,所以考虑极限情况,日志每一行都是写了1e9行代码,......
  • 华为OD刷题C卷 - 每日刷题33(小华最多能得到多少克黄金,智能成绩表)
    1、(小华最多能得到多少克黄金):这段代码是解决“小华最多能得到多少克黄金”的问题。它提供了一个Java类Main,其中包含main方法和dfs方法,以及辅助变量和getDigitSum方法,用于计算小华在地图上能收集到的最多黄金数量。main方法首先读取地图的行数m、列数n和数位之和阈值k。然......
  • 华为OD刷题C卷 - 每日刷题32(执行任务赚积分,计算三叉搜索树的高度)
    1、(执行任务赚积分):这段代码是解决“执行任务赚积分”的问题。它提供了一个Java类Main,其中包含main方法和getResult方法,用于计算在有限的时间内,处理任务可以获得的最多积分。main方法首先读取任务数量n和可用于处理任务的时间t,然后读取每个任务的最晚处理时间限制和积分值,......
  • 华为OD刷题C卷 - 每日刷题31(园区参观路径,围棋的气)
    1、(园区参观路径):这段代码是解决“园区参观路径”的问题。它提供了一个Java类Main,其中包含main方法和getResult方法,以及一个未使用的dfs方法,用于计算从园区起点到终点的不同参观路径数量。main方法首先读取园区的长和宽,然后读取园区的布局信息,其中0表示可以参观,1表示不能参......
  • 华为OD刷题C卷 - 每日刷题30(小明找位置,分隔均衡字符串)
    1、(小明找位置):这段代码是解决“小明找位置”的问题。它提供了一个Java类Main,其中包含main方法和getResult方法,用于帮助小明快速找到他在排队中应该站的位置。main方法首先读取已排列好的小朋友的学号数组和小明的学号,然后调用getResult方法并打印小明应该站的位置。getRe......
  • 打卡信奥刷题(90)用Scratch图形化工具信奥P1853 [普及组] 投资的最大效益
    投资的最大效益题目背景约翰先生获得了一大笔遗产,他暂时还用不上这一笔钱,他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券,每一种债券都能在固定的投资后,提供稳定的年利息。当然,每一种债券的投资额是不同的,一般来说,投资越大,收益也越大,而且,每一年还可以根......