算法题

我就是我 2022-06-10 07:19 158阅读 0赞

上学时学过的算法，青山遮不住，毕竟东流去，都忘得差不多了。。。。

题目1：使用一个数组实现一个循环队列

分析：简单来讲就是用一个数组，实现个队列的功能，可以用两个脚标来控制队列的头和尾，尾部插入和头部移出，并且分别将脚标后移即可，超出数组长度回到头部，同时注意一下控制数组的容量，超过不让往里存，同样，全部移除后，不能往外取，

package com.xue.qin.mpplication;
    
    import android.util.Log;
    
    /**
     * Created by xue.qin on 2017/8/11.
     */
    
    public class QueueArray {
        private static final String TAG = "QueueArray";
        int[] data;
        int maxSize;
        //队尾的脚标
        int rare = 0;
        //队首的脚标
        int front = 0;
    
        int size = 0;
    
        public QueueArray(int size) {
            //初始化最大容量
            maxSize = size;
            data = new int[size];
        }
    
        public void push(int item) {
            //超出最大容量，不让存
            if (size == maxSize) {
                Log.i(TAG, "reach maxSize");
                return;
            }
            //如果存到数组末尾了，就到数组的回到数组头部存
            if (rare == maxSize) {
                rare = 0;
            }
            //存一个，就将队尾向后移动一个
            data[rare++] = item;
            //容量增加1
            size++;
        }
    
        public int pop() {
            //如果数组中没有元素了，就不能够出对了
            if(size == 0){
                Log.i(TAG, "no more items");
                return 0;
            }
            //弹出到末尾的时候，回到数组头部弹出
            if (front == maxSize) {
                front = 0;
            }
            //容量减1
            size--;
            //队首递增//弹出后此素组位置为-1，对象的话设为null，
            int index = front++;
            int temp = data[index];
            data[index] = -1;
            return temp;
        }
    }

题目2：二叉树的遍历递归，非递归

分析：二叉树遍历

package qin.xue.com.myretrofit;
    
    /**
     * Created by xue.qin on 2017/8/9.
     */
    
    import android.util.Log;
    
    import java.util.LinkedList;
    import java.util.Stack;
    
    /**
     * 功能：把一个数组的值存入二叉树中，然后进行3种方式的遍历
     * <p>
     * 参考资料0:数据结构(C语言版)严蔚敏
     * <p>
     * 参考资料1：http://zhidao.baidu.com/question/81938912.html
     * <p>
     * 参考资料2：http://cslibrary.stanford.edu/110/BinaryTrees.html#java
     *
     * @author ocaicai@yeah.net @date: 2011-5-17
     */
    public class BinTreeTraverse2 {
        private static final String TAG = "BinTreeTraverse2";
    
        private static class Node {
            Node leftChild;
            Node rightChild;
            int data;
    
            Node(int newData) {
                leftChild = null;
                rightChild = null;
                data = newData;
            }
        }
    
        public Node createBinTree() {
            Node node1 = new Node(1);
            Node node2 = new Node(2);
            Node node3 = new Node(3);
            Node node4 = new Node(4);
            Node node5 = new Node(5);
            Node node6 = new Node(6);
            Node node7 = new Node(7);
            node1.leftChild = node2;
            node1.rightChild = node3;
            node2.leftChild = node4;
            node2.rightChild = node5;
            node3.leftChild = node6;
            node3.rightChild = node7;
            return node1;
        }
    
        //先序递归方式
        public static void preOrderTraverse(Node node) {
            if (node != null) {
                //访问父节点
                visit(node);
                //递归访问左孩子
                preOrderTraverse(node.leftChild);
                //递归访问右孩子
                preOrderTraverse(node.rightChild);
            }
        }
    
        //中序递归方式
        public static void inOrderTraverse(Node node) {
            if (node != null) {
                //递归访问左孩子
                inOrderTraverse(node.leftChild);
                //访问父节点
                visit(node);
                //递归访问右孩子
                inOrderTraverse(node.rightChild);
            }
        }
    
        //后序递归方式
        public static void postOrderTraverse(Node node) {
            if (node != null) {
                //递归访问左孩子
                postOrderTraverse(node.leftChild);
                //递归访问右孩子
                postOrderTraverse(node.rightChild);
                //访问父节点
                visit(node);
            }
        }
    
    
        //先序不递归
        public static void preOrderNoTraverse(Node node) {
            //栈（先进后出）
            Stack<Node> stack = new Stack<>();
            //首先判断一下根节点是不是null，不是null才能压栈
            if (node != null) {
                stack.push(node);
            }
            //循环是一个出栈压栈的过程
            //先序：先父节点（出栈），之后左孩子（后压入），最后右孩子(先压入）
            while (!stack.empty()) {
                Node p = stack.pop();
                visit(p);
                if (p.rightChild != null) {
                    stack.push(p.rightChild);
                }
                if (p.leftChild != null) {
                    stack.push(p.leftChild);
                }
            }
        }
    
    
        //中序不递归
        //中序：左孩子，父节点，右孩子
        public static void inOrderNoTraverse(Node p) {
            Stack<Node> stack = new Stack<Node>();
            while (p != null) {
                while (p != null) {
                    if (p.rightChild != null)
                        stack.push(p.rightChild);
                    stack.push(p);
                    p = p.leftChild;
                }
    
                p = stack.pop();
    
                while (!stack.empty() && p.rightChild == null) {
                    visit(p);
                    p = stack.pop();
                }
                Log.i(TAG, "1 first while = " + p.data);
                visit(p);
                if (!stack.empty())
                    p = stack.pop();
                else
                    p = null;
            }
        }
    
        protected static void postOrderNoTraverse(Node p) {
            Node q = p;
            Stack<Node> stack = new Stack<Node>();
            while (p != null) {
                // 左子树入栈
                for (; p.leftChild != null; p = p.leftChild)
                    stack.push(p);
                // 当前节点无右子或右子已经输出
                while (p != null && (p.rightChild == null || p.rightChild == q)) {
                    visit(p);
                    q = p;// 记录上一个已输出节点
                    if (stack.empty())
                        return;
                    p = stack.pop();
                }
                // 处理右子
                stack.push(p);
                p = p.rightChild;
            }
        }
    
        //层级遍历二叉树
        public static void levelReadNoTraverse(Node root) {
            if (root == null) {
                return;
            }
            LinkedList<Node> queue = new LinkedList<>();
            queue.add(root);
            while (queue.size() != 0) {
                int len = queue.size();
                for (int i = 0; i < len; i++) {
                    Node temp = queue.poll();
                    visit(temp);
                    if (temp.leftChild != null) {
                        queue.add(temp.leftChild);
                    }
                    if (temp.rightChild != null) {
                        queue.add(temp.rightChild);
                    }
                }
            }
        }
    
        //访问节点
        private static void visit(Node node) {
            Log.i(TAG, "node = " + node.data);
        }
    
        public static void testBinTree() {
            BinTreeTraverse2 binTree = new BinTreeTraverse2();
            Node root = binTree.createBinTree();
            Log.i(TAG, "先序遍历(递归）：");
            preOrderTraverse(root);
            Log.i(TAG, "先序遍历(非递归）：");
            preOrderNoTraverse(root);
    
            Log.i(TAG, "中序遍历(递归）：");
            inOrderTraverse(root);
            Log.i(TAG, "中序遍历(非递归）：");
            inOrderNoTraverse(root);
    //
            Log.i(TAG, "后序遍历(递归）：");
            postOrderTraverse(root);
            Log.i(TAG, "后序遍历(非递归）：");
            postOrderNoTraverse(root);
            
            Log.i(TAG, "层级遍历(非递归）：");
            levelReadNoTraverse(root);
        }
    }

题目3 二分查找

private void quickFind(int target, int[] array, int a, int b) {
            Log.i("Solution", "a = " + a + " b =" + b);
            if (a <= b) {
                int mid = (a + b) / 2;
                if (target == array[mid]) {
                    Log.i("Solution", "mid = " + mid);
                    result = true;
                } else if (target > array[mid]) {
                    quickFind(target, array, mid + 1, b);
                } else if (target < array[mid]) {
                    quickFind(target, array, a, mid - 1);
                }
            } else {
                return;
            }
        }

题目4 跳台阶， 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法

分析:

1、每一次跳要么1阶要么2阶，这就有两种方式

2、最后是1的话只能跳一阶，最后是2的话能有两种选择方式（两个一阶，或者1个2阶）

public int JumpFloor(int target) {
    	if (target <= 0) {
                return -1;
            } else if (target == 1) {
                return 1;
            } else if (target ==2) {
                return 2;
            } else {
                return  JumpFloor(target-1)+JumpFloor(target-2);
            }        
        }

题目5 斐波那契额数列

public int Fibonacci(int n) {
            if(n==1 || n==2){
                return 1;
            }
            if(n<3||n>39){
                return 0;
            }
            return Fibonacci(n-1)+Fibonacci(n-2);
        }

题目6 翻转链表

分析：链表头节点不用动，将后面的节点一次提到此链表头节点。

public ListNode reverseList(ListNode head) {
            ListNode head2 = head;
            while (head.next != null) {
                //移除紧跟head的节点
                ListNode temp = head.next;
                head.next = temp.next;
                temp.next = head2;
                head2 = temp;
            }
            return head2;
        }

分析链表尾节点不动，依次将前面的节点提取到后面。

//向尾节点插入
        public ListNode reverseList2(ListNode head) {
            if (head == null || head.next == null)
                return head;
            ListNode prev = reverseList2(head.next);//找到最后一个节点为头结点·
            head.next.next = head;
            head.next = null;
            return prev;
        }

题目7 最大公约数最小公倍数

public static int maxCommonDivisor(int m, int n) {
            if (m < n) {// 保证m>n,若m<n,则进行数据交换
                int temp = m;
                m = n;
                n = temp;
            }
            if (m % n == 0) {// 若余数为0,返回最大公约数
                return n;
            } else { // 否则,进行递归,把n赋给m,把余数赋给n
                return maxCommonDivisor(n, m % n);
            }
        }
    
    
    
        //最小公倍数
        public int getMinMultiple()
        {
            int i = 1;
            while(true)
            {
                //n最小的倍数可以把m整除
                if((n*i)%m==0)
                {
                    MinMultiple = n*i;
                    break;
                }
                i++;
            }
            return  MinMultiple;
        }

题目 8 快速排序

public void sortQuickly(int[] arr, int low, int hight) {
            int l = low;
            int h = hight;
            int p = arr[l];
    
            if (l > h) {
                return;
            }
            while (l < h && arr[h] > p) {
                h--;
            }
            if (l < h) {
                int temp = arr[l];
                arr[l] = arr[h];
                arr[h] = temp;
                l++;
            }
            Log.i(TAG,"l = "+l+"h = "+h);
            while (l < h && arr[l] < p) {
                l++;
            }
            if (l < h) {
                int temp = arr[l];
                arr[l] = arr[h];
                arr[h] = temp;
                h--;
            }
            Log.i(TAG,"l = "+l+"h = "+h);
            if (l <= h && low < l) {
                sortQuickly(arr, low, l-1);
            }
            if (l <= h && h < hight) {
                sortQuickly(arr, h+1, hight);
            }
        }