给一个包含 n 个整数的数组 S, 找到和与给定整数 target 最接近的三元组，返回这三个数的和。
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
解答部分
public class Solution {
public int threeSumClose(int[] numbers, int target) {
if (numbers == null || numbers.length < 3) {
return -1;
}
Arrays.sort(numbers); // 对数组进行排序
int bestSum = numbers[0] + numbers[1] + numbers[2];
for (int i = 0; i < numbers.length; i++) {
int start = i + 1, end = numbers.length - 1;
while (start < end) {
int sum = numbers[i] + numbers[start] + numbers[end];
if (Math.abs(target - sum) < Math.abs(target - bestSum)) {
bestSum = sum; // 通过 Math 比较新的三个数之和与初始三数和大小，进行数值的调换
}
if (sum < target) {
start++; //如果第二次的和大于初始的三数和且和小于目标值，则把start++，注意数组是排过序的。
} else {
end--; // 如果第二次的和大于初始的三数和且和大于目标值，则 end--。
}
}
}
return bestSum;
}
}
二：电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
按键对应的拼音字母截图如下
08.png
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
分析：把每个数字按键和各个的字母对应起来封装即可。
15.png
四数之和
描述：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c，和 d，使得 a + b + c + d 的值和 target 相等？找出所有满足条件且不重复的四元组。
tips：答案中不可以包含重复的四元组
public class Solution {
public List<List<Integer>> fourSum(int[] num, int target) {
List<List<Integer>> rst = new ArrayList<List<Integer>>();
Arrays.sort(num); // 排序
for (int i = 0; i < num.length - 3; i ++) {
if (i != 0 && num[i] == num[i - 1]) {
continue;
}
for (int j = i + 1; j < num.length - 2; j ++) {
if (j != i + 1 && num[j] == num[j - 1])
continue;
int left = j + 1;
int right = num.length - 1;
while (left < right) {
int sum = num[i] + num[j] + num[left] + num[right];
if (sum < target) {
left ++;
} else if (sum > target) {
right --;
} else {
ArrayList<Integer> tmp = new ArrayList<Integer>();
tmp.add(num[i]);
tmp.add(num[j]);
tmp.add(num[left]);
tmp.add(num[right]);
rst.add(tmp);
left++;
right--;
while (left < right && num[left] == num[left - 1]) {
left++;
}
while (left < right && num[right] == num[right + 1]) {
right--;
}
}
}
}
}
return rst;
}
}
删除链表的倒数第 N 个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
介绍，思想就是定义两个指针，可以第一个先走 n 步，之后在同时移动这两个指针即可。
public class Solution {
public ListNode removeFromEnd(ListNode head, int n) {
if (n <= 0) {
return null;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode preDelete = dummy; // 定义一个指针指向第一个节点
for (int i = 0; i < n; i ++) {
if (head == null) {
return null;
}
head = head.next;
}
while (head != null) {
head = head.next;
preDelete = preDelete.next;
}
preDelete.next = preDelete.next.next;
return dummy.next;
}
}
括号匹配题目
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
tips：toCharArray() 方法将字符串转换为字符数组。2，注意题目要求不是输入的括号需要成对出现才行。只要有不匹配的就可以直接返回 false。
public class Solution {
public boolean isValidParentheses(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
}
if (c == ')') {
if (stack.isEmpty() || stack.pop() != '(') {
return false;
}
}
if (c == ']') {
if (stack.isEmpty() || stack.pop() != '[') {
return false;
}
}
if (c == '}') {
if (stack.isEmpty() || stack.pop() != '{') {
return false;
}
}
}
return stack.isEmpty();
}
}
解析：这里大家需要注意题目的具体意思，只要每个相邻的括号无法匹配，就说明对比失败，直接返回 false，所以这里每次都是和栈顶的元素比较。
括号生成
给出 n 代表生成括号的对数，写出一个函数，使其能够生成 所有 可能的并且有效的括号组合
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解答：
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
backtrack(ans, "", 0, 0, n);
return ans;
}
public void backtrack(List<String> ans, String cur, int open, int close, int max){
if (cur.length() == max * 2) {
ans.add(cur);
return;
}
if (open < max)
backtrack(ans, cur+"(", open+1, close, max);
if (close < open)
backtrack(ans, cur+")", open, close+1, max);
}
}
网友评论