[移动开发]【Android春招每日一练】（十） 剑指4题+Android基础

概览

剑指offer：字符串的排列、数组中出现次数超过一半的数字、最小的k个数、数据流中的中位数
Android基础：Android消息机制、Android事件分发机制

剑指offer

1.37 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

//回溯法
class Solution {
    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x) {
        if(x == c.length - 1) {
            res.add(String.valueOf(c));      // 添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++) {
            if(set.contains(c[i])) continue; // 重复，因此剪枝
            set.add(c[i]);
            swap(i, x);                      // 交换，将 c[i] 固定在第 x 位
            dfs(x + 1);                      // 开启固定第 x + 1 位字符
            swap(i, x);                      // 恢复交换
        }
    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}

1.38 数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

//摩尔投票法

class Solution {
    public int majorityElement(int[] nums) {
        int votes = 0,x = 0;
        for(int e:nums){
            if(votes == 0) x = e;
            if(e == x) votes++;
            else votes--;
        }
        return x;
    }
}
//如果给出数组不一定存在多数元素，需要再遍历数组，记录x的次数与数组长度一半比较。

1.39 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]

//基于快排的思想
//考虑在每次哨兵划分后，判断基准数在数组中的索引是否等于k ，若true则直接返回此时数组的前k个数字即可。
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k >= arr.length) return arr;
        return quickSort(arr,k,0,arr.length-1);
    }

    int[] quickSort(int[] arr,int k,int l,int r){
        int i = l,j = r;
        while(i < j){
            while(i < j && arr[j] >= arr[l]) j--;
            while(i < j && arr[i] <= arr[l]) i++;
            swap(arr,i,j);
        }
        swap(arr,i,l);
        if (i > k) return quickSort(arr, k, l, i - 1);
        if (i < k) return quickSort(arr, k, i + 1, r);
        return Arrays.copyOf(arr, k); 
    }

    void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

1.40 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值

//堆
//设置大顶堆和小顶堆，每次依次加入堆中，数据流为奇数时，中位数为小顶堆堆顶，否则两个堆顶平均数。
class MedianFinder {
    Queue<Integer> A,B;
    /** initialize your data structure here. */
    public MedianFinder() {
        A = new PriorityQueue<>();                   // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
    }
    
    public void addNum(int num) {
        if(A.size() != B.size()){
            A.add(num);				//循环加入，保证大顶堆中数小于小顶堆中数
            B.add(A.poll());
        }else{
            B.add(num);
            A.add(B.poll());
        } 
    }
    
    public double findMedian() {
        return A.size() == B.size() ? (A.peek()+B.peek())/2.0 : A.peek();
    }
}

Android基础

Android消息机制

在Android中使用消息机制，我们首先想到的就是Handler。Handler是Android消息机制的上层接口。Handler的使用过程很简单，通过它可以轻松地将一个任务切换到Handler所在的线程中去执行。通常情况下，Handler的使用场景就是更新UI。

消息机制的模型

消息机制主要包含：MessageQueue，Handler和Looper这三大部分，以及Message；

Message：需要传递的消息，可以传递数据；

MessageQueue：消息队列，但是它的内部实现并不是用的队列，实际上是通过一个单链表的数据结构来维护消息列表，因为单链表在插入和删除上比较有优势。主要功能向消息池投递消息(MessageQueue.enqueueMessage)和取走消息池消息 (MessageQueue.next)；

Handler：消息辅助类，主要功能向消息池发送各种消息事件(Handler.sendMessage)和处理相应消息事件(Handler.handleMessage)；

Looper：不断循环执行(Looper.loop)，从MessageQueue中读取消息，按分发机制将消息分发给目标处理者。

MessageQueue，Handler和Looper三者之间的关系：每个线程中只能存在一个Looper，Looper是保存在ThreadLocal中的。主线程（UI线程）已经创建了一个Looper，所以在主线程中不需要再创建Looper，但是在其他线程中需要创建Looper。每个线程中可以有多个Handler，即一个Looper可以处理来自多个Handler的消息。 Looper中维护一个MessageQueue，来维护消息队列，消息队列中的Message可以来自不同的Handler。

原理

Looper：

loop()进入循环模式，不断重复下面的操作，直到消息为空时退出循环:读取MessageQueue的下一条Message（关于next()，后面详细介绍）；把Message分发给相应的target。当**next()**取出下一条消息时，队列中已经没有消息时，next()会无限循环，产生阻塞。等待MessageQueue中加入消息，然后重新唤醒。

Handler：

对于Handler的无参构造方法，默认采用当前线程TLS中的Looper对象，并且callback回调方法为null，且消息为同步处理方式。只要执行 的 Looper.prepare() 方法，那么便可以获取有效的Looper对象。

发送消息：

发送消息有几种方式，但是归根结底都是调用了 sendMessageAtTime() 方法。在子线程中通过Handler的post()方式或send()方式发送消息，最终都是调用了 sendMessageAtTime() 方法。

sendMessageAtTime()方法的作用很简单，就是调用MessageQueue的enqueueMessage()方法，往消息队列中添加一个消息。

MessageQueue是按照Message触发时间的先后顺序排列的，队头的消息是将要最早触发的消息。当有消息需要加入消息队列时，会从队列头开始遍历，直到找到消息应该插入的合适位置，以保证所有消息的时间顺序。

获取消息 ：

当发送了消息后，在MessageQueue维护了消息队列，然后在Looper中通过 loop() 方法，不断地获取消息。上面对 loop() 方法进行了介绍，其中最重要的是调用了 queue.next() 方法,通过该方法来提取下一条信息

next() 方法根据消息的触发时间，获取下一条需要执行的消息,队列中消息为空时，则会进行阻塞操作。

分发消息 ：

在loop()方法中，获取到下一条消息后，执行 msg.target.dispatchMessage(msg) ，来分发消息到目标Handler对象。

当Message的 msg.callback 不为空时，则回调方法 msg.callback.run() ;

当Handler的 mCallback 不为空时，则回调方法 mCallback.handleMessage(msg) ；

最后调用Handler自身的回调方法 handleMessage() ，该方法默认为空，Handler子类通过覆写该方法来完成具体的逻辑。

总结：

发送message时，message中含有当前handler的引用，将message加入MessageQueue，Looper循环取出头message，通过查看message中目标handler的引用来回调handler的handleMessage()方法来接收消息；

Handler负责发送消息和处理消息的，Looper负责接收Handler发送的消息，并直接把消息回传给Handler自己（handleMessage），MessageQueue就是一个存储消息的容器是单向链表表结构，（单项链表的增删比队列要有优势）。

Android事件分发机制

总结

1.开始了解Android的各种机制、封装类；先初步理解原理，掌握使用方法，尽量看懂源码。