剑指Offer 解题报告

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence.length == 0) return false;
        return isLegal(sequence, 0, sequence.length-1);
    }
    public boolean isLegal(int [] sequence, int start, int end){
        if (start == end) return true;
        int mid = start;
        while (sequence[mid++] < sequence[end] && mid < end);
        int tmp = mid;
        while (sequence[tmp++] > sequence[end] && tmp < end);
        if (tmp < end) return false;
        if (mid == start || mid == end){
            return isLegal(sequence, start, end-1);
        } else {
            return isLegal(sequence, start, mid-1) && isLegal(sequence, mid, end-1);
        }
    }
}

public class Solution {
    public int Fibonacci(int n) {
        int a = 0, b = 1,result = 0;
        for (int i = 2; i <= n; i++){
            result = a + b;
            a = b;
            b = result;
        }
        return n >= 2? result : n;
    }
}

// 递归
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        if (listNode != null){
            if (listNode.next != null){
                list = printListFromTailToHead(listNode.next);
            }
            list.add(listNode.val);
        }
        return list;
    }
}
// 函数反转
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        while (listNode != null){
            list.add(listNode.val);
            listNode = listNode.next;
        }
        Collections.reverse(list);
        return list;
    }
}
// 栈
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        while (listNode != null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        while (!stack.isEmpty()){
            list.add(stack.pop());
        }
        return list;
    }
}

public class Solution {
    public boolean match(char[] str, char[] pattern) {
        if (str == null || pattern == null) {
            return false;
        }
        int strIndex = 0, patternIndex = 0;
        return matchCore(str, strIndex, pattern, patternIndex);
    }

    public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
        // 有效性检验，str到尾，pattern到尾，匹配成功
        if (strIndex == str.length && patternIndex == pattern.length) {
            return true;
        }
        // pattern先到尾，匹配失败
        if (strIndex != str.length && patternIndex == pattern.length) {
            return false;
        }
        // 模式第二个是*，且字符串第一个跟模式第一个匹配，分三种匹配模式；
        if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
            if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
                    || (pattern[patternIndex] == '.' && strIndex != str.length)) {
                return matchCore(str, strIndex, pattern, patternIndex + 2) // 模式后移两位，即X*匹配空串
                        || matchCore(str, strIndex + 1, pattern, patternIndex + 2) // 模式匹配了一个字符
                        || matchCore(str, strIndex + 1, pattern, patternIndex); // *匹配了一个，但是str中不止一个
            } else {
                return matchCore(str, strIndex, pattern, patternIndex + 2);
            }
        }
        // 模式第2个不是*，且字符串第1个跟模式第1个匹配，则都后移1位，否则直接返回false
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
                || (pattern[patternIndex] == '.' && strIndex != str.length)) {
            return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
        }
        return false;
    }
}

public class Solution {
    public boolean isNumeric(char[] str) {
        try {
            double re = Double.parseDouble(new String(str));
        } catch (NumberFormatException e) {
            return false;
        }
        return true;
    }
}

public class Solution {
    public boolean isNumeric(char[] str) {
        if (str.length == 0)
            return false;
        // +-。E出现的标志
        boolean sign = false, deciminal = false, hasE = false;
        for (int i = 0; i < str.length; i++) {
            if (str[i] == 'e' || str[i] == 'E') {
                if (i == 0)
                    return false; // 指数符号前必须有整数
                if (i == str.length - 1)
                    return false; // 指数符号后必须有证书
                if (hasE)
                    return false; // 只能有一个指数符号
                hasE = true;
            } else if (str[i] == '.') {
                if (hasE)
                    return false; // 小数点只能出现在指数符号之前
                if (i == str.length - 1)
                    return false; // 小数点不能出现在最后一位上
                if (deciminal)
                    return false; // 小数点只能出现一次
                deciminal = true;
            } else if (str[i] == '+' || str[i] == '-') {
                if (!sign && i != 0 && !hasE)
                    return false; // 第一次出现+''-'符号只能在第一个字符或者指数符号后
                if (sign && !hasE)
                    return false; // 第二出现'+''-'符号只能在指数符号后
                if (i == str.length - 1)
                    return false; // '+''-'符号不能出现在最后一位上
                sign = true;
            } else if (str[i] < '0' || str[i] > '9')
                return false; // 其它的非数字字符
        }
        return true;
    }
}

import java.util.regex.Pattern;
public class Solution {
    public static boolean isNumeric(char[] str) {
        String pattern = "^[-+]?\\d*(?:\\.\\d*)?(?:[eE][+\\-]?\\d+)?$";
        String s = new String(str);
        return Pattern.matches(pattern,s);
    }
}

public class Solution {
    private int count = 0;
    public int InversePairs(int[] a) {
        if (a == null || a.length == 0)
            return -1;
        mergeSort(a, 0, a.length - 1);
        return count;
    }
    // 递归分解，分解到不可分解时候，进入合并阶段。
    public void mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(a, left, mid);
            mergeSort(a, mid + 1, right);
            merge(a, left, mid, right);
        }
    }
    // 合并阶段，从两个数组的最右侧开始比较，比较计数之后将较大元素依次插入拷贝数组，最后覆盖原数组，有点归并排序的意思。
    public void merge(int[] a, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        int t = right - left;
        int l = mid;
        int r = right;
        while (l >= left && r >= mid + 1) {
            if (a[l] > a[r]) {
                count += (r - mid);
                tmp[t--] = a[l--];
                if (count >= 1000000007) {
                    count %= 1000000007;
                }
            } else {
                tmp[t--] = a[r--];
            }
        }
        while (l >= left) {
            tmp[t--] = a[l--];
        }
        while (r >= mid + 1) {
            tmp[t--] = a[r--];
        }
        for (int i = 0; i <= right - left; i++) {
            a[left + i] = tmp[i];
        }
    }
}

public class Solution {
    int count = 0;
    public int movingCount(int threshold, int rows, int cols){
        int[][] arrays = new int[rows][cols];
        findWay(arrays, 0, 0, threshold);
        return count;
    }
    public void findWay(int[][] arrays, int i, int j, int k){
        if (i <0 || j < 0 || i >= arrays.length || j >= arrays[0].length)
            return;
        if (getSum(i)+getSum(j)>k || arrays[i][j] != 0) return;
        arrays[i][j] = 1;
        count++;
        findWay(arrays, i+1, j, k);
        findWay(arrays, i, j+1, k);
    }
    public int getSum(int i){
        int result = 0;
        while (i!=0){
            result += i%10;
            i/=10;
        }
        return result;
    }
}

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (pRoot == null) return result;
        queue.offer(pRoot);
        int length = 1;
        while (!queue.isEmpty()){
            ArrayList<Integer> rs = new ArrayList<>();
            int t_l = 0, l = 0;
            while (t_l++ < length){
                TreeNode temp = queue.poll();
                rs.add(temp.val);
                if (temp.left != null) {
                    queue.offer(temp.left);
                    l++;
                }
                if (temp.right != null) {
                    queue.offer(temp.right);
                    l++;
                }
            }
            result.add(rs);
            length = l;
        }
        return result;
    } 
}

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead, low = pHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            low = low.next;
            if (fast == low)
                break;
        }
        if (fast == null || fast.next == null)
            return null;
        low = pHead;
        while (fast != low) {
            fast = fast.next;
            low = low.next;
        }
        return fast;
    }
}

public class Solution {
    public String LeftRotateString(String str,int n) {
        if (n>=str.length()) return str;
        return str.substring(n)+str.substring(0,n);
    }
}

// 一种只需要切割一次的方法
public class Solution {
    public String LeftRotateString(String str,int n) {
        int length = str.length();
        if (length == 0) return "";
        n %= length;
        str+=str;
        return str.substring(n, n+length);
    }
}

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        int low = 1, high =2;
        while (high > low){
            int cur = (high + low) * (high - low + 1) / 2;
            if (sum == cur){
                ArrayList<Integer> rs = new ArrayList<>();
                for (int i = low; i<=high; i++){
                    rs.add(i);
                }
                result.add(rs);
                low++;
            } else if (sum > cur){
                high++;
            } else if (sum < cur){
                low++;
            }
        }
        return result;
    }

class Solution {
    public:
    string LeftRotateString(string str, int n) 
    {
        int len = str.size();
        if(len == 0) return str;
        n %= len;
        for(int i = 0, j = n - 1; i < j; ++i, --j) swap(str[i], str[j]);
        for(int i = n, j = len - 1; i < j; ++i, --j) swap(str[i], str[j]);
        for(int i = 0, j = len - 1; i < j; ++i, --j) swap(str[i], str[j]);
        return str;
    }
};

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        return biSearch(array, k+0.5)-biSearch(array, k-0.5);
    }
    // 循环写法
    public int biSearch(int[] array, double k){
        int s = 0, e = array.length-1;
        while (s <= e){
            if (k > array[s+(e-s)/2]){
                s = s+(e-s)/2+1;
            } else {
                e = s+(e-s)/2-1;
            }
        }
        return s;
    }
    // 递归写法
    public int bi(int [] array, int l, int r, double k){
        if (l == r) return l;
        int mid = (l + r) / 2;
        if (array[mid] > k){
            return bi(array, l, mid - 1, k);
        } else {
            return bi(array, mid, r, k);
        }
    }
}

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int resu = 0;
        for (int i = 0; i <= n; i++) {
            int t = i;
            while (t != 0) {
                if (t % 10 == 1)
                    resu++;
                t /= 10;
            }
        }
        return resu;
    }
}

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> result = new ArrayList<>();
        int length = input.length;
        if (k > length || k == 0) {
            return result;
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        for (int i = 0; i < length; i++) {
            if (maxHeap.size() != k) {
                maxHeap.offer(input[i]);
            } else if (maxHeap.peek() > input[i]) {
                maxHeap.poll();
                maxHeap.offer(input[i]);
            }
        }
        for (Integer integer : maxHeap) {
            result.add(integer);
        }
        return result;
    }
}

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int len = array.length;
        if (len == 0) return 0;
        int num = array[0], count=1;
        for (int i = 1; i < len; i++){
            if (array[i] == num) count++;
            else count--;
            if (count == 0){
                num = array[i];
                count = 1;
            }
        }
        count = 0;
        for (int i = 0; i < len; i++){
            if (array[i]==num) count++;
        }
        return count*2>len?num:0;
    }
}

//直接用中序遍历
public class Solution {
    TreeNode head = null;
    TreeNode realHead = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        ConvertSub(pRootOfTree);
        return realHead;
    }

    private void ConvertSub(TreeNode pRootOfTree) {
        if(pRootOfTree==null) return;
        ConvertSub(pRootOfTree.left);
        if (head == null) {
            head = pRootOfTree;
            realHead = pRootOfTree;
        } else {
            head.right = pRootOfTree;
            pRootOfTree.left = head;
            head = pRootOfTree;
        }
        ConvertSub(pRootOfTree.right);
    }
}

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }
        RandomListNode currentNode = pHead;
        // 1.复制每个节点，如复制A得到A1，将节点A1插到A后面
        while (currentNode != null) {
            RandomListNode cloneNode = new RandomListNode(currentNode.label);
            RandomListNode nextNode = currentNode.next;
            cloneNode.next = nextNode;
            currentNode.next = cloneNode;
            currentNode = nextNode;
        }
        currentNode = pHead;
        // 2.重新遍历链表，复制了老节点的随即指针给新结点，如A1.random = A.random
        while (currentNode != null) {
            currentNode.next.random = currentNode.random == null ? null : currentNode.random.next;
            currentNode = currentNode.next.next;
        }
        // 3. 拆分链表，将链表拆分为原链表和复制后的链表
        currentNode = pHead;
        RandomListNode pCloneHead = pHead.next;
        while (currentNode != null) {
            RandomListNode cloneNode = currentNode.next;
            currentNode.next = cloneNode.next;
            cloneNode.next = cloneNode.next == null ? null : cloneNode.next.next;
            currentNode = currentNode.next;
        }
        return pCloneHead;
    }
}

class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            if (nums[low] < nums[high]) return nums[low];
            int mid = low + (high - low) / 2;
            if (nums[mid] > nums[high]){
               low = mid + 1; 
            } else{
               high = mid;
            } 
          }
        return nums[low];
    }
}

public class Solution {
    public String replaceSpace(StringBuffer str) {
        return str.toString().replaceAll("\\s", "%20");
    }
}

public class Solution {
    public String replaceSpace(StringBuffer str) {
        String str1 = str.toString();
        if(str1.equals(""))
            return str1;
        char [] strArray = str1.toCharArray();
        int i =0;
        int lengthSpace = 0;
        while(i < strArray.length){
            if(strArray[i] == ' ')
                lengthSpace++;
            i++;
        }
        int newStrLength = strArray.length + lengthSpace*2;
        char [] newStr = new char[newStrLength];
        int j = newStrLength-1;
        i = strArray.length - 1;
        while(i >= 0){
            if(strArray[i] !=  ' '){
                newStr[j--] = strArray[i--];
            }else{
                newStr[j--] = '0';
                newStr[j--] = '2';
                newStr[j--] = '%';
                i--;
            }
        }
        return new String(newStr);
    }
}

public class Solution {
    public static String replaceSpace(StringBuffer str) {
        String str_to = str.toString();
        String result = "";
        for (int i = 0; i < str_to.length(); i++) {
            if (str_to.charAt(i) == ' ')
                result += "%20";
            else
                result += str_to.charAt(i);
        }
        return result;
    }
}

public class Solution {
    public boolean Find(int target, int[][] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                if (array[i][j] == target) {
                    return true;
                }
            }
        }
        return false;
    }
}

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        //初始化 i 和 j 为数组左下角元素
        int i = matrix.length - 1, 
        int j = 0;
        //如果 i 和 j 没有越界继续判断
        while(i >= 0 && j < matrix[0].length){
            if(matrix[i][j] > target){
                //行索引向上移动一格（即 i-- ），即消去矩阵第 i 行元素
                i--;
            }else if(matrix[i][j] < target){
                //列索引向右移动一格（即 j++ ），即消去矩阵第 j 列元素
                j++;
            }else{
                //找到目标值，直接返回 ture
                return true;
            }     
        }
        //没有找到目标值，返回 false
        return false;
    }
}

public class Solution {
    private ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    private ArrayList<Integer> single = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if (root == null) return result;
        single.add(root.val);
        target -= root.val;
        if (target == 0 && root.left == null && root.right == null){
            result.add(new ArrayList<Integer>(single));
        }
        FindPath(root.left, target);
        FindPath(root.right, target);
        single.remove(single.size()-1);
        return result;
    }
}

import java.util.Arrays;
import java.util.Comparator;
public class Solution {
    public String PrintMinNumber(int[] numbers) {
        String resu = "";
        if (numbers.length == 0)
            return resu;
        int len = numbers.length;
        String[] array = new String[len];
        for (int i = 0; i < len; i++) {
            array[i] = String.valueOf(numbers[i]);
        }
        Arrays.sort(array, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                String r1 = s1 + s2;
                String r2 = s2 + s1;
                return r1.compareTo(r2);
            }
        });
        for (int i = 0; i < array.length; i++) {
            resu += array[i];
        }
        return resu;
    }
}

import java.util.*;
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if (index < 7) return index;
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        int t2 = 0, t3 = 0, t5 =0;
        for (int i = 1; i < index; i++){
            int min = Math.min(arrayList.get(t2)*2, Math.min(arrayList.get(t3)*3, arrayList.get(t5)*5));
            arrayList.add(min);
            if (min == arrayList.get(t2) * 2) t2++;
            if (min == arrayList.get(t3) * 3) t3++;
            if (min == arrayList.get(t5) * 5) t5++;
        }
        return arrayList.get(index-1);
    }
}

// 3
public static int solution(String str){
    int[] words = new int[58];
    for(int i = 0;i<str.length();i++){
        words[((int)str.charAt(i))-65] += 1;
    }
    for(int i=0;i<str.length();i++){
        if(words[((int)str.charAt(i))-65]==1)
            return i;
    }
    return -1;
}
// 1java版
public int FirstNotRepeatingChar(String str) {
    int pos = -1;
    for (int i = 0; i < str.length(); i++) {
        if (str.indexOf(str.charAt(i)) == str.lastIndexOf(str.charAt(i))) {
            pos = i;
            return pos;
        }
    }
    return pos;
}

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode){
        if (pNode == null) return null;
        if (pNode.right!=null){
            pNode = pNode.right;
            while (pNode.left!=null) pNode = pNode.left;
            return pNode;
        }
        while (pNode.next!=null){
            if (pNode.next.left==pNode) return pNode.next;
            pNode = pNode.next;
        }
        return null;
    }
}

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        if (pRoot ==null) return result;
        stack1.push(pRoot);
        int layer =1;
        while (!stack1.isEmpty()||!stack2.isEmpty()){
            if (layer%2!=0){
                ArrayList<Integer> rs= new ArrayList<>();
                while (!stack1.isEmpty()){
                    TreeNode temp = stack1.pop();
                    rs.add(temp.val);
                    if (temp.left != null)
                        stack2.push(temp.left);
                    if (temp.right != null)
                        stack2.push(temp.right);
                }
                result.add(rs);
                layer++;
            }else{
                ArrayList<Integer> rs= new ArrayList<>();
                while (!stack2.isEmpty()){
                    TreeNode temp = stack2.pop();
                    rs.add(temp.val);
                    if (temp.right != null)
                        stack1.push(temp.right);
                    if (temp.left != null)
                        stack1.push(temp.left);
                }
                result.add(rs);
                layer++;
            }
        }
        return result;
    }
}

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Solution so = new Solution();
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextInt()){
            int num=scan.nextInt();
            so.Insert(num);
            Double result = so.GetMedian();
            System.out.println(result);
        }
    }

    //最大堆，存储流左边的元素
    PriorityQueue<Integer> left = new PriorityQueue<Integer>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            /**以下是对比较器升序、降序的理解.
             *(1) 写成return o1.compareTo(o2) 或者 return o1-o2表示升序
             *(2) 写成return o2.compareTo(o1) 或者return o2-o1表示降序
             */
            return o2.compareTo(o1);
        }
    });
    //最小堆，存储流右边元素
    PriorityQueue<Integer> right = new PriorityQueue<Integer>();
    //计数器,初始值为0，插进去一个增加一个
    int N = 0;

    public void Insert(Integer num) {
        //奇数放到left，从left往right倒一个最大值，为的就是保证right最小堆中的所有的值都要大于left
        if (N % 2 == 0) {
            //刚开始N=0，首先是right最小堆中有元素
            left.add(num);
            right.add(left.poll());
        } else {
            right.add(num);
            left.add(right.poll());
        }
        N++;
    }

    public Double GetMedian() {
        if (N % 2 == 1) {
            //奇数个，因为右边比左边多一个，也可以认为右边比左边先有元素
            double result = (double)right.peek();
            return result;
        } else {
            //要先将和转换为double类型，然后再除
            double result = (double) (left.peek() + right.peek())/2;
            return result;
        }
    }
}

public class Solution {
    public double Power(double base, int exponent) {
        double res = 1, curr = base;
        int n = exponent;
        if (exponent > 0)
            exponent *= 1;
        else if (exponent < 0) {
            if (base == 0)
                throw new RuntimeException("分母为0");
            exponent *= -1;
        } else {
            return 1;
        }
        while (exponent != 0) {
            if ((exponent & 1) == 1)
                res *= curr;
            curr *= curr;
            exponent >>= 1;
        }
        return n > 0 ? res : (1 / res);
  }
}

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size){
        ArrayList<Integer> result = new ArrayList<>();
        if (num.length == 0||size==0) return result;
        for (int i = 0; i <= num.length-size; i++){
            int[] temp = Arrays.copyOfRange(num, i, i+size);
            Arrays.sort(temp);
            result.add(temp[temp.length-1]);
        }
        return resut;
    }
}