面试题16：数值的整数次方
题目：实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
算法：时间复杂度为O(logN)的快速乘方
测试：力扣
说明：exponent的范围是-2147483648-2147483647，所以取绝对值时需要强制类型转换为long
public double myPow(double base, int exponent) {
if (base == 0.0 && exponent < 0) {
return -1;
}
long absExponent = exponent >= 0 ? exponent : -(long)exponent;
double result = powerWithUnsignedExponent(base, absExponent);
if (exponent < 0) {
result = 1.0 / result;
}
return result;
}
private double powerWithUnsignedExponent(double base, long exponent) {
if (exponent == 0) {
return 1;
}
if (exponent == 1) {
return base;
}
double result = powerWithUnsignedExponent(base, exponent >> 1);
result *= result;
if ((exponent & 1) == 1) {
return result * base;
}
return result;
} 面试题17：打印1到最大的n位数
题目：输入数字n，按顺序打印出从1最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数即999。
- 算法：char数组保存大数，标记进位
public void print1ToMaxOfNDigits(int n) {
if (n <= 0) {
return;
}
char[] number = new char[n];
for (int i = 0; i < n; i++) {
number[i] = '0';
}
while (!increment(number)) {
printNumbers(number);
}
}
private boolean increment(char[] number) {
boolean isOverFlow = false;
int takeOver = 0;
int length = number.length;
for (int i = length - 1; i >= 0; i--) {
int nSum = number[i] - '0' + takeOver;
if (i == length - 1) {
nSum++;
}
if (nSum >= 10) {
if (i == 0) {
isOverFlow = true;
} else {
nSum -= 10;
takeOver = 1;
number[i] = (char) ('0' + nSum);
}
} else {
number[i] = (char) ('0'+nSum);
}
}
return isOverFlow;
}
private void printNumbers(char[] number) {
boolean isBegining0 = true;
int length = number.length;
for (int i = 0; i < length; i++) {
if (isBegining0 && number[i] != '0') {
isBegining0 = false;
}
if (!isBegining0) {
System.out.printf("%c", number[i]);
}
}
System.out.printf("\t");
} - 算法：递归打印全排列
public void print1ToMaxOfNDigits(int n) {
if (n <= 0) {
return;
}
char[] number = new char[n];
for (int i = 0; i < 10; i++) {
number[0] = (char) ('0' + i);
print1ToMaxOfNDigitsRecursive(number, 1);
}
}
private void print1ToMaxOfNDigitsRecursive(char[] number, int index) {
if (index == number.length) {
printNumbers(number);
return;
}
for (int i = 0; i < 10; i++) {
number[index] = (char) ('0' + i);
print1ToMaxOfNDigitsRecursive(number, index+1);
}
}
private void printNumbers(char[] number) {
boolean isBegining0 = true;
int length = number.length;
for (int i = 0; i < length; i++) {
if (isBegining0 && number[i] != '0') {
isBegining0 = false;
}
if (!isBegining0) {
System.out.printf("%c", number[i]);
}
}
System.out.printf("\t");
} 面试题18：删除链表的结点
题目一：在O(1)时间内删除链表的结点
题目：给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。
public ListNode deleteNode(ListNode head, ListNode toBeDeleted) {
if (head == null) {
return null;
}
if (toBeDeleted == null) {
return head;
}
if (toBeDeleted.next != null) { // toBeDeleted is not the tail node
ListNode next = toBeDeleted.next;
toBeDeleted.val = next.val;
toBeDeleted.next = next.next;
} else if (head == toBeDeleted) { // toBeDeleted is the tail node and the head
head = null;
} else { // toBeDeleted is the tail node but not the head
ListNode curr = head;
while (curr.next != toBeDeleted) {
curr = curr.next;
}
curr.next = null;
}
return head;
}
题目二：删除链表中重复的结点
题目：在一个排序的链表中，如何删除重复的结点？例如，在图3.4（a）中重复结点被删除之后，链表如图3.4（b）所示。
1 --> 2 --> 3 --> 3 --> 4 --> 4 --> 5
1 --> 2 --> 5
public ListNode deleteDuplicatedNode(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
boolean needDelete = false;
ListNode next = curr.next;
if (next != null && next.val == curr.val) {
needDelete = true;
}
if (needDelete) {
int value = curr.val;
while (next != null && next.val == value) {
next = next.next;
}
if (prev == null) {
head = next;
} else {
prev.next = next;
}
curr = next;
} else {
prev = curr;
curr = curr.next;
}
}
return head;
} 面试题19：正则表达式匹配
题目：请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"及"ab*a"均不匹配。
- 算法：动态规划
1, If p.charAt(j) == s.charAt(i): dp[i][j] = dp[i-1][j-1];
2, If p.charAt(j) == '.': dp[i][j] = dp[i-1][j-1];
3, If p.charAt(j) == '*':
here are two sub conditions:
(1) if p.charAt(j-1) != s.charAt(i) :
dp[i][j] = dp[i][j-2] // in this case, a* only counts as empty
(2) if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
dp[i][j] = dp[i-1][j] // in this case, a* counts as multiple a
or dp[i][j] = dp[i][j-1] // in this case, a* counts as single a
or dp[i][j] = dp[i][j-2] // in this case, a* counts as emptypublic boolean isMatch(String string, String pattern) {
if (string == null || pattern == null) {
return false;
}
boolean[][] dp = new boolean[string.length()+1][pattern.length()+1];
dp[0][0] = true;
for (int i = 0; i < pattern.length(); i++) {
if (pattern.charAt(i) == '*' && dp[0][i-1]) {
dp[0][i+1] = true;
}
}
for (int i = 0 ; i < string.length(); i++) {
for (int j = 0; j < pattern.length(); j++) {
if (pattern.charAt(j) == '.') {
dp[i+1][j+1] = dp[i][j];
}
if (pattern.charAt(j) == string.charAt(i)) {
dp[i+1][j+1] = dp[i][j];
}
if (pattern.charAt(j) == '*') {
if (pattern.charAt(j-1) != string.charAt(i) && pattern.charAt(j-1) != '.') {
dp[i+1][j+1] = dp[i+1][j-1];
} else {
dp[i+1][j+1] = (dp[i+1][j-1] || dp[i+1][j] || dp[i][j+1]);
}
}
}
}
return dp[string.length()][pattern.length()];
} - 算法：递归，长的字符串函数调用栈过长时会有TLE
public boolean isMatch(String string, String pattern) {
if (string == null || pattern == null) {
return false;
}
return matchCore(string, pattern);
}
private boolean matchCore(String string, String pattern) {
if (pattern.length() == 0) {
if (string.length() == 0)
return true;
else
return false;
}
boolean matchNext = string.length() != 0 && (pattern.charAt(0) == '.' || pattern.charAt(0) == string.charAt(0));
if (pattern.length() >= 2 && pattern.charAt(1) == '*') {
if (matchNext) {
return matchCore(string.substring(1), pattern.substring(2)) ||
matchCore(string.substring(1), pattern) ||
matchCore(string, pattern.substring(2));
} else {
return matchCore(string, pattern.substring(2));
}
}
if (matchNext) {
return matchCore(string.substring(1), pattern.substring(1));
}
return false;
} 面试题20：表示数值的字符串
题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串“+100”、“5e2”、“-123”、“3.1416”及“-1E-16”都表示数值，但“12e”、“1a3.14”、“1.2.3”、“+-5”及“12e+5.4”都不是
- 算法：逐个扫描并删除字符
public boolean isNumber(String s) {
if (s == null) {
return false;
}
s = s.trim();
if (s.length() == 0) {
return false;
}
StringBuilder sb = new StringBuilder(s);
boolean numeric = scanInteger(sb);
// 如果出现'.'，接下来是数字的小数部分
if (sb.length() > 0 && sb.charAt(0) == '.') {
sb.deleteCharAt(0);
// 下面一行代码用||的原因：
// 1. 小数可以没有整数部分，例如.123等于0.123；左
// 2. 小数点后面可以没有数字，例如233.等于233.0；
// 3. 当然小数点前面和后面可以有数字，例如233.666
numeric = scanUnsignedInteger(sb) || numeric;
}
// 如果出现'e'或者'E'，接下来跟着的是数字的指数部分
if (sb.length() > 0 && (sb.charAt(0) == 'E' || sb.charAt(0) == 'e')) {
sb.deleteCharAt(0);
// 下面一行代码用&&的原因：
// 1. 当e或E后面没有整数时，整个字符串不能表示数字，例如12e、12e+5.4；左
// 2. 当e或E前面没有数字时，整个字符串不能表示数字，例如.e1、e1；右
numeric = scanInteger(sb) && numeric;
}
return numeric && sb.length() == 0;
}
private boolean scanInteger(StringBuilder s) {
if (s.length() > 0 && (s.charAt(0) == '+' || s.charAt(0) == '-')) {
s.deleteCharAt(0);
}
return scanUnsignedInteger(s);
}
private boolean scanUnsignedInteger(StringBuilder s) {
boolean flag = false;
while (s.length() > 0 && s.charAt(0) >= '0' && s.charAt(0) <= '9') {
s.deleteCharAt(0);
flag = true;
}
return flag;
} - 算法：四个flag标志遍历进展
- 算法：Here
public boolean isNumber(String s) {
s = s.trim();
boolean pointSeen = false;
boolean eSeen = false;
boolean numberSeen = false;
boolean numberAfterE = true;
for(int i=0; i<s.length(); i++) {
if('0' <= s.charAt(i) && s.charAt(i) <= '9') {
numberSeen = true;
numberAfterE = true;
} else if(s.charAt(i) == '.') {
if(eSeen || pointSeen) {
return false;
}
pointSeen = true;
} else if(s.charAt(i) == 'e') {
if(eSeen || !numberSeen) {
return false;
}
numberAfterE = false;
eSeen = true;
} else if(s.charAt(i) == '-' || s.charAt(i) == '+') {
if(i != 0 && s.charAt(i-1) != 'e') {
return false;
}
} else {
return false;
}
}
return numberSeen && numberAfterE;
} 面试题21：调整数组顺序使奇数位于偶数前面
题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
说明：Java中函数式接口的功能使其可以像C++中传递函数作为参数
public int[] exchange(int[] nums) {
if (nums == null || nums.length == 0) {
return nums;
}
MyFunc isEven = (x) -> (x & 1) == 0;
return exchangeWithFunc(nums, isEven);
}
private interface MyFunc {
boolean func(int x);
}
private int[] exchangeWithFunc(int[] nums, MyFunc myFunc) {
int low = 0;
int high = nums.length - 1;
while (low < high) {
while (low < high && !myFunc.func(nums[low])) {
low++;
}
while (high > low && myFunc.func(nums[high])) {
high--;
}
if (low < high) {
int temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
}
return nums;
} 
京公网安备 11010502036488号