1.四数之和
给你一个由
n
个整数组成的数组nums
,和一个目标值target
。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]
(若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < n
a
、b
、c
和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]]
//同样是排序+双指针
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.有效的括号
给定一个只包括
'('
,')'
,'{'
,'}'
,'['
,']'
的字符串s
,判断字符串是否有效。有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
//栈
//左括号入栈
//右括号出栈
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.合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
/**
* 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.括号生成
数字
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