[toc]
ConstrainLayout
https://onlyloveyd.blog.csdn.net/article/details/82915303
https://blog.csdn.net/shulianghan/article/details/97246870
约束布局 如何使用 有何优势呢?
[toc]
https://onlyloveyd.blog.csdn.net/article/details/82915303
https://blog.csdn.net/shulianghan/article/details/97246870
约束布局 如何使用 有何优势呢?
[toc]
Java 字节码 ,Dalvik字节码
[toc]
内联函数在Java中的应用
节点, 根, 兄弟节点,父子节点, 深度, 路径, 高度 ,边
二叉树的概念
表达式树 (使用栈构造表达式树)
对于树中的每一个节点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);
}
}
}
栈的实现其实有两种, 一种是使用Vector实现的, 一种是使用队列行数据结构实现的具体参考一下两种方式
写在前面, 在讲栈之前, 先要讲一下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;
}
我们在上一个文章中详细说明了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();
}
主要是一些习题吧, 队列也是比较简单的数据结构, 主要体现在应用上.
单链表的反转
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 个结点(k从1开始),不能用替换删除法
约瑟夫环 已经解决
单链表冒泡排序
找到单链表尾部, 尾部向前移动, 尾部始终是排好序的.
实现
//单链表的冒泡排序
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,说明两个链表不相交。
链表的交集, 并集等.