android面试笔记总结(算法篇)

Android面试总结(算法篇)

快速排序

  • 每次取一个基准值,然后每次从基准值左边和右边取值,找到基准值左边比基准值大或等于的值,找到基准值右边比基准值小或等于的值,然后左边和右边的值进行交换
  • 完成上面一趟交换后,基准值左边的再进行循环比较,基准值右边的再循环比较
/**
 * 快速排序
 *
 * @param arr
 * @param L   指向数组第一个元素
 * @param R   指向数组最后一个元素
 */
public static void quickSort(int[] arr, int L, int R) {
    int i = L;
    int j = R;
    //支点以数组的中间的数为准
    int pivot = arr[(L + R) / 2];
    //左右两端进行扫描,只要两端还没有交替,就一直扫描
    while (i <= j) {
        //在左边找比支点大的数
        while (pivot > arr[i])
            i++;
        //在右边找比支点小的数
        while (pivot < arr[j])
            j--;
        //此时已经分别找到了比支点小的数(右边)、比支点大的数(左边),它们进行交换
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
        for (int m = 0; m < arr.length; m++) {
            System.out.print(" " + arr[m]);
        }
        System.out.println("");
    }
    //上面一个while保证了第一趟排序支点的左边比支点小,支点的右边比支点大了。
    //“左边”再做排序,直到左边剩下一个数(递归出口)
    if (L < j)
        quickSort(arr, L, j);
    //“右边”再做排序,直到右边剩下一个数(递归出口)
    if (i < R)
        quickSort(arr, i, R);
}

插入排序

//插入排序
public void insertSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int temp = array[i];//当前的值
        int j = i - 1;//定位到当前索引的前一个
        while (j >= 0 && temp < array[j]) {
            //前面的数比当前值要大,则将前面的值替换给当前值
            array[j + 1] = array[j];
            //位置向前进一位
            j--;
        }
        //将当前值放到最前面的索引
        array[j + 1] = temp;
    }
}

选择排序

  • 第一层循环表示前面的数,后面一层循环表示后面的数
  • 而冒泡排序的第一层循环表示每一轮循环的次数
public static void order() {
    int[] a = {3, 0, 1, 2, 11, 7};
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = i; j < a.length; j++) {
            int temp;
            if (a[i] > a[j]) {
                temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }
    }
    for (int i = 0; i < a.length; i++) {
        System.out.println("result:" + a[i]);
    }
}

冒泡排序

  • 跟选择排序的不同地方是第一层循环表示每一轮循环的次数
public static void sort() {
    int[] a = {3, 0, 1, 2, 11, 7};
    for (int i = 1; i < a.length; i++) {
        for (int j = 0; j < a.length - i; j++) {
            if (a[j] > a[j + 1]) {
                int temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
            }
        }
    }
    for (int i = 0; i < a.length; i++) {
        System.out.println("result:" + a[i]);
    }
}

二分法查找

  • 排序好的数组,找出对应数的位置,没找到的话返回-1
//二分法查找
public  int erfenfa(int[] array, int find) {
    int min = 0;
    int max = array.length - 1;
    int result = -1;
    while (min <= max) {
        int temp = (max + min) / 2;
        //如果要找的数比中间值小,则将最大的索引向左移一位
        //,否则将最小的索引向右移一位
        if (find < array[temp]) {
            max = temp - 1;
        } else if (find > array[temp]) {
            min = temp + 1;
        } else {
            result = temp;
            break;
        }
    }
    return result;
}

两个栈实现队列

  • 栈的规则是先进后出,后进先出,队列是先进先出,后进后出
public class StackQueue {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    public void push(int node){
        //实现队列的push直接将元素放到第一个栈中
        stack1.push(node);
    }
    public int pop(){
        //如果第2个栈是空的,需要将第一个栈的数据依次取出来
        if(stack2.empty()){
            //直到第一个栈中的数据取完了
            while(!stack1.empty())
                stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
}

链表常见题

  • 常见题型有链表翻转、求倒数第k个节点、判断是不是环形链表、链表部分翻转、链表合并、链表排序等。
  • 链表有一个next指向下一个指针,如果next=null说明到了链表的结束位置,环链表除外,后面题型会涉及到环形链表
public static class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}

翻转链表

//链表翻转,思想是定义一个节点,然后节点的pre指向了节点的next
//1->2->3->4->5
//5->4->3->2->1
public  ListNode revertListNode(ListNode listNode) {
    ListNode preNode = null;
    ListNode nextNode;
    while (listNode != null) {
        //先取出next,后面放到listNode的时候用
        nextNode = listNode.next;
        //preNode指向next节点
        listNode.next = preNode;
        //将当前节点给到pre,下次判断节点的时候用得到
        preNode = listNode;
        listNode = nextNode;
    }
    return preNode;
}

求链表中倒数第k个结点

/**
 * 输入一个链表,输出该链表中倒数第k个结点。
 *
 * @param head
 * @param k
 * @return
 */
public static ListNode FindKthToTail(ListNode head, int k) {
    ListNode second = head;
    ListNode first = head;
    //双指针的思想,让第一个指针先走,走到第k个结点后,第二个指针也跟着走,
    // 当第一个节点走到最后的时候,第二个节点位置就是倒数第k个结点的位置
    for (int i = 0; i < k; i++) {
        first = first.next;
    }
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    return second;
}

判断一个链表是否有环

/**
 * 判断一个链表是不是环形链表
 * 定义个块的指针和慢的指针,如果两个再次相遇说明是环形链表
 * @param head
 * @return
 */
private boolean isLoop(ListNode head) {
    //定义快慢指针
    ListNode fast = head.next;
    ListNode slow = head.next;
    while(fast != null && slow != null && fast.next != null) {
            //快指针每次走两步,慢指针每次走一步
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                //如果再次相遇,则说明有环,返回true
                return true;
            }
        }
    }
    return false;
}

每k位进行翻转链表

  • 每k位翻转链表是在整个链表翻转的基础上演变而来的,它是先将链表分成每k个来进行翻转,然后将当前翻转的结果给上一次翻转结果的最后一个指针
public static ListNode reverse(ListNode head, int k) {
    ListNode current = head;
    ListNode next = null;
    ListNode prev = null;
    int count = 0;
     //翻转的条件
    while (current != null && count < k) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
        count++;
    }
    //如果后面还有元素,则递归翻转
    if (next != null) {
          //将下一次翻转的结果给当前最后一个元素的next位置
        head.next = reverse(next, k);
    }
    return prev;
}

二叉树常见题

  • 二叉树常见题型有二叉树深度计算、二叉树的镜像二叉树、根据二叉树的前序遍历、和中序遍历顺序求出二叉树结构。
  • 二叉树有一个左子节点和右子节点。
public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}

求二叉树的深度

public static int TreeDepth(TreeNode root) {
    //如果当前节点为空,说明已经到底了
    if (root == null)
        return 0;
    //递归调用深度左右子树的深度
    int left = TreeDepth(root.left);
    int right = TreeDepth(root.right);
    //取左右子树大的深度值
    return left > right ? left + 1 : right + 1;//每次将调用次数加1
}

输入两棵二叉树A,B,判断B是不是A的子结构

public boolean HasSubtree(TreeNode root1,TreeNode root2) {
 boolean result = false;
    //如果两个树都不为空才会走这里
    if (root2 != null && root1 != null) {
        //如果根的值相等
        if (root1.val == root2.val) {
            //找左右子树是否相等
            result = doesTree1HaveTree2(root1, root2);
        }
        //如果上面分析的结果是不相等,继续判断A树左节点和B树或A右节点和B树
        if (!result)
            return HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }
    return result;
}

public boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {
    //如果右边的树为空直接说明相等
    if (node2 == null) {
        return true;
    }
    //如果左边的树为空直接返回不相等,说明不包含
    if (node1 == null) {
        return false;
    }
    //如果两个值也不相等,说明也是不相等的
    if (node1.val != node2.val) {
        return false;
    }
    //继续递归调用对应的左右子树
    return doesTree1HaveTree2(node1.left, node2.left) &&
            doesTree1HaveTree2(node1.right, node2.right);
}

求二叉树的镜像二叉树

  • 镜像二叉树是将二叉树在左右方向上旋转下,左边的节点到右边、右边的节点到左边,形如下面:
image.png
  • 思路:左右节点进行颠倒,然后递归调用下一个左、右子节点
/**
 * 转成镜像二叉树
 *
 * @param root
 */
public void Mirror(TreeNode root) {
    if (root != null) {
        TreeNode left = root.left;
        TreeNode right = root.right;
        TreeNode temp = left;
        root.left = right;
        root.right = temp;
        Mirror(left);
        Mirror(right);
    }
}

根据二叉树的前序遍历、和中序遍历顺序求出二叉树结构。

  • 树的前序遍历:先是根节点、再到左子节点、再到右子节点
  • 树的中序遍历:先是左子节点、再到根节点、再到右子节点
    剑指offer上面一道题,已知前序遍历结果是{1,2,4,7,3,5,6,8},中序遍历结果是{4,7,2,1,5,3,8,6},求该二叉树的结构。
  • 分析:前序遍历第一个节点根节点、然后去中序遍历里面找根节点左边是左子节点、根节点右边的都是右子节点部分,所以我们能确定1是根节点,4、7、2是1的左子节点部分,5、3、8、6是1的右子节点,然后在4、7、2里面继续通过前序遍历的2是首位,能确定2是左子节点,4、7是2的左子节点部分,依次类推,所以有如下结果:


    image.png
/**
 * pre前序的结果:根左右
 * in后序的结果:左根右
 * pre:{1,2,4,7,3,5,6,8}
 * in:{4,7,2,1,5,3,8,6}
 *
 * @param pre
 * @param in
 * @return
 */
public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    TreeNode root = new TreeNode(pre[0]);
    for (int i = 0; i < pre.length; i++) {
        if (pre[0] == in[i]) {
            root.left = reConstructBinaryTree(
                    Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
            root.right = reConstructBinaryTree(
                    Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
        }
    }
    return root;
}

找出一个无序数组中出现超过一半次数的数字

/**
 * 计算数组里面超过一半的数字,如果没有这样的数字,则返回0
 * 先把数组排序,如果有超过一半的数字,则中间位置的数字一定是该数字
 * 然后通过出现该数的次数来判断是否超过一半
 *
 * @param array
 * @return
 */
public static int MoreThanHalfNum_Solution(int[] array) {
    Arrays.sort(array);
    int temp = array[array.length / 2];
    int num = 0;
    for (int i = 0; i < array.length; i++) {
        if (temp == array[i]) {
            num++;
        }
    }
    if (num <= array.length / 2) {
        temp = 0;
    }
    return temp;
}

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

public boolean Find(int target, int [][] array) {
    int row=0;
    int column=array[0].length-1;
    while(row<array.length&&column>=0){
        if(array[row][column]==target){
            return true;
        }
        if(array[row][column]>target){
            column--;
        }else{
            row++;
        }
    }
    return false;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,324评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,303评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,192评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,555评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,569评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,566评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,927评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,583评论 0 257
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,827评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,590评论 2 320
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,669评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,365评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,941评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,928评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,159评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,880评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,399评论 2 342