面试算法题

1、二维数组中的查找

```public class Solution {
public static boolean find(int target, int [][] array) {
int m = array.length;//行数
int n = array[0].length;//列数
//从左下角开始查找
int x=m-1;  //行号
int y=0;    //列号
while(x>=0 && y<=n-1){
if(target<array[x][y]){
x--;//上移1行
}else if(target>array[x][y]){
y++;//右移1列
}else {//查到
return true;
}
}
return false;
}

public static void main(String[] args){
int[][] array={{1,2,3,5,7,8,9,10,11},
{2,3,4,5,8,10,11,13,15},
{3,4,5,6,10,11,14,18,20},
{5,6,8,10,15,18,20,25,29},
{7,10,20,27,36,41,47,50,56},
{10,12,23,29,48,57,63,77,99}};
System.out.println(find(36,array));
System.out.println(find(19,array));
}
}```
```true
false```

2、替换空格

```public class Solution {

/**
* 偷懒方式
*/
public static String replaceSpace(StringBuffer str) {
return str.toString().replaceAll(" ", "%20");
}
/**
* 需要考察的方式
*/
public static String replaceSpace2(StringBuffer str) {
for(int i=0;i<str.length();i++){
if(' '==str.charAt(i)){
str.replace(i, i+1, "%20");
i=i+2;
}
}
return str.toString();
}

public static void main(String[] args ){
StringBuffer sb=new StringBuffer("a b cd e f g h");
System.out.println(replaceSpace(sb));
System.out.println(replaceSpace2(sb));
}
}```

3、单链表逆序的递归算法

```package test;

static class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
/**
* 单链表递归逆序，将单链表分解为首节点和其他节点
*/
}
//将头节点放到已经逆序子链表最后
}

ListNode q;
while(p!=null){//当前节点非空
q=p.next;   //q指向下一节点
p=q;
}
}

public static void main(String[] args){
p.next=new ListNode(2);
p=p.next;
p.next=new ListNode(3);
p=p.next;
p.next=new ListNode(4);
p=p.next;
p.next=new ListNode(5);
p=p.next;
p.next=new ListNode(6);
p=p.next;
p.next=new ListNode(7);
p.next.next=null;
while(p!=null){
System.out.print(p.val+" ");
p=p.next;
}
System.out.println();
while(p!=null){
System.out.print(p.val+" ");
p=p.next;
}
System.out.println();
while(p!=null){
System.out.print(p.val+" ");
p=p.next;
}
}
}```
```1 2 3 4 5 6 7
7 6 5 4 3 2 1
1 2 3 4 5 6 7 ```

4、重建二叉树

```package test;

class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}

public class BinaryTree {
public static TreeNode reConstructBinaryTree(int[] pre, int[] in) {
return createBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
}

private static TreeNode createBinaryTree(int[] pre,int startPre,int endPre,int[] in,int startIn,int endIn){
if(startPre>endPre||startIn>endIn){
return null;
}
//构造root节点,前序第一个值是根节点值
TreeNode root=new TreeNode(pre[startPre]);
int step=0;
for(int i=startIn;i<=endIn;i++){//查询root节点在中序中的位置
if(in[i]==pre[startPre]){//i是真实下标
//移动距离
step=i-startIn;
//构造左子树
root.left=createBinaryTree(pre,startPre+1,startPre+step,in,startIn,i-1);
//构造右子树
root.right=createBinaryTree(pre,startPre+step+1,endPre,in,i+1,endIn);
break;
}
}
return root;
}

public static void preOrderTraverse(TreeNode root){
if(root==null){
return ;
}
System.out.print(root.val+" ");
preOrderTraverse(root.left);
preOrderTraverse(root.right);
}

public static void inOrderTraverse(TreeNode root){
if(root==null){
return ;
}
preOrderTraverse(root.left);
System.out.print(root.val+" ");
preOrderTraverse(root.right);
}

public static void main(String[] args){
int[] pre={1,2,4,7,3,5,6,8};
int[] in={4,7,2,1,5,3,8,6};
TreeNode root=reConstructBinaryTree(pre,in);
preOrderTraverse(root);
System.out.println();
inOrderTraverse(root);
}
}```
```1 2 4 7 3 5 6 8
2 4 7 1 3 5 6 8 ```

5、用两个栈实现队列

```package test;
import java.util.Stack;
public class QueueStack {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

/**
* 当入栈的时候，将它全放进栈1中
* @param node
*/
public void push(int node) {
stack1.push(node);
}
/**
* 当需要出栈的时候，将栈1出栈到栈2中，然后再将栈2依次出栈。
* @return
*/
public int pop() {
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}

public static void main(String[] args){
QueueStack queue=new QueueStack();
queue.push(1);
queue.push(2);
System.out.print(queue.pop()+" ");
System.out.print(queue.pop()+" ");
queue.push(3);
queue.push(4);
queue.push(5);
System.out.print(queue.pop()+" ");
System.out.print(queue.pop()+" ");
System.out.print(queue.pop()+" ");
}
}```
`1 2 3 4 5 `

6、旋转数组的最小数字

```package test;
import java.util.ArrayList;

/**
* 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
* 非递减数组的一个旋转{3,4,5,1,2}
*
*/
public class ArrayDemo {
/**
* 时间复杂度O(n)
*/
public static int minNumberInRotateArray(int [] array) {
if(array.length==0){//0数组
return 0;
}
for(int i=0;i<array.length-1;i++){
if(array[i]>array[i+1]){//一般旋转情况
return array[i+1];
}
if(i==array.length-2){//特殊情况，未旋转
return array[0];
}
}
return -1;
}
/**
* 时间复杂度O(logn)
*/
public static int minNumber(int[] array) {
int low = 0 ;
int high = array.length - 1;
while(low < high){
int mid = low + (high - low) / 2;
if(array[mid]>array[high]){
low=mid+1;
}else if(array[mid]<array[high]){
high=mid;//不是mid-1
}else{//相等情况， [2,1,2,2,2,2,2] 或者[2,2,2,2,2,1,2]
high--; //无法判定在左还是在右
}
}
return array[low];
}

public static void main(String[] args){
int[] a={1,2,3,4,5};//未旋转情况
int[] b={3,4,5,1,2};
int[] c={2,1,2,2,2,2,2};
System.out.print(minNumberInRotateArray(a)+" ");
System.out.print(minNumberInRotateArray(b)+" ");
System.out.print(minNumberInRotateArray(c)+" ");
System.out.println();
System.out.print(minNumber(a)+" ");
System.out.print(minNumber(b)+" ");
System.out.print(minNumber(c)+" ");

}
}```
```1 1 1
1 1 1 ```

7、斐波那契数列

```public class Fib {
public static int fibonacci(int n) {
if(n<=0){
return 0;
}if(n<3){
return 1;
}
int f1,f2,f=0;
f1=f2=1;
for(int i=3;i<=n;i++){
f=f1+f2;
f1=f2;
f2=f;
}
return f;

}

public static void main(String[] args){
System.out.println(fibonacci(39));
}
}```
`63245986`

10、矩形覆盖

```public class Solution {
public int RectCover(int target) {
int f1=1,f2=2,f=0;
if(target==1){
return 1;
}
if(target==2){
return 2;
}
for(int i=3;i<=target;i++){
f=f1+f2;
f1=f2;
f2=f;
}
return f;
}
}```

11、二进制中1的个数

```public class Solution {
/**
* 正数的二进制中1的个数
*/
public int numberOf1(int n) {
int count=0;
while(n>0){
if( (n&1) == 1){
count++;
}
//右移1位，相当于n=n/2;
n=n >> 1;
}
return count;
}

/**
* 整数的二进制中1的个数
*/
public int countOf1(int n){
int count=0;
while(n!=0){
count++;
//每次消耗1
n=(n-1) & n;
}
return count;
}
}```

12、数值的整数次方

```import java.math.BigDecimal;
public class Solution {
public double Power(double base, int exponent) {
BigDecimal b=new BigDecimal(base);
BigDecimal result=null;
if(exponent==0){
return 1.0;
}else if(exponent<0){
result=b.pow(-exponent);
result=new BigDecimal(1).divide(result);
}else{
result=b.pow(exponent);
}
return result.doubleValue();
}
}```

13、调整数组顺序使奇数位于偶数前面

```package test;

public class ArrayDemo {
//利用插排的思想就好了，是奇数就前移。
public void reOrderArray(int [] array) {
int tmp=0;
//i指向当前元素，j指向已经查找到的最后一个奇数
for(int i=0,j=-1;i<array.length;i++){
if(array[i]%2==1){//奇数插入
tmp=array[i];
for(int k=i;k>j+1;k--){
array[k]=array[k-1];
}
array[++j]=tmp;
}
}
}
}```

14、链表中倒数第k个结点

```public class Solution {
public static ListNode FindKthToTail(ListNode head,int k) {
ListNode p,q;
return null;
}
for(int i=0;i<k-1;i++){
if(p.next!=null){
p=p.next;
}else{
return null;
}
}
while(p.next!=null){
p=p.next;
q=q.next;
}
return q;
}
}```

15、合并两个排序的链表

```public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
//合并后的链表表头
//p1和p2分别指向两个链表
ListNode p1=list1,p2=list2;
if(list1!=null){
p1=p1.next;
}else if(list2!=null){
p2=p2.next;
}else{
return null;
}

while(p1!=null&&p2!=null){
if(p1.val<=p2.val){
p.next=p1;
p=p.next;
p1=p1.next;
}else{
p.next=p2;
p=p.next;
p2=p2.next;
}
}
if(p1!=null){
p.next=p1;
}
if(p2!=null){
p.next=p2;
}

}
}```

16、树的子结构

```public class Solution {
/**
* 从当前的根节点开始的子结构判定，
*/
public static boolean isRootSubtree(TreeNode root1,TreeNode root2){
if(root2==null){
return true;
}
if(root1==null ){
return false;
}
if(root1.val!=root2.val){
return false;
}else{
return isRootSubtree(root1.left,root2.left) && isRootSubtree(root1.right,root2.right);
}

}
public static boolean HasSubtree(TreeNode root1,TreeNode root2) {
//空树不是任意一个树的子结构
if(root1==null||root2==null){
return false;
}
//以下情况是root1,root2均非空
if(HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2)){//root2是root1的子树的子结构
return true;
}else{//判定是否从根节点开始的子结构
return isRootSubtree(root1,root2);
}
}
}```

17、二叉树镜像

```源二叉树
8
/  \
6   10
/ \  / \
5  7 9  11

8
/  \
10   6
/ \  / \
11 9 7   5```
```public class Solution {
public void Mirror(TreeNode root) {
if(root==null){
return;
}
TreeNode tmp=root.left;
root.left=root.right;
root.right=tmp;
Mirror(root.left);
Mirror(root.right);
}
}```

0 条评论

• 基于WebMagic写的一个入门级CSDN博客爬虫

参考： 1、http://webmagic.io/docs/zh/ 2、http://blog.csdn.net/qq598535550/article...

• Hibernate @Transient实现临时字段映射

Hibernate @Transient实现临时字段映射 @Transient还可以在持久化类中直接获取关联表中的字段值 @Transient表示该属性并非...

• SpringCloud 2.x学习笔记：17、Spring Cloud Gateway之服务注册与发现(Greenwich版本）完整代码

一共三个模块，服务注册模块eureka-server、服务提供模块service-hello和网关模块service-gateway。

• 挑战程序竞赛系列（45）：4.1Polya 计数定理（1）

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• POJ 刷题系列：2586. Y2K Accounting Bug

POJ 刷题系列：2586. Y2K Accounting Bug 传送门：2586. Y2K Accounting Bug 题意： 有一个公司由于某个病毒使...

• POJ 刷题系列：3295. Tautology

题意： 给出二元变量 p，q，r，s，t以及运算符K，A，N，E，C，求所给运算符和变量的集合是否符合永真，若永真输出tautology，否则输出not。 思...

• 挑战程序竞赛系列（42）：4.1模运算的世界（4）

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• POJ 刷题系列：2159. Ancient Cipher

POJ 刷题系列：2159. Ancient Cipher 传送门：POJ 2159. Ancient Cipher 题意： 给定两个长度相等的字符串a, b...

• POJ 刷题系列：1936. All in All

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/...

• POJ 刷题系列：2388. Who's in the Middle

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/...