头像

Cloudeeeee

共同成长,共同进步! 博客地址:https://blog.csdn.net/weixin_43972154




在线 


最近来访(59)
用户头像
zlb
用户头像
菜狗一个
用户头像
carder
用户头像
IceCola丶
用户头像
夏野了_0
用户头像
沈知秋.
用户头像
Lucky_1002
用户头像
skim
用户头像
月色美兮
用户头像
不灭孽蜥
用户头像
jinyc
用户头像
IER
用户头像
紫芋仙子
用户头像
阿兔
用户头像
karmenko
用户头像
acwwgy
用户头像
nfksdlv
用户头像
储物盒
用户头像
Wiselnn
用户头像
KkkkkkkkkKK


Cloudeeeee
14小时前

1. 题目

在这里插入图片描述

2. 读题(需要重点注意的东西)

思路:
括号合法的两个结论(很常用)
① 任意前缀中,左括号数量 >= 右括号数量
② 左右括号数量相等

具体实现方法如下
所以合法方案可以用dfs递归来实现
① 填(的情况:只要还有左括号,就能填左括号
② 填)的情况:还有右括号左括号数量 > 右括号数量

另外,括号合法的数量符合卡特兰数
在这里插入图片描述

3. 解法

---------------------------------------------------解法---------------------------------------------------

class Solution {
    List<String> list = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        // dfs(括号对数,当前已经使用的左括号,当前已经使用的右括号,当前的括号序列)
        dfs(n,0,0,"");
        return list;
    }
    private void dfs(int n,int lc,int rc,String cur){
        if(lc == n && rc == n) list.add(cur);
        else{
            if(lc <= n) dfs(n,lc+1,rc,cur+'(');
            if(rc <= n && lc > rc) dfs(n,lc,rc+1,cur+')');
        }
    }
}

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

  • 递归
  • dfs

6. 总结



活动打卡代码 AcWing 22. 括号生成

Cloudeeeee
14小时前

1. 题目

在这里插入图片描述

2. 读题(需要重点注意的东西)

思路:
括号合法的两个结论(很常用)
① 任意前缀中,左括号数量 >= 右括号数量
② 左右括号数量相等

具体实现方法如下
所以合法方案可以用dfs递归来实现
① 填(的情况:只要还有左括号,就能填左括号
② 填)的情况:还有右括号左括号数量 > 右括号数量

另外,括号合法的数量符合卡特兰数
在这里插入图片描述

3. 解法

---------------------------------------------------解法---------------------------------------------------

class Solution {
    List<String> list = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        // dfs(括号对数,当前已经使用的左括号,当前已经使用的右括号,当前的括号序列)
        dfs(n,0,0,"");
        return list;
    }
    private void dfs(int n,int lc,int rc,String cur){
        if(lc == n && rc == n) list.add(cur);
        else{
            if(lc <= n) dfs(n,lc+1,rc,cur+'(');
            if(rc <= n && lc > rc) dfs(n,lc,rc+1,cur+')');
        }
    }
}

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

  • 递归
  • dfs

6. 总结




Cloudeeeee
22小时前

1. 题目

在这里插入图片描述

2. 读题(需要重点注意的东西)

思路1:迭代,逐一比较l1的节点和l2的节点,小的加入到新的链表中,再往后走一步,再往后继续比较,直到某一方链表为null,将另一方剩余的节点全部加入到新的链表后。(类似于归并排序,容易理解但是有额外的节点开销)。
思路2:递归(理解困难但是开销较小),递归法的思想是在每次递归时,取出l1链表和l2链表中的头节点,比较大小,然后递归到next节点,直到某一条链表为空,返回另一条链表。

递归的三要素:
终止条件
每次递归的返回值—返回给上一层递归的值
在这层递归做什么

递归过程
在这里插入图片描述

3. 解法

解法1:迭代法

/**
 * 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 l1, ListNode l2) {
        if(l1 == null || l2 == null) return l1 == null ? l2 : l1;
        ListNode tail = new ListNode(0);
        ListNode cur = tail;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }
            else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return tail.next;
    }
}

解法2:递归法

/**
 * 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 l1, ListNode l2) {
        if(l1 == null || l2 == null) return l1 == null ? l2 : l1;
        if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }
        else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

6. 总结

递归法要理解从上至下执行递归,然后又从下至上返回值的两步走步骤。




Cloudeeeee
22小时前

1. 题目

在这里插入图片描述

2. 读题(需要重点注意的东西)

思路1:迭代,逐一比较l1的节点和l2的节点,小的加入到新的链表中,再往后走一步,再往后继续比较,直到某一方链表为null,将另一方剩余的节点全部加入到新的链表后。(类似于归并排序,容易理解但是有额外的节点开销)。
思路2:递归(理解困难但是开销较小),递归法的思想是在每次递归时,取出l1链表和l2链表中的头节点,比较大小,然后递归到next节点,直到某一条链表为空,返回另一条链表。

递归的三要素:
终止条件
每次递归的返回值—返回给上一层递归的值
在这层递归做什么

递归过程
在这里插入图片描述

3. 解法

解法1:迭代法

/**
 * 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 l1, ListNode l2) {
        if(l1 == null || l2 == null) return l1 == null ? l2 : l1;
        ListNode tail = new ListNode(0);
        ListNode cur = tail;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }
            else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return tail.next;
    }
}

解法2:递归法

/**
 * 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 l1, ListNode l2) {
        if(l1 == null || l2 == null) return l1 == null ? l2 : l1;
        if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }
        else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

6. 总结

递归法要理解从上至下执行递归,然后又从下至上返回值的两步走步骤。




Cloudeeeee
23小时前

1. 题目

在这里插入图片描述

2. 读题(需要重点注意的东西)

栈的特性—先进后出
思路:遇到左括号 ( [ } 进栈,遇到右括号 ) ] } 出栈配对。
需要注意的是:无论任何数据结构,在执行类似出栈的操作时,一定要先判断是否为空。

优化:通过ASCII码来优化

通过查表可以知道,如果是匹配的括号,那么他们ASCII码的值之差不会超过2,因此可以由此来判断是否匹配。

3. 解法

------------------------------------解法1:优化前----------------------------------------------

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        int len = s.length();
        int i = 0;
        while(len > 0){
            // 遇到左括号 ( [ } 进栈
            if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') stack.push(s.charAt(i));
            // 遇到右括号 ) ] } 出栈配对
            if(s.charAt(i) == ')'){
                if(stack.isEmpty()) return false;
                char c = stack.pop();
                if(c != '(') return false;
            }
            if(s.charAt(i) == ']'){
                if(stack.isEmpty()) return false;
                char c = stack.pop();
                if(c != '[') return false;
            }
            if(s.charAt(i) == '}'){
                if(stack.isEmpty()) return false;
                char c = stack.pop();
                if(c != '{') return false;
            }
            i ++ ;
            len --;
        }
        return stack.isEmpty();
    }
}

-------------------------------解法2:通过ASCII码进行优化后-----------------------------

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        int len = s.length();
        int i = 0;
        for(char c : s.toCharArray()){
            // 遇到左括号 ( [ } 进栈
            if(c == '(' || c == '[' || c == '{') stack.push(c);
            // 遇到右括号 ) ] } 出栈配对
            else{
                if(stack.isEmpty() == false && Math.abs(c-stack.peek()) <= 2) stack.pop();
                else return false;
            }
        }
        return stack.isEmpty();
    }
}

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

6. 总结

括号配对,经典栈入门题,可以很好的理解栈先入后出的特性。注意通过ASCII码来判断是否匹配的方法。



活动打卡代码 AcWing 20. 有效的括号

Cloudeeeee
23小时前

1. 题目

在这里插入图片描述

2. 读题(需要重点注意的东西)

栈的特性—先进后出
思路:遇到左括号 ( [ } 进栈,遇到右括号 ) ] } 出栈配对。
需要注意的是:无论任何数据结构,在执行类似出栈的操作时,一定要先判断是否为空。

优化:通过ASCII码来优化

通过查表可以知道,如果是匹配的括号,那么他们ASCII码的值之差不会超过2,因此可以由此来判断是否匹配。

3. 解法

------------------------------------解法1:优化前----------------------------------------------

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        int len = s.length();
        int i = 0;
        while(len > 0){
            // 遇到左括号 ( [ } 进栈
            if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') stack.push(s.charAt(i));
            // 遇到右括号 ) ] } 出栈配对
            if(s.charAt(i) == ')'){
                if(stack.isEmpty()) return false;
                char c = stack.pop();
                if(c != '(') return false;
            }
            if(s.charAt(i) == ']'){
                if(stack.isEmpty()) return false;
                char c = stack.pop();
                if(c != '[') return false;
            }
            if(s.charAt(i) == '}'){
                if(stack.isEmpty()) return false;
                char c = stack.pop();
                if(c != '{') return false;
            }
            i ++ ;
            len --;
        }
        return stack.isEmpty();
    }
}

-------------------------------解法2:通过ASCII码进行优化后-----------------------------

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        int len = s.length();
        int i = 0;
        for(char c : s.toCharArray()){
            // 遇到左括号 ( [ } 进栈
            if(c == '(' || c == '[' || c == '{') stack.push(c);
            // 遇到右括号 ) ] } 出栈配对
            else{
                if(stack.isEmpty() == false && Math.abs(c-stack.peek()) <= 2) stack.pop();
                else return false;
            }
        }
        return stack.isEmpty();
    }
}

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

6. 总结

括号配对,经典栈入门题,可以很好的理解栈先入后出的特性。注意通过ASCII码来判断是否匹配的方法。




1. 题目

在这里插入图片描述

2. 读题(需要重点注意的东西)

思路(用一趟扫描实现):快慢指针,快指针先走n步,然后慢指针和快指针一起走,直到快指针走到终点(fast.next == null),此时慢指针指向的节点的下一个节点,就是需要删除的节点。此外,需要注意要删除的是第一个节点的情况。

3. 解法

解法:迭代法

/**
 * 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) {
        ListNode fast = head;
        ListNode slow = head;
        // 快指针先走n步
        while (n > 0) {
            fast = fast.next;
            n--;
        }
        // 表明要删除的是第一个节点 
        if (fast == null) return head.next;
        // 慢指针和快指针一起走
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 当快指针走到终点时,慢指针的下一个节点就是需要删除的节点
        slow.next = slow.next.next;
        return head;
    }
}

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

6. 总结

链表的相关题目,考虑快慢指针是一个不错的思路




1. 题目

在这里插入图片描述

2. 读题(需要重点注意的东西)

思路(用一趟扫描实现):快慢指针,快指针先走n步,然后慢指针和快指针一起走,直到快指针走到终点(fast.next == null),此时慢指针指向的节点的下一个节点,就是需要删除的节点。此外,需要注意要删除的是第一个节点的情况。

3. 解法

解法:迭代法

/**
 * 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) {
        ListNode fast = head;
        ListNode slow = head;
        // 快指针先走n步
        while (n > 0) {
            fast = fast.next;
            n--;
        }
        // 表明要删除的是第一个节点 
        if (fast == null) return head.next;
        // 慢指针和快指针一起走
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 当快指针走到终点时,慢指针的下一个节点就是需要删除的节点
        slow.next = slow.next.next;
        return head;
    }
}

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

6. 总结

链表的相关题目,考虑快慢指针是一个不错的思路



活动打卡代码 AcWing 18. 四数之和

1. 题目

在这里插入图片描述
在这里插入图片描述

2. 读题(需要重点注意的东西)

思路:
[LeetCode] 15. 三数之和(java实现)完全相同。

双指针算法,双指针算法要求数列是有序的,因此首先要对数列进行排序

枚举
排序后定好两个数nums[i]和nums[j],指针k指向j+1,指针m指向n-1
如果nums[i] + nums[j] + nums[k] + nums[m] > 0,指针k向左走,使和变小
如果nums[i] + nums[j] + nums[k] + nums[m] < 0,指针m向右走,使和变大
如果nums[i] + nums[j] + nums[k] + nums[m] == 0,存下{nums[i],nums[j],nums[k],nums[m]}作为一个结果

判重
如果nums[i] == nums[i-1]或者nums[j] == nums[j-1]或者nums[k] == nums[k+1]或者nums[m] == nums[m+1],说明与上一个判断的数相同,直接跳过即可防止重复

3. 解法

---------------------------------------------------解法---------------------------------------------------

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        if(nums.length == 0) return new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        // 定下nums[i]
        for(int i = 0;i < n;i++){
            // 去重
            if(i != 0 && nums[i] == nums[i - 1]) continue;
            // 定下nums[j]
            for(int j = i + 1;j < n - 2;j++){
                // 去重
                if(j != i+1 && nums[j] == nums[j-1]) continue;
                int k = j + 1,m = n-1;
                // 双指针
                while(k < m){
                    int sum = nums[i] + nums[j] + nums[k] + nums[m];
                    if(sum > target){
                        m--;
                        continue;
                    }
                    if(sum < target){
                        k++;
                        continue;
                    }else if(sum == target){
                        list.add(Arrays.asList(nums[i],nums[j],nums[k],nums[m]));
                    }
                    // 去重
                    do{k++;}while(k < m && nums[k] == nums[k - 1]);
                    do{m--;}while(k < m && nums[m] == nums[m + 1]);
                }
            }
        }
        return list;
    }
}

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

6. 总结

定两个数 nums[i]nums[j],移动两个指针km
注意去重的操作是如何实现的。




1. 题目

在这里插入图片描述
在这里插入图片描述

2. 读题(需要重点注意的东西)

思路:
[LeetCode] 15. 三数之和(java实现)完全相同。

双指针算法,双指针算法要求数列是有序的,因此首先要对数列进行排序

枚举
排序后定好两个数nums[i]和nums[j],指针k指向j+1,指针m指向n-1
如果nums[i] + nums[j] + nums[k] + nums[m] > 0,指针k向左走,使和变小
如果nums[i] + nums[j] + nums[k] + nums[m] < 0,指针m向右走,使和变大
如果nums[i] + nums[j] + nums[k] + nums[m] == 0,存下{nums[i],nums[j],nums[k],nums[m]}作为一个结果

判重
如果nums[i] == nums[i-1]或者nums[j] == nums[j-1]或者nums[k] == nums[k+1]或者nums[m] == nums[m+1],说明与上一个判断的数相同,直接跳过即可防止重复

3. 解法

---------------------------------------------------解法---------------------------------------------------

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        if(nums.length == 0) return new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        // 定下nums[i]
        for(int i = 0;i < n;i++){
            // 去重
            if(i != 0 && nums[i] == nums[i - 1]) continue;
            // 定下nums[j]
            for(int j = i + 1;j < n - 2;j++){
                // 去重
                if(j != i+1 && nums[j] == nums[j-1]) continue;
                int k = j + 1,m = n-1;
                // 双指针
                while(k < m){
                    int sum = nums[i] + nums[j] + nums[k] + nums[m];
                    if(sum > target){
                        m--;
                        continue;
                    }
                    if(sum < target){
                        k++;
                        continue;
                    }else if(sum == target){
                        list.add(Arrays.asList(nums[i],nums[j],nums[k],nums[m]));
                    }
                    // 去重
                    do{k++;}while(k < m && nums[k] == nums[k - 1]);
                    do{m--;}while(k < m && nums[m] == nums[m + 1]);
                }
            }
        }
        return list;
    }
}

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

6. 总结

定两个数 nums[i]nums[j],移动两个指针km
注意去重的操作是如何实现的。