LeetCode 编程

给一个包含 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);
    }
}