力扣爆刷第106天之CodeTop100五连刷16-20

力扣爆刷第106天之CodeTop100五连刷16-20

一、141. 环形链表

题目链接：https://leetcode.cn/problems/linked-list-cycle/description/
思路：快慢指针，一个每次走两步，一个走一步，只要相遇必定成环。

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) return true;
        }
        return false;
    }
}

二、20. 有效的括号

题目链接：https://leetcode.cn/problems/valid-parentheses/description/
思路：遇到左括号，添加右括号，如果是右括号，栈为空报错，栈非空看栈顶，不同报错。

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == '(') {
                stack.push(')');
            }else if(c == '[') {
                stack.push(']');
            }else if(c == '{') {
                stack.push('}');
            }else if(stack.isEmpty() || stack.pop() != c) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

三、236. 二叉树的最近公共祖先

题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/
思路：直接前序遍历，遇到p或者q直接返回，接收左右子树的返回值，都不为空返回父节点，否则返回非空的那一个。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
       if(root == null) return null;
       if(root == p || root == q) return root;
       TreeNode left = lowestCommonAncestor(root.left, p, q);
       TreeNode right = lowestCommonAncestor(root.right, p, q);
       if(left != null && right != null) return root;
       return left != null ? left : right;
    }
}

四、88. 合并两个有序数组

题目链接：https://leetcode.cn/problems/merge-sorted-array/description/
思路：归并排序的思路。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = 0, j = 0, k = 0;
        int[] temp = new int[m+n];
        while(i < m && j < n) {
            if(nums1[i] <= nums2[j]) {
                temp[k++] = nums1[i++];
            }else{
                temp[k++] = nums2[j++];
            }
        }
        while(i < m) {
            temp[k++] = nums1[i++];
        }
        while(j < n) {
            temp[k++] = nums2[j++];
        }
        i = 0;
        while(i < n + m) {
            nums1[i] = temp[i];
            i++;
        }
    }
}

五、46. 全排列

题目链接：https://leetcode.cn/problems/permutations/description/
思路：元素无重要求排列，元素无重不需要考虑横向去重，求排列不需要起始位置，只需要纵向去重，使用used数组即可。

class Solution {
    List<List<Integer>> arrayList = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    boolean[] flag;
    public List<List<Integer>> permute(int[] nums) {
        flag = new boolean[nums.length];
        backTracking(nums);
        return arrayList;
    }
    
    void backTracking(int[] nums) {
        if(list.size() == nums.length) {
            arrayList.add(new ArrayList(list));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            if(flag[i]) continue;
            flag[i] = true;
            list.add(nums[i]);
            backTracking(nums);
            flag[i] = false;
            list.remove(list.size()-1);
        }
    }

}