面试算法题
题目来源于牛客网：https://www.nowcoder.com/ta/coding-interviews
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
false2、替换空格
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
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;
public class LinkList {
static class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
/**
* 单链表递归逆序，将单链表分解为首节点和其他节点
* @param head
*/
public static ListNode reverse(ListNode head){
if(head==null||head.next==null){
return head;
}
ListNode newTail=head.next;
//对其他节点进行逆序。注意：head.next指向子链表的第一个节点，逆序后指向最后一个节点
ListNode newHead=reverse(head.next);
//将头节点放到已经逆序子链表最后
newTail.next=head;
head.next=null;
return newHead;
}
public static ListNode reverseList(ListNode head){
ListNode q;
ListNode p=head.next;//p节点是当前节点
head.next=null;//断开
while(p!=null){//当前节点非空
q=p.next; //q指向下一节点
p.next=head;
head=p;
p=q;
}
return head;
}
public static void main(String[] args){
ListNode head=new ListNode(1);
ListNode p=head;
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;
p=head;
while(p!=null){
System.out.print(p.val+" ");
p=p.next;
}
System.out.println();
head=reverse(head);
p=head;
while(p!=null){
System.out.print(p.val+" ");
p=p.next;
}
System.out.println();
head=reverseList(head);
p=head;
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、重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
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、用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
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、旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
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、斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。 n<=39
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));
}
}632459868、跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2，只有3阶时，f(3)=3
最后一跳，跳1阶时，有f(n-1)种 最后一跳，跳2阶时，有f(n-2)种 所以f(n)=f(n-1)+f(n-2)
这是一个斐波那契数列
9、任意跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
最后一跳，跳1阶时，有f(n-1)种 最后一跳，跳2阶时，有f(n-2)种 … 最后一跳，跳n阶时，有f(0)=1种
所以f(n)=f(n-1)+f(n-2)+..+f(0) f(n-1)=f(n-2)+f(n-3)..+f(0) 所以，f(n)=2f(n-1)
初始值 f(0)=0 f(1)=1 f(2)=2
所以，f(n)=2f(n-1)=22f(n-2)=..=2n-1f(n-(n-1))=2n-1f(1)=2n-1
10、矩形覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
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的个数
输入一个整数，输出该数二进制表示中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、数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
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个结点
输入一个链表，输出该链表中倒数第k个结点。
两个指针，先让第一个指针和第二个指针都指向头结点，然后再让第一个指正走(k-1)步，到达第k个节点。然后两个指针同时往后移动，当第一个结点到达末尾的时候，第二个结点所在位置就是倒数第k个节点了。
public class Solution {
public static ListNode FindKthToTail(ListNode head,int k) {
ListNode p,q;
p=q=head;
if(head==null||k<=0){
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) {
//合并后的链表表头
ListNode head,p;
//p1和p2分别指向两个链表
ListNode p1=list1,p2=list2;
if(list1!=null){
head=list1;
p=head;
p1=p1.next;
}else if(list2!=null){
head=list2;
p=head;
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;
}
return head;
}
}16、树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
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 5public 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);
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-12-11 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录