[toc]
ConstrainLayout
https://onlyloveyd.blog.csdn.net/article/details/82915303
https://blog.csdn.net/shulianghan/article/details/97246870
约束布局 如何使用 有何优势呢?
我的小站∎
Keep and carry on.
post @ 2020-01-12
[toc]
进入Dalvik虚拟机
虚拟机特点
优点
- 体积小,占用内存小
- 专有dex(Dalvik executable file)体积更小,执行速度更快
- 常量池采用32位索引值,寻址类方法名,字段名,常量更快
- 基于寄存器架构,并拥有一套完整的指令系统
- 提供了对象生命周期管理,堆栈管理 ,线程管理,安全和异常管理以及垃圾回收等重要功能
- 所有Android程序都运行在Android系统进程里, 每个进程对应一个Dalvik虚拟机
与Java虚拟机区别
Java 字节码 ,Dalvik字节码
post @ 2020-01-11
[toc]
post @ 2019-11-25
内联函数在Java中的应用
post @ 2019-11-14
post @ 2019-11-13
post @ 2019-11-09
post @ 2019-10-16
树
树的基本概念
节点, 根, 兄弟节点,父子节点, 深度, 路径, 高度 ,边
二叉树
二叉树的概念
表达式树 (使用栈构造表达式树)
二叉查找树
对于树中的每一个节点X, 它的左子树中所有项的值小于X中的项, 右子树中的所有值大于X中的项目; 这意味着这种树可以用某一种方式排序
平衡二叉查找树
对于树中的每一个节点, 左子树和右子树的高度差小于等于1.
伸展树
不记录高度, 每次查找一个元素的时候, 都将这个元素通过一系列的旋转操作移动到根部(如果一个元素被访问了, 那么下次被访问的可能性会变大)
摊还时间复杂度O(M*LgN) M此操作的时间复杂度.
再谈树的遍历
- 前序. 中序. 后续遍历
- 层序遍历
//使用队列(或者表)装载每层的元素, 每次出队一个元素,把该元素的下一层子节点全部入队(每层全部出队后, 下一层的子节点也已经入队了.)
public void printTreeWithLevel(TreeNode root) {
List list = new LinkedList();
TreeNode curNode = null;
list.add(root);
while(!list.isEmpty) {
curNode = list.remove();
System.out.println("data = " + curNode.data);
if(curNode.left != null) {
list.add(curNode.left);
}
if(curNode.right != null) {
list.add(curNode.right);
}
}
}
B树
TreeSet和TreeMap类的实现, 将在12章红黑树中
post @ 2019-10-10
栈
栈的实现其实有两种, 一种是使用Vector实现的, 一种是使用队列行数据结构实现的具体参考一下两种方式
实现方式1 线程安全的
写在前面, 在讲栈之前, 先要讲一下Vector, Vector其实是类似于ArrayList的, 其内部本身实现的方式也是使用数组存放元素,其与ArrayList不同之处在于, Vector对数组的操作是同步的, 其是一个线程安全的集合类.(方法是synchronized)
整体的代码非常简单, 注意这个栈的操作也是线程安全的
public
class Stack<E> extends Vector<E> {
/**
* Creates an empty Stack.
*/
public Stack() {
}
/**
* Pushes an item onto the top of this stack. This has exactly
* the same effect as:
* <blockquote><pre>
* addElement(item)</pre></blockquote>
*
* @param item the item to be pushed onto this stack.
* @return the <code>item</code> argument.
* @see java.util.Vector#addElement
*/
public E push(E item) {
addElement(item);
return item;
}
/**
* Removes the object at the top of this stack and returns that
* object as the value of this function.
*
* @return The object at the top of this stack (the last item
* of the <tt>Vector</tt> object).
栈顶是数组的末尾.
* @throws EmptyStackException if this stack is empty.
*/
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
/**
* Looks at the object at the top of this stack without removing it
* from the stack.
*
* @return the object at the top of this stack (the last item
* of the <tt>Vector</tt> object).
* @throws EmptyStackException if this stack is empty.
*/
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
/**
* Tests if this stack is empty.
*
* @return <code>true</code> if and only if this stack contains
* no items; <code>false</code> otherwise.
*/
public boolean empty() {
return size() == 0;
}
/**
* Returns the 1-based position where an object is on this stack.
* If the object <tt>o</tt> occurs as an item in this stack, this
* method returns the distance from the top of the stack of the
* occurrence nearest the top of the stack; the topmost item on the
* stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
* method is used to compare <tt>o</tt> to the
* items in this stack.
*
* @param o the desired object.
* @return the 1-based position from the top of the stack where
* the object is located; the return value <code>-1</code>
* indicates that the object is not on the stack.
*/
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = 1224463164541339165L;
}
实现方式2 非线程安全
我们在上一个文章中详细说明了LinkedList, 其实LinkedList也是可以做为栈使用的.参考一片文章Java 集合源码剖析, ArrayDeque和LinkedList是Deque的两个通用实现，由于官方更推荐使用AarryDeque用作栈和队列.
从名字可以看出ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组（circular array），也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是非线程安全的（not thread-safe），当多个线程同时使用的时候，需要程序员手动同步；另外，该容器不允许放入null元素。
public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable{}
可以直接参考一下Java 集合源码剖析无非就是对数组两端的增删改查, 特殊的在于ArrayDeque实现的是循环数组.
非常经典的一个方法
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
head = (head - 1) & (elements.length - 1), 这一句由于elements.length 始终是2的整数倍, 且是int类型因此
elements.length -1 的二进制应该是
0 xxxxxxxx 1111(初始化是16 0-15)
因此首次head -1 = -1 (1的反码+1 就是-1)
因该是(补码)
111111111111111
与上面的按位与被置为整数15 (保留低位4位)
下一次
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
post @ 2019-10-10
主要是一些习题吧, 队列也是比较简单的数据结构, 主要体现在应用上.
习题
单链表的反转
fun <E> Node<E>.printList() { var r: Node<E>? = this while (r?.next != null) { println(r.item) r = r.next } } fun <E> revserSingleOriententList(head: Node<E>?) { var newHead = Node<E>(null, null, null) var cur = head while (cur != null) { var temp = cur.next cur.next = newHead newHead = cur cur = temp } newHead.printList() } fun test() { val head: Node<Int>? = Node(0, null, null) var x = head for (i in 1..9) { x?.next = Node(i, null, null) x = x?.next } revserSingleOriententList(head) }判断链表是否带环；若带环，求环的长度和入口点
实现思路：设置两个快慢指针分别指向链表的头节点，快指针一次走两步，慢指针一次走一步，如果两个相遇了，则单链表带环，如果快指针走到NULL节点，则链表不带环；
实现思路：在判断单链表是否带环的问题中，我们找到了单环单链表的相遇结点，用于个指针从单链表的相遇结点开始走，并且设置一个计数器，每走一步，计数器加一，直到该指针再次遇到相遇点，则返回计数器的数；
遍历一次，找到中间节点; 快慢指针, 快的是慢的两倍.
遍历一次，找到倒数第 k 个结点（k从1开始）原理同上.
- 先让快指针走k-1步,然后两个指针一起走,直到快指针指向null了,此时慢指针指向倒数第k个节点.
遍历一次，删除倒数第 k 个结点（k从1开始），不能用替换删除法
- 找到倒数第k-1个节点, 即k的前一个节点, 让next节点指向k个节点的next即可
约瑟夫环 已经解决
单链表冒泡排序
找到单链表尾部, 尾部向前移动, 尾部始终是排好序的.
实现
//单链表的冒泡排序 fun <E: Comparable<E>> bubbleSort(head: Node<E>?): Node<E>? { val pHead = head; var tail: Node<E>? = pHead var p: Node<E>? = pHead var prev: Node<E>? = p while (tail?.next != null) tail = tail.next while (tail != pHead) { while (p != tail) { if (p?.item != null && p.next?.item != null){ if (p.item!! > p.next!!.item!!){ val temp = p.item p.item = p.next!!.item p.next!!.item = temp } prev = p p = p.next } } tail = prev p = pHead } return head
合并两个有序链表 同交集并集
判断两个链表是否相交;相交则求交点(链表不带环)
先判断有无环, 如果一个有一个没有,则肯定不会相交
如果两个链表都没有环, 那么两个链表的尾结点肯定是交点
如果两个链表都有环 如果两个链表h1,h2都有环，则可以找到两个链表上并且在环上的任何一个结点p1和p2。如果从结点p1开始遍历链表h1，能够遍历到p2，说明两个链表相交；否则从p1开始遍历h1，遍历一圈后又回到p1，而未遍历到p2，说明两个链表不相交。
链表的交集, 并集等.