Android interview Guide (five) ———— algorithm

High frequency record

BubbleSort

Compare two adjacent elements in sequence, swap if the order is wrong, until all elements are exhausted, the last element is the largest (smallest) value, and then sort as described above.

Time complexity: O(n^2)

 private void bubbleSort(int a[]){
        int temp;
        for(int i = 0; i<a.length-1; i++){for(int j = 0; j<a.length-1-i; j++){if(a[j]>a[j+1]){
                    temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp; }}}}Copy the code

Selection sort

On the first trip, find the smallest and put it on the first, on the second trip, find the second smallest and put it on the second…

Time complexity: O(n^2)

public static void selectSort(int a[]){
        for(int i = 0; i<a.length; i++){for(int j = i+1; j<a.length; j++){if(a[i]>a[j]){
                    inttemp = a[i]; a[i] = a[j]; a[j] = temp; }}}}Copy the code

QuickSort

Divide and conquer: divide a large piece into smaller pieces and count them one by one

• Set the value of one side to sentry
• I’m going to put everything to the right of this number, everything less than or equal to this number on the left.
• I’m sorting the rest of the interval

private void quickSort(int a[],int left,int right){
    // End condition
    if(left <right){
        // Sort each time
        int base = division(a,left,right);
        // The sentries start sorting
        / / the left
        quickSort(a,left,base-1);
        / / right
        quickSort(a,base+1,right); }}// Use divide-and-conquer sorting
private int division(int a[],int left,int right){
    / / the sentry
    int base = a[left];
    while (left<right){
        // The sentry is on the left, so move right left
        while(left<right && a[right]>=base){
            right--;
        }
        if(left ! = right) { a[left] = a[right]; }// The sentry is on the right, so the left moves right
        while(left<right && a[left]<=base){
            left++;
        }
        if(left ! = right) { a[right] = a[left]; } } a[left] = base;return left;
}

Copy the code

Binary insertion:

 while (lo <= hi) {
            // Dichotomy is divided into two, array middle index
            final int mid = (lo + hi) >>> 1;
            // The dichotomy is one and two, the value at the middle index of the array
            final int midVal = array[mid];
            
            if (midVal < value) {
                /** If the value in the middle of the array is smaller than the value you are looking for, the value is in the middle and back of the array, so the current subscript is mid + 1 */
                lo = mid + 1;
            } else if (midVal > value) {
                /** If the value in the middle of the array is greater than the value to be found, it means that the value to be found is in the middle of the array, so the current subscript value is mid-1 */
                hi = mid - 1;
            } else {
                // If the value in the middle of the array is the same as the value in question, return the index mid in the middle of the array
                return mid;  // value found}}Copy the code

Poker algorithm

Path from the root node to the destination node

Find the smallest k number

1. Using quicksort: O(nlogn)

       public static int[] getLeastNumbers1(int[] input, int k) {
        if (input == null || input.length < k) {
            return null;
        }
        int[] output = new int[k];
        pivotFindMinK(input, output, k, 0, input.length - 1);
        return output;
    }

    private static void pivotFindMinK(int[] numbers, int[] output, int k, int start, int end) {
        if (numbers == null || numbers.length == 0) {
            return;
        }
        int left = start;
        int right = end;
        int temp = numbers[left];
        while (left < right) {
            while (numbers[right] > temp && left < right) {
                right--;
            }
            numbers[left] = numbers[right];
            while (numbers[left] <= temp && left < right) {
                left++;
            }
            numbers[right] = numbers[left];
        }
        numbers[left] = temp;
        if (left > k-1) {
            pivotFindMinK(numbers, output, k, start, left - 1);
        } else if (left < k-1) {
            pivotFindMinK(numbers, output, k, right + 1, end);
        } else {
            System.arraycopy(numbers, 0, output, 0, k); }}Copy the code

2. Create an array, put k numbers in front of the array, and arrange them in order from small to large, traverse the original array, if there is a smaller value than the new array, insert sort, and then get the new array.
3. Small root heap implementation, in order to put the small root heap — big top heap (parent <= children), small root heap size k, over size, delete the top element, conversely, add the big root heap — small top heap (parent >= children)

Binary search method

/ * * * using recursive binary search * title: recursionBinarySearch *@paramArr ordered array *@paramKey Indicates the keyword to be searched. *@returnLocation found */
	public static int recursionBinarySearch(int[] arr,int key,int low,int high){
		
		if(key < arr[low] || key > arr[high] || low > high){
			return -1;				
		}
		
		int middle = (low + high) / 2;			// The initial middle position
		if(arr[middle] > key){
			If the value is larger than the keyword, the keyword is in the left area
			return recursionBinarySearch(arr, key, low, middle - 1);
		}else if(arr[middle] < key){
			If the value is smaller than the keyword, the keyword is in the right area
			return recursionBinarySearch(arr, key, middle + 1, high);
		}else {
			return middle;
		}	
Copy the code

Can the sum of two numbers in an integer array equal a given number

1. If the array is ordered, the two subscripts, if they’re greater than the given number, the left hand side — if they’re less than the given number, the right hand side ++, until they’re equal or the right hand side equals the left hand side

        int[] a = {1.4.5.7.9.12.56.456};
        int i = 0;
        int j = a.length-1;
        int sum = 65;
        while(i<j){
            if(a[i] + a[j] >sum){
                j--;
            }else if(a[i] + a[j] <sum){
                i++;
            }else{
                System.out.println(a[i] + "+" + a[j] + "=" + sum);
                break; }}Copy the code

2. If the array is unordered

public static void twoSum(int[] nums,int target){
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i<nums.length; i++){ System.out.println("-- -- -- -- -- -- -- --");
            if(map.containsKey(nums[i])){
                System.out.println(nums[map.get(nums[i])] + "+" + nums[i] + "=" + target);
                break;
            }
            intvalue = target-nums[i]; map.put(value,i); }}Copy the code

Maximum sum of contiguous subarrays

    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int sum = nums[0];
        for(int i = 1; i<nums.length; i++){if(nums[i] + sum < nums[i]){
                sum = nums[i];
            }else{
                sum +=nums[i];
            }
            if(sum > max){ max = sum; }}return max;
    }
Copy the code

Moore voting method

class Solution {
    public int majorityElement(int[] nums) {
        int x = 0, votes = 0;
        for(int num : nums){
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        returnx; }}Copy the code

Binary tree

Binary tree traversal

 // sequence traversal
    public void levelOrder(BinaryTreeNode root) {
        BinaryTreeNode temp;
        Queue<BinaryTreeNode> queue = new LinkedList<BinaryTreeNode>();
        queue.offer(root);
        while(! queue.isEmpty()) { temp = queue.poll(); System.out.print(temp.getData() +"\t");
            if (null! = temp.getLeft()) queue.offer(temp.getLeft());if (null! = temp.getRight()) { queue.offer(temp.getRight()); }}}// Preorder traversal recursively
    public void preOrder(BinaryTreeNode root) {
        if (null! = root) { System.out.print(root.getData() +"\t"); preOrder(root.getLeft()); preOrder(root.getRight()); }}// Preorder traversal in a non-recursive manner
    public void preOrderNonRecursive(BinaryTreeNode root) {
        Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
        stack.push(root);
        while(! stack.isEmpty()) { BinaryTreeNode node = stack.pop(); System.out.print(node.getData() +"\t");
            if(node.getRight() ! =null) {
                stack.push(node.getRight());
            }
            if(node.getLeft() ! =null) { stack.push(node.getLeft()); }}}// Middle order facilitates non-recursion
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root == null) {return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while(! stack.isEmpty()){ TreeNode node = stack.pop();if(node.left ! =null){
                stack.add(node);
                stack.add(node.left);
            }else{
                list.add(node.val);
                if(node.right ! =null){
                    stack.add(node.right);
                }else{
                    while(! stack.isEmpty()){ TreeNode node1 = stack.pop(); list.add(node1.val);if(node1.right ! =null){
                            stack.add(node1.right);
                            break;
                        }
                    }
                }
            }
        }
        return list;
    }
    
    // after the sequence traversal
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null) {return new ArrayList<>();
        }
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while(! stack.isEmpty()){ TreeNode node = stack.pop(); list.add(node.val);if(node.left ! =null){
                stack.add(node.left);
            }
            if(node.right ! =null){
                stack.add(node.right);
            }
        }
        List<Integer> result = new ArrayList<>();
        for(int i = list.size()-1; i>=0; i--){ result.add(list.get(i)); }return result;
    }
		// Zigzag print
		public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> listList = new ArrayList<>();
        if(root == null) {return listList;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int i = 1;
        while(! queue.isEmpty()){ LinkedList<Integer> list =new LinkedList<>();
            int count = queue.size();
            for(int j = 0; j<count; j++){ TreeNode node = queue.poll();if(i%2= =0){
                    list.addFirst(node.val);
                }else{
                    list.add(node.val);
                }
                if(node.left ! =null){
                    queue.add(node.left);
                }
                if(node.right ! =null){
                    queue.add(node.right);
                }
            }
            i++;
            if(list.size()>0){ listList.add(list); }}return listList;
    }

Copy the code

Two views the first public parent view

1. Add a set and a set, one to store a, put b in array A, return false when array a is repeated, and return in another set.

public static Set<Integer> getIds(Integer[] a, Integer[] b){
	  
	  Set<Integer> same = new HashSet<Integer>();  // Store the same elements in two arrays
	  Set<Integer> temp = new HashSet<Integer>();  // To store the elements of array A
	  
	  for (int i = 0; i < a.length; i++) {
		  temp.add(a[i]);   // Insert elements from array A into Set to remove duplicate elements
	  }
	  
	  for (int j = 0; j < b.length; j++) {
	    // Add elements from array B to temp
	    Temp. Add (b[j]) returns false if the same element already exists in temp
		if(!temp.add(b[j]))
			same.add(b[j]);
	}
}
Copy the code

If you want to find the index of two arrays, use map where key is the value and value is the index of the array

2. Put array A into set, poll b into set, return false, repeat the value

public static void getIds(int a[], int b[]) {
        Set<Integer> set1 = new HashSet<>();
        for(Integer integer:a){
            set1.add(integer);
        }

        for(Integer j:b){
            if(! set1.add(j)){ System.out.println(j);break; }}}Copy the code

3. The first root node in two linked lists

The two Pointers run two chains respectively. After the short run, the long head is assigned to the past, and then the long run is also completed. Finally, the intersection of the two Pointers is the first root node of the two linked lists

 public static void getNode(Node nodeA, Node nodeB) {
        Node pA = nodeA;
        Node pB = nodeB;
        while(pA ! = pB) {if (pA.next == null) {
                pA = nodeB;
            } else {
                pA = pA.next;
            }
            if (pB.next == null) {
                pB = nodeA;
            } else {
                pB = pB.next;
            }
        }
        System.out.print(pA.value);
    }
Copy the code

4. The most recent common ancestor of a binary tree

class Solution {
    TreeNode node;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dps(root,p,q);
        return node;
    }

    public boolean dps(TreeNode root, TreeNode p, TreeNode q){
        if(root == null) {return false;
        }
        if(root.val == p.val){
            node = p;
            return true;
        }
        if(root.val == q.val){
            node = q;
            return true;
        }
        boolean a = dps(root.left,p,q);
        boolean b = dps(root.right,p,q);
        if(a && b){
            node = root;
        }
        if(a || b){
            return true;
        }
        return false; }}Copy the code

Determine if the list is circular and return to the entry

Two Pointers, one running one at a time, one running two at a time, if they intersect, there is a ring chain

The slow ones will run one by one from the beginning, the fast ones will run from the intersection point, one by one, and finally meet is the entrance

public static Node isCircle(Node node) {
        Node p = node;
        Node q = node;
        while(p ! =null&& q ! =null) {
            p = p.next.next;
            q = q.next;
            if(p == q){
                while(node ! = p){ node = node.next; p = p.next; }returnnode; }}return p;
    }
Copy the code

We have an array of integers, positive and negative numbers, and we put the negative numbers to the left, keeping their relative positions the same

To a linked list, traversing the linked list will recover and separate linked to the remaining positive chain

The array has two indexes, one that records the end of a negative number, and one that iterates through the array.

 public static void get(int a[]){
        for(int i = 0,j = 0; j<a.length; j++){if(a[j]<0) {int temp = a[j];
                int k = j;
                while(i<=k-1){
                    a[k] = a[k-1]; k--; } a[i] = temp; i++; }}for(inti:a){ System.out.println(i); }}Copy the code

Print the serpentine matrix

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0) return new int[0];
        int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, x = 0;
        int[] res = new int[(r + 1) * (b + 1)];
        while(true) {
            for(int i = l; i <= r; i++) res[x++] = matrix[t][i]; // left to right.
            if(++t > b) break;
            for(int i = t; i <= b; i++) res[x++] = matrix[i][r]; // top to bottom.
            if(l > --r) break;
            for(int i = r; i >= l; i--) res[x++] = matrix[b][i]; // right to left.
            if(t > --b) break;
            for(int i = b; i >= t; i--) res[x++] = matrix[i][l]; // bottom to top.
            if(++l > r) break;
        }
        returnres; }}Copy the code

Find the number of leaves in a binary tree

public int testTree(Tree tree){
        if(tree==null) {return 0;
        }
        if(tree.left==null&&tree.right==null){
            System.out.println("Leaf node:"+tree.val);
            return 1;
        }
        return testTree(tree.left)+testTree(tree.right);
    }
Copy the code

Find the depth of the binary tree

public static int treeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // Calculate the depth of the left subtree
        int left = treeDepth(root.left);
        // Calculate the depth of the right subtree
        int right = treeDepth(root.right);
        // Depth of tree root = depth of subtree with longest path + 1
        return left >= right ? (left + 1) : (right + 1);
    }
Copy the code

Dynamic programming

Maximum sum of arrays

Cumulative value: a cumulative value

Maximum: Records the maximum value of the cumulative value

Assuming the array is the largest, add one value at a time. If i-1 is less than 0, add I to the sum, if >0, add I to the sum, and update the maximum if the sum is greater than the maximum.

If the subscript of the largest sum of the array is needed, the subscript of the largest value is recorded

    public static void main(String[] args) {
        int[] array = {1, -2.3.10, -4.7.2, -5};
        Long begintime = System.nanoTime();
        int result =  FindGreatestSumOfSubArray(array);
        Long endtime = System.nanoTime();
        System.out.println("The maximum sum of a continuous subarray is:"+result+", running time:"+(endtime - begintime) + "ns");

    }

    public static int FindGreatestSumOfSubArray(int[] array) {
        int len = array.length;
        if (len == 0) {return 0;
        }
        int[] currentsum = new int[len];
        currentsum[0] = array[0];
        int greatsetsum = array[0];
        System.out.println("Step 1: Summing subarrays and:"+currentsum[0] +", the largest subarray and:+greatsetsum);
        for(int i=1; i<array.length; i++){// The following is the state transition equation for dynamic programming
            if(currentsum[i-1] >0){
                currentsum[i] = currentsum[i-1] + array[i];
            }else{
                currentsum[i] = array[i];
            }
            // Update greatSetSum based on currentSum
            if(currentsum[i] > greatsetsum){
                greatsetsum  = currentsum[i];
            }
            System.out.println("The first"+(i+1) +"Step: summing subarrays and:"+currentsum[i]+", the largest subarray and:+greatsetsum);
        }
        returngreatsetsum; }}Copy the code