美国建设工程网站bt磁力兔子引擎

15.三数之和

题目链接：15. 三数之和 - 力扣（Leetcode）

思路：

（1）双指针，在外层for循环里加入两个指针，left和right

（2）排序：为了更好地进行去重

（2）去重：a. 外层for循环要去重 b. 里层循环，双指针找到符合条件的 list 也要去重判断

Java代码：（见注释）

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();//先判断特殊情况if(nums.length == 0 || nums == null){return res;}//排序：为了方便后续去重Arrays.sort(nums);for(int i = 0; i < nums.length;i++){//判断特殊情况if(nums[i] > 0){return res;}//去重if(i > 0 && nums[i - 1] == nums[i]){continue;}//定义双指针int left = i + 1;int right = nums.length - 1;while(left < right){int sum = nums[i] + nums[left] + nums[right];if(sum > 0){right--;}else if(sum < 0){left++;}//找到else{List<Integer> path = new ArrayList<>();path.addAll(Arrays.asList(nums[i],nums[left],nums[right]));res.add(path);//去重while(left < right && nums[left] == nums[left + 1]) left++;while(left < right && nums[right] == nums[right - 1]) right--;left++;right--;}}}return res;}
}

17. 电话号码的字母组合

题目链接：17. 电话号码的字母组合 - 力扣（Leetcode）

思路：属于回溯算法中的组合问题，回溯三部曲，此题是在多个独立的集合里取值进行组合

（1）确定函数返回值与参数

参数有digits，string数组，以及index，其中这里的index不是之前的startIndex，index表示的是digits的第几个字符

（2）确定终止条件

当index == digits.length()时，收获结果

（3）确定单层递归逻辑

巩固的知识：

（1）StringBuilder的删除指定位置字符的方法为deleteCharAt()

（2）获取StringBuilder的长度，sb.length()

Java代码：

class Solution {List<String> res = new ArrayList<>();StringBuilder sb = new StringBuilder();public List<String> letterCombinations(String digits) {//先判断特殊情况if(digits.equals("") || digits.length() == 0){return res;}//将数字转换为string，定义一个string数组String[] strarr = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};backtracing(digits,strarr,0);return res;}//这里index表示的digits中的第几个字符private void backtracing(String digits,String[] strarr,int index){//(2)确定终止条件，当index == digits.length()时if(index == digits.length()){res.add(new String(sb));return;}//(3)确定单层逻辑String str = strarr[digits.charAt(index) - '0'];//先找到string数组中对应的字符串字母//这里没有用到startIndex，因为此题是多个独立的集合取值for(int i = 0; i < str.length();i++){sb.append(str.charAt(i));//递归backtracing(digits,strarr,index + 1);//回溯sb.deleteCharAt(sb.length() - 1);}}
}

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

题目链接：19. 删除链表的倒数第 N 个结点 - 力扣（Leetcode）

思路：双指针 + 虚拟头节点

（1）定义两个指针，pre 和 cur 均指向虚拟头节点，首先让cur移动n步

（2）然后两个指针开始同时移动，直到cur.next为空结束，此时pre指针就到达了要删除节点的前一个节点，让temp = pre.next.next  ，pre.next = temp;

Java代码：

/*** 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(head == null){return null;}//定义一个虚拟头节点ListNode dummynode = new ListNode();dummynode.next = head;//定义两个指针ListNode pre = dummynode;ListNode cur = dummynode;for(int i = 0; i < n;i++){cur = cur.next;}while(cur.next != null){pre = pre.next;cur = cur.next;}//此时pre指向要删除节点的前一个节点ListNode temp = pre.next.next;pre.next = temp;return dummynode.next;}
}