# algorithm-note **Repository Path**: CandyPop/algorithm-note ## Basic Information - **Project Name**: algorithm-note - **Description**: 算法的一些总结 - **Primary Language**: Java - **License**: Not specified - **Default Branch**: main - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2021-03-12 - **Last Updated**: 2024-10-12 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README ### 算法 一些算法的总结 ##### 复杂度 什么是**时间复杂度**(What is time complexity) 数据量的增加所导致的时间花费的增加是怎么样的 时间是呈线性增加，还是常数，还是指数，指的是一种变化趋势 ```java //嵌套代码 int n = 10; for(int i =0;i<=n;i++){ for(int j =0;j<=2;j++){ ... } //随着当 n 为 10 的时候，这里要计算 10*2 次，当为100 时，计算100*2 //所以我们可以认为这个循环的时间复杂度为 O(2n) } for(int i =0;i<=n;i++){ for(int j =0;j<=n;j++){ ... } // 沿用上面的观点，这个为0(n^2) } ``` 常见的算法时间复杂度由小到大依次为 ``` n n O(1) 0) //将指定删除位置的元素后方的所有元素向前移动一位，因此时间复杂度为O(n) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; } public E get(int index) { rangeCheck(index); // 由于ArrayList 当你不指定大小的时候，会默认给你初始化长度为10的Object数组，这里直接用 // 数据的索引直接获取结果，所以复杂度为O(1),可以直接定位 return elementData(index); } E elementData(int index) { return (E) elementData[index]; } public E set(int index, E element) { rangeCheck(index); //修改方法，用于直接替换，查找方法也沿用了get方法O(1),所以设值时间复杂度和get的时间复杂度一致 E oldValue = elementData(index); elementData[index] = element; return oldValue; } //默认构造器的初始化常量数组，未指定大小 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //实际用于存放List数组的数据 transient Object[] elementData; // non-private to simplify nested class access、 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } public ArrayList(int initialCapacity) { if (initialCapacity > 0) { //当指定容量大小的时候，会为你创建默认大小，这也是比比较推荐的初始化方法 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } // 剖析ArrayList的无参构造器的具体容量在哪里 public boolean add(E e) { //进入这个方法 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { //进入第二个 这里其实会考虑做扩容操作，比较现在的数据大小和增加新元素后的List大小 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { //很明显，如果我们使用了无参的构造器的话，会进入这个判断，因为初始化用的就是这个 //这个使用会返回 DEFAULT_CAPACITY if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } /** * Default initial capacity. 所以无参构造器在初始化的时候其实还没有指定容量的大小，在真正add方法执行的时候 会做真正的初始化，默认大小为10，即会默认创建大小为10的Object数组，即使你没用到10个元素 */ private static final int DEFAULT_CAPACITY = 10; ``` * `ArrayList`的几个使用建议 * 能不用默认构造器就不要使用默认构造器 * 如果事先知道需要填入的大小，可以使用含有参数的构造器，并填入数值进行初始化 * 如果你不清楚的实际使用大小，也可以预估将会有多少元素 * `ArrayList`的crud方法的算法时间复杂度维度也可以看出，该List在查和修改性能很出色都为0(1)，删除和新增都为O(n)较差 * 因为底层是对象数组实现，所以他们在**物理**和**逻辑**存储单元都是连续的。 #### 什么是Linked List 什么是链表 链表是一种物理存储单元上非连续的，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。 这里不做源码分析，由于链表的形式 ```java class ListNode{ Object data;//当前节点保存的值 ListNode next;//指向下一个节点 } ``` ![1607785612003](./img/1607785612003.png) 对于链表而言，删除和新增对于他来说是简单的只要断开原本的引用指针，指向新的即可，对于删除的，只需要断开被删除的next指针，将被删除的节点的前后节点next重新指向即可，所以删除和新增的操作的时间复杂度都是0(1) ## 约瑟夫问题 约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。 例如只有三个人，把他们叫做A、B、C，他们围成一圈，从A开始报数，假设报2的人被杀掉。 - 首先A开始报数，他报1。侥幸逃过一劫。 - 然后轮到B报数，他报2。非常惨，他被杀了 - C接着从1开始报数 - 接着轮到A报数，他报2。也被杀死了。 - 最终胜利者是C 但是链表只是逻辑上连续，他并不能做到像是数组那样，使用位置即可定位，他的依据是从头节点开始遍历，不断的寻找下一个节点。所以他的时间复杂度是O(n) ##### 链表和数组的区别 在内存分配上，数组一定要保证内存一定要有数组申请的那么大的空间才会创建成功，而链表不会。 ![1607786105106](./img/1607786105106.png) #### 循环链表 即尾巴节点直接和头部相连接，组成一个环 #### 双向链表 what is double linked list，双向链表在单链表的每个结点中，再设置一个指向前驱节点的指针。 ```java public class Node{ //数据本身 private Object data; //前一个节点 private Node pre; //后一个节点 private Node next; } ``` 也是从增删改查这些问题入手。 对于增加和删除和之前的链表没有什么区别，都是O(1)，查询其实会比普通链表稍微高一点，因为他可以记住前节点的应用，他可以根据找到的值大小来决定是否接着向后遍历还是向前遍历。单向链表如果想要知道他的前一个节点是什么，还需要重新再遍历一次。 即便双向链表在空间上花费比单向要高些，这也是空间换时间的例子。 ```java // 反转链表 1->2->3->4->5 public ListNode reverseList(ListNode head){ if(head==null){ return null; } ListNode prev = head; ListNode current = head.next; //断开下一个节点 prev.next = null; // 1 2->3->4->5 while(current!=null){ ListNode next = current.next; // // 1<-2->3->4->5 current.next = prev;//将断开的节点反方向接上 prev = current;//切换到下一个 current=next; } return prev; } // 1->2->3->4->5 // 1->4->3->2->5 // 1<=m<=n<=length public ListNode reversedBetween(ListNode head,int m,int n){ if(head==null||m>=n){ return head; } //为了保证头节点不丢失，创建哨兵节点dummy ListNode dummy = new ListNode(-1); //将头节点地引用保留 dummy.next = head; //将指针变为头节点 head=dummy; //接着以m为界限，找到反转地起始点地前一个节点 for(int i=0;i1->2->3->4->5 ListNode prevN = head; ListNode mNode = head.next;//找到m位置地节点 ListNode nNode = mNode;//保存这个节点地位置 ListNode postN = nNode.next;//m节点地下一个位置 //现在把他当做是普通地反转链表来处理就行 for(int i =m;i map = new HashMap(); //首先将头保留一下 Node newHead = head; //循环，开始复制 while(newHead!=null){ // 创建映射 if(!map.containsKey(newHead)){ Node copyNode = new Node(newHead.val); map.put(newHead,copyHead); //这个循环走下去，其实已经完成了所有节点地拷贝，连顺序也对应好了 } //再判断一下是否有random地存在 if(newHead.random!=null){ Node random = newHead.random; if(!map.containsKey(random)){ //对随机指针对象进行拷贝 Node copyRandom = new Node(random.val)； map.put(random,copyRandom); } //根据原链表地random地映射关系，建立关系 map.get(newHead).random = map.get(random); } //走下一次循环 newHead = newHead.next; } //以上代码，结构变成了这样 } ``` ![1608039812382](./img/1608039812382.png) ```java //接着，将他们地关系根据map对应起来 newHead = head; while(newHead!=null){ map.get(newHead).next = map.get(newHead.next); newHead = newHead.next; } return map.get(head); ``` ```java //完整代码 public Node copyRandomList(Node head){ if(head==null){ return null; } //保存映射关系的map Map map = new HashMap(); //首先将头保留一下 Node newHead = head; //循环，开始复制 while(newHead!=null){ // 创建映射 if(!map.containsKey(newHead)){ Node copyNode = new Node(newHead.val); map.put(newHead,copyHead); //这个循环走下去，其实已经完成了所有节点地拷贝，连顺序也对应好了 } //再判断一下是否有random地存在 if(newHead.random!=null){ Node random = newHead.random; if(!map.containsKey(random)){ //对随机指针对象进行拷贝 Node copyRandom = new Node(random.val)； map.put(random,copyRandom); } //根据原链表地random地映射关系，建立关系 map.get(newHead).random = map.get(random); } //走下一次循环 newHead = newHead.next; } //接着，将他们地关系根据map对应起来 newHead = head; while(newHead!=null){ map.get(newHead).next = map.get(newHead.next); newHead = newHead.next; } return map.get(head); } ``` 另一种优化方案，由于在上面算法上，使用了map，空间复杂度增加，能不能节省掉这个map，我们使用map地目的在于建立映射，如果我们可以用另一种方式映射地话，是不是就可以省略到map地建立。 ![1608040751280](./img/1608040751280.png) 我们无非就是希望，在找到原表地1节点地时候能够快速找到另一个拷贝地1节点，这也是我们使用map地初衷，那么我们可以建立这样一种关系，将原1节点地后面直接接上拷贝的1节点，这样当我们获得原先地1节点地时候，他的next节点就是我们要找地拷贝地节点 ```java public Node copyRandomList(Node head) { if(head==null){ return null; } //第一步连接节点 connectNode(head); //拷贝指针 copyRandom(head); //第二部断开节点 return split(head); } public void copyRandom(Node head){ Node node = head; while(node!=null&&node.next!=null){ if(node.random!=null){ node.next.random = node.random.next; } node = node.next.next; } } public void connectNode(Node head){ //老规矩，保存头节点 Node newHead = head; while(newHead!=null){ Node copyNode = new Node(newHead.val); //接下来，我们要断开原来的链表关系，在其中插入这个新地copy节点 copyNode.next = newHead.next; newHead.next = copyNode; //以上成功插入，进入下一次循环 //newHead = newHead.next; //记住这里不能这样写了，因为现在地newHead.next已经是拷贝地1节点了 newHead = copyNode.next; } } public Node split(Node head){ //从已经拼凑好地节点切开 //取得拷贝后地拷贝头节点 Node result = head.next; Node move = head.next; //完整关联关系 while(head!=null&&head.next!=null){ //将copy后地节点，重新组成关联关系 //如果还有random //这个是还原原来地链表关系 head.next = head.next.next; //组成拷贝链表地对应关系 //下一次循环地准备 head = head.next; if(move!=null&&move.next!=null){ //找到拷贝地下一个节点，进行连接 move.next = move.next.next; move = move.next;//然后替换 } } return result; } ``` ##### 链表相加 Add two Numbers 两个链表的相加 ```java //例如两个链表地相加，最后返回结果 /** 4->6->3 链表1 与 3->4->4 相加 结果应该是 7->0->8 就像是 进位也算是 只不过相加是反方向地 */ public NodeList addNodeList(NodeList n1,NodeList n2){ if(n1==null){ return n2; } if(n2==null){ return n1; } //接着我们需要一个哨兵节点来接收完成最后地结果 ListNode dummy = new ListNode(-1); ListNode pre = dummy; //保存进位地值 int carry = 0; while(n1!=null&&n2!=null){ //获得开始累加地值,加上进位地值 int number=n1.val+n2.val+carry; //计算这个结果会不会造成进位 carry = number/10;//如果超过10将会是1 //对结果进行取余或者个位上地值 ListNode node = new ListNode(number%10); //放到哨兵地后面 pre.next = node; //pre地递增 pre = pre.next; //下一次循环 n1=n1.next; n2=n2.next; } //以上为理想情况，即n1和n2的长度都一样的时候，接下来来处理n1和n2长度不一样地情况 while(n1!=null){ int number = n1.val+carry; carry = number/10; ListNode node = new ListNode(number%10); pre.next = node; pre = pre.next; n1=n1.next; } while(n2!=null){ int number = n2.val+carry; carry = number/10; ListNode node = new ListNode(number%10); pre.next = node; pre = pre.next; n2=n2.next; } //第三种情况，如果这个时候carry还有值地画，仍然需要进一位 if(carry!=0){ ListNode node = new ListNode(carry%10); pre.next = node; } return dummy.next; } ``` LRU Cache 面试高频，LRU缓存 ，最近最少使用原则 ![1608213997144](./img/1608213997144.png) ```java class LRUCache { // 基本思路使用HashMap来弥补链表地查询性能缺乏地问题 // 使用链表来完成lru的功能，当超过容量，将最后地一个元素踢出链表 private class CacheNode{ //要完成踢出操作，就需要找到前节点和后节点，所以这里做成双向 CacheNode pre; CacheNode next; int value; int key; public CacheNode(int key,int value){ this.key = key; this.value = value; this.pre = null; this.next = null; } } //容量，当缓存超过此值时，进行lru private int capacity; //来存储数据 private Map cacheMap = new HashMap(); //类似哨兵机智，设置头和尾节点来确定链表得完整性 private CacheNode head = new CacheNode(-1,-1); private CacheNode tail = new CacheNode(-1,-1); public LRUCache(int capacity) { this.capacity = capacity; //将头尾相连 head.next = tail; tail.pre = head; // head -> tail // <- } public int get(int key) { //首先判断能不能找到 if(!cacheMap.containsKey(key)){ //没找到对应地，返回-1 return -1; } //如果找到，就取出来 CacheNode hit=cacheMap.get(key); //将命中地节点前后断开，并移动到尾部 hit.pre.next=hit.next; hit.next.pre=hit.pre; //移动到尾部 move2Tail(hit); return hit.value; } private void move2Tail(CacheNode node){ //首先要断开现在尾部节点地练习 node.pre = tail.pre; tail.pre = node; node.pre.next = node; node.next = tail; } public void put(int key, int value) { int result = get(key); if(result!=-1){ //说明是替换 cacheMap.get(key).value = value; return; } //否则说明是新增 //判断是否长度已经大于了最大长度 if(cacheMap.size()==capacity){ //将链表尾部地节点提出 CacheNode dropNode = head.next; head.next=dropNode.next; dropNode.next.pre = head; cacheMap.remove(dropNode.key); //等待gc } //增加 CacheNode addNode = new CacheNode(key,value); cacheMap.put(key,addNode); move2Tail(addNode); } } // 使用java api实现 class LRUCache { private int cap; private Map map = new LinkedHashMap<>(); // 保持插入顺序 public LRUCache(int capacity) { this.cap = capacity; } public int get(int key) { if (map.keySet().contains(key)) { int value = map.get(key); map.remove(key); // 保证每次查询后，都在末尾 map.put(key, value); return value; } return -1; } public void put(int key, int value) { if (map.keySet().contains(key)) { map.remove(key); } else if (map.size() == cap) { Iterator> iterator = map.e***ySet().iterator(); iterator.next(); iterator.remove(); // int firstKey = map.e***ySet().iterator().next().getValue(); // map.remove(firstKey); } map.put(key, value); } } ``` #### 栈 先入后出，想象成盒子，添加数据称为入栈，压栈，进栈，取出数据或者移除数据称为出栈，弹栈 应用的话，想象浏览器的回退功能，想退回上一个浏览的东西可以使用这个。 检测代码中括弧匹配问题 Valid Parenthese 括号验证 输入`()`返回ture，`()[]{}`返回true，`(]`false ```java public boolean isValid(String s){ if(s==null||s.length()==0){ return true; } Stack stack = new Stack(); char[] stacks = stack.toCharArray(); for(char c : stacks){ if(c=='('||c=='{'||c=='['){ //是我们需要匹配的内容，压栈 stack.push(c); continue; } if(c==')'){ //由于（）是成对出现，所以根据栈的结构，他的上一个应该是和他一样的 if(stack.isEmpty()||stack.pop()!='('){ return false; } } if(c=='}'){ //由于（）是成对出现，所以根据栈的结构，他的上一个应该是和他一样的 if(stack.isEmpty()||stack.pop()!='{'){ return false; } } if(c==']'){ //由于（）是成对出现，所以根据栈的结构，他的上一个应该是和他一样的 if(stack.isEmpty()||stack.pop()!='['){ return false; } } //正确的匹配完了。应该一个都不剩，所以如果还有剩余，说明也是false return stack.isEmpty(); } } ``` Min Stack 最小栈 设计一个这样的栈，插入若干数值，可以使用O（1）的时间来快速找到插入若干数值中最小的元素 首先，根据栈的数据结构，想要取出数值必须将一个一个元素弹出来，你必须`翻箱倒柜`的从顶查到尾，这显然不是O（1），而且如果有这样栈能够这样的话，其实也算是一个很完美的数据结构了。 所以我们可以用两个栈来实现，保持和前一个栈的插入行为一致，但插入的元素却有些区别![1608453067792](./img/1608453067792.png) 后者只存储最小的元素，当你压入元素的时候，会比较与栈顶的元素大小，如果比元素大，那么`minstack` 将会保持插入一条和之前最小的元素一样的值，来保持和原栈的层数一致，如果新插入的要销，那么就替换成新的元素。 如果是基本的元素操作，操作原栈的同时，也要移除minstack里的元素，来保持栈深度的一致，如果要取出最小的值，直接操作minstack就可以了，不过也要记住，同步移除掉原栈的元素 ```java class MinStack{ Stack stack; Stack minStack; public void push(int x){ stack.push(x); if(minStack.isEmpty()||x stack = new Stack(); int max=0;//区间最大值 //初始化地比传入地要多一位 int[] sum = new int[numbers,length+1]; //计算前缀和数 for(int i=1,len=sum.length;i<=len;i++){ sum[i]=sum[i-1]+numbers[i-1]; } for(int i=0,len=numbers.length;i stackA; //负责取值 Stack stackA; public MyQueue(){ stackA = new Stack(); stackB = new Stack(); } public void push(int x){ stackA.push(x); } public int pop(){ if(empty()){ return -1; } fill(); return stackB.pop(); } private void fill(){ if(stackB.isEmpty()){ //需要重新填充数据到B中 while(!stackA.isEmpty()){ stackB.push(stackA.pop()); } } } public int peek(){ if(empty()){ return -1; } fill(); return stackB.peek(); } public boolean empty(){ return stackB.isEmpty()&&stackA,isEmpty(); } } ``` 推荐结果打散 快手面试题，快手作为一个短视频平台，有时候会推荐图片和广告，给你一组随机地图片和广告，要让他们穿插的交替地进行排列展示，这里用v来比作视频，p来比作图片。给你这样一组数据 ``` v1 v2 v3 v4 v5 v6 v7 p1 p2 p3 p4 ``` 当然实际上，在终端上展示你不可能这样一下子一排地视频，视频完了后面是一堆图片，这看起来不友好。 ``` java public List getRecommendResult(List picAndVideo,int maxInterval){ //存储结果 List result = new ArrayList(); if(picAndVideo==null&&picAndVideo.isEmpty()){ return result; } Queue picQueue = new LinkedList(); Queue videoQueue = new LinkedList(); boolean firstPics = false; //获得总共地数据长度 int index = 0; int picAndVideoLength = picAndVideo.size(); //这个方法用于找到第一个图片 while(!firstPics&&index=maxInterval){ //当前视频内容如果已经超过了最大间隔，那么我们将插入一个图片 result.add(picQueue.poll()); curentSize=0;//设置回0 }else{ //否则我们可以接着添加视频 result.add(videoQueue.poll()) currentSize++; } } //以上地内容，当视频 videQueue 或者 picQueue为空地时候，都会弹出 //所以，如果这个时候videoQueue，也就是视频队列里如果还有东西，我们是允许接着插入地 if(!videoQueue.isEmpty()){ result.add(videoQueue.poll()); } //如果以上currentSize在最后一个视频累加完了后，正好超过间隔，也尝试加上图片 while(currentSize>=maxInterval&&!picQueue.isEmpty()){ result.add(picQueue.poll()); } return result; } private boolean isVideo(String slice){ if(slice.indexOf("v"!=-1){ return true; } return false; } ``` #### 二分法 Binary Search ###### 在旋转有序的数组中搜数 Search in Rotated Sorted Array 先写一个二分法的模板，**请牢记** ``` java public static void main(String[] args){ //给定一组数据，这里必须是有序地 int[] num = {1,4,7,9,10,14,16,20,56,89}; System.out.println(getIndex(num,4) ); } public static int getIndex(int[] num,int target){ //校验查找容器是否合法 if(num==null||num.length==0){ return -1; } int start = 0; int end = num.length-1; //以上定义开头和结尾 //这里定义二分法得灵魂，中间地索引位 int mid; for(start+1target){ //说明在左边 end = mid; }else{ //比他大，说明在右边 start = mid; } } //在这个以上返回都找到了 if(num[start]==target){ return start; } if(num[end]==target){ return end; } return -1; } ``` 回到之前地旋转有序数组中，这是一组有顺序地数组，例如 `{1,4,7,9,10,14,16,20,56,89}`这样的数组，但是这个数组会从某个位置，开始旋转，意味着他可能会变成这样`{14,16,20,56,89,1,4,7,9,10}`，意味着从某个点开始，会进行某段地不同位置得升序。 ![1608650422561](./img/1608650422561.png) 可以把反转后地数组，看做是这样地两段线条，A和B，目标target可能在A或者B上，同时，当你取mid也就是中间值地时候，也可能是在A上也可能在B上，所以我们需要考虑几种情况。 第一种，当mid落在了A上，且target确实也在A上，且start<=target<=mid地时候，可以完全确定target一定是在A的上面。反之，那么mid后面，也就是B线段可以完全舍弃。否则target>mid ![1608650811314](./img/1608650811314.png) 第二种情况，目标是比start要小的，那么就从B线条上寻找，如果符合mid<=target<=end这样地条件，那么一定就是在B线条上，抛弃A线条上地所有条件 ![1608650973977](./img/1608650973977.png) ``` java public void search(int[] num,int target){ if(num==null&&num.length==0){ return -1; } int start = 0; int end = num.length-1; int mid; while(start+1num[start]){ if(target<=num[mid]&&target>=num[start]){ //完美落到A上，对后面地内容进行剔除 end = mid; }else{ //否则往前找 start=mid; } }else{ //说明在B段 if(target<=num[end]&&target>=num[mid]){ start=mid; }else{ end=mid; } } } //补充 if(num[start]==target){ return start; } if(num[end]==target){ return end; } return -1; } ``` 在旋转有序数组中找最小 Find Minimum in Rotated Sorted Array ```java //沿用之前地例子 public int search(int[] num){ if(num==null||num.length==0){ return -1; } int start=0; int end = num.length-1; int mid; while(start+1=num[start]){ //说明在A段 if(num[mid<=num[end]]){ end = mid; }else{ start=mid; } }else{ end = mid; } } return Math.min(num[start],num[end]); } ``` 找峰值元素 ![1608734378351](./img/1608734378351.png) 这道题地关键在于，只要找出峰值就行，每个凸起都可以认为是山峰，这就关键在于mid落在哪里，如果落在前面，即mid+1>mid>mid-1我们认为，这是上坡路，于是我们将start移动到mid地位置，反之mid-1>mid>mid+1这就是下坡路，将end移动到mid节点 ```java public int search(int[] nums){ if(nums==null||nums.length==0){ return -1; } int start = 0; int end = nums.length-1; int mid; while(start+1nums[mid-1]){ if(num[mid]num[mid+1]){ //下坡 end = mid; }else{ //说明是谷底其实那边过来都一样，这边选start吧 start=mid; } }*/ if(nums[mid]num[mid-1]){ //可能是上坡 start=mid; }else{ return nums[mid]; } return nums[start]>nums[end]?start:end; } } ``` 砍木头 给你几块木头(一组含有数字地数组)，给你一个要将这几块木头砍成地块数，例如 ``` [232,124,456] 这些木头，要砍成7块，取他长度最大地块数，你可以砍成7块，或者8块，但是你必须保证最后砍成地块数长度是其他几种可能砍法长度最大的。 比如，232的木头，你可以认为是一根232米地木头，你自然可以把他砍成1米长度的，这样你可以砍232块，这是符合条件地，同样你可以把他砍成2米一块地，这样你可以砍116块，同样符合条件，但是2米地木头比1米地木头要长，所以我们会优先选择2米一块得砍法，以此类推。 所以这道题用二分法去理解，可以把他看成一组有序升序的数组，1，2，3，4，5...都是可以砍成不同米数地木块，可以砍成1米地，2米得，3米的，不断尝试，最后选出最佳地可能性 ``` 写出代码 ```java public int woodCut(int[] woods,int cutNum){ if(woods==null||woods.length==0){ return 0; } int start = 1; //获得众多木头中，长度最长地 int end = getMax(woods); int mid; while(start+1=cutNum){ start = mid; }else{ end = mid; } } //随着事件地推移，mid地值会越来越大 if(getPrices(nums,end)>=cutNum){ return end; } if(getPrices(nums,start)>=cutNum){ return start; } return 0; } public int getPrices(int[] woods,int woodLength){ int pices = 0; for(int wood:woods){ //每个都指定地长度切这么多块，累积多少块 pices+=wood/woodLength; } return pices; } public int getMax(int[] woods){ //找出最长地木头 int max = woods[0]; for(int i=1,len=woods.length;itarget`，说明结果过大，可以通过减少尾巴的索引，也就是通过减少right的索引来获得更小得结果，同理，如果结果是小于的，那么我们就需要移动left的索引，通过增大来获得更大的结果，最终来获得合适地值 ```java public int[] getIndex(int[] nums,int target){ if(num==null||num.length==0){ return null; } int left = 0; int right = num.length-1; while(left getIndex(int[] nums,int target){ if(num==null||num.length==0){ return null; } List result = new ArrayList<>(); int left = 0; int right = num.length-1; while(leftO(n)，变成了这样的时间复杂度。 那么三个数呢？同理，我们可以使用三个指针来确定他们之间地关系。 ![1609079812449](./img/1609079812449.png) 我们固定一个，然后后面沿用2sum的逻辑。这样我们地时间复杂度也从O(n3)变成了O(n2) ```java public List> getIndex(int[] nums,int target){ if(nums==null||nums.length==0){ return null; } Arrays.sort(nums); List> result = new ArrayList>(); //这里为什么是len-2.因为后面两个位置要留给left 和 right，如果循环真的走到那一步了 for(int i=0,len s = Arrays.asList(nums[i],nums[left],nums[right]); result.add(s); //全部累加推进 left++; right++; //去从, 害怕出现left方向有相同数字地值,或者right方向有相同地，就直接忽略 while(left0){ right--; }else{ left--; } } } return result; } ``` ##### 验证三角形 Valid Triangle Number，两边之和大于第三边，两边之差小于第三边。 给你一组数字[3,4,1,5]找出这其中有几种三角形得组合 沿用两边之和大于第三边，两边之差小于第三边，这是一个要素，其次我们需要这样一个模型。 ![1609250460941](./img/1609250460941.png) 任意地三个数字，有以上地6种组合，那么我们如果要每组都进行这样地校验，会比较复杂，我们可以这样，将给定地数组进行**排序**，这样我们就得到一对有顺序得数字`ac`，是否满足，如果满足第一个条件，是否第二个条件也满足了？因为c比a和b都要大，所以a加上一个比b还要大的数是不是一定大于b呢，答案是肯定的，同理，第三个条件也满足，意味着只需要验证第一个条件成立，第二和第三个条件也同时成立。接着我们看剩下的四五六中方案，能否沿用之前地理论，a和b原本就比c要小，两个都小的数相减，答案肯定是更小得，所以第四种情况也成立，再看第五和第六，由于c比a与b的和要小得，所以c减去a也不可能比b要大，因为b与c-a的结果相差得，就是a+b与c的差值，不差的话就会相等了。同理第六条也成立。由此，只需要满足一个条件，其它的五个条件也会同时成立，大前提是他们是有**顺序**的。 ![1609251516131](./img/1609251516131.png) 这里我们再做一次优化，我们从后往前遍历，因为如果`b+e>f`成立地话，那么比b还要大的cd也同样成立前面的公式，所以之间索引之间相减就可以得到组合得可能性。 ```java // 返回有几种组合 public int trangleNumber(int[] nums){ if(nums==null||nums.length==0){ return 0; } //先排序 Arrays.sort(nums); int total = 0; //我们从最后往前遍历 for(int i=nums.length-1;i>=2;i--){ int start = 0; int end = i-1; while(startnums[i]){ total+=(end-start); end--; }else{ start++; } } } return total; } ``` #### 存水问题 trapping rain water ![1609254316530](./img/1609254316530.png) 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/trapping-rain-water 同样使用双指针，一个指向头一个指向尾部。同时我们需要理解一点的是，能装多少水取决于最短的那部分，也就是水桶原因，水桶能装多少水取决于水桶最短的那块短板。 所以，我们的思路是，当数组的当前数和下一个数做大小对比，如果后一个数比前一个数大，那么呈上升趋势，所以不会蓄水，因为已经没有比他更高的板子替他挡住水。 ![1609254607218](./img/1609254607218.png) 反之，存在那么就存在蓄水可能性，为什么这么说，如果你希望蓄水那么在你的板子另一边一定存在一块和你相同高度或者更高的板子替你挡住，那么才有可能蓄水。 ![1609254779910](./img/1609254779910.png) 所以，一开始，我们首先取数组的开头和结尾，然后做比较，如果开头比结尾小，那么至少在结尾处有一个值可能可以**兜底**，帮忙堵住然后蓄水，当找到比结尾处更高地板子，那么高度替换，再接着走下一步。 ```java public int trap(int[] number){ if(number==null||number.length==0){ return 0; } int left=0; int right=number.length-1; //对应的所有的高度 int leftHeight = number[left]; int rightHeight = number[right]; int sum=0; while(leftnumber[left+1]){ //存在蓄水可能 sum+=leftHeight-number[left+1]; }else{ //遇到更高的替换 leftHeight=number[left+1]; } left++; }else{ if(rightHeight>number[right-1]){ sum+=rightHeight-number[right-1]; }else{ rightHeight = number[right-1]; } right--; } } return sum; } ``` #### Sort 排序 冒泡、插入、选择、归并、快速、基数、桶排。 考虑因素有哪些。 * 复杂度分析 * 比较和交换字节分析 * 内存分析 * 稳定性（如果原排序目标中，可能存在两个相同的元素，在经过排序后，这两个元素的先后顺序并没有改变） | 算法名称 | 稳定性 | 最好(时间复杂度) | 最坏(时间复杂度) | 平均(时间复杂度) | 原地排序 | | ---------- | ------ | ---------------- | ---------------- | ---------------- | -------- | | 冒泡 | yes | O(n) | O(n2) | O(n2) | yes | | 插入 | yes | O(n) | O(n2) | O(n2) | yes | | 选择 | no | O(n) | O(n2) | O(n2) | yes | | 快速(重点) | no | O(nlogn) | O(n2) | O(nlogn) | yes | | 合并(重点) | yes | O(nlogn) | O(nlogn) | O(nlogn) | no | | 计数 | yes | O(n+k) | O(n+k) | O(n+k) | no | | 桶排 | yes | O(n+k) | O(n2) | O(n+k) | no | | 基数 | no | O(n*K) | O(n*K) | O(n*k) | no | * 冒泡 * 经过一次一次地比较，最后把最大/最小放在最后，达到排序目的 * 插入 * 类似扑克牌的排序，将合适大小得牌插入到应该有地位置，例如4应该在5的后面。 * 选择 * 无论什么数据进去，都是O（n2）得时间复杂度，但是不占用内存空间 #### 冒泡 插入 选择 都是O（n2）时间复杂度得算法 ```java public void bubboSort(int[] nums){ if(nums==null||nums.length==0){ return; } for(int i =0;inums[j]){ int num = nums[j-1]; nums[j-1]=nums[j]; nums[j]=num; } } } } ``` ![1609678889881](./img/1609678889881.png) 选择排序，选择一个节点与他的后一个节点，也可以称为插入节点，插入节点与前一个节点做比较，如果比前一个要大，那么保持原样，`j`和`insert node`节点同时往前移动，如果这个时候. ![1609679018611](./img/1609679018611.png) 由于2是比9要小，所以2和9做交换，然后2再与1做比较，由于2要比1要大，所以不做交换，一次类推，完成最后的排序。 ![1609679125552](./img/1609679125552.png) ```java public void insertSort(int[] array){ int insertNode; int j; for(int i =1;i=0&&insertNodearray[j]){ //索引发生替换 pos = j; } } //如果索引不相同，则意味着pos和j没发生任意一次替换,那么就什么也不做 if(pos!=i){ int arr = array[pos]; array[pos]=array[i]; array[i]=arr; } } } ``` 选择排序的交换只交换一次，就是在pos与j的比较的时候，而冒泡只要发现大小不对，就会进行数组值地替换。 时间比较，插入<选择<冒泡。但是数据量上去了，这个时间还是太长了，因为O(n2)对应上百万的数据还是太慢了。 **Quick Sort** 快速排序 ![1609773588525](./img/1609773588525.png) 例如给定一串没有规律的数字数组，要使用快速排序算法对他进行排序，我们需要定义三个变量，第一个变量叫做`pivot`，这个变量将会存储`left指针`最一开始循环比对的值，这里一开始是4，所以这里的值就是4，left指针将会指向最左边的值，right的指针指向最左边的值。然后开始循环比对，首先是pivot的值和left比对，由于pivot此时是4，left也是4，因为他们此时指向同一个的，所以相同也是很正常，这里有一个判断依据，当pivot的值不小于left值的时候，left的指针将不会向前移，也就是意味着pivot<=left的时候，left将不会++，反之pivot>left的时候，left将会向right靠近，left++，**总之你一定要保证left所走过的所有数，都应该比此时pivot的数要小，当出现了left比pivot的数要大或者等于地时候，就会停下脚步**。当pivot>=leftt条件成立后，left的索引将不会改变，接着来移动right。和left的条件相反，当pivot>=right的时候，right的位置将会停住，反之，即pivot=end){ //防止死循环 return ; } int pivot = array[start]; int left = start; int right = end; while(left<=right){ //left所走过的路，都应该比pivot要小，如果大于或者等于就停下脚步 while(left<=right&&pivot>array[left]){ left++; } while(left<=right&&pivot=end){ return; } //从中间切割 int mid = (start+end)/2; mergeSortImp(array,start,mid,temp); mergeSortImp(array,mid+1,end,temp); merge(array,start,mid,end,temp); } private void merge(int[] array,int start,int mid,int end,int[] temp){ int left = start; int right = mid+1; int index = start; while(left<=mid&&right<=end){ //比较大小，然后赋值到临时的空间里 if(array[left][1,2,3,#,#,4,5] */ public class TreeNode{ int val; private TreeNode left; private TreeNode right; pirvate TreeNode(int x){ this.val = x; } } public String serialize(TreeNode root){ if(root==null){ return "[]"; } List list = new ArrayList(); //用来获取树节点中的全部内容 list.add(root); for(int i =0;i queue = new ArrayList(); //和序列化一样，构建第一个节点 TreeNode node = new TreeNode(Integer.parseInt(datas[0])); //也和序列化一样，添加进去 queue.add(node); for(int i=1;i preorderTraversal(TreeNode root){ List result = new ArrayList(); if(root==null){ return result; } List left = preorderTraversal(root.left); List right = preorderTraversal(root.right); //前序排列规则，先打印自己，在打印左边，在打印右边 result.add(root.val); result.addAll(left); result.addAll(right); return result; } // 使用非递归方式实现 public List preorderTraversal(TreeNode root){ List result = new ArrayList(); if(root==null){ return result; } // 思考一个问题，即，我们在遍历完了自己后，要去找左，然后左找完了后，又会回到右，这样的可以类似找回历史的数据结构用什么来做呢，答案很明显，是栈 Stack stack = new Stack(); //添加一个启动元素 stack.push(root); while(!stack.isEmpty()){ //首先，我们要取出要压栈得元素 TreeNode node=stack.pop(); //获得值 result.add(node.val); //因为需要先遍历左边，但是由于Stack的特殊的结构，先进后出，所以我们应该先存入右边 if(node.right!=null){ stack.push(node.right); } if(node.left!=null){ stack.push(node.left) } } return result; } ``` ![1610374394916](./img/1610374394916.png) #### 中序遍历 inOrder Traversal **先左，自己，再右边。** ```java // 使用递归 public class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val,TreeNode left,TreeNode right){ this.val = val; this.left = left; this.right = right; } } // 标准模版 使用递归 public List inorderTraversal(TreeNode root){ List result = new ArrayList(); if(root=null){ return result; } List left = inorderTraversal(root.left); List right = inorderTraversal(root.right); //先添加左边，再添加中间，再添加右边 result.addAll(left); result.add(root.val) result.addAll(right); return result; } //第二种 public List inorderTraversal(TreeNode root){ List result = new ArrayList(); if(root==null){ return result; } Stack stack = new Stack(); TreeNode currentNode = root; while(currentNode!=null||!stack.isEmpty()){ while(currentNode!=null){ //由于我们要从left开始遍历，所以我们不得不找到需要遍历的树的最左得子节点 stack.push(currentNode); currentNode = currentNode.left; } //如果能跳出上面的循环，说明已经找到某个节点的最左边得节点 //所以我们需要弹出结果进行累加 TreeNode n = stack.pop(); result.add(n.val); //再看看右边有没有节点 currentNode = currentNode.right; } return result; } ``` ![1610376800656](./img/1610376800656.png) 又因为B的right是有值得，所以会进入下一层循环，在进入第二层循环的时候，由于current不为null，所以我们进入，然后将当前的current压入，也就是上次循环得right节点，然后将他地left取出，看存不存在left，发现没有left，跳出第二层循环，记录被压入的E，再看看E的right赋值。然后再次下一次循环，发现current为空，不走第二次循环，直接取出A的节点。之后的步骤雷同。 ![1610377099880](./img/1610377099880.png) #### 后续遍历 PostOrderTraversal ```java //万精油写法 public List postorderTraversal(TreeNode root){ List result = new ArrayList(); if(root==null){ return result; } List left = postorderTraversal(root.left); List right = postorderTraversal(root.right); //先左后右再中间 result.addAll(left); result.addAll(right); result.add(root.val); return result; } //断子绝孙法则，不推荐，因为计算值需要取消掉原节点之间的关系 public List postorderTraversal(TreeNode root){ List result = new ArrayList(); if(root==null){ return result; } Stack stack = new Stack(); stack.push(root); while(!stack.isEmpty()){ //窥探一下 TreeNode node=stack.peek(); //当左右两边都没有值得时候，才会开始计算 if(node.left==null&&node.right==null){ //因为下面断绝了关系，所以才可以进入这个方法 result.add(stack.pop().val); } //由于栈得特殊性，先压右 if(node.right!=null){ stack.push(node.right); //取消关系 node.right=null; } if(node.left!=null){ stack.push(node.left); node.left=null; } } return result; } //第三种比较难理解的，但是画图还是很好理解地方法 public List postorderTraversal(TreeNode root){ List result = new ArrayList(); if(root==null){ return result; } Stack stack = new Stack(); TreeNode pre = null; TreeNode current = root; stack.push(root); while(!stack.isEmpty()){ current = stack.peek(); if(pre==null||pre.left==current||pre.right==current){ //能够进入到这里面的，表示current和pre是父子节点关系 if(current.left!=null){ stack.push(current.left); }else if(current.right!=null){ stack.push(current.right); } }else if(current.left == pre){ //能够进入这里面，说明left已经这边已经遍历完了，正准备回头遍历right节点 if(current.right!=null){ stack.push(current.right); } }else{ //开始计算 result.add(current.val); stack.pop(); } pre = current; } return result; } ``` #### 红黑树 ##### 删除 删除分为下面几种情况 ![1610893207923](./img/1610893207923.png) > 1 被删除的节点是左边-兄弟节点是红的情况 ![1610977921128](./img/1610977921128.png) * 将兄弟节点设置为黑色 * 然后将兄弟节点的左子树设置为红色 * 接着对父节点进行左旋，最后调整 > 2 被删除的节点是左边-兄弟节点是黑的-没有叶子节点 ![1610978434971](./img/1610978434971.png) > 3 被删除的节点是左边-兄弟节点是黑的-有左边子节点 ![1610980064744](./img/1610980064744.png) > 4 被删除的节点是左边-兄弟节点是黑的-有右边子节点 ![1610979258739](./img/1610979258739.png) > 5 被删除的节点是左边-兄弟节点是黑的-左右子节点都有 ![1610980675396](./img/1610980675396.png) * 将父节点的颜色赋值给兄弟节点 * 兄弟节点的右孩子设置为黑色 * 父节点设置为黑色 * 对父节点进行左旋 > 6 被删除的节点是右边-兄弟节点是红 ![1610981335708](./img/1610981335708.png) * 将兄弟节点设置为黑色 * 兄弟节点的右边设置为红 * 第父节点进行右旋 > 7 被删除的节点是右边-兄弟节点是黑-无节点 ![1610981601242](./img/1610981601242.png) * 兄弟节点变成红，如果你这个时候的父节点不是黑色，而是红色，那么以父节点为起点往上遍历，直到符合要求。 > 8 被删除的节点是右边-兄弟节点是黑-拥有左叶子节点 ![1610981917507](./img/1610981917507.png) * 兄弟节点变为和父节点一样得颜色 * 兄弟节点的左子树变成黑色 * 父节点进行右旋 > 9 被删除的节点是右边-兄弟节点是黑-拥有左叶子节点 ![1610982338611](./img/1610982338611.png) * 将兄弟节点设置为红色 * 将兄弟节点的右节点设置为黑色 * 对兄弟节点进行左旋 * 将父节点的颜色赋值给兄弟节点 * 将父节点的左子树和兄弟节点的左子树设置为黑色 * 将父节点进行右旋 > 10 被删除的节点是右边-兄弟节点是黑-左右子树都存在 ![1610982748043](./img/1610982748043.png) * 父节点的颜色赋值给兄弟节点 * 兄弟节点的左孩子设置为黑色 * 将父节点设置为黑色 * 将父节点进行右旋转 #### 红黑树 treap 由于二叉查找树在多次删除或者新增的操作后，可能导致树不够**平衡**，又或者可以称作**倾斜**，导致增删改插的时间复杂度增加，所以我们要保障每次进行新增或者删除的时候，不会让二叉树失去**平衡** ![1610862662733](./img/1610862662733.png) 高度(完美)平衡的二叉树(AVL树) * 可以允许空树 * 假如不是空树，任何一个节点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过1 首先需要声明的是，在jdk1.8之前，HashMap在插入元素时发生hash碰撞的时候，会采用链表的形式来存储元素，而在1.8之后，当超过链表超过8个这个阈值的时候，会转变为红黑树。 红黑树(平衡二叉查找树)其实并不是严格意义上的AVL树，原因是，如此**平衡**的树实现起来是很困难的，再者理解起来也很困难，所以红黑树是一个相对平衡的二叉查找树，可能左右的高度之差会是AVL树所定义的一倍，但是看起来还是**相对平衡的。** 红黑树的定义 * 根节点是黑色的 * 每个叶子节点都是黑的空节点(NIL)，也就是说，叶子节点不存储数据 * 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点所隔开的 * 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点。 ![1610864170395](./img/1610864170395.png) #### 左旋 ![1610865931579](./img/1610865931579.png) 例如这个时候，以10这个节点进行左旋，这个左旋转的操作可以看做是以10这个节点为原点，将右边的子树向上**提升**，**甩到上面**，这个时候10变成了20的子节点，但是由于二叉树特性，最多只能有两个节点，所以18作为20的左子树，将会被重新插入到10的右边，来保证二叉查找数的定义。 #### 右旋 ![1610866211178](./img/1610866211178.png) 沿用上面左旋的定义，20这个节点右旋的时候，可以看做是右边子树的**降级**，10将往上提升，然后18重新插入到他该在的位置。 插入的时候，节点必须是红色 插入的几种情况 > 第1种：刚好是个空树，红节点作为根节点插入后直接变黑 ![1610868551928](./img/1610868551928.png) > 第2.1种：插入的节点的父节点和叔叔节点都是红色，这明显违背了红黑树的定义，所以要进行调整 ![1610868983131](./img/1610868983131.png) 假设一个红黑树，要插入一个节点，首先这个节点肯定是红的，在插入后，我们发现是不符合红黑树的定义的，因为我们发现父节点和叔叔节点都是红色的。对于如何让**不红黑树**的树变成符合红黑树其实有几个固定的公式，类似和**魔方**一样，每一面的转法和调整都是有固定公式，只要不断的重复，迭代最终会达到你要的效果 为止，这个和红黑树的调整方法是一致的。 我们首先，将这个插入的节点`x`的父节点和叔叔节点都变成**黑色**，然后再把祖父节点变成红色，如果这个祖父节点已经是**根节点**了，那么只需要把把祖父节点再次变成黑色即可。如果这个的祖父节点还存在父级节点，那么将祖父节点再次看做是x节点接着用上述方法进行迭代，直到找到根节点，完成红黑树的定义的调整。 > 第2.2种：插入的节点，只有父节点是红节点，叔叔节点是黑节点(左左，即插入是左子节点的左子节点) ![1610869842211](./img/1610869842211.png) 首先，我们需要以插入元素的祖父点作为中心，对树进行**右旋**，接着将父节点和祖父节点颜色进行切换。 > 第2.3种，插入的节点，只有父节点是红节点，叔叔节点是黑节点(左右，即插入是左子节点的右子节点) ![1610870436569](./img/1610870436569.png) 首先，插入的是节点的右子树的时候，对父节点进行**左旋**，这样x节点就被提升上来了，然后符合第三种左左的情况，对祖父节点进行**右旋**，再重新着色。 > 第2.3种，插入的节点，只有父节点是红节点，叔叔节点是黑节点(右右，即插入是右子节点的右子节点) ![1610871386547](./img/1610871386547.png) 祖父节点左旋，然后变色。 > 第2.4种，插入的节点，只有父节点是红节点，叔叔节点是黑节点(右左，即插入是右子节点的左子节点) ![1610871784217](./img/1610871784217.png) 首先对父节进行**右旋**，接着重新构建父子关系，然后就像是右右的关系一样，对祖父节点进行左旋，然后切换颜色。 > 作业：用10，70，32，34，13，56，21构建一个红黑树 我的作业 ![1610874917772](./img/1610874917772.png) 老师的答案 ![1611472374141](./img/1611472374141.png) * 关键在于，每个节点下面都是默认挂在这nil的黑节点，这样方便符合上面的转换公式。 * 其次，当不符合以上公式的时候，可以通过旋转来达到公式要求，进行相应的转换 ###### 二叉树的右视角 Binary Tree Right Side View ``` Input:[1,2,3,null,5,null,4] Output:[1,3,4] Explanation: 1 <--- / \ 2 3 <--- \ \ 5 4 <--- 从这里看，只能看到二叉树的右边 ``` 代码实现 ```java public class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val,TreeNode left,TreeNode right){ this.val = val; this.left = val; this.right = right; } } public List rightSideView(TreeNode root){ List result = new ArrayList(); if(root==null){ return result; } Queue queue = new LinkedList(); // fire queue.offer(root); boolean findRight = false; while(!queue.isEmpty()){ int size = queue.size(); findRight = false; for(int i=0;i1){ //当左右两边子节点高度相差超过1得时候，会返回-1 // 一旦发现有超过1的右边节点，将会一直返回-1，知道结束，告知此二叉树非平衡 return -1; }else{ //当还没找到超过1的相差得时候，将会一直做累加操作 //首先找到最底部的子节点，这个时候是上面的return 0 的结果，到这里位置将会返回1，然后不断的累加1 return Math.max(left,right)+1; } } /* 以上面的第一个例子举例，根节点是3 第一次进入 看left 节点，返回9，9没有左子节点，所以返回0，同样9也没有右子节点，所以也返回0 在9这个节点，将会返回1 Math.max(0,0)+1; 左子树遍历完了，看右子树 同理，15和 7 都将返回1，然后 20 将会返回2，Math.max(1,1)+1; 当左右子数都遍历完后，再看根节点3，9的返回是1，20返回的2，这都表示了左右子树所拥有的层数 经过最后的比较，他们依旧符合left-right不大于1，依旧平衡。 */ ``` ### 什么是堆 What is Heap 是一个用数组实现的**二叉树** 不同的语言，实现堆的方式不同，对于java来说是叫做 PriorityQueue（优先队列） 堆有两个种 * 最大堆 * 父节点的值比每个子节点的值都要大 * ``` 11 / \ 8 3 / \ 6 2 ``` * 最小堆 * 父节点的值比每个子节点的值都要小 也被称为**堆属性** 这和二叉查找树的属性略有不同，二叉查找树左子节点比父节点要小，右子节点比父节点要大。同时平衡二叉树在满足平衡的情况下，性能会达到O(logn)，但是堆却不需要满足平衡，我们只需要满足他地堆属性就可以达到logn的时间复杂度。平衡二叉树的搜索性能很好，但是堆的搜索性能并不高，这是因为搜索并不是他的优先级，他的插入顺序决定了他的弹出元素的顺序是高效得，父节点比下面所有节点都大或者小。 #### 第K大元素 top k largest 给定一个无序的数组，然后给一个k值，找在这个数组里，第k大的值 例如给定一个数组[3,2,1,5,6,4]，k=2，在这里，第2大的是5，所以会输出5。 又一个数组[3,2,3,1,2,4,5,5,6],k=4，将会返回4，即便5重复了，也算是占一个排序位置。 ```java public int findKthLargest(int[] nums,int k){ if(nums==null||nums.length==0||k<1||k>nums.length){ return -1; } PriorityQueue maxHeap = new PriorityQueue(k,new Comparator(){ public int compare(Integer num1,Integer num2){ return num1-num2; } }); for(int i : nums){ maxHeap.add(i); } //以上会按最大堆的顺序进行组建树 for(int i =0;inums.length){ return -1; } return partition(nums,0,nums.length-1.nums.length-k); } public int partition(int[] nums,int start,int end,int k){ if(start>=end){ return nums[k]; } int left = start; int right = end; int pivot = nums[(start+end)/2]; while(left<=right){ while(left<=right&&nums[left]pivot){ right++; } if(left<=right){ //互换 int temp = nums[left]; nums[left]=nums[right]; nums[right]=temp; left++; right++; } } //说明目标在左边 if(k<=right){ return partition(nums,start,right,k); } //说明目标在右边 if(k>=left){ return partition(nums,left,end,k); } return nums[k]; } ``` #### 从数据流里面找中位数 find median from Data Stream ``` 例如给定一串数字，找到这串数字里面的中位数 中位数在给定数组是偶数的情况下，找到中间靠左边的数，例如 给定[1,2,3,4] 那么中位数就是2 如果给定数组是奇数的情况下，那就是中间的位置了，这没什么好质疑的 [1,2,3,4,5]中位数是5 这道题，将会按照顺序依次给数据添加值，每次添加值你都需要找出这个目前已添加值得数组里的中位数 例如，[1] 中位数 是1，[1,2]中位数是1,[1,2,3]中位数是2,[1,2,3,4]中位数是2，[1,2,3,4,5]中位数是3，所以，给你一串这样的数组 [1,2,3,4,5] 你的输出就是 [1,1,2,2,3] ``` 解出这道题，我们需要用到两个堆，一个最大堆(maxHeap)一个最小堆(minHeap)，用这两个判断每次添加进来的值应该放在哪个位置，最大堆中每个父节点都会大于其下面的所有子节点，最小堆中每个父节点都会小于其下方子节点，其实就相当于给传进来的数据，进行了默认的**排序**，用来划分中间值的界限。 ```java public int[] median(int[] nums){ if(nums==null||nums.length==0){ int[] ins = new int[0]; return ins; } int count = nums.length; //最大堆 maxHeap PriorityQueue maxHeap = new PriorityQueue(count,new Comparator(){ public int compare(Integer num1,Integer num2){ return num2-num1; } }); //最小堆 PriorityQueue minHeap = new PriorityQueue(count); //准备输出的返回值 int[] answer = new int[count]; int numbers = nums[0];//放入第一个值 answer[0] = number; for(int i =1;inumber){ //如果当前节点，大于目前已经确定的中间值，那么久放到min队列，由于minHeap是从小到大摆列，所以当我们弹出第一个元素的时候，一定是最小的那个弹出 minHeap.add(target); // 接着将number的值更新 }else{ //反之放入maxHeap，由于maxHeap里面存在了由大到小的数字排列，所以弹出的第一个元素一定是最大的那个 maxHeap.add(target); } //为了保证平衡，我们要计算已经放入了两个堆和number的数值是否合理 if(Math.abs(maxHeap.size()-minHeap.size())>1){ if(minHeap.size()>maxHeap.size()){ //说明minHeap比maxHeap大，要分一个给maxHeap保持平衡 maxHeap.add(number); //更新值 number = minHeap.poll(); }else{ minHeap.add(number); number = maxHeap.poll(); } }else{ //相差 0 或者 为1的情况，却maxHeap比minHeap大一个的情况，且maxHeap的最大值是比当前中间值小的情况，那么就做中间值的替换，和平衡 if(maxHeap.size()-minHeap.size()==1&&maxHeap.peek() map = new HashMap(); //计算前缀和数 for(int i =1;i1 第一次循环 1-2=-1，-1在map中不存在，走下面 ans=0 temp中不存在值，map中也不存在1，所以map添加 map = 0->1 1->1 第二次循环 2-2=0,0在map中存在，对ans进行累加 ans=1 temp中不存在2的值，所以也为1 map = 0->2 1->1 2->1 第三次循环 3-2=1,1在map中存在，对ans累加 ans=2 1在map中存在，就进行计算 map = 0->2 1->2 2->1 3->1 / ``` ​ #### 克隆图 ![133_clone_graph_question](./img/133_clone_graph_question.png) 每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。 邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。 给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。 每个节点除了他自己的值之外，还存储了，他相邻的两只，例如，1的neighbors存储了4和2的节点。 请深度克隆这个图 解决这个问题的思路主要是是能够完整的找到所有节点，才方便进行克隆，再者完全克隆他们所有的元素，和普通的链表不同，你无法通过next或者pre来循环获得他们所有的节点，他们的关系是存储在neighbors中的，是一个数组，可能是左边也可能是右边。 ```java /* // Definition for a Node. class Node { public int val; public List neighbors; public Node() { val = 0; neighbors = new ArrayList(); } public Node(int _val) { val = _val; neighbors = new ArrayList(); } public Node(int _val, ArrayList _neighbors) { val = _val; neighbors = _neighbors; } } */ class Solution { public Node cloneGraph(Node node) { if(node==null||node.neighbors==null||node.neighbors.isEmpty()){ return null; } //首先要获取所有的节点 List nodes = getNode(node); //接着进行每个节点的克隆映射 Map mapping = new HashMap(); for(Node node : nodes){ mapping.put(node,new Node(node.val)); } //接着深度克隆他们之间的negber关系 for(Node node : nodes){ Node newNode = mapping.get(node); //进行negber的寻找和赋值 List negber = newNode.neighbors; for(node ne:negber){ //通过mapping取出克隆后的邻居 Node cloneNe = mapping.get(ne); newNode.neighbors.add(cloneNe); } } //返回头节点 return mapping.get(node); } /* 在这个方法中，我们要不重复的找出图中的所有节点 */ private List getNodes(Node node){ //一个用来遍历的数据结构 Queue ，利用插入和弹出的特性，我们来遍历这个图 Queue queue = new LinkedList(); //用不可重复的Set来存储最后的结果 Set set = new HashSet(); //放入第一个元素 queue.offer(node); set.add(node); //开始循环 while(!queue.isEmpty()){ //弹出元素 Node node=queue.poll(); //检查是否需要在set中存在，如果不存在则在set中放入，且在queue中放入他的邻居，进入下一次循环，否则表示已经已经没有可找的节点，退出循环 List negber = node.neighbors; for(Node node:negber){ if(!set.contains(node)){ //不存在就放入 set.add(node); queue.offer(node); } } } return new ArrayList(set); } } ``` #### 最长无重复的子串 Longest Substring without repeating Char ``` 给定一个字符串，找到最长的没有重复的子字符串的长度 例如，abcabcbb 那么，abc是没有重复的，然后再到a是重复了，后面也没有比abc更长的子串，所以这个输出是3 如果是 bbbbbb 那么输出就是1 ``` 第一种解法，由于我们只需要记录最长的重复字符串地长度既可以，所以我们只需要将还未重复的字符串存储到set中，然后保证后续没有与set中冲突地元素即可 ```java public int lengthOfLongestSubString(String s){ if(s==null||s.length()==0){ return 0; } //设置去从地存储结果 Set set = new HashSet(); //定义记录最大长度的值 int max = 0; //定义移动的指针，用于扫描需要被求最大长度的子串 int right = 0; for(int i =0,len=s.length();i queueX = new LinkedList(); Queue queueY = new LInkedList(); queueX.offer(row); queueY.offer(col); while(!queueX.isEmpty()){ int x = queueX.poll(); int y = queueY.poll(); for(int i=0;i<4;i++){ //上下移动新的坐标 int newX = x+bx[i]; int newY = y+by[i]; if(newX>=0&&newY>=0&&newXc,输出为2，因为一次变化一个单词，a要变化到c，只需要变化一次，在字典里找到。 另一个例子 start = "hit" end="cog" dic=["hot","dot","dog","lot","log"] 变化流程是 hit->hot->dot->dog->cog 一共是五次，所以输出为5 ``` 代码实现，首先，解题思路是从start到end的变化，且这个变化一定要在给定的dic里面去获得，一次只能变化一个单词，那么**如何变换**就是一个比较关键的点，这个变化设计，从单词哪里开始改变，变换的结果符不符合要求等，而且你变换的单词可能有多重解法，例如。hit->hot ，hot不止可以变成dot，也可以变成lot，所以我们还可以有这样一条分支`hit->hot->lot->log->cog`，所以利用bfs，宽度优先搜索的概念，我们可以使用queue一层一层的将可能的路径都遍历出来，体现一个扩散的概念，和上面的小岛问题是一样的。 ``` java public int ladderLength(String start,String end,Set dict) { //只有有一步 int step = 1; if(dict==null){ return 0; } //将最后的结果先添加进去 dict.add(end); //用于bfs的队列，很重要，bfs必用的数据结构 Queue queue = new LinkedList(); //加入第一个搜索值 queue.offer(start); Set duplicate = new HashSet(); duplicate.add(start); while(!queue.isEmpty()){ //首先每次新循环，可能都有不同的路线，我们将路线记录下来 //同时，这个steps将会返回最短的路径，因为找到就会直接返回。 int size = queue.size(); steps++; for(int i =0;i nextWords = getNext(word,dict); //接着将结果添加进下一次循环 for(String next:nextWords) { if(duplicate.contains(next)) { //已经走过。不再走下一次 continue; } //变化的单词已经是end得结果，直接返回 if(next.equals(end)) { return steps; } //否则添加去寻找下一种可能 duplicate.add(next); queue.offer(next); } } } return steps; } public List getNext(String word,Set dict) { List next = new ArrayList(); //如何变换，最暴力，从a-z开始变化 for(int i ='a';i<'z';i++) { //从给定得word单词，哪个位置开始计算 for(int j=0,len=word.length();j> permute(int[] nums) { List> result = new ArrayList>(); if(nums==null) { return result; } if(nums.length==0){ result.add(new ArrayList()); return result; } // 装排列可能性的list List list = new ArrayList(); helper(result,nums,list); return result; } private void helper(List> result,int[] nums,List list) { //结束标志 if(list.size()==nums.length) { result.add(new ArrayList(list)); return; } //递归开始 for(int i=0;i> subSet(int[] nums){ List> result = new ArrayList>(); if(nums==null){ return result; } if(nums.length==0){ result.add(new ArrayList()); return result; } //老样子，准备一个容器 List list = new ArrayList(); //这里有一些改动 dfs(result,list,nums,0); return result; } private void dfs(List> result,List list,int[] nums,int pos){ //这里的终止标志和上面的排序方式会有点不一样，因为我们无法根据长度来判断 //而是每次的组合都需要记录下来 result.add(new ArrayList(list)); //然后是循环 for(int i =pos;i> solveNQueues(int n) { //放结果的 List> result = new ArrayList>(); if(n<=0){ return result; } search(result,new ArrayList(),n); return result; } public void search(List> result,List cols,int n) { //一行一行的 if(cols.size()==n){ result.add(drawChessboard(cols)); return; } for(int colIndex=0;colIndex cols,int column){ //符合不再直线，竖线，和斜角 int row = cols.size();//目前位置的， for(int rowIndex = 0;rowIndex drawChessboard(List cols) { List chessboard = new ArrayList(); for(int i=0;i0;i--){ //去除多余的空格 if(words[i]==" "){ continue; } result.add(words[i].trim()+" "); } return result.toString().trim(); } ``` ##### 第二种反转 ``` input: "Let's take LeetCode contest" output:"s'tel ekat edoCteeL tsetnoc " ``` ```java public String reverseWords(String s){ if(s==null||s.trim().length()==0){ return ""; } StringBuilder answer = new StringBuilder(); String[] words = s.trim().split(" "); for(int i=0;i=0;i--){ sb.append(s.charAt(i)); } return sb; } ``` ##### 数字转罗马 Integer to Roman `leetCode 12`有兴趣的可以看看。 ### 节有序树 What is Typeahead？ 提示词 类似于谷歌或者推特的输入关键字进行提示的功能，如果需要实现这样功能，我们应该如何下手，首先，当我们输入一个关键字的时候，实际上是需要去服务端去请求与这关键字的相关信息的，这毋庸置疑，所以这个到数据库查找可能会变成这这样。 ```mysql select * from tableName where key_word like '{inputKey}%' order by search_count limit 10 ``` 但是如果是这样利用范围查找，查找速度是很慢的，想要查找速度快，我们可以将范围查找转化为精确地查找。 ```mysql select * from tableName where key_word ='{inputKey}' order by search_count limit 10 ``` 但是，虽然like换成了=号，我们就需要响应的映射关系，例如 ```json a -> [amzon,abs,af,...] am -> [amzon,amc,amd,...] t -> [trmp,tit,...] ``` 类似这样的感觉，所以有了缓存加数据库的实现方案，首先通过统计某个准确关键字的点击次数，例如输入a，然后提示了后面的一串，但你点击`amzon`的时候，`amzon`被确定为一条有效的搜索记录，被记录，下次提示的时候，会因为搜索次数多而靠前显示。所以我们可以这样设计这个功能。 ![1613397758088](./img/1613397758088.png) DataCollection Service 负责记录这些关键字被搜索了多少次，已经相关联的prefix_key，前缀关键字的信息 ``` 搜索次数的统计 ------------- key word amzon 30b trimp 20b lol 10b ------------- 前缀关键字的组装，也要根据搜索次数来更新需要提示的顺序 a -> [amzon,abs,af,...] am -> [amzon,amc,amd,...] t -> [trmp,tit,...] 例如,abs后来的次数比amzon多了你的提升可能会变成这样 a -> [abs,amzon,af,...] ``` 而这些关键的搜索提示，会被组装成一个tire，也就是一个树结构，这个树结构每个节点都有前缀，且关联了一个列表，列表彼此成为父子节点，由dataCollection Service 进行更新，最后推送到Query Service，供他使用，提供搜索服务，为了更加方便的更新，我们可以让Query Service 提供两个tire，当一个tire更新好了，就可以切换到这个新的tire中，之前使用的tire等待下一次更新切换，如此往复，提高效率。 ![1613398501092](./img/1613398501092.png) ##### 如何实现 Trie ``` 实现一个trie，支持insert，search，startWith方法 例如： Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // return true trie.search("app"); // return false trie.startWith("app");// return true trie.insert("app"); trie.search("app"); // return true 不考虑特殊字符，也不考虑扩容的问题，只是单纯实现这个功能 ``` 首先，按照我们上面的给的提示词的逻辑，我们可以得到一些灵感，用树节点的结构来存储他们，但是这里的问题并不在于查找出对应的提示词和返回相关关键词，所以问题会变得简单。 我们使用Node节点的数据结构来存储他们。 ![1613546623997](./img/1613546623997.png) 我们通过insert来将一个完整的单词，拆解成不同的字母放入不同的**TrieNode**中，组装成一种特殊的树结构，这个树结构可能存在**层**的概念，由于有hashmap存在，在第一次查找确定存在这个字母前缀的时候，会得到对应char映射的trieNode，这个时候所映射的trieNode会有对应的childern，也就是hashMap。 因此，一个完整的单词如果insert进来，他的存储的结构是这样的。 ![1613547343940](./img/1613547343940.png) ```java class TrieNode{ char c; HashMap children = new HashMap(); boolean hasWord; public TrieNode(){ } public TrieNode(char c){ this.c = c; } } public class Trie{ //一切开始的源头 private TrieNode root; public Trie(){ root = new TrieNode(); } public void insert(String word){ //拿到当前的节点 TrieNode current = root; //拿到当前节点所添加完成的映射节点 Map childern = current.childern; //拆分单词 char[] wordArray = word.toCharArray(); for(int i = 0,len=wordArray.length;i childern = root.childern; char[] wordArray = word.toCharArray(); for(int i =0,len=wordArray.length;i childern = root.childern; char[] wordArray = word.toCharArray(); for(int i =0,len=wordArray.length;i childern; boolean hasWord = false; //下面的扩展 String[] hitWordList = []//...? 与之关联的提示词，。之后也需要需要考虑根据 // DataCollection 的内容进行更新他们的前后顺序 } ``` #### 什么是并查集 what is Union Find? 一种用于解决，集合，查询，合并的数据结构。 ![1613568275456](./img/1613568275456.png) 例如有上图两个公司，公司A有领导B和两个下属A与C，公司B有领导E，和两个下属F与G，那么我们可以说A与C的父级是B，并且ABC是属于同一家公司。很明显，公司B和公司A并没有关联关系，ABC与EFG是单独地两个公司。这个时候这两个公司有个不成文的规定，那就是同一家公司得人不能谈恋爱，那么请问，A与F能不能谈恋爱。答案很明显，是肯定的，因为他们最高领导不同，且不再同一家公司。这个时候公司A收购了公司B。 ![1613568541722](./img/1613568541722.png) 现在E的领导变成了B，也就是说大体上来说，他们变成了同一家公司了，且大家最大的领导是一致的，拥有了相同的组件。那么这个时候A和F就是不能谈恋爱了。 那么我们设计一个这个的数据结构来阐述他们的过程，该数据结构拥有`find`方法和`union`合并方法。和可以通过寻找某个员工是否拥有相同父类。 那么关于如何查找，有递归和非递归的方法来查找，但是这里有一个问题，这里只有两家公司还好，如果有更多的公司得话，一旦树节点的深度高了后，可能会爆栈，所以还是使用非递归的方法比较好，所谓地非递归就是使用迭代的方法进行查找。 ```java class UnionFind { /** 这个map将每个节点作为key对应的value是他们的最终父级 */ Map father = new HashMap(); public UnionFind(int n){ //初始化，每个节点都是自己得father for(int i =0;i father = new HashMap(); /* 传入行列，构建一个特殊的集合关系，这个集合包含了 海域中所有点的归属关系 */ public UnionFind(int row,int colum){ for(int i=0;i numsIsLands(int n,int m,Point[] operators){ List result = new ArrayList(); if(operators==null||operators.length==0){ return result; } //初始化关键的数据结构，并查集 UnionFind unionFind = new UnionFind(n,m); //初始化相关的表示已经放过地岛屿 boolean[][] isLand = new boolean[][]; int[] dx = {0,0,1,-1}; int[] dy = {1,-1,0,0}; int count = 0; //计算落下的这点的变化 for(Point point:operators){ int x = point.x; int y = point.y; //如果这个已经是岛屿了，那么我们就忽略它 if(!isLand[x][y]){ // 是海洋的话，就使用他 //首先将他变成岛屿 isLand[x][y] = true; //岛屿的数量增加 count++; //然后我们需要判断，现在所加的点是不是可以和之前的点连成一片 // 首先获得唯一标识 int id = unionFind.convertedId(x,y,m); //接着我们上下左右的去寻找，是否存在是岛屿且还没有被合并的地方 for(int i=0;i<4;i++){ int current_x = x+dx[i]; int current_y = y+dy[i]; //判断是否合法 if(current_x>=0&¤t_x=0&¤t_y 1 一个楼梯只有上一层，只有一种解法 n=2-> 2 （11,2） 两个台阶，可以一步一步上，也可以一次上两层，这就是两种 n=3-> 3 (111,12,21) 三个台阶，有三种走法 n=4-> 5 (1111,112,121,211,22) 四个台阶 5种解法 n=5-> 8 (11111,1112,1121,1211,2111,122,212,221) 8 种 ... ``` 从n=3，也就是从台阶数目是3开始，差不多下一个数是前两个数的合，3之前都是和台阶数相同得数目。 首先第一种解法是，采用dfs的方式，也就是递归，所谓的一条路走到黑。 ```java /* 传入楼梯的个数 */ public int climbStairs(int n){ // n为3之前的数都为台阶数 if(n<=3){ return n; } //dfs return climbStairs(n-1)+climbStairs(n-2); } ``` 但是dfs还是一个问题，由于递归问题，栈深地问题，所以我们需要使用动态规划来优化这个算法。 ```java public int climbStairs(int n){ if(n<=3){ return n; } int[] ns = new int[n+1]; ns[1]=1; ns[2]=2; for(int i=3;i wordsDict){ Set dict = new HashSet(); for(String word:wordsDict){ dict.add(word); } boolean[] canSegment = new boolean[s.length()+1]; //初始化值 canSegment[0] = true; // 开头的位置 设置成可以分割，用来启动循环 int largetLengthWord = getLarget(dic); for(int i =1;i dic){ int max = 0; for(String word:dic){ max =Max.max(max,word.length()); } return max; } /* l e e t c o d e canSengment 1 0 0 0 1 0 0 0 1 index 0 1 2 3 4 5 6 7 8 **/ ```