剑指offer41-67

21.栈的压入弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
1.创建一个栈，模拟人工判断的方式就可；

public class Solution {public boolean IsPopOrder(int [] pushA,int [] popA) {Stack stack = new Stack();int i=1,j=0;stack.push(pushA[0]);while (!stack.empty()){if(popA[j]==(int)stack.peek()){j++;stack.pop();}else if(i==pushA.length)return false;else{stack.push(pushA[i++]);}}return true;}
}

22.从上往下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。
1.层次遍历，队列实现；注：所有都须注意边界检测。

23.二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
1.递归：刚看到没思路，后来想想后序遍历的特点；

public boolean helpVerify(int [] sequence, int start, int root){if(start >= root)return true;int key = sequence[root];int i;//找到左右子数的分界点for(i=start; i < root; i++)if(sequence[i] > key)break;//在右子树中判断是否含有小于root的值，如果有返回falsefor(int j = i; j < root; j++)if(sequence[j] < key)return false;return helpVerify(sequence, start, i-1) && helpVerify(sequence, i, root-1);}public boolean VerifySquenceOfBST(int [] sequence) {if(sequence == null || sequence.length == 0)return false;return  helpVerify(sequence, 0, sequence.length-1);}
}

2.非递归，遇到比最后一个元素大的节点，就说明它的前面都比最后一个元素小，该元素后面的所有值都必须大于最后一个值：

bool VerifySquenceOfBST(vector sequence) {if(sequence.size()==0){return false;}int sum = sequence.size()-1;int count = 0;while(sum){while(sequence[count] < sequence[sum]){++count;}while(sequence[count] > sequence[sum]){++count;}if(count < sum){return false;}--sum;count = 0;}return true;
}

3.最大最小边界约束法：从根节点出发往下走，高层祖辈节点序列就会不停地对低层未遍历节点形成一个上下限约束。
注：边界要注意and递归的三大部分：true、false、递归体。

24.二叉树中和为某一值的路径

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
1.递归。
注：list是递归最外层，不是每层递归都是新的list，不过可以每层调用时new一个；可将和转变为减，后面只需判断是否与0相等；注意list.remove这行解决的问题。

public class Solution {public ArrayList PrintFromTopToBottom(TreeNode root) {ArrayList result = new ArrayList();if(root == null)return result;Queue queue = new LinkedList();queue.offer(root);while(!queue.isEmpty()){TreeNode temp = queue.poll();result.add(temp.val);if(temp.left != null)queue.offer(temp.left);if(temp.right != null)queue.offer(temp.right);}return result;}
}

25.复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
1.map：用一个 hashmap 建立新旧链表节点的对应的结点关系；

public class Solution {public RandomListNode Clone(RandomListNode pHead){Map map =new HashMap();RandomListNode p=pHead;while (p!=null){map.put(p,new RandomListNode(p.label));p=p.next;}p=pHead;while (p!=null){map.get(p).next=map.get(p.next);map.get(p).random=map.get(p.random);p=p.next;}return map.get(pHead);}
}

2.三次遍历：遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next；拆分链表，将链表拆分为原链表和复制后的链表。

26.二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
1.线索二叉树。

public class Solution {TreeNode pre=null;public TreeNode Convert(TreeNode pRootOfTree) {if (pRootOfTree==null)return null;Convert(pRootOfTree.right);if (pre!= null){pRootOfTree.right=pre;pre.left=pRootOfTree;}pre=pRootOfTree;Convert(pRootOfTree.left);return pre;}
}

注：自己想的这种思路：

public TreeNode convert(TreeNode pRootOfTree, TreeNode behindNode) {if (pRootOfTree==null)return null;TreeNode preNode= convert(pRootOfTree.left, pRootOfTree);pRootOfTree.left = preNode;pRootOfTree.right = behindNode;p=pRootOfTree;convert(pRootOfTree.right, pRootOfTree);return pRootOfTree;}

不能实现，因为左子树和右子树对前后节点定义不同。

27.字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba（输入数字n，打印从1到最大的n位数）。
1.递归，这个题卡了半天，须注意的点有点多：

import java.util.ArrayList;
import java.util.Collections;
public class Solution {public ArrayList Permutation(String str) {ArrayList result = PermutationHelp(new StringBuilder(str));Collections.sort(result);return result;}public ArrayList PermutationHelp(StringBuilder str) {ArrayList result = new ArrayList();if (str.length() == 1) result.add(str.toString());for (int i = 0; i < str.length(); i++) {if (i== 0||str.charAt(i) != str.charAt(0)) {char x = str.charAt(i);str.setCharAt(i, str.charAt(0));str.setCharAt(0, x);ArrayList newResult = PermutationHelp(new StringBuilder(str.substring(1)));for (int j = 0; j < newResult.size(); j++)result.add(str.substring(0, 1) + newResult.get(j));x = str.charAt(i);str.setCharAt(i, str.charAt(0));str.setCharAt(0, x);}}return result;}
}

28.数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
1.用Map；
2.用preValue记录上一次访问的值，count表明当前值出现的次数，如果下一个值和当前值相同那么count++；如果不同count–，减到0的时候就要更换新的preValue值了，因为如果存在超过数组长度一半的值，那么最后preValue一定会是该值。

29.最小的K个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
1.堆排，快排；

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;public class TopK
{/*** 取最小的k个数 */public static int[] getTopKByPartition(int[] arr, int k) {if (arr == null || arr.length <= 0 || k <= 1) {return null;} int size = arr.length;int target = k;int low = 0;int high = size - 1;int mid = getMid(arr, low, high);while (mid != target) {if (mid < target) {mid = getMid(arr, mid + 1, high);} else {mid = getMid(arr, low, mid - 1);}}int[] ret = new int[target];System.arraycopy(arr, 0, ret, 0, target);return ret;}/*** 快排思想-一趟排序*/private static int getMid(int[] arr, int low, int high) {int base = arr[low];while (low < high) {// 判断条件必须加=场景，为<= 不能为<，否则数组中有相同数据时，会一直循环while (low < high && base <= arr[high]) {high--;}arr[low] = arr[high];// 判断条件必须加=场景，为>= 不能为>，否则数组中有相同数据时，会一直循环while (low < high && base >= arr[low]) {low++;}arr[high] = arr[low];}arr[low] = base;return low;}/*** 堆排序，组建一个(size+1)/2大小的最大堆 ，取到top (size+1)/2个小的值，则堆顶元素即为中位数*/public static Queue getTopKByMaxHeap(int[] arr, int k) {if (arr == null || arr.length <= 0 || k <= 1) {return null;}// 初步组建最大堆int heapSize = k;// JDK1.7 需指定初始大小，内部实现了最大堆(实现自定义从大到小排序)PriorityQueue queue = new PriorityQueue<>(heapSize, new Comparator() {@Overridepublic int compare(Integer o1, Integer o2){return o2 - o1;}});for (int i=0; i temp) {queue.poll();queue.offer(temp);}}// 返回堆顶元素return queue;}public static void main(String[] args){int[] arr = {4,5,6,1,2,0,3,7,8,9,10,1,1,1,1,1,1};System.out.println(Arrays.toString(getTopKByPartition(arr, 10)));        int[] arr2 = {4,5,6,1,2,0,3,7,8,9,10,1,1,1,1,1,1};System.out.println(getTopKByMaxHeap(arr2, 10));}
}

2.冒泡、选择，插入；

30.连续子数组的最大和

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
1.用max记录即可。

public class Solution {public int FindGreatestSumOfSubArray(int[] array) {int max = array[0];for (int i = 1; i < array.length; i++) {array[i] += array[i - 1] > 0 ? array[i - 1] : 0;max = Math.max(max, array[i]);}return max;}
}

31.整数中1出现的次数（从1到n整数中1出现的次数）

求出1_{13的整数中1出现的次数,并算出100}1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
1、感觉是数学问题，李志雄都不会，建议放弃。

public class Solution {public int NumberOf1Between1AndN_Solution(int n) {int cnt = 0;for (int m = 1; m <= n; m *= 10) {int a = n / m, b = n % m;cnt += (a + 8) / 10 * m + (a % 10 == 1 ? b + 1 : 0);}return cnt;}
}

32.把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
1.比较两个字符串s1, s2大小的时候，先将它们拼接起来，比较s1+s2,和s2+s1那个大，如果s1+s2大，那说明s2应该放前面，所以按这个规则，s2就应该排在s1前面；

public class Solution {public String PrintMinNumber(int [] numbers) {if(numbers == null || numbers.length == 0)return "";for(int i=0; i < numbers.length; i++){for(int j = i+1; j < numbers.length; j++){int sum1 = Integer.valueOf(numbers[i]+""+numbers[j]);int sum2 = Integer.valueOf(numbers[j]+""+numbers[i]);if(sum1 > sum2){int temp = numbers[j];numbers[j] = numbers[i];numbers[i] = temp;}}}String str = new String("");for(int i=0; i < numbers.length; i++)str = str + numbers[i];return str;}
}

33.丑数

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
1.维持三个指针来记录当前乘以2、乘以3、乘以5的最小值。

public class Solution {public int GetUglyNumber_Solution(int index) {if(index <= 0)return 0;int p2=0,p3=0,p5=0;//初始化三个指向三个潜在成为最小丑数的位置int[] result = new int[index];result[0] = 1;//for(int i=1; i < index; i++){result[i] = Math.min(result[p2]*2, Math.min(result[p3]*3, result[p5]*5));if(result[i] == result[p2]*2)p2++;//为了防止重复需要三个if都能够走到if(result[i] == result[p3]*3)p3++;//为了防止重复需要三个if都能够走到if(result[i] == result[p5]*5)p5++;//为了防止重复需要三个if都能够走到}return result[index-1];}
}

34.第一个只出现一次的字符

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
1.hashmap or长度为52的数组遍历两遍。（注意hashmap的使用）

35.数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
1.归并排序，参考左神。

public class Main {private int reversePair = 0; // 统计数组中的逆序对public int inversePairs(int[] array) {if (array == null) { //数组为null返回0return 0;}int len = array.length;if (len == 0) { //数组长度为0返回0return 0;}sort(array, 0, len - 1); //进行排序return reversePair;}private void sort(int[] arr, int start, int end) {if (start < end) { //利用归并排序的思想int mid = (start + end) / 2;sort(arr, start, mid);sort(arr, mid + 1, end);merger(arr, start, mid, mid + 1, end);}}    private void merger(int[] arr, int start1, int end1, int start2, int end2) { //归并排序int len = end2 - start1 + 1;int [] nums = new int[len];int k = end2 - start1 + 1;int i = end1;int j = end2;		while(i >= start1 && j >= start2){if(arr[i] > arr[j]){nums[--k] = arr[i--];reversePair = reversePair + (j - start2 + 1);}else{nums[--k] = arr[j--];}}for( ; i >= start1; i--){nums[--k] = arr[i];}for( ; j >= start2; j--){nums[--k] = arr[j];}for(int m =0; m < len; m++){arr[start1++] = nums[m];}}
}

36.两个链表的第一个公共结点

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
1.双指针法;
2.a+b==b+a；
3.左神（又有简单的map法！！！）。

37.数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。
1.二分查找（上限下限分开查找）。

class Solution {
public:int GetNumberOfK(vector nums ,int target) {int lbound = 0, rbound = 0;// 寻找上界int l = 0, r = nums.size();while (l < r) {int mid = l + (r - l) / 2;if (nums[mid] < target) {l = mid + 1;}else {r = mid;}}lbound = l;// 寻找下界l = 0, r = nums.size();while (l < r) {int mid = l + (r - l) / 2;if (nums[mid] <= target) {l = mid + 1;}else {r = mid;}}rbound = l;return rbound - lbound;}
};

38.二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
1.分治法；

class Solution {
public:int TreeDepth(TreeNode* pRoot){if (!pRoot) return 0;int lval = TreeDepth(pRoot->left);int rval = TreeDepth(pRoot->right);return max(lval, rval) + 1;}
};

2.层次遍历。

39.平衡二叉树

输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
1.递归；

public class Solution {public int depth(TreeNode root){if(root == null)return 0;int left = depth(root.left);if(left == -1)return -1; //如果发现子树不平衡之后就没有必要进行下面的高度的求解了int right = depth(root.right);if(right == -1)return -1;//如果发现子树不平衡之后就没有必要进行下面的高度的求解了if(left - right <(-1) || left - right > 1)return -1;elsereturn 1+(left > right?left:right);}public boolean IsBalanced_Solution(TreeNode root) {return depth(root) != -1;}
}

40.数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
1、哈希法；
2、位运算，假设AB是出现一次的数组。我们首先还是先异或，剩下的数字肯定是A、B异或的结果，这个结果的二进制中的1，表现的是A和B的不同的位。我们就取第一个1所在的位数，假设是第3位，接着把原数组分成两组，分组标准是第3位是否为1。如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。

41.和为S的连续正数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
1.前缀和：就是两层循环；
2.滑动窗口。

import java.util.ArrayList;/**
思路：
输入sum=20（1，2，3，4，5，6，7，8，9，10，11，12，13，14，15
1，定义两个指针，左指针从1开始，右指针从2开始
循环开始
2，求和（1+2 = 3
3，如果判断3小于20，右指针++，2变为3，求和3+3=6。循环一直到右指针=6，和为21。
4，else if 判断21大于20，左指针++，1变为2，和减去左指针值，和为21-1=20。
5，else 和与输入一样，存数。   【再把右指针++，求和，求剩余组合】
循环结束
*/
public class Solution {public ArrayList> FindContinuousSequence(int sum) {ArrayList> resp = new ArrayList<>();if(sum <= 0){return resp;}int leftP = 1;int rightP = 2;int sumVal = leftP + rightP;while(sum > rightP){if(sumVal < sum){rightP++;sumVal += rightP;} else if (sumVal > sum){sumVal -= leftP;leftP++;} else {ArrayList list = new ArrayList<>();for (int i=leftP; i<=rightP; i++) {list.add(i);}resp.add(list);rightP++;sumVal += rightP;}}return resp;}
}

42.和为S的两个数字

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
1.哈希；
2.双指针，有点像41的滑动窗口。

43.左旋转字符串

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
1.遍历，时空都为O(n)。

44.翻转单词顺序列

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
1.转换成string的字符串数组，然后拼接；
2.先整个反转，然后分单词分别反转。

45.扑克牌顺子

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
1、初始化一个set，最大值max_ = 0, 最小值min_ = 14，遍历数组， 对于大于0的整数，没有在set中出现，则加入到set中，同时更新max, min，如果出现在了set中，直接返回false，数组遍历完，最后再判断一下最大值与最小值的差值是否小于5；
2、排序+遍历。

46.孩子们的游戏(圆圈中最后剩下的数)

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数…这样下去…直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
如果没有小朋友，请返回-1
1.链表模拟；

public class Solution {public int LastRemaining_Solution(int n, int m) {if (n <= 0 || m <= 0) {return -1;}ListNode head = new ListNode(0);ListNode node = head;for (int i = 1; i < n; i++) {node.next = new ListNode(i);node = node.next;}node.next = head;int k = 0;while (node.next != node) {if (++k == m) {node.next = node.next.next;k = 0;} else {node = node.next;}}return node.val;}
}

2.递归；

class Solution {
public:int f(int n, int m) {if (n == 1) return 0;int x = f(n-1, m);return (x+m) % n;}int LastRemaining_Solution(int n, int m){if (n <= 0) return -1; return f(n,m);}
};

3.动态规划，根据2可知，f[1] = 0，f[2] = (f{1] + m) % 2，f[3] = (f[2] + m) % 3，…，f[n] = (f[n-1] + m) % n。

public class Solution {public int LastRemaining_Solution(int n, int m) {if (n <= 0 || m <= 0) {return -1;}int ans = 0;for (int i = 2; i <= n; i++) {ans = (ans + m) % n;}return ans;}
}

47.求1+2+3+…+n

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
1、改版的递归。

class Solution {
public:int Sum_Solution(int n) {bool x = n > 1 && (n += Sum_Solution(n-1)); // bool x只是为了不报错return n;}
};

48.不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
1.用异或和与计算。

49.把字符串转换成整数

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
1.注意边界。

 public int StrToInt(String str) {//最优解if(str == null || "".equals(str.trim()))return 0;str = str.trim();char[] arr = str.toCharArray();int i = 0;int flag = 1;int res = 0;if(arr[i] == '-'){flag = -1;}if( arr[i] == '+' || arr[i] == '-'){i++;}while(i Integer.MAX_VALUE/10 || res == Integer.MAX_VALUE/10 && cur >7)){return 0;}if(flag == -1 && (res > Integer.MAX_VALUE/10 || res == Integer.MAX_VALUE/10 && cur >8)){return 0;}res = res*10 +cur;i++;}else{//不是数字return 0;}}return res*flag;}public static boolean isNum(char c){return c>='0'&& c<='9';} 

50.数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
1.hashset；
2.in-place算法（记得问面试官是否可以修改原数据）：如果arr[i] != i, 交换arr[i] 和arr[arr[i]]。交换之后，如果arr[i] ！= i, 继续交换。如果交换的过程中，arr[i] == arr[arr[i]]，说明遇到了重复值；

import java.util.*;
public class Solution {public boolean duplicate(int nums[],int length,int [] duplication) {if(nums == null || length == 0){return false;}for(int i=0;i

class Solution {
public:vector multiply(const vector& A) {vector B(A.size(), 1);for (int i=1; i=0; --j) {tmp *= A[j+1]; // right[i]用tmp代替B[j] *= tmp;}return B;}
};

class Solution {
public:bool match(char* s, char* p){    // 如果 s 和 p 同时为空if (*s == '\0' && *p == '\0') return true;// 如果 s不为空， 但是 p 为空if (*p == '\0') return false;// 如果没有 '*'if (*(p+1) != '*') {if (*s != '\0' && (*s == *p || *p == '.'))return match(s+1, p+1);elsereturn false;}// 如果有 '*'else {bool ret = false;// 重复 1 次或多次if (*s != '\0' && (*s == *p || *p == '.'))ret = match(s+1, p);// 重复 0 次return ret || match(s, p+2);}}
};

import java.util.Queue;
import java.util.LinkedList;
import java.lang.Character;
public class Solution {int[] charCnt = new int[128];Queue queue = new LinkedList();//Insert one char from stringstreampublic void Insert(char ch) {if (charCnt[ch]++ == 0) //新来的单身字符，入队queue.add(ch);}//return the first appearence once char in current stringstreampublic char FirstAppearingOnce() {Character CHAR = null;char c = 0;while ((CHAR = queue.peek()) != null) {c = CHAR.charValue();if (charCnt[c] == 1) //判断是否脱单了，没脱单则输出return c;else queue.remove(); //脱单了就移出队列，它不会再回来了}return '#'; //队空，返回#}
}

public class Solution {public ListNode EntryNodeOfLoop(ListNode pHead){if(pHead == null || pHead.next == null){return null;}ListNode fast = pHead;ListNode slow = pHead;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){ListNode slow2 = pHead;while(slow2 != slow){slow2 = slow2.next;slow = slow.next;}return slow2;}}return null;}
}

public class Solution {public ListNode deleteDuplication(ListNode pHead){if(pHead == null || pHead.next == null){return pHead;}// 自己构建辅助头结点ListNode head = new ListNode(Integer.MIN_VALUE);head.next = pHead;ListNode pre = head;ListNode cur = head.next;while(cur!=null){if(cur.next != null && cur.next.val == cur.val){// 相同结点一直前进while(cur.next != null && cur.next.val == cur.val){cur = cur.next;}// 退出循环时，cur 指向重复值，也需要删除，而 cur.next 指向第一个不重复的值// cur 继续前进cur = cur.next;// pre 连接新结点pre.next = cur;}else{pre = cur;cur = cur.next;}}return head.next;}
}

public TreeLinkNode GetNext(TreeLinkNode pNode) {// 1. if (pNode.right != null) {TreeLinkNode pRight = pNode.right;while (pRight.left != null) {pRight = pRight.left;}return pRight;}// 2. if (pNode.next != null && pNode.next.left == pNode) {return pNode.next;}// 3. if (pNode.next != null) {TreeLinkNode pNext = pNode.next;while (pNext.next != null && pNext.next.right == pNext) {pNext = pNext.next;}return pNext.next;}return null;}

class Solution {
public:bool isSame(TreeNode *root1, TreeNode *root2) {if (!root1 && !root2) return true;if (!root1 || !root2) return false;return root1->val == root2->val && isSame(root1->left, root2->right) &&isSame(root1->right, root2->left);}bool isSymmetrical(TreeNode* pRoot){return isSame(pRoot, pRoot);}};

import java.util.LinkedList;
public class Solution {public ArrayList > Print(TreeNode pRoot) {LinkedList q = new LinkedList<>();ArrayList> res = new ArrayList<>();boolean rev = true;q.add(pRoot);while(!q.isEmpty()){int size = q.size();ArrayList list = new ArrayList<>();for(int i=0; i

public class Solution {public ArrayList > Print(TreeNode pRoot) {ArrayList> result = new ArrayList<>();if(pRoot == null) return result;Stack tmp = new Stack<>();Stack tmp1 = new Stack<>();tmp.add(pRoot);while(tmp.size() > 0 || tmp1.size() > 0) {ArrayList flood = new ArrayList<>();if(tmp.size() > 0) {int size = tmp.size();for(int i=0; i 0) {int size = tmp1.size();for(int i=0; i

public class SerializeTree {int index = -1;/*** 分别遍历左节点和右节点，空使用#代替，节点之间，隔开** @param root* @return*/public String Serialize(TreeNode root) {if (root == null) {return "#";} else {return root.val + "," + Serialize(root.left) + "," + Serialize(root.right);}}/*** 使用index来设置树节点的val值，递归遍历左节点和右节点，如果值是#则表示是空节点，直接返回** @param str* @return*/TreeNode Deserialize(String str) {String[] s = str.split(",");//将序列化之后的序列用，分隔符转化为数组index++;//索引每次加一int len = s.length;if (index > len) {return null;}TreeNode treeNode = null;if (!s[index].equals("#")) {//不是叶子节点 继续走 是叶子节点出递归treeNode = new TreeNode(Integer.parseInt(s[index]));treeNode.left = Deserialize(str);treeNode.right = Deserialize(str);}return treeNode;}
}

char* Serialize(TreeNode *root){string s;queue qt;qt.push(root);while (!qt.empty()){// pop operatorTreeNode *node = qt.front();qt.pop();// process null nodeif (node == nullptr){s.push_back('N');s.push_back(',');continue;}// process not null nodes += to_string(node->val);s.push_back(',');// push operatorqt.push(node->left);qt.push(node->right);}char *ret = new char[s.length() + 1];strcpy(ret, s.c_str());return ret;
}
TreeNode* Deserialize(char *str)
{if (str == nullptr) {return nullptr;}// 可用string成员函数string s(str);if (str[0] == '#') {return nullptr;}// 构造头结点queue nodes;TreeNode *ret = new TreeNode(atoi(s.c_str()));s = s.substr(s.find_first_of(',') + 1);nodes.push(ret);// 根据序列化字符串再层次遍历一遍，来构造树while (!nodes.empty() && !s.empty()){TreeNode *node = nodes.front();nodes.pop();if (s[0] == '#'){node->left = nullptr;s = s.substr(2);}else{node->left = new TreeNode(atoi(s.c_str()));nodes.push(node->left);s = s.substr(s.find_first_of(',') + 1);}if (s[0] == '#'){node->right = nullptr;s = s.substr(2);}else{node->right = new TreeNode(atoi(s.c_str()));nodes.push(node->right);s = s.substr(s.find_first_of(',') + 1);}}return ret;
}

import java.util.Stack;
public class Solution {TreeNode KthNode(TreeNode pRoot, int k){if(pRoot == null || k <= 0){return null;}Stack stack = new Stack<>(); //建立栈TreeNode cur = pRoot;//while 部分为中序遍历while(!stack.isEmpty() || cur != null){ if(cur != null){stack.push(cur); //当前节点不为null，应该寻找左儿子cur = cur.left;}else{cur = stack.pop();//当前节点null则弹出栈内元素，相当于按顺序输出最小值。if(--k == 0){ //计数器功能return cur;}cur = cur.right;}}return null;}
}

    private int cnt = 0;private PriorityQueue low = new PriorityQueue<>();// 默认维护小顶堆private PriorityQueue high = new PriorityQueue<>(new Comparator() {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}});public void Insert(Integer num) {// 数量++cnt++;// 如果为奇数的话if ((cnt & 1) == 1) {// 由于奇数，需要存放在大顶堆上// 但是呢，现在你不知道num与小顶堆的情况// 小顶堆存放的是后半段大的数// 如果当前值比小顶堆上的那个数更大if (!low.isEmpty() && num > low.peek()) {// 存进去low.offer(num);// 然后在将那个最小的吐出来num = low.poll();} // 最小的就放到大顶堆，因为它存放前半段high.offer(num);} else {// 偶数的话，此时需要存放的是小的数// 注意无论是大顶堆还是小顶堆，吐出数的前提是得有数if (!high.isEmpty() && num < high.peek()) {high.offer(num);num = high.poll();} // 大数被吐出，小顶堆插入low.offer(num);}}public Double GetMedian() {// 表明是偶数double res = 0;// 奇数if ((cnt & 1) == 1) {res = high.peek();} else {res = (high.peek() + low.peek()) / 2.0;}return res;}

public class Solution {public ArrayList maxInWindows(int [] num, int size){ArrayList list = new ArrayList<>();LinkedList stack = new LinkedList<>();if(size==0||num.length==0||size>num.length)return list;for (int i = 0; i < size; i++) {while(!stack.isEmpty()&&num[stack.peekLast()]stack.peekFirst()){stack.pollFirst();}while(!stack.isEmpty()&&num[stack.peekLast()]

boolean[] visited = null;public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {visited = new boolean[matrix.length];for(int i = 0; i < rows; i++)for(int j = 0; j < cols; j++)if(subHasPath(matrix,rows,cols,str,i,j,0))return true;return false;}public boolean subHasPath(char[] matrix, int rows, int cols, char[] str, int row, int col, int len){if(matrix[row*cols+col] != str[len]|| visited[row*cols+col] == true) return false;if(len == str.length-1) return true;visited[row*cols+col] = true;if(row > 0 && subHasPath(matrix,rows,cols,str,row-1,col,len+1)) return true;if(row < rows-1 && subHasPath(matrix,rows,cols,str,row+1,col,len+1)) return true;if(col > 0 && subHasPath(matrix,rows,cols,str,row,col-1,len+1)) return true;if(col < cols-1 && subHasPath(matrix,rows,cols,str,row,col+1,len+1)) return true;visited[row*cols+col] = false;return false;}

public class Solution {public int movingCount(int threshold, int rows, int cols) {if (rows <= 0 || cols <= 0 || threshold < 0)return 0;boolean[][] isVisited = new boolean[rows][cols];//标记int count = movingCountCore(threshold, rows, cols, 0, 0, isVisited);return count;}private int movingCountCore(int threshold,int rows,int cols,int row,int col, boolean[][] isVisited) {if (row < 0 || col < 0 || row >= rows || col >= cols || isVisited[row][col]|| cal(row) + cal(col) > threshold)return 0;isVisited[row][col] = true;return 1 + movingCountCore(threshold, rows, cols, row - 1, col, isVisited)+ movingCountCore(threshold, rows, cols, row + 1, col, isVisited)+ movingCountCore(threshold, rows, cols, row, col - 1, isVisited)+ movingCountCore(threshold, rows, cols, row, col + 1, isVisited);}private int cal(int num) {int sum = 0;while (num > 0) {sum += num % 10;num /= 10;}return sum;}
}

class Solution {
public:using pii = pair;int dir[5] = {-1, 0, 1, 0, -1};int check(int n) {int sum = 0;while (n) {sum += (n % 10);n /= 10;}return sum;}int movingCount(int sho, int rows, int cols){if (sho <= 0) {return 0;}int ret = 0;int mark[rows][cols];memset(mark, -1, sizeof(mark));queue q;q.push({0, 0});mark[0][0] = 1;while (!q.empty()) {auto node = q.front();q.pop();// 每次保证进队列的都是满足条件的坐标++ret;for (int i = 0; i < 4; ++i) {int x = node.first + dir[i];int y = node.second + dir[i + 1];if (x >= 0 && x < rows && y >= 0 && y < cols && mark[x][y] == -1) {if (check(x) + check(y) <= sho) {q.push({x, y});mark[x][y] = 1;}}}}return ret;}
};

class Solution {
public:int back_track(int n) {// n <= 4, 表明不分，长度是最大的if (n <= 4) {return n;}int ret = 0;for (int i = 1; i < n; ++i) {ret = max(ret, i * back_track(n - i));}return ret;}int cutRope(int number) {// number = 2 和 3 时，分 2 段和分 1 段的结果是不一样的，所以需要特判一下if (number == 2) {return 1;}else if (number == 3) {return 2;}return back_track(number);}
};

class Solution {public double findMedianSortedArrays(int[] A, int[] B) {int m = A.length;int n = B.length;// 保证 m <= nif (m > n) { int[] temp = A; A = B; B = temp;int tmp = m; m = n; n = tmp;}int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;while (iMin <= iMax) {int i = (iMin + iMax) / 2;int j = halfLen - i;if (i < iMax && B[j-1] > A[i]){// i偏小iMin = i + 1; }else if (i > iMin && A[i-1] > B[j]) {// i偏大iMax = i - 1;}else { // 此时i符合条件int maxLeft = 0;if (i == 0) { maxLeft = B[j-1]; }else if (j == 0) { maxLeft = A[i-1]; }else { maxLeft = Math.max(A[i-1], B[j-1]); }if ( (m + n) % 2 == 1 ) { return maxLeft; }int minRight = 0;if (i == m) { minRight = B[j]; }else if (j == n) { minRight = A[i]; }else { minRight = Math.min(B[j], A[i]); }return (maxLeft + minRight) / 2.0;}}return 0.0;}
}

public class smallSum {public static int samllSum(int[] arr) {if (arr == null||arr.length<2) {return 0 ;}return mergeSort(arr,0,arr.length-1);}public static int mergeSort(int[] arr,int L,int R) {if (L == R) {return 0;}int m=L+((R-L)>>1);return mergeSort(arr,L,m)+mergeSort(arr,m+1,R)+merge(arr, L,m,R);}public static int merge(int[] arr, int l, int m,int r) {//help用来存放临时数据int[] help=new int[r-l+1];int count=0;int index1=l;int index2=m+1;int i=0;while (index1<=m&&index2<=r) {count+=(arr[index1]

public class Ex11 {/*** 思路：* 		将matrix分为一圈一圈的小圈* 		顺时针旋转其实就是每圈中各个元素依次占位*/private static void rotate(int[][] matrix) {int tR = 0;int tC = 0;int dR = matrix.length - 1;int dC = matrix[0].length - 1;while (tR < dR) {rotateEdge(matrix, tR++, tC++, dR--, dC--);}} private static void rotateEdge(int[][] matrix, int tR, int tC, int dR, int dC) {int total = dC - tC;int temp = 0;for (int i = 0; i < total; i++) {temp = matrix[tR][tC + i];matrix[tR][tC + i] = matrix[dR - i][tC];matrix[dR - i][tC] = matrix[dR][dC - i];matrix[dR][dC - i] = matrix[tR + i][dC];matrix[tR + i][dC] = temp;}}	 
}//或者先逆时针旋转，在进行按照Y轴翻转
class Solution {public void rotate(int[][] matrix) {int n = matrix.length;for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {int tmp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = tmp;}for (int j = 0; j < n / 2; j++) {int tmp = matrix[i][j];matrix[i][j] = matrix[i][n - j - 1];matrix[i][n - j - 1] = tmp;}}}
}

class Solution {//中序遍历每一节点，将当前节点与其前驱节点进行比较TreeNode prev = null;　//记录当前节点的前驱节点private boolean inOrder(TreeNode x){if(x == null)return true;boolean left = inOrder(x.left);if(left == false)return false;if(prev != null && x.val <= prev.val)return false;prev = x; //判断当前节点后，当前节点成为前驱动节点return inOrder(x.right);}public boolean isValidBST(TreeNode root) {return inOrder(root);}
}

public static boolean isComplete(Node head){if(head == null){return true;}Queue queue = new LinkedList();boolean leaf = false;Node cur = null;Node l = null;Node r = null;queue.offer(head);while(!queue.isEmpty){cur = queue.poll();l = cur.left;r = cur.right;if((leaf && (l != null || r != null)) || (l == null && r != null)){return false;}if(l != null){queue.offer(l);}if(r != null){queue.offer(r);}else{leaf = true;}}
}

public class Test {public static void main(String[] args) {int count = 0;for (int i = 0; i < daoyu.length; i++)for (int j = 0; j < daoyu[i].length; j++)if (daoyu[i][j] == 1) {count++;lj(i, j);}System.out.println("岛屿数量为:" + count);}//递归修改附近数值static void lj(int i, int j) {daoyu[i][j] = 2;// 上边if (i - 1 >= 0 && daoyu[i - 1][j] == 1)lj(i - 1, j);// 下边if (i + 1 < daoyu.length && daoyu[i + 1][j] == 1)lj(i + 1, j);// 左边if (j - 1 >= 0 && daoyu[i][j - 1] == 1)lj(i, j - 1);// 右边if (j + 1 < daoyu[i].length && daoyu[i][j + 1] == 1)lj(i - 1, j + 1);}
}

public class Sqrt{/*** 可以使用牛顿迭代法* 首先随便猜一个近似值x，然后不断令x等于x和a/x的平均数，迭代个六七次后x的值就已经相当精确了*/public static double iter(int v,double t){int i = 0;// 首先预估一个数double random = v >> 1;while(abs((v-random*random)) > t){random = (random + v/random) >> 1;i++;}System.out.println("开根号值: "+random+"  ,循环次数: "+i);return random;}// 二分查找法public static double binarySearch(int v,double t){int i = 0;double max = v;double min = 0;double temp = v >> 1;while (abs(temp*temp-v) > t){if (temp*temp > v ){max = temp;} else if(temp*temp < v){min = temp;}temp = (min+max) >> 1;i++;}System.out.println("开根号值: "+temp+"  ,循环次数: "+i);return temp;}public static double abs(double a){return (a <= 0.0D) ? 0.0D - a : a ;}
}

class Solution {public ListNode mergeKLists(ListNode[] lists) {if(lists.length == 0)return null;if(lists.length == 1)return lists[0];if(lists.length == 2){return mergeTwoLists(lists[0],lists[1]);}int mid = lists.length/2;ListNode[] l1 = new ListNode[mid];for(int i = 0; i < mid; i++){l1[i] = lists[i];}ListNode[] l2 = new ListNode[lists.length-mid];for(int i = mid,j=0; i < lists.length; i++,j++){l2[j] = lists[i];}return mergeTwoLists(mergeKLists(l1),mergeKLists(l2));}public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode node = new ListNode(-1);ListNode tmp=node;while(l1!=null&&l2!=null){if (l1.val

class Solution {int res = Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {helper(root);return res;}private int helper(TreeNode root) {if (root == null) return 0;int left = helper(root.left); // 左子节点最大值int right = helper(root.right); // 右子节点最大值res = Math.max(left + right + root.val, res); //res 已经是 加节点后的最大值  return Math.max(0, Math.max(left, right) + root.val); // 0 和 左右节点和根节点结合的最大值,交给上层进行计算}
}

int rand7() { //已知rand5()产生0,1,2,3,4，求rand7()int a;do {a = 5*rand5() + rand5(); //产生0-24} while (a > 20); //只取0-20return a%7;}

public class Test5 {public static int value = 100;public static int[] arrays = new int[]{1,2,4,5,6,7,8,9,10,11,12,13,20,40,60,67,80,99,100};public static void main(String[] args){long a = System.currentTimeMillis();method2();System.out.println(System.currentTimeMillis()-a);}public static void method2(){Set arraysSet = new HashSet();Set duplicateSet = new HashSet();for(int i = 0; i

class Solution {public boolean isPalindrome(ListNode head) {//1.if(head==null || head.next==null){return true;}//2.ListNode middle = findMiddle(head);//3.middle.next = reverseList(middle.next);//4.ListNode p1 = head, p2 = middle.next;//5.    while (p1 != null && p2 != null && p1.val == p2.val) {p1 = p1.next;p2 = p2.next;}//6.return p2 == null;}private ListNode findMiddle(ListNode head) {if (head == null) {return null;}ListNode slow = head, fast = head.next;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}public ListNode reverseList(ListNode head) {if(head==null || head.next==null){return head;}ListNode h = reverseList(head.next);head.next.next = head;head.next = null;return h;}
}

class Solution {public int trap(int[] height) {int n = height.length, sum = 0;if(n == 0) return 0;int[] left = new int[n];int[] right = new int[n];left[0] = height[0];right[n-1] = height[n-1];for(int i = 1; i < n; i ++) {left[i] = Math.max(height[i], left[i-1]);}for(int i = n-2; i >= 0; i --) {right[i] = Math.max(height[i], right[i+1]);}//计算每一列中水滴的数量for(int i = 0; i < n; i ++) {sum += Math.min(left[i], right[i])-height[i];}return sum;}
}class Solution {public int trap(int[] height) {int left = 0, right = height.length - 1;int left_max = 0, right_max = 0;int area = 0;  while(left <= right) {if(height[left] <= height[right]) {left_max = (height[left] > left_max) ? height[left] : left_max;if(height[left] < left_max) {area = area + left_max - height[left];}left ++;} else {right_max = (height[right] > right_max) ? height[right] : right_max;if(height[right] < right_max) {area = area + right_max - height[right];}right --;}}return area;}
}

class Solution {private static class Cell implements Comparable {int row;int col;int height;public Cell(int row, int col, int height) {this.row = row;this.col = col;this.height = height;}@Overridepublic int compareTo(Cell o) {return this.height - o.height;}}public static int trapRainWater(int[][] heightMap) {if (heightMap.length <= 1 || heightMap[0].length <= 1) {// <=1行或每行<=1个元素,没法3维接水return 0;}boolean[][] visited = new boolean[heightMap.length][heightMap[0].length];// 默认被初始化为falsePriorityQueue queue = new PriorityQueue();// 小堆int waterTraped = 0;// 1.初始化把最外围圈入队for (int j = 0; j < heightMap[0].length; j++) {// 上下行queue.add(new Cell(0, j, heightMap[0][j]));queue.add(new Cell(heightMap.length - 1, j,heightMap[heightMap.length - 1][j]));visited[0][j] = true;visited[heightMap.length - 1][j] = true;}for (int i = 1; i < heightMap.length - 1; i++) {// 左右列，notice顶点不要重复添加，因此...from// 1 to length-2queue.add(new Cell(i, 0, heightMap[i][0]));queue.add(new Cell(i, heightMap[0].length - 1,heightMap[i][heightMap[0].length - 1]));visited[i][0] = true;visited[i][heightMap[0].length - 1] = true;}// 2.逐点收集雨水--通过优先队列找短板Cell lowestWall;// 最矮的墙int row, col;int[][] direction = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };// 下右上左四个方向while (!queue.isEmpty()) {lowestWall = queue.poll();for (int i = 0; i < 4; i++) {row = lowestWall.row + direction[i][0];col = lowestWall.col + direction[i][1];if (row < 0 || row > heightMap.length - 1 || col < 0|| col > heightMap[0].length - 1|| visited[row][col] == true) {// 越界检查+已经计算检查continue;}waterTraped += Math.max(lowestWall.height - heightMap[row][col], 0);// 当前单元格高

public class LRUCache2 extends LinkedHashMap {private final int MAX_CACHE_SIZE;public LRUCache2(int cacheSize) {super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);MAX_CACHE_SIZE = cacheSize;}@Overrideprotected boolean removeEldestEntry(Map.Entry eldest) {return size() > MAX_CACHE_SIZE;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();for (Map.Entry entry : entrySet()) {sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));}return sb.toString();}
}public class LRUCache1 {private final int MAX_CACHE_SIZE;private Entry first;private Entry last;private HashMap> hashMap;public LRUCache1(int cacheSize) {MAX_CACHE_SIZE = cacheSize;hashMap = new HashMap>();}public void put(K key, V value) {Entry entry = getEntry(key);if (entry == null) {if (hashMap.size() >= MAX_CACHE_SIZE) {hashMap.remove(last.key);removeLast();}entry = new Entry();entry.key = key;}entry.value = value;moveToFirst(entry);hashMap.put(key, entry);}public V get(K key) {Entry entry = getEntry(key);if (entry == null) return null;moveToFirst(entry);return entry.value;}public void remove(K key) {Entry entry = getEntry(key);if (entry != null) {if (entry.pre != null) entry.pre.next = entry.next;if (entry.next != null) entry.next.pre = entry.pre;if (entry == first) first = entry.next;if (entry == last) last = entry.pre;}hashMap.remove(key);}private void moveToFirst(Entry entry) {if (entry == first) return;if (entry.pre != null) entry.pre.next = entry.next;if (entry.next != null) entry.next.pre = entry.pre;if (entry == last) last = last.pre;if (first == null || last == null) {first = last = entry;return;}entry.next = first;first.pre = entry;first = entry;entry.pre = null;}private void removeLast() {if (last != null) {last = last.pre;if (last == null) first = null;else last.next = null;}}private Entry getEntry(K key) {return hashMap.get(key);}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();Entry entry = first;while (entry != null) {sb.append(String.format("%s:%s ", entry.key, entry.value));entry = entry.next;}return sb.toString();}class Entry {public Entry pre;public Entry next;public K key;public V value;}
}

public static int[] findMaxRight(int[] array) {if(array == null)return array;int size = array.length;int[] result = new int[size];Stack stack = new Stack<>();stack.push(0);int index = 1;while(index < size) {if(!stack.isEmpty() && array[index] > array[stack.peek()]) {result[stack.pop()] = array[index];}else {stack.push(index);index++;}}if(!stack.isEmpty())result[stack.pop()] = -1;return result;}

import java.util.Random;public class SkipList {private static final int MAX_LEVEL = 16;private int levelCount = 1;private Node head = new Node();private Random random = new Random();public Node find(int value){Node p = head;for(int i = levelCount - 1; i >= 0; i--){while(p.forwards[i] != null && p.forwards[i].data < value){p = p.forwards[i];}}if(p.forwards[0] != null && p.forwards[0].data == value) return p.forwards[0];return null;}public void insert(int value){Node p = head;int level = randomLevel();Node node = new Node();node.data = value;node.maxLevel = level;Node update[] = new Node[level];for(int i = level; i >= 0; i--){while(p.forwards[i] != null && p.forwards[i].data < value){p = p.forwards[i];}update[i] = p;}for(int i = 0; i < level; i++){node.forwards[i] = update[i].forwards[i];update[i].forwards[i] = node;}if(levelCount < level) levelCount = level;}public void delete(int value){Node[] deleteNode = new Node[MAX_LEVEL];Node p = head;for(int i = levelCount - 1; i >=0; i--){while(p.forwards[i] != null && p.forwards[i].data < value){p = p.forwards[i];}deleteNode[i] = p;}if(p.forwards[0] != null && p.forwards[0].data == value){for(int i = levelCount - 1; i >= 0; i--){if(deleteNode[i] != null && deleteNode[i].forwards[i].data == value){deleteNode[i].forwards[i] = deleteNode[i].forwards[i].forwards[i];}}}}public void printAll(){Node p = head;while(p.forwards[0] != null){System.out.print(p.forwards[0] + " ");p = p.forwards[0];}System.out.println();}private int randomLevel() {int level = 0;for(int i = 0; i < MAX_LEVEL; i++){if(random.nextInt()%2 == 1){level++;}}return level;}class Node{private int data;private Node[] forwards = new Node[MAX_LEVEL];private int maxLevel;public String toString(){StringBuilder sb = new StringBuilder();sb.append("{data: ");sb.append(data);sb.append("; level: ");sb.append(maxLevel);sb.append(" }");return sb.toString();}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！