二刷Leetcode-Days04

数组：

    /**
     * 27. 移除元素
     * @param nums
     * @param val
     * @return 很多考察数组、链表、字符串等操作的面试题，都使用双指针法。
     */
    public int removeElement(int[] nums, int val) {
        int left = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[left] = nums[i];
                left++;
            }
        }
        return left;
    }

链表：

    /**
     * 707. 设计链表
     */
    class MyLinkedList {
        private ListNode head;
        //size存储链表元素的个数
        private int size;
        public MyLinkedList() {
            size = 0;
            head = new ListNode(-1);
        }

        public int get(int index) {
            //如果index非法，返回-1
            if (index < 0 || index >= size) {
                return -1;
            }
            ListNode cur = head;
            //包含一个虚拟头节点，所以查找第 index+1 个节点
            for (int i = 0; i <= index; i++) {
                cur = cur.next;
            }
            return cur.val;
        }

        //在链表最前面插入一个节点，等价于在第0个元素前添加
        public void addAtHead(int val) {
            addAtIndex(0, val);
        }

        //在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
        public void addAtTail(int val) {
            addAtIndex(size, val);
        }

        // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
        // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
        // 如果 index 大于链表的长度，则返回空
        public void addAtIndex(int index, int val) {
            if (index > size) {
                return;
            }
            if (index == 0) {
                index = 0;
            }
            size++;
            //找到要插入节点的前驱
            ListNode cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            ListNode addNode = new ListNode(val);
            addNode.next = cur.next;
            cur.next = addNode;

        }

        public void deleteAtIndex(int index) {
            if (index < 0 || index >= size) {
                return;
            }
            size--;
            // 除了头结点需要单独考虑，其他不用
            if (index == 0) {
                head = head.next;
                return;
            }
            ListNode cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
    }

哈希表：

    /**
     * 349. 两个数组的交集
     * @param nums1
     * @param nums2
     * @return 给定两个数组nums1和nums2，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序 。
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> tempSet = new HashSet<>();
        Set<Integer> res = new HashSet<>();
        // 使用set集合的去重功能
        for (int i = 0; i < nums1.length; i++) {
            tempSet.add(nums1[i]);
        }
        for (int num : nums2) {
            if (tempSet.contains(num)) {
                res.add(num);
            }
        }
        return res.stream().mapToInt(x -> x).toArray();
    }

// end -> 快排、堆排序、希尔排序、归并排序