强化第一章

1 Two Sum

    public int[] twoSum(int[] numbers, int target) 
    {
        int[] res = {-1, -1};
        if (numbers == null || numbers.length < 2) {
            return res;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(target - numbers[i])) {
                res[0] = map.get(target - numbers[i]) + 1;
                res[1] = i + 1;
                return res;
            }
            map.put(numbers[i], i);
        }
        return res;
    }

2 Two Sum - Input array is sorted

        int[] res = new int[]{-1, -1};
        if (nums == null || nums.length == 0) {
            return res;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                res[0] = left + 1;
                res[1] = right + 1;
                return res;
            } else if (sum > target) {
                right--;
            } else {
                left++;
            }
        }
        return res;

3 Triangle Count

    public int triangleCount(int s[]) {
        if (s == null || s.length < 3) {
            return 0;
        }
        int res = 0;
        Arrays.sort(s);
        for (int i = s.length - 1; i >= 2; i--) {
            int left = 0, right = i - 1;
            while (left < right) {
                if (s[left] + s[right] > s[i]) {
                    res += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return res;
    }

4 Segment Tree Build

    public SegmentTreeNode build(int start, int end) {
        if (start > end) {
            return null;
        }
        SegmentTreeNode root = new SegmentTreeNode(start, end);
        if (start != end) {
            int mid = (start + end) / 2;
            root.left = build(start, mid);
            root.right = build(mid + 1, end);
        }
        return root;
    }

5 Segment Tree Build II

    public SegmentTreeNode build(int[] A) {
        // write your code here
        return buildTree(0, A.length - 1, A);
    }
    public SegmentTreeNode buildTree(int start, int end, int[] a){
        if (start > end) {
            return null;
        }
        if (start == end) {
            return new SegmentTreeNode(start, end, a[start]);
        }
        SegmentTreeNode root = new SegmentTreeNode(start, end, a[start]);
        int mid = (start + end) / 2;
        root.left = buildTree(start, mid, a);
        root.right = buildTree(mid + 1, end, a);
        if (root.left != null && root.left.max > root.max) {
            root.max = root.left.max;
        }
        if (root.right != null && root.right.max > root.max) {
            root.max = root.right.max;
        }
        return root;
    }

6 Segment Tree Query

  public int query(SegmentTreeNode root, int start, int end) {
        if (root == null || start > end) {
            return -1;
        }
        if (root.start == start && root.end == end) {
            return root.max;
        }
        int mid = (root.start + root.end) / 2;
        int left_max = Integer.MIN_VALUE;
        int right_max = Integer.MIN_VALUE;
        if (start <= mid) {
            left_max = query(root.left, start, Math.min(mid, end));
        } 
        if (mid + 1 <= end) {
            right_max = query(root.right, Math.max(start, mid + 1), end);
        }
        return Math.max(left_max, right_max);
    }

7 Segment Tree Modify

    public void modify(SegmentTreeNode root, int index, int value) {
        if (root.start == index && root.end == index) {
            root.max = value;
            return;
        }
        int mid = (root.start + root.end) / 2;
        if (root.start <= index && index <= mid) {
            modify(root.left, index, value);
        }
        if (mid + 1 <= index && index <= end) {
            modify(root.right, index, value);
        }
        root.max = Math.max(root.left.max, root.right.max);
    }