概览剑指offer
1.37 字符串的排列1.38 数组中出现次数超过一半的数字1.39 最小的k个数1.40 数据流中的中位数 Android基础
Android消息机制Android事件分发机制 总结
概览剑指offer:字符串的排列、数组中出现次数超过一半的数字、最小的k个数、数据流中的中位数
Android基础:Android消息机制、Android事件分发机制
输入一个字符串,打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。
示例: 输入:s = "abc" 输出:["abc","acb","bac","bca","cab","cba"]
//回溯法 class Solution { List1.38 数组中出现次数超过一半的数字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 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: 输入: [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 { QueueAndroid基础 Android消息机制A,B; 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中使用消息机制,我们首先想到的就是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的各种机制、封装类;先初步理解原理,掌握使用方法,尽量看懂源码。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)