前22道题中需要二刷的有
题目4 重建二叉树
题目6 旋转数组的最小数字
题目12 数值的整次方
题目21 栈的压入弹出序列
题目1 二维数组的查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
public boolean Find(int target, int [][] array) {
if(array==null||array.length<1||array[0].length<1)
{
return false;
}
int startx=0;
int starty=array.length-1;
while(startx<array.length&&starty>-1)
{
if(array[startx][starty]>target)
{
starty--;
}else if(array[startx][starty]<target)
{
startx++;
}else
{
return true;
}
}
return false;
}总结：因为这儿二维数组都是有序的所以要利用这个条件
题目2 替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
public String replaceSpace(StringBuffer str) {
char[] chars = str.toString().toCharArray();
int count=0;
for(int i=0;i<chars.length;i++)
{
if(chars[i]==' ')
count++;
}
char[] res=new char[chars.length+count*2];//承载结果的数组，一个空格对应这个三个字符
int index=res.length-1;
for(int i=chars.length-1;i>=0;i--)//倒着走，并且使用一个全局的index走新的数组
{
if(chars[i]!=' ')
{
res[index--]=chars[i];
}else
{
res[index--]='0';
res[index--]='2';
res[index--]='%';
}
}
return String.valueOf(res);
}总结：for循环走原数组，index走新的数组
题目3 链表的逆置
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ListNode pre=null;
ListNode next=null;
while(listNode!=null)
{
next=listNode.next;
listNode.next=pre;
pre=listNode;
listNode=next;
}
ArrayList<Integer> list=new ArrayList<Integer>();
while(pre!=null)
{
list.add(pre.val);
pre=pre.next;
}
return list;
}总结：需要注意的点
1，需要提前定义的变量pre，next都是指向空的
2，最后返回的是pre，这个指向的是新的头，因为cur已经指向了null
3，我们使用next来保留下一个需要处理的结点
4，当前的结点的next指向pre
5，pre变成了当前的结点
6，当前结点变成了后面的结点
next=listNode.next;//3,
listNode.next=pre;//4,
pre=listNode;//5,
listNode=next;//6,题目4 重建二叉树 (二刷)
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if (pre == null || in == null) {
return null;
}
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < in.length; i++) {
map.put(in[i], i);
}
return preIn(pre, 0, pre.length - 1, in, 0, in.length - 1, map);
}
public static TreeNode preIn(int[] p, int pi, int pj, int[] n, int ni, int nj,
HashMap<Integer, Integer> map) {
if (pi > pj) { //base case
return null;
}
TreeNode head = new TreeNode(p[pi]);
int index = map.get(p[pi]);
head.left = preIn(p, pi + 1, pi + index - ni, n, ni, index - 1, map);
head.right = preIn(p, pi + index - ni + 1, pj, n, index + 1, nj, map);
return head;
}
}总结：
1，需要一个map，我们从前序到中序的映射，需要通过这个map
2，这个map在递归之前将中序的内容和下标依次存入
3，base case start前序 > end中序 极端情况是只有一个数的时候
4，index是我们通过映射得到的在中序的下标，index-start中序 中序中对应的左子树
题目5 两个栈实现一个队列
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int num)
{
stack1.push(num);
}
public int pop()
{
if(stack2.isEmpty())
{
while(!stack1.isEmpty())
{
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}题目6 旋转数组的最小数字 (二刷)
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
public int minNumberInRotateArray(int [] arr) {
int start=0;
int end=arr.length-1;
int mid=0;
while(start<end)
{
/*
注意这两个情况
*/
if(start+1==end) break;
if(arr[start]<arr[end]) return arr[start];
mid=(start+end)/2;
if(arr[mid]>arr[start])
{
start=mid;//为什么不使用mid+1,因为mid有可能就是最后的结果
continue;
}
if(arr[mid]<arr[start])
{
end=mid;
continue;
}
//如果是其他的情况
//start，end，min相同
while(start<=mid)
{
if(arr[start]==arr[mid])
{
start++;
}
// 3 3 4 5 3 3 3 3 3
else if(arr[start]>arr[mid])
{
return arr[mid];
}
else if(arr[start]<arr[mid])
{
return arr[start];
}
}
}
/*
5 4
3 4
最后剩下的如果是两个
*/
return Math.min(arr[start],arr[end]);
}总结：
1，最后我们剩下的是两个数字，所以需要注意的两个位置
循环条件 start<end
程序结束位置 return Math.min(arr[start],arr[end]);
2，程序最开始的 if(start+1==end) break;
3，start=mid;//为什么不使用mid+1,因为mid有可能就是最后的结果
4，特殊情况的处理，我们列举出三种情况
3 4 5 3 3 3 3 3//case 1 3 1 2 3 3 3 3 3//case 2 3 3 3 3 3 4 5 6
情况1 2 都可以直接返回，因为我们特殊情况是while(start<=end)
题目7 斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
public int Fibonacci(int n) {
if(n==0) return 0;
if(n==1||n==2) return 1;
int pre=1;
int prepre=1;
int cur=0;
for(int i=3;i<=n;i++)
{
cur=pre+prepre;
prepre=pre;
pre=cur;
}
return cur;
}题目8 跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
public int JumpFloor(int n) {
if(n==0) return 0;
if(n==1||n==2) return n;
int pre=2;
int prepre=1;
int cur=0;
for(int i=3;i<=n;i++)
{
cur=pre+prepre;
prepre=pre;
pre=cur;
}
return cur;
}题目9 疯狂跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
public class Solution {
public int JumpFloorII(int target) {
int tmp=2;
int res=1;
target=target-1;
for(;target!=0;target>>>=1)
{
if((target&1)!=0)
{
res=tmp*res;
}
tmp=tmp*tmp;
}
return res;
}
}总结：2^(n-1)
题目10 矩形覆盖
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
public class Solution {
public int RectCover(int n) {
if(n==0) return 0;
if(n==1||n==2) return n;
int pre=2;
int prepre=1;
int cur=0;
for(int i=3;i<=n;i++)
{
cur=pre+prepre;
prepre=pre;
pre=cur;
}
return cur;
}
}题目11 二进制中1的个数
public int NumberOf1(int n) {
int res=0;
while(n!=0)
{
n-=n&(~n+1);//n=n&(n-1);
res++;
}
return res;
}总结：两种写法
题目12 数值的整次方 二刷
public double Power(double base, int exponent) {
if(exponent==0 && base != 0)//情况1 非0数的0次方
return 1;
if(exponent==1)//情况2 任何数的1次方
return base;
if(base == 0 && exponent <= 0){//情况3 0的0次方没有意义
throw new RuntimeException();
}
if(base ==0 && exponent>0){ //0的次方
return 0;
}
//以上全部都是判断情况
int n= exponent;
if(exponent<0){
n = -exponent;
}
double result=Power(base,n>>1);
result*=result;
if((n&1)==1)
result*=base;
if(exponent<0)
result=1/result;
return result;
}总结：
核心代码
double result=Power(base,n>>1);
result*=result;
if((n&1)==1)
result*=base; 举一个例子
2^11
11的二进制形式为1011
我们将2^*(101)B算出来，任何让它多加一个零变成1010B，也就是自己和自己相乘，然后判断当前的为是0还是1，如果是0的话，不管，如果是1的话，我们还要多乘一个base
题目13 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
public void reOrderArray(int [] arr) {
int index=0;
int index2=0;
while(index<arr.length)
{
/*
index指向第一个偶数
index2指向第一个奇数
*/
while(index<arr.length&&(arr[index]&1)!=0)
{
index++;
}
//index 找到偶数
//index2 找到奇数
index2=index+1;
while(index2<arr.length&&(arr[index2]&1)==0)
{
index2++;
}
if(index2<arr.length)
{
int tmp=arr[index2];
for(int i=index2;i>index;i--)
{
arr[i]=arr[i-1];
}
arr[index++]=tmp;
}else
{
break;
}
}
}题目14 链表中倒数第k个结点
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null) return null;
ListNode cur=head;
int count=0;
while(cur!=null)
{
cur=cur.next;
count++;
}
if(count<k) return null;
cur=head;
while(cur!=null)
{
cur=cur.next;
k--;
count++;
}
cur=head;
for(int i=k;i!=0;i++)
{
cur=cur.next;
}
return cur;
}题目15 链表逆置
public ListNode ReverseList(ListNode head) {
ListNode next=null;
ListNode pre=null;
ListNode cur=head;
while(cur!=null)
{
next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}题目16 合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
public ListNode Merge(ListNode head1,ListNode head2) {
if(head1==null)
{
return head2;
}else if(head2==null)
{
return head1;
}
ListNode head=head1.val<head2.val?head1:head2;
ListNode cur1=head==head1?head1:head2;
ListNode cur2=head==head1?head2:head1;
ListNode next=null;
ListNode pre=null;
while(cur1!=null&&cur2!=null)
{
if(cur1.val<=cur2.val)
{
pre=cur1;
cur1=cur1.next;
}else
{
next=cur2.next;
pre.next=cur2;
cur2.next=cur1;
pre=cur2;
cur2=next;
}
}
pre.next=cur1==null?cur2:cur1;
return head;
}总结：我们的pre指针要时刻的指向上一次操作的结点，为了最后的连接
题目17 树的子结构
public boolean HasSubtree(TreeNode node1,TreeNode node2) {
if(node2==null) return false;
return isContained(node1,node2);
}
public boolean isContained(TreeNode node1,TreeNode node2) {
if (node2 == null) {
return true;
}
if (node1 == null) {
return false;
}
return isCheck(node1,node2)||isContained(node1.left,node2)||isContained(node1.right,node2);
}
public static boolean isCheck(TreeNode node1, TreeNode node2)
{
if(node2==null)
{
return true;
}
if(node1==null||node1.val!=node2.val){
return false;
}
return isCheck(node1.left,node2.left)&&isCheck(node1.right, node2.right);
}题目18 镜像二叉树
public void Mirror(TreeNode root) {
if(root==null) return ;
TreeNode tmp=root.right;
root.right=root.left;
root.left=tmp;
Mirror(root.left);
Mirror(root.right);
}题目19 顺时针打印矩阵
public ArrayList<Integer> printMatrix(int[][] arr)
{
ArrayList<Integer> list=new ArrayList<>();
int startl=0;
int startc=0;
int endl=arr.length-1;
int endc=arr[0].length-1;
while(startc<=endc&&startl<=endl)
{
printMatrixEdge(arr,startl++,startc++,endl--,endc--,list);
}
return list;
}
public static void printMatrixEdge(int[][] arr,int startl,int startc,int endl,int endc,ArrayList<Integer> list)
{
if(startl==endl)//只有一行
{
for(int i=startc;i<=endc;i++)
{
list.add(arr[startl][i]);
}
}else if(startc==endc)//只有一列
{
for(int i=startl;i<=endl;i++)
{
list.add(arr[i][startc]);
}
}else
{
int curl=startl;
int curc=startc;
while(curc<endc)
{
list.add(arr[startl][curc]);
curc++;
}
while(curl<endl)
{
list.add(arr[curl][endc]);
curl++;
}
while(curc>startc)
{
list.add(arr[endl][curc]);
curc--;
}
while(curl>startl)
{
list.add(arr[curl][startc]);
curl--;
}
}
}题目20 包含min函数的栈
private Stack<Integer> stack=new Stack<>();
private Stack<Integer> minStack=new Stack<>();
public void push(int node) {
stack.push(node);
if(stack.size()==1)
{
minStack.push(node);
}else
{
int curValue=minStack.peek();
if(curValue>=node){
minStack.push(node);
}else {
minStack.push(curValue);
}
}
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int min() {
return minStack.peek();
}题目21 栈的压入弹出序列 二刷
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
public boolean IsPopOrder(int [] lpush,int [] lpop) {
int index=0;
Stack<Integer> stack=new Stack<>();
for(int i=0;i<lpush.length;i++)
{
stack.push(lpush[i]);
while(!stack.isEmpty()&&stack.peek()==lpop[index])
{
stack.pop();
index++;
}
}
return stack.isEmpty();
}题目22 层次遍历
public ArrayList<Integer> PrintFromTopToBottom(TreeNode head) {
ArrayList<Integer> list=new ArrayList<>();
if(head==null) return list;
LinkedList<TreeNode> queue=new LinkedList<>();
queue.addLast(head);
while(!queue.isEmpty())
{
TreeNode node = queue.pollFirst();
list.add(node.val);
if(node.left!=null)
{
queue.addLast(node.left);
}
if(node.right!=null)
{
queue.addLast(node.right);
}
}
return list;
}
京公网安备 11010502036488号