算法一回首之《括号匹配验证》

    private static final Map<Character, Character> patternMatch = new ConcurrentHashMap<>();

    static {
        patternMatch.put('(', ')');
        patternMatch.put('{', '}');
        patternMatch.put('[', ']');
    }

    /**
     * 1.  括号匹配验证
     * 一个字符串中，包括字符  ‘(‘,  ‘)’,  ‘{‘,  ‘}’,  ‘[‘,  ‘]’。
     * 要求写一个函数，验证字符串中这些括号是以正确的顺序匹配的。
     * 注意：(,  ),  [,  ],  {,  }可以互相嵌套。
     * 譬如："()"  和"()[]{}"是正确的，"(]"  and  "([)]"是不正确的
     *
     * @return
     */
    public boolean bracketMatch(String bracketSource) {
        if (StringUtils.isBlank(bracketSource)) {
            return false;
        }
        char[] charArray = bracketSource.toCharArray();
        Stack<Character> stack = new Stack<>();
        stack.push(charArray[0]);
        for (int i = 1; i < charArray.length; i++) {
            char next = charArray[i];
            if (stack.isEmpty()) {
                stack.push(next);
                continue;
            }
            Character first = stack.peek();
            if (Objects.equals(next, patternMatch.get(first))) {
                stack.pop();
            } else {
                stack.push(next);
            }
        }
        return stack.isEmpty();
    }

    private static <T>
    int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {
        int low = 0;
        int high = list.size()-1;

        while (low <= high) {
            int mid = (low + high) >>> 1; //>>>:无符号右移，忽略符号位，空位都以0补齐
            Comparable<? super T> midVal = list.get(mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }

    /**
     * 冒泡排序：升序
     *
     * @param sourceList
     */
    public void bubbleSort(List<Integer> sourceList) {
        if (sourceList == null || sourceList.isEmpty()) {
            return;
        }
        for (int i = 0; i < sourceList.size(); i++) {
            for (int j = 0; j < sourceList.size() - 1 - i; j++) {
                if (sourceList.get(j) > sourceList.get(j + 1)) {
                    int tmp = sourceList.get(j);
                    sourceList.set(j, sourceList.get(j + 1));
                    sourceList.set(j + 1, tmp);
                }
            }
        }
    }