LeetCode几道经典题

1. 数组的全排列：

https://leetcode-cn.com/problems/permutations/submissions/

回溯法

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<List<Integer>> res = new LinkedList<List<Integer>>();
        if (nums == null || nums.length == 0)
            return res;
        Helper(res, new LinkedList<Integer>(), nums, new HashSet<Integer>());
        return res;
    }
    private void Helper(List<List<Integer>> res, List<Integer> curlist, int[] nums,
                       HashSet<Integer> set){
        if (curlist.size() == nums.length)
            res.add(new LinkedList<Integer>(curlist));
        else{
            for (int i = 0; i < nums.length; i++){ //对每个数而言
                if (set.contains(nums[i]))
                    continue;
//加数
                curlist.add(nums[i]);
                set.add(nums[i]);
                Helper(res, curlist, nums, set);  //下层的执行完，要把刚刚加进的数字弹出
//删数
                set.remove(nums[i]);
                int last = curlist.size() - 1;
                curlist.remove(last);
            }
        }
    }
}

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0)
            return res;
        Helper(nums, res, new ArrayList<Integer>(), new HashSet<Integer>());
        return res;
    }
    private void Helper(int[] nums, ArrayList<List<Integer>> res, ArrayList<Integer> curlist,
                       HashSet<Integer> set){
        if (nums.length == curlist.size())
            res.add(new ArrayList<Integer>(curlist));
        else{
            for (int i = 0; i < nums.length; i++){
                if (set.contains(nums[i]))
                    continue;
                set.add(nums[i]);
                curlist.add(nums[i]);
                Helper(nums, res, curlist, set);
                set.remove(nums[i]);
                curlist.remove(curlist.size() - 1);
            }
        }
    }
}

2. 去重的全排列：

先排序然后只需要在每个元素入数组之前判断：这个索引之前没用过&&这个数和上个数不一样

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums == null || nums.length == 0)
            return null;
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Helper(nums, new boolean[nums.length], new LinkedList<Integer>(), res);
        return res;
    }
    private void Helper(int[] nums, boolean[] used, List<Integer> curlist, List<List<Integer>> res){
        if (curlist.size() == nums.length)
            res.add(new ArrayList<Integer>(curlist));
        else{
            int pre = nums[0] - 1;  //这个目的： 记录前一个数
            for (int idx = 0; idx < nums.length; idx ++){
                if (used[idx] == false && (nums[idx] != pre)) {
                    //索引没被用过，而且索引上的数字和前一个数不一样
                    pre = nums[idx];
                    curlist.add(nums[idx]);
                    used[idx] = true;
                    Helper(nums, used, curlist, res);
                    curlist.remove(curlist.size() - 1);
                    used[idx] = false;
                }
            }
        }
    }
}

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums == null || nums.length == 0)
            return null;
        Arrays.sort(nums);
        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
        Helper(res, nums, new boolean[nums.length], new ArrayList<Integer>());
        return res;
    }
    private void Helper(ArrayList<List<Integer>> res, int[] nums, boolean[] use, 
                       ArrayList<Integer> curlist){
        if (curlist.size() == nums.length)
            res.add(new ArrayList<Integer>(curlist));
        else{
            int pre = nums[0] - 1;
            for (int i = 0; i < nums.length; i++){
                if (use[i] == false && pre != nums[i]){
                    pre = nums[i];
                    use[i] = true;
                    curlist.add(nums[i]);
                    Helper(res, nums, use, curlist);
                    curlist.remove(curlist.size() - 1);  //往上回溯时候  去掉后面的尾巴
                    use[i] = false;
                }
            }
        }
    }
}

3. 最长回文串：

https://leetcode-cn.com/problems/longest-palindrome/submissions/

class Solution {
    public int longestPalindrome(String s) {
        if(s == null || s.length() == 0)
            return 0;
        int[] count = new int[128];
        int res = 0;
        for (char c : s.toCharArray()){
            count[c] ++;
        }
        
        for (int val : count){
            res += val/2 *2;
            if (val%2 == 1 && res%2 == 0)  //如果想当中心
                res++;
        }
        return res;
    }
}

4. 最长回文子串：

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode/

中心拓展法，对每个字母进行中心拓展。

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1)
            return "";
        int start = 0, end = 0;
        int len = 0;
        for(int i = 0; i < s.length(); i++){
            int len1 = expand(s, i, i);
            int len2 = expand(s, i, i+1);
            len = Math.max(len1, len2);
            if (len > (end - start)){
                start = i - (len - 1)/2;
                end = i + (len/2);
            }
        }
        
        return s.substring(start,end + 1);
    }
    
    private int expand(String s, int l, int r){
        int i = l, j = r;
        while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)){
            i --;
            j ++;
        }
        return j - i - 1;
    }
}

5. 二叉树展开为链表

后序递归，先右后左。

class Solution {
    TreeNode pre = null;
    public void flatten(TreeNode root) {
        if (root == null)
            return;
        flatten(root.right);
        flatten(root.left);
        root.right = pre;
        root.left = null;
        pre = root;
    }
}

6. 最长递增子序列：

https://leetcode-cn.com/problems/longest-increasing-subsequence/submissions/

动态规划，

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < dp.length; i++) {
            int maxval = 0;
            for (int j = 0; j < i; j++) {          //对i之前的数遍历：如果i比j上的数大，那就看maxval能不能取更大的
                if (nums[i] > nums[j]) {
                    maxval = Math.max(maxval, dp[j]);  
                }
            }
            dp[i] = maxval + 1;
            maxans = Math.max(maxans, dp[i]);             //每个i结束，都看看能不能当最大的
        }
        return maxans;
    }
}
//我的方法：
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int res = 1;
        for (int i = 1; i < nums.length; i++){
            int maxFori = 0;
            for (int j = 0; j < i; j++){
                if(nums[i] > nums[j])
                    maxFori = Math.max(maxFori, dp[j]);
            }
            dp[i] = maxFori + 1;
            res = Math.max(res, dp[i]);
        }
        
        return res;
    }
}

7. 最长公共子数组：

https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

从后往前

class Solution {
    public int findLength(int[] A, int[] B) {
        int ans = 0;
        int[][] memo = new int[A.length + 1][B.length + 1];
        //从后往前
        for (int i = A.length - 1; i >= 0; --i) {
            for (int j = B.length - 1; j >= 0; --j) {
                if (A[i] == B[j]) {
                    memo[i][j] = memo[i+1][j+1] + 1;
                    if (ans < memo[i][j])
                        ans = memo[i][j];
                }
            }
        }
        return ans;
    }
}

8. 快速幂：

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double ans = 1;
        double current_product = x;
        for (long i = N; i > 0; i /= 2) {
            if ((i % 2) == 1) {
                ans = ans * current_product; //注意这里：不管n是奇数还是偶数，都会走这一步，因为最后i都是1，如果n是奇数，那么就在第一步时候多乘个自己
            }
            current_product = current_product * current_product;
        }
        return ans;
    }
};

9. 合并k个有序链表

使用优先队列

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0)
            return null;
        PriorityQueue<ListNode> qu = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                if (o1.val < o2.val) return -1;
                else if (o1.val == o2.val) return 0;
                else return 1;
            }
        });
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        for (ListNode node: lists){ //先把头放进去
            if (node != null)
                qu.add(node);
        }
        //出队  下一个不空入队
        while(!qu.isEmpty()){
            p.next = qu.poll();
            p = p.next;
            if (p.next != null) qu.add(p.next);
        }
        return dummy.next;
    }
}