Du Yao's blog

查找数字x是否在有序数组中(无重复)key 左闭右闭区间 left<=right 无重复 123456789101112131415161718192021// 查找数字x是否在有序数组中,无重复public static int f1(int[] a, int x) { int left = 0; int right = a.length - 1; int mid = ... 阅读全文...

子数组的最大和及系列问题子数组的最大累加和问题给定一个数组arr，返回子数组的最大累加和。例如，arr=[1,-2,3,5,-2,6,-1]，所有的子数组中，[3,5,-2,6]可以累加出最大的和12，所以返回12。 思路时间复杂度O(n)使用max记录当前和的最大值和sum记录当前的和 sum < 0 -> 舍弃前面的，sum = 当前值 sum >= 0 -> 累加每次更新完sum，要更新max 代码12345678910111213141516171819public static int getMaxSum(int[] a) { //记录当前的和 int sum = 0; //记录最大值 int maxNum = Integer.MIN_VALUE; for (int i = 0; i < a.length; i++) { //如果和小于0，说明加上正数或会变大，但是仍然起副作用 //因此直接丢掉，使得sum为当前值，注意不是0，因为可能所有数字都是负数 if (sum < 0) { sum = a[i]; } else { //和大于0，可以继续累加 sum += a[i]; } //每次算完和，要更新max，这样才能记录下最大值 maxNum = Math.max(maxNum, sum); } return maxNum;} 阅读全文...

子数组累加和系列问题题目给定一个无序数组arr，其中元素可正、可负、可0，再给定一个整数k，求arr所有的子数组中累加和为k的最长子数组长度。 思路如果暴力的算就是遍历所有子数组，求所有和为k的长度，求出最大，时间复杂度是o(n*n)还可以用sum表示所有以i结尾的数组的和，如果sum[i]-k=sum[j]，则说明(j,i]的区间上的和是k那么可以用hashMap记录下所有出现的和的第一次，然后每次进行比较则可以算出时间复杂度是O(n) 阅读全文...

最长的可整合子数组的长度先给出可整合数组的定义。如果一个数组在排序之后，每相邻两个数差的绝对值都为1，则该数组为可整合数组。例如，[5,3,4,6,2]排序之后为[2,3,4,5,6]，符合每相邻两个数差的绝对值都为1，所以这个数组为可整合数组。给定一个整型数组arr，请返回其中最大可整合子数组的长度。例如，[5,5,3,2,6,4,3]中最大可整合子数组为[5,3,2,6,4]，所以返回5。 思路注意是子数组，不能全排序如果按照题目中的做，应该每个子数组排序，判断是否可整合，那么时间复杂度是o(n*n*log(n)*n)但是仔细观察，可整合数组有两个规律 无重合数字 最大值 - 最小值 + 1 = 子数组长度 因此只要遍历所有n*n个子数组，找到满足以上规律的结合即可 阅读全文...

MaxTree一个数组的MaxTree定义如下：数组必须没有重复元素；MaxTree是一棵二叉树，数组的每一个值对应一个二叉树节点；包括MaxTree树在内并且在其中的每一颗子树上，值最大的节点都是树的头； 给定一个没有重复元素的数组arr，写出生成这个数组的MaxTree的函数，要求如果数组长度为N，时间复杂度O(N)，额外空间复杂度O(N) 思路该树并不是堆，因为不是平衡的，只是有性质任意子树的头结点比任何结点的值都大 leftMap和rightMap本题使用leftMap和rightMap分别记录当前结点左边第一个比它大的结点和当前结点右边第一个比它大的结点这个记录过程是利用栈来实现的，栈中必须满足从堆底到堆顶是从小到大的顺序先从左向右遍历，如果当前结点比堆顶小就直接进入，否则就弹出，直到可以进入为止，弹出的过程就记录比当前结点大的结点然后从右向左遍历，同理 建树建树的过程就是利用leftMap和rightMap遍历所有结点，找到其lNode和rNode 都不空，选择较小的为父，因为较大的可能被选为根节点 有一个空，选择不空的为父 都空，自己就是头 阅读全文...

设计可以变更的缓存结构设计一种缓存结构，该结构在构造时确定大小，假设大小为 K 功能： set(key,value)：将记录(key,value)插入该结构。 get(key)：返回key对应的value值。 要求: set和get方法的时间复杂度为O(1)。 某个key的set或get操作一旦发生，认为这个 key 的记录成了最经常使用的。 当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。 举例假设缓存结构的实例是cache，大小为3，并依次发生如下行为:1，cache.set(“A”,1)。最经常使用的记录为(“A”,1)。2，cache.set(“B”,2)。最经常使用的记录为(“B”,2)，(“A”,1)变为最不经常的。3，cache.set(“C”,3)。最经常使用的记录为(“C”,2)，(“A”,1)还是最不经常的。4，cache.get(“A”)。最经常使用的记录为(“A”,1)，(“B”,2)变为最不经常的。5，cache.set(“D”,4)。大小超过了 3，所以移除此时最不经常使用的记录(“B”,2)，加入记录(“D”,4)，并且为最经常使用的记录，然后(“C”,2)变为最不经常使用的记录。 思路LRU是最近最少使用页面置换算法(Least Recently Used),也就是首先淘汰最长时间未被使用的页面!LFU是最近最不常用页面置换算法(Least Frequently Used),也就是淘汰一定时期内被访问次数最少的页!比如,第二种方法的时期T为10分钟,如果每分钟进行一次调页,主存块为3,若所需页面走向为2 1 2 1 2 3 4注意,当调页面4时会发生缺页中断 按LRU算法,应换页面1(1页面最久未被使用) 按LFU算法应换页面3(十分钟内,页面3只使用了一次) 区别 LRU关键是看页面最后一次被使用到发生调度的时间长短 LFU关键是看一定时间段内页面被使用的频率 本题是LRU，使用hashMap和双端队列完成 双端队列的功能 队列头旧尾新，加入新节点从尾部加入 把其中任何一个节点移动到尾部，且不影响其他的联系 可以扔掉第一个，即最旧的，第二个就成为头结点 hashMap是完成node与key的相互映射，加速查找 cache的实现 set方法当有节点进来，进行添加或者修改，然后看窗口值是否达到门限，如果没有就添加，冰放入队头，如果达到，就删除队头，放入新节点最后把该节点移动到队尾 get方法从map中得到节点，放入队尾 阅读全文...

一种怪异的节点删除方式链表节点值类型为int型，给定一个链表中的节点node，但不给定整个链表的头节点，如何在链表中删除node？请实现这个函数,并分析这么会出现哪些问题。要求时间复杂度为O(1)。 解决方法将后一个结点的值付给前面的节点，然后将后面的节点删除 出现三个问题 如果给出的是最后一个结点，无法删除 有的结点无拷贝函数 结点具有依赖性，无法拷贝依赖性 阅读全文...

一种消息接收并打印的结构设计消息流吐出 2,一种结构接收而不打印 2,因为 1 还没出现。消息流吐出 1,一种结构接收 1,并且打印:1,2。消息流吐出 4,一种结构接收而不打印 4,因为 3 还没出现。消息流吐出 5,一种结构接收而不打印 5,因为 3 还没出现。消息流吐出 7,一种结构接收而不打印 7,因为 3 还没出现。消息流吐出 3,一种结构接收 3,并且打印:3,4,5。消息流吐出 9,一种结构接收而不打印 9,因为 6 还没出现。消息流吐出 8,一种结构接收而不打印 8,因为 6 还没出现。消息流吐出 6,一种结构接收 6,并且打印:6,7,8,9。已知一个消息流会不断地吐出整数1~N，但不一定按照顺序吐出。如果上次打印的数为i，那么当i+1出现时,请打印i+1及其之后接收过的并且连续的所有数,直到1~N全部接收并打印完，请设计这种接收并打印的结构。 应用udp和滑动窗口 思路把每一个吐出的消息都看成单独的一个集合，每当进入新的集合n时候就进行合并。与上面n-1合并，与下面的n+1合并合并的过程就是查找是否有该值，因此使用hashMap分别存放未打印的可能成为头和尾的结点然后根据即将打印的值，判断本次是否可以打印 阅读全文...

最大值减去最小值小于或等于num的子数组数量给定数组arr和整数num，返回有多少个子数组满足如下情况:max(arr[i..j]) - min(arr[i..j]) <= nummax(arr[i..j])表示子数组arr[i..j]中的最大值，min(arr[i..j])表示子数组arr[i..j]中的最小值。如果数组长度为 N，请实现时间复杂度为 O(N)的解法。 思路有两个规律 如果max(arr[i..j]) - min(arr[i..j]) <= num，那么ij往里缩，仍然满足要求因为范围缩小后，最大值只能比当前最大值小，而最小值只能比当前大，那么差值会变小，故仍满组要求 如果max(arr[i..j]) - min(arr[i..j]) > num，不满足要求，那么ij往外扩大，仍不满足要求因为范围扩大，最大值可能比当前还大，最小值可能比当前值还小，那么差值会变大，仍不满足要求 利用双端队列，利用双端队列动态记录子数组的大小值 qmax和qmin是双端队列，记录大小值的序号，且满足数组的顺序是有序的由于过程中ij一直只增不减，且到末尾就停止，相当于2n次遍历，而更新qmax和qmin时，所有的数字都是进出各一次队列，相当2n次遍历故一共4n次遍历，时间复杂度是o(n) 阅读全文...

生成窗口最大值数组有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时： [4 3 5] 4 3 3 6 7 窗口中最大值为54 [3 5 4] 3 3 6 7 窗口中最大值为54 3 [5 4 3] 3 6 7 窗口中最大值为54 3 5 [4 3 3] 6 7 窗口中最大值为44 3 5 4 [3 3 6] 7 窗口中最大值为64 3 5 4 3 [3 6 7] 窗口中最大值为7 如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。请实现一个函数，给定一个数组arr，窗口大小w。返回一个长度为n-w+1的数组res,res[i]表示每一种窗口状态下的最大值。以本题为例，结果应该返回[5,5,5,4,6,7]。 思路普通解法就是对于每个大小为w窗口都遍历，找到最大值，一共遍历n-w+1次，时间复杂度为O(w*n)O(n)解法就是利用双端队列双端队列中存放的是数组中的下标，表示的当前窗口中从大到小的最大值的下标只需要遍历一次数组，对个数组中的每个值，如果比队列中末尾值小就放入队列，否则就把队列中的最后一个值pop，直到可以放入为止。然后更新结果res，队列中的第一个值是当前的最大值，但是要注意是否在窗口范围内，如果不在，就pop，选择在窗口范围内的最大值 阅读全文...