1. In a two-dimensional array, each row is sorted in ascending order from left to right and each column is sorted in ascending order from top to bottom. Complete a function that inputs such a two-dimensional array and an integer and determines whether the array contains the integer.

  • If the two dimensional array to {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}}; The value for both searches is 15.

    • The general idea is to take the value of each two-dimensional array, and then iterate over each value to see if it’s equal! And we know it’s going to loop16Times. The following code 
      Private Boolean lookUpInTwoDimensionalArrays (int [] [] a, int num) {/ / at least that length of at least 1, and there are elements,if (a == null || a.length < 1 || a[0].length < 1) {
      return false;
  }
  int b = 0;
  for (int i = 0; i < a.length; i++) {
      for (int j = 0; j < a[i].length; j++) {
          b++;
          if(num == a[I][j]) {12 system.out.println (TAG +)"How many times in total:" + b);
              return true; }}}return false;
 }
Copy the code
    • The idea is as follows
      • 1, select the first element of the two-dimensional array, compare the rightmost values, if they are equal, the search ends
      • 2. Select the first element in the two-dimensional array, compare the rightmost value, if greater than, look for that element, subtract 1 from the Angle, and continue looking
      • 3. Select the first element in a two-dimensional array and compare the rightmost value. If the value is greater than, it is not the element you are looking for, then go to the next array and continue the search

  • The final code looks like this

/** * The array is incrementing, from left to right from top to bottom, so the array must be a square ** @param arr the original array * @param num the number to look for * @returnIf found * / private Boolean newLookUpInTwoDimensionalArrays (int [] [] arr, int num) {if (arr == null || arr.length < 1 || arr[0].length < 1) {
            return false; } int rowTotal = arr.length; Int colTolal = arr[0].length; Int row = 0; int col = colTolal - 1; int i = 0;while(row >= 0 && row < rowTotal &&col >= 0 &&col < colTolal) {// arr[0][arr[0].length-1] = arr[0].length-1];if (arr[row][col] == num) {
                System.out.println(TAG + How many times "newLookUpInTwoDimensionalArrays performed" + i);
                return true;
            } else if(arr[row][col] > num) {// select * from arr[row][col] > num; // Select * from 'left' where 'left' = 'left';else{// if num is larger than the target, add 1 to the number of rows and move row++ down; }}return false;
    }
Copy the code
  • If the lookup value is15, then the old code will execute15The new code will only be executed3Times.

2, implement a function that replaces each space in the string with “%20”, for example, “We are happy.”, then “We%20are% 20Happy.”

  • The first method is to first determine the number of whitespace in the string. Determine if the string has enough space to replace with “%20” based on the number. If there is enough space, figure out how much space you need. Maintain a pointer at the end according to the total space required at the end. From the back to the front, encounter non-empty will move the value to the pointer to the position, and then the pointer forward one, encounter “”, the pointer forward, replaced by” 02% “.
Public char[] replaceBlank(char[] string, int usedLength) {system.out.println (TAG+)"string.length="+string.length);
        System.out.println(TAG+"usedLength="+usedLength);
        if (string == null || string.length < usedLength) {
            returnnull; } // Count the number of whitespace characters in the character array int whiteCount = 0;for (int i = 0; i < usedLength; i++) {
            if (string[i] == ' ') { whiteCount++; }} // If there are no whitespace characters, do not handle themif (whiteCount == 0) {
            returnstring; Int targetLength = whiteCount * 2 + usedLength; // Array of new saved strings char[] newChars = new char[targetLength]; int tmp = targetLength; // Save the length result for return //if(targetLength > string.length) {// If the converted length is greater than the maximum length of the array, return failure directly //return- 1; } // todo must do this first, notice the difference between I and I -- usedLength; TargetLength --; targetLength--; targetLength--; // There are whitespace characters in the character, until all the whitespace characters have been processedwhile(usedLength >= 0 && usedLength < targetLength) {// If the current character is whitespace, go ahead"% 20"replaceif (string[usedLength--] == ' ') {
                newChars[targetLength--] = '0';
                newChars[targetLength--] = '2';
                newChars[targetLength--] = The '%';
            } elseNewChars [targetLength--] = string[usedLength]; } usedLength--; }return newChars;
    }
Copy the code
  • The second method is very time and memory consuming.
 private String idoWorkReplace(String str, String tagStr) {
        if (str == null || str.length() < 1) {
            return "";
        }
        String[] split = str.split("");
        StringBuffer stringBuffer = new StringBuffer();
        for (String s : split) {
            stringBuffer.append(s);
            stringBuffer.append(tagStr);
        }
        CharSequence charSequence = stringBuffer.subSequence(0, stringBuffer.length() - tagStr.length());
        return charSequence.toString();
    }
Copy the code
  • The third method, callreplaceMethod, if it’s just to replace strings, is the best way to do itindexOf(this, targetStr, lastMatch).
StringBuffer sb = new StringBuffer(); sb.append(str); Sb.tostring ().replace().replace();""."% 20");
Copy the code
  • The fourth method is similar to the first method: first count the number of whitespace, then calculate the length of whitespace, and then set the new lengthStringBuffer, by inserting the largest corner mark, and keep inserting, and that’s it
Private String replaceSpaces(String String) {// Check whether the input is validif (string == null || string.length() < 1) {
            return ""; } char[] chars = string.toCharArray(); // Count how many empty arrays there are int whiteCount = 0;for (int i = 0; i < chars.length; i++) {
            if (chars[i] == ' ') { whiteCount++; }}if (whiteCount == 0) {
            returnstring; Int indexOld = string.length() -1; Int newLength = string.length() + whiteCount * 2; Int indexNew = newLength - 1; StringBuffer stringBuffer = new StringBuffer(string); // Set the new buffer length stringbuffer.setLength (newLength);for(; indexold >= 0 && indexold < newlength; Indexold --) {// The last bit of the original string was a spaceif (string.charAt(indexold) == ' ') {
                stringBuffer.setCharAt(indexnew--, '0');
                stringBuffer.setCharAt(indexnew--, '2');
                stringBuffer.setCharAt(indexnew--, The '%');
            } else{string buffer.setCharat (indexNew --, string.charat (indexOld)); string Buffer.setCharat (indexNew --, string.charat (indexOld)); }}return stringBuffer.toString();
    }
Copy the code

3, input a list of the head node, from the end to the reverse print out the value of each node.

  • The data structure
public static class ListNode { int val; ListNode next; public ListNode(int v){ this.val=v; }}Copy the code
  • Initialize the
     ListNode listNode = new ListNode(10);
     ListNode listNode1 = new ListNode(11);
     ListNode listNode2 = new ListNode(12);
     ListNode listNode3 = new ListNode(13);
      ListNode listNode4 = new ListNode(14);
        listNode.next=listNode1;
        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
Copy the code
  • The details of the first method, which is very much like traversing a binary tree, are the simplest.
   public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        arrayList.clear();
        if(listNode ! = null) {printListFromTailToHead(listNode.next); // Point to the next node arraylist.add (listnode.val); // Store the value of the current node in the list}return arrayList;
    }
Copy the code
  • The second way is to useStackThe characteristics of theStackClass: inherited fromVectorImplement a lifO stack. If you don’t understand, you can see herePrinciple analysis of common sets;
private static void doWhat(ListNode listNode) {
        Stack<ListNode> stack = new Stack<>();
        while(listNode! =null){ stack.push(listNode); listNode=listNode.next; } System.out.println(" stack "+stack.size());
//        for(int i=0; i<stack.size(); i++){ // System.out.println("Each element to be printed ::"+stack.get(i).val);
//        }
        ListNode tmp;
        while(! Stack.empty ()){// remove the object at the top of the stack and return it as the value of this function. tmp = stack.pop(); System.out.println("tmp="+tmp.val);
          //  System.out.println("Each element to be printed:"+tmp.val); }}Copy the code

4. Input the results of preorder traversal and in-order traversal of a binary tree, and reconstruct the binary tree. Assume that there are no duplicate numbers in the result of either the preorder walk or the in-order walk of the input. I have serious doubts about the official answer to this question, or I may not have found the right answer at all!

  • A binary tree is a tree structure in which each node has at most two subtrees. Usually a subtree is called a left subtree.(left subtree)And the right subtree(right subtree). Binary tree is often used to implement binary search tree and binary heap. The tree data structure has the advantages of fast array lookup and fast list insertion and deletion
  • The code structure
Public interface Tree {// Node find(int key); Boolean insert(int data); Void infixOrder(Node current); Void preOrder(Node current); Void postOrder(Node current); Node findMax(); // Find the minimum Node findMin(a); Boolean delete(int key); }Copy the code
  • Node
public class Node { int data; // Node leftChild; // The reference to the left child Node rightChild; Public Node(int data){this.data = data; } // Print the contents of the node public voiddisplay(){
        System.out.println(data);
    }

    @Override
    public String toString() {
        returnsuper.toString(); }}Copy the code
  • The process of inserting data
      BinaryTree bt = new BinaryTree();
       // 第一个插入的结点是 根节点
       bt.insert(50);
       bt.insert(20);
       bt.insert(80);
       bt.insert(10);
       bt.insert(30);
       bt.insert(60);
       bt.insert(90);
       bt.insert(25);
       bt.insert(85);
       bt.insert(100);
Copy the code
  • Insert the code
Public Boolean insert(int data) {Node newNode = newNode (data);if(root == null) {// The current tree is empty, there is no node root = newNode;return true;
        } else {
            Node current = root;
            Node parentNode = null;
            while(current ! = null) { parentNode = current;if(current.data > newnode.data) {// if the current value is larger than the inserted value, search for the leftChild node.ifParentnode.leftchild = newNode; parentNode.leftChild = newNode; parentNode.leftChild = newNode; parentNode.leftChild = newNode;return true; }}else {
                    current = current.rightChild;
                    ifParentnode.rightchild = newNode; (current == null) {parentNode.rightChild = newNode;return true; }}}}return false;
    }
Copy the code

  • The final diagram is as follows

  • Binary tree preorder traversal: root node >> left subtree >> right subtree
  public void preOrder(Node current) {
        if(current ! = null) { System.out.print(current.data +""); infixOrder(current.leftChild); infixOrder(current.rightChild); }}Copy the code
  • 1, root 50, look for the left node, find 20, then 10, output 10, then find 25, then 30. I’m going to print out 50, 10, 20, 25, 30
  • 2, find the right node of the root 50, then find 80, find the left node of 80 60. Then 80, look for the right node 95 of 80, print 85, then 90, and finally print 100
  • 3, the final output of the result 50 10 20 25 30 60 80 85 90 100

  • Binary tree in order traversal: first traversing the left subtree, then access the root, and finally traversing the right subtree. Left subtree — root —- Right subtree
  public void infixOrder(Node current) {
        if(current ! = null) { infixOrder(current.leftChild); System.out.print(current.data +""); infixOrder(current.rightChild); }}Copy the code
  • 1. Pass in the value of root node 50, find the left node of 50, 20 is not null, find the left node of 20 again, 10 is not null, then find the left node of 10, null, output 10, the output of the first node is 10
  • Next, find the right node of 10, null, do not enter the output statement
  • 3, this output statement 20, find the right node of 20, find the value of 30, the first step to find the value of the left node, find the value of 25, find the right node is null
  • 4, the output here is 10, 20, 25, 30
  • 5, in this case 50 left node all search
  • 6, next find the right node of 50, find the right node of 80, then find the left node of 80, find the value of 60,60 has no right node, continue to find the right node of 80, output the result here 10 20 25 30 50 60 80
  • 7, find the right node of 80, find the value of 90, then find the left node of 90, find the value of 85, then find the left node of 85 is null, return directly find the right node of 90, find the value of 100,
  • 8, the final output results, 10 20 25 30 50 60 80 85 90 100

  • Back-order traversal: in a binary tree, the left subtree is traversed first, then the right subtree is traversed, and finally the root node is visited.
    • 1, the root node 50, find the left node 20, continue to find the left node 10 of 20,10 has no left or right nodes, print 10, then find the right node 30 of 20,30 continue to find 25, the first output is 10, 20, 25,30
    • 2, the final output 10 20 25 30 60 80 85 90 100 50

  • Look for the maximum or minimum value
// Find the maximum public NodefindMax() {
        Node current = root;
        Node maxNode = current;
        while(current ! = null) { maxNode = current; current = current.rightChild; }returnmaxNode; } // Find the minimum public NodefindMin() {
        Node current = root;
        Node minNode = current;
        while(current ! = null) { minNode = current; current = current.leftChild; }return minNode;
    }
Copy the code
  • For example, preorder traversal sequence{50 10 20 25 30 60 80 85 90 100}And in order traversal sequence{10 20 25 30 50 60 80 85 90 100}, rebuild the binary tree and output its head node.
  • The result of traversing the original node, you can see very clearly, how many left and right nodes there are, which node is the node of that and so on.
09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node50 is over there Root 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node20 is over there Left 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node10 is over there Left 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node30 is over there Right 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node25 is over there Left 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node80 is over there Right 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node60 is over there Left 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node90 is over there Right 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node85 is over there Left 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: the value is what Node100 is over there rightCopy the code
  • Solution 1:
 public static Node reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in== null || pre.length ! = in.length)// If one of the first or middle ordinals is null, the tree cannot be built, and null is returnedreturn null;
        else {
            return reBulidTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
        }
    }

    /**
     * @param pre
     * @param startPre
     * @param endPre
     * @param in
     * @param startIn
     * @param endIn
     * @return
     */
    private static Node reBulidTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
        if(startPre > endPre | | startIn > endIn) / / to pass judgment parameter to check firstreturnnull; int root = pre[startPre]; Int locateRoot = locate(root,in, startIn, endIn); The middle order of the left subtree and the middle order of the right subtree are bounded by the position of the root nodeif(locateRoot == -1) // If no follow-node is found in the ordinal group, return nullreturnnull; Node treeRoot = new Node(root); TreeRoot. LeftChild = alter lidTree(pre, startPre + 1, startPre + locateRoot - startIn,in, startIn, locateRoot - 1); RightChild = alter lidTree(pre, startPre + locateRoot - startIn + 1, endPre,in, locateRoot + 1, endIn); // Recursively construct the right subtreereturntreeRoot; } private static int locate(int root, int[] private static int locate(int root, int[]) private static int locate(int root, int[])in, int startIn, int endIn) {
        for (int i = startIn; i < endIn; i++) {
            if (root == in[i])
                return i;
        }
        return- 1; }Copy the code
  • However, the output of this is as follows, which is obviously not successful in rebuilding the binary tree. Its execution process is as shown in the above code. In my opinion, there is no output diagram because there is no reconstruction
09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: New - in the beginning of the sequence traversal 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node50 is over there Root 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node10 is over there Left 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node20 is over there Right 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node25 is over there Right 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node60 is over there Right 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node80 is over there Right 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node85 is over there Right 09-02 05:51:53. 177, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node90 is over there Right 09-02 05:51:53. 185, 2590-2590 / com. Android. The interview I/System. Out: new, in the end of the sequence traversalCopy the code
  • Solution two: the idea of solving the problem is constantly traversal, the code is as follows
 public static Node reConstructBinaryTreeNew(int[] pre, int[] in) {
        if (pre.length == 0 || in.length == 0)
            return null;
         Node node = new Node(pre[0]);
        for (int i = 0; i < pre.length; i++) {
            if (pre[0] == in[i]) {
                node.leftChild = reConstructBinaryTreeNew(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                node.rightChild = reConstructBinaryTreeNew(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
                break; }}return node;
    }
Copy the code
  • The output is the same as the result of method one. The binary tree is still going to be different.
09-02 05:51:53. 185, 2590-2590 / com. Android. The interview I/System. Out: New - in the beginning of the sequence traversal -- -- -- -- -- -- -- -- -- -- -- - 09-02 05:51:53. 185, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node50 is over there Root 09-02 05:51:53. 185, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node10 is over there Left 09-02 05:51:53. 186, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node20 is over there Right 09-02 05:51:53. 194, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node25 is over there Right 09-02 05:51:53. 211, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node30 is over there Right 09-02 05:51:53. 212, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node60 is over there Right 09-02 05:51:53. 212, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node80 is over there Right 09-02 05:51:53. 212, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node85 is over there Right 09-02 05:51:53. 213, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node90 is over there Right 09-02 05:51:53. 213, 2590-2590 / com. Android. The interview I/System. Out: This value is what Node100 is over there Right 09-02 05:51:53. 214, 2590-2590 / com. Android. The interview I/System. Out: the new new - in the end of the sequence traversal -- -- -- -- -- -- -- -- -- -- -- --Copy the code
  • Solution 3: The root node is known from the first node traversed in the preceding order. According to the root node, the in-order traversal can be divided into left and right subtrees. In the preorder traversal to find the corresponding left and right subtree, its first node is the left and right child nodes of the root node. The binary tree can be reconstructed recursively in the above manner.
Public class Test {/** * please implement a function that replaces each space in the string with"% 20"For example, "We are happy.", "We%20are% 20Happy." is displayed. * * @param string Array of characters to convert * @param usedLength Length already used in the character array * @return*/ public static int replaceBlank(char[] string, int usedLength) {// Check whether the input is validif (string == null || string.length < usedLength) {  
            return- 1; } // Count the number of whitespace characters in the character array int whiteCount = 0;for (int i = 0; i < usedLength; i++) {  
            if (string[i] == ' ') { whiteCount++; Int targetLength = whiteCount * 2 + usedLength; int targetLength = whiteCount * 2 + usedLength; int tmp = targetLength; // Save the length result for returnif(targetLength > string.length) {// If the length of the converted array is greater than the maximum length of the array, a failure is returnedreturn- 1; } // If there are no whitespace characters, do not handle themif (whiteCount == 0) {  
            returnusedLength; } usedLength--; TargetLength --; targetLength--; targetLength--; // There are whitespace characters in the character, until all the whitespace characters have been processedwhile(usedLength >= 0 && usedLength < targetLength) {// If the current character is whitespace, go ahead"% 20"replaceif (string[usedLength] == ' ') {  
                string[targetLength--] = '0';  
                string[targetLength--] = '2';  
                string[targetLength--] = The '%';  
            } else{// Otherwise move character string[targetLength--] = string[usedLength]; } usedLength--; }returntmp; }}Copy the code

  • The result of these three ways is also the same, I think that the binary tree did not reconstruct successfully, if there is a big guy understand, can point out, thank you!

  • Thanks for the help given to me by the following materials

    • Java data Structures and algorithms (x) — Binary trees
    • android_interview