package com.dengzm.jianzhioffer;
/**
* @Description 016 数值的整数次方
* 实现函数double power(double bas...
package com.dengzm.jianzhioffer;
/**
* @Description 016 数值的整数次方
* 实现函数double power(double base, int exponent)，求base的exponent次方。
* 不得使用库函数，同时不需要考虑大数问题。
* Created by deng on 2018/12/20.
*/
public class Jianzhi016 {
public static void main(String[] args) {
System.out.println(power(0, 20));
System.out.println(power(1, 20));
System.out.println(power(1.3, 20));
System.out.println(power(-1.3, 20));
System.out.println(power(1.3, 21));
System.out.println(power(1.3, -21));
}
//0的0次幂没有意义，且指数为负的时候无法0无法作为分母求倒数
public static double power(double base, int exponent) {
if (base == 0.0 && exponent <= 0) {
return 0.0;
}
int absExponent = exponent < 0 ? - exponent : exponent;
double absResult = powerCore(base, absExponent);
return exponent < 0 ? 1.0 / absResult : absResult;
}
//优化后的求法：
//当指数为偶数时，不需要一步步求解，而是复用上一步的操作，例如：32次幂相当于16次幂的平方；
//当指数为奇数时，例如：31次幂相当于15次幂的平方再乘以base
//根据上述方法可以写成一个递归的操作
private static double powerCore(double base, int exponent) {
if (exponent == 0) {
return 1;
}
if (exponent == 1) {
return base;
}
double result = powerCore(base, exponent >> 1);
result *= result;
if ((exponent & 0x1) == 1) {
result *= base;
}
return result;
}
}
package com.dengzm.jianzhioffer;
/**
* @Description 017 打印从1到最大的n位数
* 输入数字n，按顺序打印从1到最大的n位十进制数。
* Created by deng on 2018/12/21.
*/
public class Jianzhi017 {
public static void main(String[] args) {
print1ToMaxOfDigits(2);
print1ToMaxOfDigits(3);
}
//本题可以看成，打印每位数字0-9的全排列，高位为0的时候0不打印。
//使用递归的方式，从高位向下递归，当到达位数时，开始打印
public static void print1ToMaxOfDigits(int n) {
if (n < 0) {
return;
}
char[] numbers = new char[n];
for (int i = 0; i < 10; i ++) {
//0的ASCII码为48
numbers[0] = (char) (48 + i);
print1ToMaxOfDigitsRecursively(numbers, 0);
}
System.out.println();
}
//递归的函数体：判断index为length - 1时，已经递归所有需要的位数，故开始打印。
private static void print1ToMaxOfDigitsRecursively(char[] numbers, int index) {
if (index == numbers.length - 1) {
printNumber(numbers);
return;
}
for (int i = 0; i < 10; i ++) {
numbers[index + 1] = (char) (48 + i);
print1ToMaxOfDigitsRecursively(numbers, index + 1);
}
}
//打印函数：高位0不打印；当出现不为0的数字后，打印后续数字
private static void printNumber(char[] numbers) {
boolean isBeginning = true;
StringBuilder sb = new StringBuilder();
for (char number : numbers) {
if (isBeginning) {
if (number != \'0\') {
isBeginning = false;
}
}
if (!isBeginning) {
sb.append(number);
}
}
String result = sb.toString();
if (result.length() > 0) {
System.out.print(result + \" \");
}
}
}
package com.dengzm.jianzhioffer;
/**
* @Description 018 删除链表的节点
* Created by deng on 2018/12/21.
*/
public class Jianzhi018 {
public static void main(String[] args) {
Node head = new Node(1);
Node temp1 = new Node(2);
Node temp2 = new Node(3);
Node temp3 = new Node(4);
Node temp4 = new Node(5);
head.mNext = temp1;
temp1.mNext = temp2;
temp2.mNext = temp3;
temp3.mNext = temp4;
//题目1
//deleteNode(head, temp3);
deleteNode(head, temp4);
printList(head);
System.out.println();
//题目2
Node head1 = new Node(1);
Node temp11 = new Node(1);
Node temp12 = new Node(3);
Node temp13 = new Node(4);
Node temp14 = new Node(4);
head1.mNext = temp11;
temp11.mNext = temp12;
temp12.mNext = temp13;
temp13.mNext = temp14;
head1 = deleteDuplicatedNode(head1);
printList(head1);
}
//题目1：给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。
//链表长度为n时，删除尾节点的时间复杂度为O(n)，其他节点为O(1)，平均时间为（O(n) + (n - 1) * O(1)) / n，结果仍为O(1)
public static void deleteNode(Node mHeadNode, Node mDelNode) {
if (mHeadNode == null || mDelNode == null) {
return;
}
if (mDelNode.mNext != null) { //待删除节点不是尾节点
Node pNext = mDelNode.mNext;
mDelNode.value = pNext.value;
mDelNode.mNext = pNext.mNext;
pNext.deleteSelf();
} else if (mHeadNode == mDelNode) { //只有一个节点
mHeadNode.deleteSelf();
} else { //删除尾节点
Node temp = mHeadNode;
while (temp.mNext != mDelNode) {
temp = temp.mNext;
}
temp.mNext = null;
mDelNode.deleteSelf();
}
}
//题目2：在一个排序的链表中，删除重复的节点。例如，1->2->3->3->4->4->5,删除后为1->2->5
public static Node deleteDuplicatedNode(Node pHead) {
if (pHead == null) {
return null;
}
Node preNode = null;
Node pNode = pHead;
while (pNode != null) {
Node pNext = pNode.mNext;
if (pNext != null && pNext.value == pNode.value) {
//当两个节点值相等时，循环向后判断是否仍有相同值；
//删除所有相同节点，将后继节点与preNode拼接；
//preNode为null则头节点被删，换为新的头节点
int value = pNode.value;
Node pToBeDel = pNode;
while (pToBeDel != null && pToBeDel.value == value) {
pToBeDel = pToBeDel.mNext;
}
if (preNode == null) {
pHead = pToBeDel;
} else {
preNode.mNext = pToBeDel;
}
pNode = pToBeDel;
} else {
preNode = pNode;
pNode = pNode.mNext;
}
}
return pHead;
}
//打印链表
private static void printList(Node head) {
if (head == null) {
return;
}
while (head.mNext != null) {
System.out.println(head.value);
head = head.mNext;
}
System.out.println(head.value);
}
static class Node {
int value;
Node mNext;
Node(int value) {
this.value = value;
}
void deleteSelf() {
//TODO:删除节点
}
}
}
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
