赞
踩
迭代器:iterator listiterator 工具类:Arrays Collections 比较器Comparable Comparator
使用集合框架 便于高效快速的写出代码
//不可以new T类型的数组 //基本类型不可以作为泛型参数 class arrayT <T>{ public T[]elem; public int size; public arrayT(){ this.elem=(T[])new Object[]; } public void add(T val){ this.elem[this.size]=val; this.size++; } public T getVal(int index) { return this.elem[index]; } } public class Main{ public static void main(String[] args) { arrayT<String>arrayT1=new arrayT<>(); arrayT1.add("daf");//指定的时候添加就会进行对比 arrayT<Integer>arrayT2=new arrayT<>(); arrayT2.add(66); arrayT2.getVal(1); } }
泛型:只存在编译期间
擦出机制:在编译的时候将T类型擦除为Object
<>中的类型不参与类型组成 编译的时候进行擦除 不存在运行的时候
解决基本的类型转换
Integer a=10; //自动装箱
Integer b=Integer.valueof(i);
Integer a=100;
Integer b=100;
Integer c=200;
Integer d=200;
System.out.println(a==b);//true
System.out.println(c==d);//false
//cache里面只有127
Integer a=129;
int b=a;//自动拆箱
boolean add(E e) 尾插 e
void add(int index, E element) 将 e 插入到 index 位置
boolean addAll(Collection c) 尾插 c 中的元素
E remove(int index) 删除 index 位置元素
boolean remove(Object o) 删除遇到的第一个 o
E get(int index) 获取下标 index 位置元素
E set(int index, E element) 将下标 index 位置元素设置为 element
void clear() 清空
boolean contains(Object o) 判断 o 是否在线性表中
int indexOf(Object o) 返回第一个 o 所在下标
int lastIndexOf(Object o) 返回最后一个 o 的下标
List subList(int fromIndex, int toIndex) 截取部分 list (浅拷贝)前闭后开
ArrayList 在new的时候长度为0 在添加的时候才会为10 之后1.5倍扩容
Linkedlist 双向链表 默认尾插法
//扑克牌游戏 package demo; import java.util.ArrayList; import java.util.List; import java.util.Random; class Card { public String suit;//花色 public int rank;//数字 public Card(String suit, int rank) { this.suit = suit; this.rank = rank; } @Override public String toString() { /* return "Card{" + "suit='" + suit + '\'' + ", rank=" + rank + '}';*/ return suit+" "+rank+" "; } } public class TestCard { public static final String[] suits ={"♥","♠","♦","♣"}; public static List<Card> buyCard () { List<Card> list = new ArrayList<>(); for (int i = 0; i < 4; i++) { for (int j = 1; j <= 13; j++) { /* String suit = suits[i]; int rank = j; Card card = new Card(suit,j); list.add(card);*/ list.add(new Card(suits[i],j)); } } return list; } public static void swap(List<Card> cardList,int i,int j) { Card tmp = cardList.get(i); cardList.set(i,cardList.get(j)); cardList.set(j,tmp); } public static void shuffle(List<Card> cardList) { Random random = new Random(); int i = cardList.size()-1; for (; i > 0 ; i--) { int randIndex = random.nextInt(i); swap(cardList,i,randIndex); } } public static void main(String[] args) { List<Card> list = buyCard(); System.out.println(list); System.out.println("洗牌:"); shuffle(list); System.out.println(list); System.out.println("揭牌:"); List<List<Card>> hand = new ArrayList<>(); List<Card> hands1 = new ArrayList<>(); List<Card> hands2 = new ArrayList<>(); List<Card> hands3 = new ArrayList<>(); hand.add(hands1); hand.add(hands2); hand.add(hands3); for (int i = 0; i < 5; i++) { for (int j = 0; j < 3; j++) { Card card = list.remove(0); hand.get(j).add(card); } } System.out.println(hand); System.out.println("剩下的牌:"); System.out.println(list); } }
栈:先进后出 stack
中缀表达式: 后缀表达式:
输入:a+b*c/d-a+f/b 输出abc*d/+a-fb/+
先乘除后加减加括号挪符号去括号;
后缀表达式计算结果:是数字入栈 遇到符号出站两个数 栈顶为右操作数
Stack<Integer>stack1=new Stack<>();
stack1.push(1);//入栈
stack1.push(2);
stack1.pop(); //出站
stack1.peek();//获取元素
stack1.empty();//判断是否为空
public class MyStack { public int[] elem; public int top;//usedSize public MyStack() { this.elem = new int[10]; this.top = 0;//-1 } public boolean isFull() { if(this.top == this.elem.length) { return true; } return false; } public void push(int val) { if(this.isFull()) { //扩容 return; } this.elem[this.top] = val; this.top++; } public int pop() throws UnsupportedOperationException{ if(this.empty()) { throw new UnsupportedOperationException("栈为空!"); } //下来之后 不需要写else 因为抛出异常 就不执行了 int old = this.elem[this.top-1]; //this.elem[this.top-1] = null this.top--; return old; } public int peek() { if(this.empty()) { throw new UnsupportedOperationException("栈为空!"); } //下来之后 不需要写else 因为抛出异常 就不执行了 //int old = this.elem[this.top-1]; //this.elem[this.top-1] = null return this.elem[this.top-1]; } public boolean empty() { return this.top == 0; } }
单链表:头插法O(1) 出栈O(1); 尾插法O(n)
队列:先进先出 queue
单链表实现简单
class Node { public int val; public Node next; public Node(int val) { this.val = val; } } public class MyQueue { public Node front;//头 public Node rear;//尾 public int usedSize; //入队 public void offer(int val) { Node node = new Node(val); if(this.front == null) { this.front = node; this.rear = node; }else { this.rear.next = node; this.rear = node; } this.usedSize++; } //出队 public int poll() throws UnsupportedOperationException { if(isEmpty()) { throw new UnsupportedOperationException("队列为空!"); } int old = this.front.val; this.front = this.front.next; this.usedSize--; return old; } //获取队头元素 但是不删除 public int peek() throws UnsupportedOperationException{ if(isEmpty()) { throw new UnsupportedOperationException("队列为空!"); } return this.front.val; } public boolean isEmpty() { return this.usedSize == 0; //return this.front == null; } public int size() { return this.usedSize; } }
数组实现的话必须实现循环
public class MyCircularQueue { public int[] elem; public int front; public int rear;//一定是 当前可以存放元素的下标 public MyCircularQueue(int k) { this.elem = new int[k]; } //入队 public boolean enQueue(int value) { if(isFull()) { return false; } this.elem[this.rear]=value; this.rear = (this.rear+1)%this.elem.length; return true; } // public boolean deQueue() { if(isEmpty()) { return false; } this.front = (this.front+1)%this.elem.length; return true; } //得到队头元素 但是不删除 public int Front() { if(isEmpty()) { return -1; } return this.elem[this.front]; } //得到队尾元素 public int Rear() { if(isEmpty()) { return -1; } /* if(this.rear == 0) { return this.elem[this.elem.length-1]; }else { return this.elem[this.rear-1]; }*/ return this.rear == 0 ? this.elem[this.elem.length-1] :this.elem[this.rear-1] ; } public boolean isEmpty() { return this.front == this.rear; } public boolean isFull() { //rear的下一个是不是front if( (this.rear+1)%this.elem.length == this.front) { return true; } return false; } }
Queue<Integer>queue=new LinkedList<>();
queue.offer(1);
queue.offer(2);//入队
queue.poll();//出队
queue.peek();
双端队列 Dequeue
子树不相交 只有一个父节点 n各节点n-1条边
节点的度:一个节点含有的子树的个数称为该节点的度
树的度:树种最大节点的度成为树的度
叶子节点,终端节点:度为0的节点
双亲结点/父节点:含有子节点的节点
**子节点:**含有父节点的节点
**根节点:**没有双亲节点的节点
节点的层次:根为第1层,根的子节点为第2层,以此类推;
树的高度或深度:树中节点的最大层次;
**兄弟节点:**具有相同父节点的节点互称为兄弟节点;
堂兄弟节点:双亲在同一层的节点互为堂兄弟;
节点的祖先:从根到该节点所经分支上的所有节点;
**子孙:**以某节点为根的子树中任一节点都称为该节点的子孙。
森林:由m(m>=0)棵互不相交的树的集合称为
双亲表示法 孩子兄弟表示法
树的应用:文件目录
满二叉树:果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果 一个二叉树的层数为K,且结点总数是 ,则它就是满二叉树。
完全二叉树:对于深度为K的,有n 个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全 二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
前序 中序 后序 层次遍历
前序:访问根节点 左子树 右子树
中序:左 根 右
后序:左 右 根
class Node { public char val; public Node left; public Node right; public Node(char val) { this.val = val; } } public class BinaryTree { //public Node root;//二叉树的根 public Node createTree() { Node A = new Node('A'); Node B = new Node('B'); Node C = new Node('C'); Node D = new Node('D'); Node E = new Node('E'); Node F = new Node('F'); Node G = new Node('G'); Node H = new Node('H'); A.left = B; A.right = C; B.left = D; B.right = E; C.left = F; C.right = G; E.right = H; return A; } // 前序遍历 -> 递归 -》 子问题 思路 void preOrderTraversal(Node root) { if(root == null) return; System.out.print(root.val+" "); preOrderTraversal(root.left); preOrderTraversal(root.right); } // 中序遍历 void inOrderTraversal(Node root) { if(root == null) return; inOrderTraversal(root.left); System.out.print(root.val+" "); inOrderTraversal(root.right); } // 后序遍历 void postOrderTraversal(Node root) { if(root == null) return; postOrderTraversal(root.left); postOrderTraversal(root.right); System.out.print(root.val+" "); } // 遍历思路-求结点个数 static int size = 0; void getSize1(Node root) { if(root == null) return; size++; getSize1(root.left); getSize1(root.right); } // 子问题思路-求结点个数 int getSize2(Node root) { if(root == null) return 0; return getSize2(root.left) + getSize2(root.right) + 1; } // 遍历思路-求叶子结点个数 static int leafSize = 0; void getLeafSize1(Node root) { if(root == null) return; if(root.left == null && root.right == null) { leafSize++; } getLeafSize1(root.left); getLeafSize1(root.right); } // 子问题思路-求叶子结点个数 int getLeafSize2(Node root) { if(root == null) { return 0; } if(root.left==null && root.right == null) { return 1; } return getLeafSize2(root.left) + getLeafSize2(root.right); } // 子问题思路-求第 k 层结点个数 int getKLevelSize(Node root,int k) { if(root == null) return 0; if(k == 1) { return 1; } return getKLevelSize(root.left,k-1) + getKLevelSize(root.right,k-1); } // 获取二叉树的高度 int getHeight(Node root) { if (root == null) return 0; int leftHight = getHeight(root.left); int rightHight = getHeight(root.right); return leftHight > rightHight ? leftHight+1:rightHight+1; } //查找 Node find(Node root, char val) { if(root == null) return null; if(root.val == val) return root; Node r = find(root.left,val); if(r != null) { return r; } r = find(root.right,val); if(r != null) { return r; } return null; } }
判断相同的树
class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if(p == null&&q == null){ return true; } if(p==null&&q!=null){ return false; } if(p!=null&&q==null){ return false; } if(p.val!=q.val){ return false; } return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right); } }
判断子树
class Solution { public boolean isSameTree(TreeNode p,TreeNode q){ if(p==null&&q!=null){ return false; }if(q==null&&p!=null){ return false; } if(p==null&&q==null){ return true; } if(p.val!=q.val){ return false; } return (isSameTree(p.right,q.right)&&isSameTree(p.left,q.left)); } public boolean isSubtree(TreeNode root, TreeNode subRoot) { if(root==null)return false; if(isSameTree(root,subRoot))return true; if(isSubtree(root.right,subRoot))return true; if(isSubtree(root.left,subRoot))return true; return false; } }
判断一棵树是否为平衡二叉树
class Solution {
int getHeight(TreeNode root){
if (root == null)
return 0;
return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}
public boolean isBalanced(TreeNode root) {
if(root==null)return true;
int a=getHeight(root.right);
int b=getHeight(root.left);
return Math.abs(b-a)<2 && isBalanced(root.left)
&& isBalanced(root.right);
}
}
对称二叉树
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null)return true;
return isSystree(root.left,root.right);
}
public boolean isSystree (TreeNode Lefttree,TreeNode Righttree){
if(Lefttree==null&&Righttree!=null)return false;
if(Righttree==null&&Lefttree!=null)return false;
if(Lefttree==null&&Righttree==null)return true;
if(Righttree.val!=Lefttree.val)return false;
return (isSystree(Lefttree.left,Righttree.right)&&isSystree(Lefttree.right,Righttree.left));
}
}
层序遍历
void levelOrderTraversal(Node root) { if(root == null) return; Queue<Node> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { Node cur = queue.poll(); System.out.print(cur.val+" "); if(cur.left != null) { queue.offer(cur.left); } if(cur.right != null) { queue.offer(cur.right); } } } class Solution { public List<List<Integer>> levelOrder(TreeNode root) { if(root == null) return new ArrayList<>(); List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while(!queue.isEmpty()){ int count = queue.size(); List<Integer> list = new ArrayList<Integer>(); while(count > 0){ TreeNode node = queue.poll(); list.add(node.val); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); count--; } res.add(list); } return res; } }
判断完全二叉树
boolean isCompleteTree(Node root) { if(root == null) return true; //1、队列 Queue<Node> queue = new LinkedList<>(); queue.offer(root); //2、网队列扔元素-》 出元素(==null) while (!queue.isEmpty()) { Node cur = queue.poll(); if(cur != null) { queue.offer(cur.left); queue.offer(cur.right); }else { break; } } while (!queue.isEmpty()) { Node cur = queue.poll(); if(cur != null) { return false; } } return true; } }
根据先序遍历构建树 然后中序遍历
import java.util.Scanner; class Node{ char val; Node left; Node right; public Node(char val){ this.val=val; } } public class Main{ static int i=0; public static Node Creatprevtree(String str){ Node root=null; if(str.charAt(i)!='#'){ root=new Node(str.charAt(i)); i++; root.left=Creatprevtree(str); root.right=Creatprevtree(str); }else { i++; } return root; } public static void inOrderTraversal(Node root){ if(root ==null)return; inOrderTraversal(root.left); System.out.print(root.val+" "); inOrderTraversal(root.right); } public static void main(String[]args){ Scanner scanner=new Scanner(System.in); String str=scanner.nextLine(); Node root=Creatprevtree(str); inOrderTraversal(root); } }
根据二叉树创建字符串
class Solution { public void tree3str(TreeNode root ,StringBuilder str1){ if(root==null) return; str1.append(root.val); if(root.left==null){ if(root.right==null){ return; }else{ str1.append("()"); } }else{ str1.append("("); tree3str(root.left,str1); str1.append(")"); } if(root.right==null){ return; }else{ str1.append("("); tree3str(root.right,str1); str1.append(")"); } } public String tree2str(TreeNode root) { StringBuilder str1=new StringBuilder(); if(str1==null)return str1.toString(); tree3str(root,str1); return str1.toString(); } }
找公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null)return null;
if(p==root||q==root) return root;
TreeNode lefttree=lowestCommonAncestor(root.left,p,q);
TreeNode righttree=lowestCommonAncestor(root.right,p,q);
if(lefttree!=null&&righttree!=null)return root;
if(lefttree!=null&&righttree==null)return lefttree;
if(lefttree==null&&righttree!=null)return righttree;
return null;
}
}
二叉树搜索树转换成排序双向链表
二叉搜索树:左子树小于根 右子树大于根节点 (中序遍历有序)
public class Solution { TreeNode prev = null; public void convertChild(TreeNode pCur) { if(pCur == null) { return; } convertChild(pCur.left); pCur.left = prev; if(prev != null) { prev.right = pCur; } prev = pCur; convertChild(pCur.right); } public TreeNode Convert(TreeNode pRootOfTree) { if(pRootOfTree == null) return null; convertChild(pRootOfTree); TreeNode head = pRootOfTree; while(head.left != null) { head = head.left; } return head; } }
根据前序中序遍历构建二叉树
根据前序和后续无法构建一棵树
class Solution { public int preindex=0; public TreeNode buildtreechild(int[] preorder,int[] inorder,int inbegin,int inend){ if(inbegin>inend){ return null; } TreeNode root=new TreeNode(preorder[preindex]); int index=findIndex(inorder,inbegin,inend,preorder[preindex]); preindex++; root.left=buildtreechild(preorder,inorder,inbegin,index-1); root.right=buildtreechild(preorder,inorder,index+1,inend); return root; } public int findIndex(int [] inorder,int inbegin,int inend,int key){ for (int j = inbegin; j <=inend ; j++) { if(inorder[j]==key){ return j; } } return -1; } public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder==null||inorder==null)return null; return buildtreechild(preorder,inorder,0,inorder.length-1); } }
非递归前序中序后序
// 前序遍历 void preOrderTraversalNor(Node root) { if(root == null) { return; } Stack<Node> stack = new Stack<>(); Node cur = root; while (cur != null || !stack.empty()) { while (cur != null) { stack.push(cur); System.out.print(cur.val + " "); cur = cur.left; } Node top = stack.pop(); cur = top.right; } } // 中序遍历 void inOrderTraversalNor(Node root) { if(root == null) { return; } Stack<Node> stack = new Stack<>(); Node cur = root; while (cur != null || !stack.empty()) { while (cur != null) { stack.push(cur); cur = cur.left; } Node top = stack.pop(); System.out.print(top.val+" "); cur = top.right; } System.out.println(); } // 后序遍历 void postOrderTraversalNor(Node root) { if(root == null) { return; } Stack<Node> stack = new Stack<>(); Node cur = root; Node prev = null; while (cur != null || !stack.empty()) { while (cur != null) { stack.push(cur); cur = cur.left; } cur = stack.peek();// if(cur.right == null || cur.right == prev) { stack.pop(); System.out.print(cur.val+" "); prev = cur; cur = null; }else { cur = cur.right; } } } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。