刷刷编程基础题~(1)
咳咳咳，今晚开始刷剑指offer，以前做过一部分，这次认真再来一下
1.二维数组中的查找
题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路：
第一种方法：
把每一行看成有序递增的数组，
利用二分查找，
通过遍历每一行得到答案，
时间复杂度是nlogn
第二种方法：
从左下角的元素开始比较，target大的话row++，target小的话col--
//第一种
public class Solution {
public boolean Find(int [][] array,int target) {
//对每列二分检索(每列每行都一样)
for(int i=0;i<array.length;i++){
int low=0;
int high=array[0].length-1;
while(low<=high){//别忘了这里
int mid=(low+high)/2;
if(target==array[i][mid])
{
return true;
}else{
if(target>array[i][mid]){
low=mid+1;
}else{
high=mid-1;
}
}
}
}
return false;
}
}//第二种
public class Solution {
public boolean Find(int [][] array,int target) {
int row=0;
int col=array[0].length-1;
while(row<array.length&&col>=0){//边界这里其实有点问题
if(target==array[row][col]){
return true;
}else if(target>array[row][col]){
row++;
}else{
col--;
}
}
return false;
}
}2.替换空格
题目描述
请实现一个函数，将一个字符串中的空格替换成“%20”。
例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解体思路：
这种题有很多种方法，可以巧妙地用已有的方法
第一种：
(简单粗暴)正则表达式
题中给定的参数传的是StringBuffer类的，先str.toString()转化为String类【那个括号不要忘了】
然后用String类的replaceAll("\s","%20");
s表示空格，前面的 用来转义第二个
！！注意：replaceAll方法返回一个String，而不是更改原来的字符串，所以要新定义一个String a=s.replaceAll("","")
第二种：
转化为String类后，在转化成char[]数组，遍历，声明一个StingBuffer类，遇到空格，加上%20，否则加原来的字符
//第一种
public class Solution {
public String replaceSpace(StringBuffer str) {
return str.toString().replaceAll("\s", "%20");
}
}//第二种
public class Solution {
public String replaceSpace(StringBuffer str) {
String s=str.toString();
char[] c=s.toCharArray();
StringBuffer sb=new StringBuffer();
for(int i=0;i<c.length;i++){
if(c[i]==' '){
sb.append("%20");
}else{
sb.append(c[i]);
}
}
return sb.toString();
}
}3.从尾到头打印链表
题目描述
输入一个链表，从尾到头打印链表每个节点的值。
输入描述:
输入为链表的表头
输出描述:
输出为需要打印的“新链表”的表头
解题思路：
第一种：
利用堆栈"先进后出"
第二种：
递归【！！！二刷的时候还不熟悉】
判断当前结点是否为空，不空的话，递归调用该函数，不停地找next，到了尾节点，其next为空，此时，将尾节点添加进list中，递归开始往回了，不停地倒着加入节点
//第一种
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack=new Stack<Integer>();
while(listNode!=null){
stack.push(listNode.val);
listNode=listNode.next;
}
ArrayList<Integer> arr=new ArrayList<Integer>();
while(!stack.isEmpty()){
arr.add(stack.pop());
}
return arr;
}
}//第二种
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> list=new ArrayList<Integer>();//在函数外面声明
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode!=null){
this.printListFromTailToHead(listNode.next);//用this调用
list.add(listNode.val);
}
return list;
}
}4.重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
解题思路：
先判断这两种遍历数组是否为空，不要用pre==null,用pre.length==0
根据题目给出的前序遍历、后序遍历数组，
首先找出根节点，然后再根据中序遍历找到左子树和右子树的长度，
分别构造出左右子树的前序遍历和中序遍历序列，
最后分别对左右子树采取递归，递归跳出的条件是序列长度为1.
先序遍历第一个位置肯定是根节点node，
中序遍历的根节点位置在中间p，这样就可以知道左子树和右子树的长度
用Arrays.copyOfRange(int[] ,int from,int to)【取不到to】
递归递归【递归递归!!二刷的时候还是不够熟练】
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.*;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length==0||in.length==0){
return null;
}
TreeNode node=new TreeNode(pre[0]);
for(int i=0;i<in.length;i++){
if(pre[0]==in[i]){
node.left=reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
node.right=reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
}
}
return node;
}
}5.用两个栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
解题思路：
这个题之前整理过，主要注意的是，一个栈负责压入，一个栈负责弹出
弹出时，那个栈要保证里面是空的，从压入栈中压入后，弹出
压入时，也要保证压入栈里没有东西，这两点一样，【弹出压入这两点一样，只要实现一个就行，全都放在弹出那】
注意到要将int类型转为Integer类型！！！
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(new Integer(node));//注意到要将int类型转为Integer类型//不一定用转换，直接也行
}
public int pop() {
if(stack2.isEmpty()){//判断栈空不空，用isEmpty()！！！
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop().intValue();//注意到要将Integer类型转为int类型//不一定用转换，直接也行
}
}6.旋转数组的最小数字【有点疑惑】
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
【其实这个题就是求数组中最小元素，只是因为它自身的特性可以减小时间复杂度来求】
解题思路：
根据题意说明是一个递增数组的旋转，所以如题所示【3,4,5】，【1,2】还是局部递增的，
在这种的数组中查找，一般选择二分的方法；
基本模型有了，下面试着分析：
1.先取出中间的数值，和最后一个比较5>2 说明mid之前的某些部分旋转到了后面，
所以下次寻找 low = mid+1 开始；
2.取出的中间值要是小于high，说明mid-high之间都应为被旋转的部分，所以最小应该在mid的前面，
但是也有可能当前的mid 就是最小的值 所以下次需找的应该 从mid开始，也即high = mid 开始
3.当*mid == *high的时候，说明数组中存在着相等的数值，
可能是这样的形式 【2,2,2,2,1,2】所以应该选择的high 应该递减1 作为下次寻找的上界。
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int low=0;
int high=array.length-1;
while(low<high){
int mid=low+(high-low)/2;//最好用这种，不用(high+low)/2
if(array[mid]>array[high]){
low=mid+1;
}else if(array[mid]<array[high]){
high=mid;
}else {
high=high-1;
}
}
return array[low];//返回最小
}
}7.斐波那契数列
现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39
解题思路：
迭代方法，用两个变量记录fn-1和fn-2
还有P.S. f(n) = f(n-1) + f(n-2)，第一眼看就是递归啊，简直完美的递归环境
if(n<=1)
return n;
else return Fibonacci(n-1)+Fibonacci(n-2);
public class Solution {
public int Fibonacci(int n) {
if(n<2){
return n;
}
int numfn1=0;
int numfn2=1;
int current=0;
for(int i=2;i<=n;i++){
current=numfn1+numfn2;
numfn1=numfn2;
numfn2=current;
}
return current;
}
}8.跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解题思路：
f(n) = f(n-1) + f(n-2)同上同上
最后一次可能跳一阶，可能跳两阶，
public class Solution {
public int JumpFloor(int target) {
if(target<=2){
return target;
}
int f1=2;// 当前台阶后退一阶的台阶的跳法总数(初始值当前台阶是第3阶)
int f2=1;// 当前台阶后退二阶的台阶的跳法总数(初始值当前台阶是第3阶)
int current=0;
for(int i=3;i<=target;i++){
current=f1+f2;
f2=f1;//后退一阶在下一次迭代变为后退两阶
f1=current;// 当前台阶在下一次迭代变为后退一阶
}
return current;
}
}9.变态跳台阶
题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
求该青蛙跳上一个n级的台阶总共有多少种跳法。
题目解析：
重要的是分析化简，，，
关于本题，前提是n个台阶会有一次n阶的跳法。分析如下:
f(1) = 1
f(2) = f(2-1) + f(2-2) //f(2-2) 表示2阶一次跳2阶的次数。
f(3) = f(3-1) + f(3-2) + f(3-3)
...
f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)
说明：
1）这里的f(n) 代表的是n个台阶有一次1,2,...n阶的 跳法数。
2）n = 1时，只有1种跳法，f(1) = 1
3) n = 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1） ，f(2) = f(2-1) + f(2-2)
4) n = 3时，会有三种跳得方式，1阶、2阶、3阶，
那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)
因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)
5) n = n时，会有n中跳的方式，1阶、2阶...n阶，得出结论：
f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)
6) 由以上已经是一种结论，但是为了简单，我们可以继续简化：
f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
可以得出：
f(n) = 2*f(n-1)
7) 得出最终结论,在n阶台阶，一次有1、2、...n阶的跳的方式时，总得跳法为：
| 1 ,(n=0 )
f(n) = | 1 ,(n=1 )
| 2*f(n-1),(n>=2)
【注！！】
也可以看成，最后一步走1，2，3，n阶
则f(n)=f(n-1)+f(n-2)+....+f(n-n);
而f(n-1)刚好等于f(n-2)+...f(n-n)
所以得出f(n)=2*f(n-1)
public class Solution {
public int JumpFloorII(int target) {
if (target <= 0) {
return -1;
} else if (target == 1) {
return 1;
} else {
return 2 * JumpFloorII(target - 1);
}
}
}10.矩形覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。
请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
解题思路
依旧是斐波那契数列
2*n的大矩形，和n个2*1的小矩形
其中target*2为大矩阵的大小
有以下几种情形：
1、target = 1大矩形为2*1，只有一种摆放方法，return1；
2、target = 2 大矩形为2*2，有两种摆放方法，return2；
3、target = n 分为两步考虑：
如果第一格竖着放，只占一个格，还剩n-1格 f(target-1)种方法
如果前两格横着放两个，占两个格，还剩n-2格 f(target-2)种方法
public class Solution {
public int RectCover(int target) {
if(target==0||target==1||target==2){
return target;
}else if(target<0){return -1;}
else{
return RectCover(target-1)+RectCover(target-2);
}
}
}
11.二进制中1的个数
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
解题思路：
第一种：
如果一个整数不为0，那么这个整数至少有一位是1。
如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，
原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。
举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。
减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.
我们发现减1的结果是把最右边的一个1开始的所有位都取反了。
这个时候如果我们再把原来的整数和减去1之后的结果做与运算，
从原来整数最右边一个1那一位开始所有位都会变成0。
如1100&1011=1000.
也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.
那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
第二种：
Java自带的函数
Java.lang.Integer.bitCount()方法
统计参数i转成2进制后有多少个1
【要不是这道题还真不知道这个函数呢】
第三种：
把这个数逐次 右移 然后和1 与,
就得到最低位的情况,其他位都为0,
如果最低位是0和1与 之后依旧 是0，如果是1，与之后还是1。
对于32位的整数 这样移动32次 就记录了这个数二进制中1的个数了
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n!= 0){
count++;
n = n & (n - 1);//!!与运算
}
return count;
}
}public class Solution {
public int NumberOf1(int n) {
return Integer.bitCount(n);
}
}
//这个方法也是很6的
public class Solution {
public int NumberOf1(int n) {
return Integer.toBinaryString(n).replaceAll("0","").length(); }
}
public class Solution {
public int NumberOf1(int n) {
int count=0;
for(int i=0;i<32;i++){
if((n>>i&1)==1){//！！！注意这里用i标记，每次循环，就重新右移i位
count++;
}
}
return count;
}
}12.数值的整数次方
题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
解题思路：
第一种：
咳咳，Java自带的函数~
第二种：
算法的本质就是模拟数学规律，我们可以先模拟一下幂运算就是乘法的连乘，那么用算法写出来，然后再考虑几个测试用例的极端情况，如exponent==0或者exponent<0的情况，然后按逻辑写出你的代码
public class Solution {
public double Power(double base, int exponent) {
return Math.pow(base,exponent);
}
}public class Solution {
public double Power(double base, int exponent) {
if(exponent==0){
return 1;
}else if(exponent>0){
double num=base;
for(int i=1;i<exponent;i++){
num=num*base;
}
return num;
}else{
double num2=base;
int flag=-exponent;
for(int i=1;i<flag;i++){
num2=num2*base;
}
num2=1/num2;
return num2;
}
}
}13.调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解题思路：
第一种：
空间换时间，创建一个数组，奇数从头放，偶数从奇数个数的末尾开始放
或者，直接两个数组
第二种：
在一个数组中，类似冒泡算法，前偶后奇数就交换
import java.util.*;
public class Solution {
public void reOrderArray(int [] array) {
ArrayList<Integer> odd=new ArrayList<Integer>();//奇数
ArrayList<Integer> even=new ArrayList<Integer>();//偶数
for(int i=0;i<array.length;i++){
if(array[i]%2==0){
even.add(array[i]);
}else{
odd.add(array[i]);
}
}
for(int i=0;i<odd.size();i++){
array[i]=odd.get(i);
}
for(int i=odd.size();i<array.length;i++){
array[i]=even.get(i-odd.size());
}
}
}public class Solution {
public void reOrderArray(int [] array) {
for(int i=0;i<array.length;i++){
for(int j=array.length-1;j>i;j--){
if(array[j]%2==1&&array[j-1]%2==0){
int temp=array[j];
array[j]=array[j-1];
array[j-1]=temp;
}
}
}
}
}14.链表中倒数第k个结点
题目描述
输入一个链表，输出该链表中倒数第k个结点。
解题思路：
两个指针，先让第一个指针和第二个指针都指向头结点，然后再让第一个指针走(k-1)步，到达第k个节点。然后两个指针同时往末尾移动，当第一个结点到达末尾的时候，第二个结点所在位置就是倒数第k个节点了
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null||k<=0){
return null;
}
ListNode pre=head;//先走的那个
ListNode last=head;//之后走的那个人
for(int i=1;i<k;i++){//先让第一个走到k
if(pre.next!=null){//k大于链长就返回空
pre=pre.next;
}else{
return null;
}
}
while(pre.next!=null){
pre=pre.next;
last=last.next;
}
return last;
}
}15.反转链表
题目描述
输入一个链表，反转链表后，输出链表的所有元素。
解题思路：
三个指针，先记录当前结点的下一个节点
让当前结点指向前一个节点，
让前一个节点取代当前节点，因为还要继续向下走
让当前节点挪到下一个节点的位置，这是已经继续向下走了
循环，当前节点为空时，正好前一个节点为最后一个节点，而且所有节点的指向已经都反转过来了
1-->2-->3-->4-->5
1<--2<--3<--4<--5
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode pre=null;
ListNode next=null;
ListNode cur=head;
while(cur!=null){
next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
}16.合并两个排序的链表
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解题思路：
第一种
新建一个头节点用来存储新的链表
比较两个链表的值，哪个小就放到新链表中
第二种：
递归
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode head=new ListNode(0);//必须new一个，构造函数必须有参数
head.next=nul;//有没有这个都行
ListNode root=head;//head是要跟着动的，留一个root是不动的，最后返回时要用
while(list1!=null&&list2!=null){
if(list1.val<list2.val){
head.next=list1;//head是最前面一个无用的节点，从list1或者list2开始
head=list1;//之后head还有list1节点继续往后挪,!!!!head和list1一块往后移，
list1=list1.next;
}else{
head.next=list2;
head=list2;
list2=list2.next;
}
}
//把未结束的链表连接到合并后的链表尾部
if(list1!=null){
head.next=list1;
}
if(list2!=null){
head.next=list2;
}
return root.next;//其实没有办法确定第一个节点是谁，所以从第一个节点前面的节点声明，最后结果是root.next
}
}/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1==null){return list2;}
else if(list2==null){return list1;}
ListNode head=null;
if(list1.val<list2.val){
head=list1;
head.next=Merge(list1.next,list2);
}else{
head=list2;
head.next=Merge(list2.next,list1);
}
return head;
}
}17.树的子结构
题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
解题思路：
1、首先设置标志位result = false，因为一旦匹配成功result就设为true，
剩下的代码不会执行，如果匹配不成功，默认返回false
2、递归思想
如果根节点相同则递归调用DoesTree1HaveTree2（），
如果根节点不相同，则判断tree1的左子树和tree2是否相同，再判断右子树和tree2是否相同
3、注意null的条件，HasSubTree中，如果两棵树都不为空才进行判断，
DoesTree1HasTree2中，如果Tree2为空，则说明第二棵树遍历完了，即匹配成功，
tree1为空有两种情况
（1）如果tree1为空&&tree2不为空说明不匹配，
（2）如果tree1为空，tree2为空，说明匹配。
1.首先需要递归pRoot1树，找到与pRoot2根一样的节点，这需要一个遍历
2.找到相同的根节点后，要判断是否子树，仍需要一个一个遍历对比
树的遍历我们一般就用递归来做，那么根据分析需要两个递归函数如下：
!!!!!关于树的问题还要再加强!!!!
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result=false;
//当tree1和tree2都不为空是，才进行比较，否则直接返回false
if(root1!=null&&root2!=null){
//如果找到了对应tree2的根节点
if(root1.val==root2.val){
//以这个根节点为起点判断是否包含tree2
result=DoesTree1HaveTree2(root1,root2);
}
//如果找不到，那么就再去root1的左儿子当作起点
if(!result){
result=HasSubtree(root1.left,root2);
}
//如果还找不到，那么就再去root1的有儿子当作起点
if(!result){
result=HasSubtree(root1.right,root2);
}
}
return result;
}
//判断tree1是否包含tree2
public static boolean DoesTree1HaveTree2(TreeNode node1,TreeNode node2){
//如果tree1已经遍历完了，都能对应的上，返回true
if(node2==null){
return true;
}
//如果tree2还没有遍历完，tree1却遍历完了，返回false
if(node1==null){
return false;
}
//如果其中有一个点没有对应上，返回false
if(node1.val!=node2.val){
return false;
}
//如果根节点对应的上，那么久分别去自子节点里面匹配
return DoesTree1HaveTree2(node1.right,node2.right)&&DoesTree1HaveTree2(node1.left,node2.left);
}
}
18.二叉树的镜像
题目描述
操作给定的二叉树，将其变换为源二叉树的镜像。
解题思路：
第一种：
递归，关于树的很多都可以用递归来解
第二种：
非递归
层次遍历
用一个栈，压入根节点，弹出后交换其左右子树，再将左右子树压入，直到遍历完所有节点
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
public void Mirror(TreeNode root) {
if(root == null){
return;
}
//用堆栈
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);//压入根节点
while(!stack.isEmpty()){
TreeNode node = stack.pop();
//至少有一边子树不为空时，交换左右子树
if(node.left != null||node.right != null){
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
//左子树不为空时，把左子数压入栈中
if(node.left!=null){
stack.push(node.left);
}
//右子树不为空时，把右子树压入栈中
if(node.right!=null){
stack.push(node.right);
}
}
}
}
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root!=null){//!要记得判断要不然出不去了
TreeNode temp=null;
temp=root.right;
root.right=root.left;
root.left=temp;
Mirror(root.right);
Mirror(root.left);
}
}
}19.顺时针打印矩阵【等下再看，，】
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，
例如，如果输入如下矩阵：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
解题思路：
把绕的每一圈拆成四步
可以用所有数字来衡量，当所有数字都走完就退出
！！增加一种方法！！
一圈一圈打印
import java.util.ArrayList;
public class Solution {
static ArrayList<Integer> list=new ArrayList<Integer>();
public static ArrayList<Integer> printMatrix(int [][] matrix) {
int r1=0;
int c1=0;
int r2=matrix.length-1;
int c2=matrix[0].length-1;
while(r1<=r2&&c1<=c2){
printEdge(matrix,r1++,c1++,r2--,c2--);
}
return list;
}
public static void printEdge(int[][] matrix,int r1,int c1,int r2,int c2){
if(r1==r2){//只有一行
for(int i=c1;i<=c2;i++){
list.add(matrix[r1][i]);
}
}else if(c1==c2){//只有一列
for(int i=r1;i<=r2;i++){
list.add(matrix[i][c1]);
}
}else{
int curr=r1;
int curc=c1;
while(curc!=c2){
list.add(matrix[r1][curc]);
curc++;
}
while(curr!=r2){
list.add(matrix[curr][c2]);
curr++;
}
while(curc!=c1){
list.add(matrix[r2][curc]);
curc--;
}
while(curr!=r1){
list.add(matrix[curr][c1]);
curr--;
}
}
}
}
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> ls = new ArrayList<Integer>();
int colStart = 0;
int colEnd = matrix[0].length;
int lineStart = 0;
int lineEnd = matrix.length;
int count = lineEnd * colEnd;
if (matrix == null)
return ls;
while (count != 0) {
for(int i = colStart;i<colEnd;i++){
ls.add(matrix[lineStart][i]);
count--;
}
lineStart++;
if(count==0)
break;
for(int i = lineStart;i<lineEnd;i++){
ls.add(matrix[i][colEnd-1]);
count--;
}
colEnd--;
if(count==0)
break;
for(int i = colEnd-1;i>=colStart;i--){
ls.add(matrix[lineEnd-1][i]);
count--;
}
lineEnd--;
if(count==0)
break;
for(int i = lineEnd-1;i>=lineStart;i--){
ls.add(matrix[i][colStart]);
count--;
}
colStart++;
if(count==0)
break;
}
return ls;
}
}
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix){
ArrayList<Integer> list=new ArrayList<Integer>();
if(matrix.length==0)
return list;
int n=matrix.length;
int m=matrix[0].length;
if(m==0)
return list;
int layer=(Math.min(m,n)-1)/2+1;
//循环几圈
for(int i=0;i<layer;i++){
//从左上到右上
for(int j=i;j<m-i;j++){
list.add(matrix[i][j]);
}
//从右上到右下
for(int k=i+1;k<n-i;k++){
list.add(matrix[k][m-1-i]);
}
//从右下到左下
//考虑奇数圈的情况，最后一圈只走了上面一行，要对最后两步进行限制
for(int j=m-i-2;(j>=i)&&(n-i-1!=i);j--){
list.add(matrix[n-i-1][j]);
}
//从左下到左上
for(int k=n-i-2;k>i&&(m-i-1!=1);k--){
list.add(matrix[k][i]);
}
}
return list;
}
}20.包含min函数的栈
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
import java.util.Stack;
public class Solution {
Stack<Integer> data=new Stack<Integer>();
Stack<Integer> min=new Stack<Integer>();
public void push(int node) {
data.push(node);
if(min.isEmpty()){//这里要注意！栈要用isEmpty(),不要用null
min.push(node);
}else{
int temp=min.pop();//这里需要知道现在的最小值，pop出来之后记得放回去
min.push(temp);
if(node<temp){
min.push(node);
}
}
}
public void pop() {//弹出这里，只用考虑弹出的那个值是不是最小值就行，不用想弹出他后，还在最小值的栈里
int num=data.pop();
int num1=min.pop();
if(num!=num1){
min.push(num1);
}
}
public int top() {
int num=data.pop();
data.push(num);
return num;
}
public int min() {
int num=min.pop();
min.push(num);
return num;
}
}21.栈的压入、弹出序列【还要看！！】
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
假设压入栈的所有数字均不相等。
例如序列1,2,3,4,5是某栈的压入顺序，
序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
（注意：这两个序列的长度是相等的）
解题思路：
借用一个辅助的栈，遍历压栈顺序，先将第一个放入栈中，这里是1，
然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1≠4，所以我们继续压栈，
直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，
直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。
举例：
入栈1,2,3,4,5
出栈4,5,3,2,1
首先1入辅助栈，此时栈顶1≠4，继续入栈2
此时栈顶2≠4，继续入栈3
此时栈顶3≠4，继续入栈4
此时栈顶4＝4，出栈4，弹出序列向后一位，此时为5，,辅助栈里面是1,2,3
此时栈顶3≠5，继续入栈5
此时栈顶5=5，出栈5,弹出序列向后一位，此时为3，,辅助栈里面是1,2,3
….
依次执行，最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
while(pushA.length==0||popA.length==0){
return false;
}
Stack<Integer> stack=new Stack<Integer>();
int index=0;
for(int i=0;i<pushA.length;i++){
stack.push(pushA[i]);
while(!stack.empty()&&stack.peek()==popA[index]){
stack.pop();
index++;
}
}
return stack.empty();
}
}22.从上往下打印二叉树
题目描述：
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
解题思路：
二叉树层次遍历
import java.util.ArrayList;
import java.util.*;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
Queue<TreeNode> queue=new LinkedList<TreeNode>();//队列里存的是TreeNode类型的节点！
ArrayList<Integer> list=new ArrayList<Integer>();
if(root==null){//为空的条件一定要考虑到！！！
return list;
}
queue.offer(root);//队列中添加最好用offer，将根节点压入队列
while(!queue.isEmpty()){//每次都会压入当前结点的左右子树，所以直到最后全都压完队列才会变空
TreeNode temp=queue.poll();//每次取出最后一个节点
//放入左右子树
if(temp.left!=null){
queue.offer(temp.left);
}
if(temp.right!=null){
queue.offer(temp.right);
}
list.add(temp.val);
}
return list;
}
}
23.二叉搜索树的后序遍历序列
题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
解题思路：
后序遍历，最后一个数是根节点
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
//数组为空时返回
if(sequence.length==0){
return false;
}
return subtree(sequence,0,sequence.length-1);
}
public static boolean subtree(int[] a,int st,int root){
//不停地分割数组，最后st>=root时说明分完了，所有的都满足要求，返回true
if(st>=root)
return true;
//最后一个数是根节点，从它前面那个数开始看
int i=root-1;
//根节点前面那个的节点开始找，找到第一个比根节点小的数
while(i>st&&a[i]>a[root]){////！！！！这里要判断i>st
i--;
}
//判断从头到刚刚找到的那个节点之间没有比根结点大的
for(int j=st;j<i;j++){///!!!!这里判断的时候j<i不能有等号！！！！！
if(a[j]>a[root]){//有的话说明不符合二叉搜索树，返回false
return false;
}
}
//判断完后分别看左右子树是否满足二叉搜索树
return subtree(a,st,i)&&subtree(a,i+1,root-1);
}
}
24.二叉树中和为某一值的路径【！！！】
题目描述
输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
解析：原来的那个不是特别好理解~再来一种
在原方法中定义好ArrayList<ArrayList<Integer>> paths，之后就一直用这个，
要用一个方法find来递归，find主要是确定当前是不是叶节点而且当前的target是不是已经等于root.val了，如果是的话把这个path放进paths结果集中
如果还没满足条件，则再递归从左右子树开始找，这里要注意，新建一个path2，复制已经放进root的path，然后左右子树用不同的path开始分头找
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
ArrayList<ArrayList<Integer>> paths=new ArrayList<ArrayList<Integer>>();
if(root==null)
return paths;
find(paths,new ArrayList<Integer>(),root,target);
return paths;
}
public void find(ArrayList<ArrayList<Integer>> paths,ArrayList<Integer> path,TreeNode root,int target){
if(root==null)
return;
path.add(root.val);
if(root.left==null&&root.right==null&&target==root.val){
paths.add(path);
return;
}
ArrayList<Integer> path2=new ArrayList<Integer>();
path2.addAll(path);
find(paths,path,root.left,target-root.val);
find(paths,path2,root.right,target-root.val);
}
}
import java.util.ArrayList;
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
private ArrayList<ArrayList<Integer>> listAll=new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> list=new ArrayList<Integer>();//声明在外面，因为一直要用
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
//递推到最后的叶节点时要用到
if(root==null){
return listAll;
}
//遍历到这个节点，啥都不管先加到list里面
list.add(root.val);
target-=root.val;//更新target
//这是说明到达符合要求的叶节点了
if(target==0&&root.left==null&&root.right==null){
listAll.add(new ArrayList<Integer>(list));//新new一个list，原来的list还要一直用
}
//向下找左子树右子树
FindPath(root.right,target);
FindPath(root.left,target);
//遍历到叶节点不符合要求，把它在list里面删掉，回退，然后再继续递归遍历
list.remove(list.size()-1);
return listAll;
}
}25.复杂链表的复制
题目描述
输入一个复杂链表
（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）
返回结果为复制后复杂链表的head。
（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
解题思路：
map关联
首先遍历一遍原链表，创建新链表（赋值label和next），用map关联对应结点；
再遍历一遍，更新新链表的random指针。（注意map中应有NULL ----> NULL的映射）
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.Set;
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
//声明一个map用来关联原来的节点和新的链表里的节点
HashMap<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
//原来的链表
RandomListNode p = pHead;
//新的链表
RandomListNode q = new RandomListNode(-1);//这里一定要这么定义，不能用null
while(p!=null){
//根据原来的链表节点的值，创建节点
RandomListNode t = new RandomListNode(p.label);
q.next = t;//把新的链表里的节点连起来
q = t;
map.put(p, q);//把原来的链表的节点和新链表里的节点关联起来
p = p.next;//向后移动
}
//取得map中的键值对
Set<Entry<RandomListNode,RandomListNode>> set = map.entrySet();
//变成set后用迭代器遍历
Iterator<Entry<RandomListNode,RandomListNode>> it = set.iterator();
while(it.hasNext()){
Entry<RandomListNode, RandomListNode> next = it.next();
//把新链表中的节点的random连上，用了get()，所以连的是新链表的节点
next.getValue().random = map.get(next.getKey().random);
}
//map中键值对里的值，是新的链表
return map.get(pHead);
}
}
26.二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点，只能调整树中结点指针的指向。
解题思路：
中序遍历，左中右
最终形成了一个串，左指针指向左边的数，右指针指向右边的数，变成横着的了
跟着程序走一遍
又看了一遍，这道题再换一种方法更好理解
解析：
核心是中序遍历的非递归算法
修改当前遍历节点的指针指向
中序遍历非递归算法是：用一个栈，从根节点开始，一直找左节点，压入栈中，没有左节点后，弹出当前结点，找它的右节点，右节点存在的话，压入栈中，再找右节点的左节点压入栈中，每次都是找不到时弹出当前栈顶节点
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
import java.util.*;
public class Solution {
public TreeNode Convert(TreeNode pRootOfTree) {
if(pRootOfTree==null)
return null;
Stack<TreeNode> stack=new Stack<TreeNode>();
TreeNode p=pRootOfTree;
TreeNode pre=null;//用于保存中序遍历的上一个节点
boolean isFirst=true;//用这个判断是不是第一次弹出节点，第一次弹出的节点是链表的首节点
TreeNode root=null;//这个是最后链表的头节点，结果返回这个就行
while(!stack.isEmpty()||p!=null){
while(p!=null){
stack.push(p);
p=p.left;//只要还有左节点，就一直压入栈中
}
p=stack.pop();//找不到左节点时，弹出栈顶元素
if(isFirst){//如果是第一次弹出
root=p;//把这个节点给root，这个就是链表的首节点了
pre=root;
isFirst=false;
}else{
pre.right=p;//和前一个节点绑定关系
p.left=pre;
pre=p;//移动
}
p=p.right;//找不到左节点后，弹出栈顶元素要进行一些操作，之后去找右节点
}
return root;
}
}/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
//!!这两个要声明在外面
TreeNode head=null;
TreeNode realhead=null;//最终形成排序链表的头
public TreeNode Convert(TreeNode pRootOfTree) {
ConvertSub(pRootOfTree);
return realhead;
}
//不返回东西，只是把每个节点的左右指针调整成平的，一个挨着一个
public void ConvertSub(TreeNode pRootOfTree){
if(pRootOfTree==null){
return;
}
//先调整左子树
ConvertSub(pRootOfTree.left);
//这一步就是确定最左边的那个realhead
if(head==null){
head=pRootOfTree;
realhead=pRootOfTree;
}else{
//以后的每一步走的都是这里
head.right=pRootOfTree;//让原来的head的右指针指向现在的根
pRootOfTree.left=head;//让现在的根的左指针指向原来的head
head=pRootOfTree;//把原来的head更新一下
}
ConvertSub(pRootOfTree.right);
}
}27.字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。
例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
结果请按字母顺序输出。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
解题思路：
有重复元素的全排列
import java.util.ArrayList;
import java.util.*;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> list=new ArrayList<String>();
if(str!=null&&str.length()>0){//哎呀呀记住一定要判断是否为空
PermutationHelper(str.toCharArray(),0,list);
Collections.sort(list);//用Collection自带的sort，这次就不用考虑顺序的问题了
}
return list;
}
public void PermutationHelper(char[] a,int start,ArrayList<String> list){
//交换到最后一个数时，将这个序列输出，添加进list中
if(start==a.length){
list.add(String.valueOf(a));//有char数组转化为String
}
for(int i=start;i<a.length;i++){
//比原来的全排列多了一个判断条件，因为可能有重复的数
if(a[i]!=a[start]||i==start){//要有i==start的判断，否则当所有元素相等时就直接都lue'guo'le
swap(a,i,start);
PermutationHelper(a,start+1,list);
swap(a,i,start);
}
}
}
public static void swap(char[] list, int start, int i) {
char temp;
temp = list[start];
list[start] = list[i];
list[i] = temp;
}
}
28.数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半
因此输出2。如果不存在则输出0。
解题思路：
用hashmap
import java.util.*;
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
HashMap<Integer,Integer> hash=new HashMap<Integer,Integer>();
for(int i=0;i<array.length;i++){
Integer temp=hash.get(array[i]);
if(temp==null){
hash.put(array[i],1);
temp=1;
}else{
hash.put(array[i],temp+1);
temp++;
}
if(temp>array.length/2){
return array[i];
}
}
return 0;
}
}29.最小的K个数【还有更好的方法，记得看一下】
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
bubble(input,input.length);
ArrayList<Integer> list=new ArrayList<Integer>();
if(input==null || input.length<=0 || input.length<k){//为空的时候一定要注意！每种情况都考虑一下
return list;
}
for(int i=0;i<k;i++){
list.add(input[i]);
}
return list;
}
public static void bubble(int[] a,int n){
for(int i=0;i<n-1;i++){
for(int j=1;j<n-i;j++){
if(a[j-1]>a[j]){
int temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
}
}
}
}
}30.整数中1出现的次数（从1到n整数中1出现的次数）
题目描述:
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？
为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。
可以很快的求出任意非负整数区间中1出现的次数。
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int count=0;//记录1出现的次数
for(int i=0;i<=n;i++){
String str=String.valueOf(i);
int len=str.length();
for(int j=0;j<len;j++){
if(str.charAt(j)=='1'){
count++;
}
}
}
return count;
}
}31.把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
解题思路：
先把整型数组换成字符串型数组，元素都变成String类型，然后给它们排序，重写Collections或者Arrays的sort方法，重新定义一下排序规则，然后直接用sort排序，排好序之后，连接起来输出
import java.util.ArrayList;
import java.util.*;
public class Solution {
public String PrintMinNumber(int [] numbers) {
int len=numbers.length;
StringBuilder sb=new StringBuilder();
String str[]=new String[len];
for(int i=0;i<len;i++){
str[i]=String.valueOf(numbers[i]);
}
Arrays.sort(str,new Comparator<String>(){
public int compare(String s1,String s2){
String c1=s1+s2;
String c2=s2+s1;
return c1.compareTo(c2);
}
});
for(int i=0;i<len;i++){
sb.append(str[i]);
}
return sb.toString();
}
}32.丑数
把只包含因子2、3和5的数称作丑数（Ugly Number）。
例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
解题思路：
后面的一个丑数是由前面某一个丑数乘以2，3，4得来的，可以用动态规划去解
public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index<=0)
return 0;
if(index==1)
return 1;
//创建一个数组保存所有的丑数
int[] a=new int[index];
a[0]=1;
int t2=0,t3=0,t5=0;最开始的时候是，这三个数哪一个也没用到
for(int i=1;i<index;i++){
a[i]=Math.min(a[t2]*2,Math.min(a[t3]*3,a[t5]*5));
if(a[i]==a[t2]*2)//确定这个数乘以2得到的，t2++记录上，
t2++;
if(a[i]==a[t3]*3)
t3++;
if(a[i]==a[t5]*5)
t5++;
}
return a[index-1];
}
}33.找出字符串中第一个只出现一次的字符
找出字符串中第一个只出现一次的字符
详细描述：
接口说明
原型：
bool FindChar(char* pInputString, char* pChar);
输入参数：
char* pInputString：字符串
输出参数（指针指向的内存区域保证有效）：
char* pChar：第一个只出现一次的字符
如果无此字符 请输出"."
输入描述:
输入一串字符,由小写字母组成
输出描述:
输出一个字符
输入例子:
asdfasdfo
输出例子:
o
解题思路：
这道题最后写成了整个程序，没有单独写接口或者函数
用hashMap，而且是LinkedHashMap!!!这个可以保持元素有序！！
import java.util.*;
public class Main{
public static char FindChar(String str){
LinkedHashMap<Character,Integer> map=new LinkedHashMap<Character,Integer>();
int n=str.length();
for(int i=0;i<n;i++){
if(map.containsKey(str.charAt(i))){//containsKey这个方法记一下
int time=map.get(str.charAt(i));//
map.put(str.charAt(i),++time);
}else{
map.put(str.charAt(i),1);
}
}
char pos='.';
int i=0;
for(;i<n;i++){
char c=str.charAt(i);
if(map.get(c)==1){
return c;//找到了就在这里返回就行
}
}
return pos;//如果没有找到，最后返回空
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
String str=sc.next();
System.out.println(FindChar(str));
}
}
}34.数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
- 上一篇：没有了
- 下一篇：没有了
