面试11：数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
public class Solution {
static boolean flag_invalidinput = false;
public double Power(double base, int exponent) {
double result = 0.0;
//判断是否输入有效
if(equals(base, 0.0)&&exponent<0){
flag_invalidinput = true;
return 0.0;
}
int absexponent = exponent;
//判断指数是正数还是负数
if(exponent<0)
absexponent = -exponent;
result = powerUnsignedNum(base, absexponent);
//如果是负数求倒数。
if (exponent<0) {
result = 1.0/result;
}
return result;
}
public double powerUnsignedNum(double base, int absexponent){
double result = 0.0;
if(absexponent==0)
return 1;
if(absexponent==1)
return base;
result = powerUnsignedNum(base, absexponent>>1);
result = result*result;
if((absexponent&0x1)==1){
result *= base;
}
return result;
}
public boolean equals(double num1,double num2){
return (num1-num2<0.0000001)&&(num1-num2>-0.0000001)?true:false;
}
}注：
使用位运算符的效率比乘除法及求余运算效率高很多。
面试题12：打印1到最大的n位数
public void printToMaxOfNDigits(int n) {
//小于等于0，直接退出
if(n<=0){
return;
}
char[] chs = new char[n];
for (int i = 0; i < 10; i++) {
chs[0] = (char) (i +'0');
printToMaxOfNDigits(chs,n,0);
}
}
public void printToMaxOfNDigits(char[] chs,int length,int index){
if(index == length-1){
printNumber(chs);
return;
}
for (int i = 0; i < 10; i++) {
chs[index+1] = (char) (i+'0');//chs[1]='0'
printToMaxOfNDigits(chs,length,index+1);
}
}
//打印数字
public void printNumber(char[] number){
boolean isBegin = true;//假设开始为0
for (int i = 0; i < number.length; i++) {
if (isBegin&&number[i]!='0') {
isBegin = false;//设置开始不为0
}
if(!isBegin){
System.out.print(number[i]);
}
}
System.out.print("-");
}面试题13：在O(1)的时间删除链表结点
public class Demo13 {
//需要确保删除的元素在链表中
public void DeleteNode(Node head,Node deleteNode){
//要删除的节点不为空
if(deleteNode.next!=null){
Node tempNode = deleteNode.next;
deleteNode.value = tempNode.value;
deleteNode.next = tempNode.next;
tempNode.next = null;
}else if(head==deleteNode){//这里有个隐含条件了，deleteNode.next=null
head.next=null;//链表只有一个节点，删除头结点（也是尾节点）
}else {//链表有多个节点，删除的尾节点
Node temp = head;
while(temp.next!=deleteNode){
temp = temp.next;
}
temp.next = null;
deleteNode = null;
}
}
class Node{
Node next;
int value;
}
}
注：本来删除一个链表节点我们需要知道该节点的头一个节点这就需要O（n）的时间，题目要求我们要在O（1）的时间内完成。因此我们只能找到该节点的下一个节点，将值覆盖该节点，然后删除下一个节点。这题存在一个缺陷就是我们必须要确保该节点存在于该链表中。
面试题14：调整数组顺序使奇数位于偶数前面
public class Solution {
public static void reOrderArray(int [] array) {
int low=0;
int high = array.length-1;
while(high>low){
//如果是偶数，继续循环
/*while((high>low)&&(array[high]&0x1)==0){ high--; }*/
while((high>low)&&isOdd(array[high])){
high--;
}
//如果是奇数，继续循环
/*while((high>low)&&(array[low]&0x1)==1){//加上判断条件high>low，可以节约一定步骤 low++; }*/
while((high>low)&&!isOdd(array[low])){
low++;
}
if(high>low){
int temp = array[low];
array[low] = array[high];
array[high] = temp;
}
}
}
public static boolean isOdd(int num){
return (num&0x1)==0?true:false;
}
public static boolean isPlus(int num){
return num>=0?true:false;
}
}附加：
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
public class Solution {
public void reOrderArray(int [] array) {
int len = array.length;
for (int i = 0; i < len; i++) {
if((array[i]&0x1)==0){//判断是否是偶数
int j=i;
int temp = array[j];
while(j<array.length-1){
array[j] = array[j+1];
j++;
}
array[j]=temp;
len--;//表名后面已经有一个偶数了
//i=-1;//交换之后，控制i每次从第一个开始比较
i--;//相对于i=-1更优
}
}
}
}面试题15：链表中倒数第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 firstNode = head;
ListNode secordNode = head;
for (int i = 0; i < k-1; i++) {
if(secordNode.next!=null){
secordNode = secordNode.next;
}else {
return null;
}
}
while(secordNode.next!=null){
firstNode = firstNode.next;
secordNode = secordNode.next;
}
return firstNode;
}
}面试题16：反转链表
输入一个链表，反转链表后，输出链表的所有元素。
非递归版
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution
{
public ListNode ReverseList(ListNode head) {
ListNode newHead=null;
ListNode first=null;
ListNode second=head;
ListNode three=null;
if(second==null){
return second;
}
while(second!=null){
three = second.next;
if(three==null)
newHead = second;
second.next = first;
first = second;
second = three;
}
return newHead;
}
}递归版
public class Demo16 {
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public ListNode reverse(ListNode head) {
if (null == head || null == head.next) {
return head;
}
ListNode reversedHead = reverse(head.next);
head.next.next = head;
head.next = null;
return reversedHead;
}
/** * 测试 */
public static void main(String[] args) {
Demo16 demo16 = new Demo16();
ListNode node1 = demo16.new ListNode(1);
ListNode node2 = demo16.new ListNode(2);
ListNode node3 = demo16.new ListNode(3);
ListNode node4 = demo16.new ListNode(4);
ListNode node5 = demo16.new ListNode(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
ListNode reListNode = demo16.reverse(node1);
ListNode tempListNode = reListNode;
while (tempListNode!=null) {
System.out.println(tempListNode.val);
tempListNode = tempListNode.next;
}
}
}
面试题17：合并两个排序的链表
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
/*
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;
if(list2 == null)
return list1;
ListNode mergeList = null;
if(list1.val>list2.val){
mergeList = list2;
mergeList.next = Merge(list1, list2.next);
}else {
mergeList = list1;
mergeList.next = Merge(list1.next, list2);
}
return mergeList;
}
}面试题18：树的子结构
输入两颗二叉树A，B，判断B是不是A的子结构。
/** 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;
if(root1 != null && root2 !=null){
if(root1.val == root2.val){
result = DoesTree1HavaTree2(root1, root2);
}
//遍历左子树
if(!result){
result = HasSubtree(root1.left,root2);
}
//遍历右子树
if(!result){
result = HasSubtree(root1.right,root2);
}
}
return result;
}
public boolean DoesTree1HavaTree2(TreeNode root1,TreeNode root2){
//为什么要判断是否为null？ 因为该函数还会进行递归。
if (root2==null) {
return true;
}
if(root1==null){
return false;
}
if (root1.val != root2.val) {
return false;
}
return DoesTree1HavaTree2(root1.left,root2.left)
&&DoesTree1HavaTree2(root1.right,root2.right);
}
}原文链接：https://blog.csdn.net/scgaliguodong123_/article/details/48231271
本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。
还没有人抢沙发呢~