电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
//一个映射表，第二个位置是"abc“,第三个位置是"def"
//这里也可以用map，用数组可以更节省点内存
String[] letter_map = {" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
//注意边界条件
if(digits==null || digits.length()==0) {
return new ArrayList<>();
}
iterStr(digits, new StringBuilder(), 0);
return res;
}
//最终输出结果的list
List<String> res = new ArrayList<>();
//递归函数
void iterStr(String str, StringBuilder letter, int index) {
//递归的终止条件，注意这里的终止条件看上去跟动态演示图有些不同，主要是做了点优化
//动态图中是每次截取字符串的一部分，"234"，变成"23"，再变成"3"，最后变成""，这样性能不佳
//而用index记录每次遍历到字符串的位置，这样性能更好
if(index == str.length()) {
res.add(letter.toString());
return;
}
//获取index位置的字符，假设输入的字符是"234"
//第一次递归时index为0所以c=2，第二次index为1所以c=3，第三次c=4
//subString每次都会生成新的字符串，而index则是取当前的一个字符，所以效率更高一点
char c = str.charAt(index);
//map_string的下表是从0开始一直到9， c-'0'就可以取到相对的数组下标位置
//比如c=2时候，2-'0'，获取下标为2,letter_map[2]就是"abc"
int pos = c - '0';
String map_string = letter_map[pos];
//遍历字符串，比如第一次得到的是2，页就是遍历"abc"
for(int i=0;i<map_string.length();i++) {
//调用下一层递归，用文字很难描述，请配合动态图理解
letter.append(map_string.charAt(i));
//如果是String类型做拼接效率会比较低
//iterStr(str, letter+map_string.charAt(i), index+1);
iterStr(str, letter, index+1);
letter.deleteCharAt(letter.length()-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]]
解题思路：用map提前计算好3数之和，可以将时间复杂度降到O(n^3)，最主要一点是最后输出结果不能重复，思路跟三数之和完全一致。
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();
if (nums == null || nums.length < 4) {
// 数组为空或者长度不够4直接返回空
return quadruplets;
}
// 先排序，解决可能输出重复结果问题
// [-2, -1, 0, 0, 1, 2]
Arrays.sort(nums);
int len = nums.length;
for(int i = 0; i < len - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
if(nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
if(nums[i] + nums[len - 3] + nums[len - 2] + nums[len - 1] < target) {
continue;
}
for (int j = i + 1; j < len - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
if (nums[i] + nums[j] + nums[len - 2] + nums[len - 1] < target) {
continue;
}
int left = j + 1;
int right = len - 1;
while(left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
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 quadruplets;
}
删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1 输出：[]
示例 3：
输入：head = [1,2], n = 1 输出：[1]
解题思路：先循环一次拿到链表总长度，然后循环到要删除节点的前一个节点开始操作删除。
这里有两种解法，第一就是根据链表长度，遍历拿到要删除元素的前一个元素；第二个就是通过栈的方式，先把所有元素压入栈中，然后根据要删除的元素下标遍历栈取出前一个元素。
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
// 计算出链表长度
int length = 0;
while (head != null) {
++length;
head = head.next;
}
// 拿到要删除元素的前一个元素
ListNode cur = dummy;
for (int i = 1; i < length - n + 1; ++i) {
cur = cur.next;
}
// 进行删除操作，改变指针引用
cur.next = cur.next.next;
ListNode ans = dummy.next;
return ans;
}
有效括号
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = “()” 输出：true
示例 2：
输入：s = “()[]{}” 输出：true
示例 3：
输入：s = “(]” 输出：false
解题思路：遇到左括号就push到栈，遇到右括号并且栈顶为对应的左括号就把元素出栈，最后看栈中是否还有元素。
private static final Map<Character,Character> map = new HashMap<Character,Character>(){{
put('{','}'); put('[',']'); put('(',')'); put('?','?');
}};
public boolean isValid(String s) {
// 首先判断是否包含左括号
if(s.length() > 0 && !map.containsKey(s.charAt(0))) {
return false;
}
LinkedList<Character> stack = new LinkedList<Character>() {{
add('?');
}};
// 遍历每个元素
for(Character c : s.toCharArray()) {
if(map.containsKey(c)) {
// 匹配到左括号入栈
stack.addLast(c);
} else if (map.get(stack.removeLast()) != c) {
// 再判断是否是对称
return false;
}
}
return stack.size() == 1;
}
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = [] 输出：[]
示例 3：
输入：l1 = [], l2 = [0] 输出：[0]
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
} else if (list2 == null) {
return list1;
}
// 如果链表1的值小于链表2，再根据小的元素的下一个节点去比较
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
