面试题49：丑数
题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。求按从小到大的顺序的第1500个丑数。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做第一个丑数。
- 算法：暴力
- 丑数在一直除2一直除3一直除5后结果是1
public int nthUglyNumber(int n) {
checkArguments(n);
int number = 0;
int uglyIndex = 0;
while (uglyIndex < n) {
number++;
if (isUglyNumber(number)) {
uglyIndex++;
}
}
return number;
}
public boolean isUglyNumber(int n) {
while ((n & 1) == 0) {
n >>= 1;
}
while (n % 3 == 0) {
n /= 3;
}
while (n % 5 == 0) {
n /= 5;
}
return n == 1;
} - 算法：空间换时间
- 保存结果到数组中
- 下一个丑数一定是前面的丑数分别乘2乘3乘5中的最小但又大于目前最大丑数的值
- 遍历的同时分别找到乘2乘3乘5刚好大于目前最大丑数的位置
public int nthUglyNumber(int n) {
checkArguments(n);
int[] uglyArray = new int[n];
uglyArray[0] = 1;
int multiply2Index = 0;
int multiply3Index = 0;
int multiply5Index = 0;
for (int i = 1; i < n; i++) {
uglyArray[i] = Math.min(Math.min(uglyArray[multiply2Index]*2, uglyArray[multiply3Index]*3), uglyArray[multiply5Index]*5);
if (uglyArray[multiply2Index] * 2 == uglyArray[i]) {
multiply2Index++;
}
if (uglyArray[multiply3Index] * 3 == uglyArray[i]) {
multiply3Index++;
}
if (uglyArray[multiply5Index] * 5 == uglyArray[i]) {
multiply5Index++;
}
}
return uglyArray[n-1];
} 面试题50：第一个只出现一次的字符
题目一：字符串中第一个只出现一次的字符
题目：在字符串中找出第一个只出现一次的字符。如输入"abaccdeff"，则输出'b'。
- 算法：基于数组创建简单的哈希表
- 键是ASCII码
- 值是字符出现的次数
public char firstUniqChar(String s) {
checkArguments(s);
int[] hashTable = new int[256];
for (char c : s.toCharArray()) {
hashTable[c]++;
}
for (char c : s.toCharArray()) {
if (hashTable[c] == 1) {
return c;
}
}
return ' ';
} 题目二：字符流中第一个只出现一次的字符
题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是'g'。当从该字符流中读出前六个字符"google"时，第一个只出现一次的字符是'l'。
class CharStatistics {
// occurrence[ch] = 0: ch has not been found
// occurrence[ch] >= 1: ch has been found one times and occurrence[ch] is the index+1 of ch in string stream
// occurrence[ch] = -1: ch has been found for multiple times
private int[] occurrence = new int[256];
private int index = 1;
public void insert(char ch) {
if (occurrence[ch] == 0) {
occurrence[ch] = index++;
}
if (occurrence[ch] >= 1) {
occurrence[ch] = -1;
}
}
public char firstAppearingOnce() {
char result = ' ';
int minIndex = Integer.MAX_VALUE;
// 因为字符流随时间增长可能变得很长，所以选择遍历数组而不是遍历当前的字符流。时间复杂度就是O(1)
for (int i = 0; i < 256; i++) {
if (occurrence[i] >= 1 && occurrence[i] < minIndex) {
result = (char) i;
minIndex = occurrence[i];
}
}
return result;
}
} 面试题51：数组中的逆序对
题目：在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
- 算法：归并排序
- nums数组和copy数组在递归时掉包了
- 每次在
left = reversePairs(copy, nums, start, start+middle);right = reversePairs(copy, nums, start+middle+1, end);函数中对nums数组排序后，在reversePairs(nums, copy, start, middle, end)函数中就可以利用左右有序计算逆序对 - 返回最后结果时，copy数组是有序的，nums数组是左右两边分别有序的
public int reversePairs(int[] nums) {
checkArguments(nums);
int[] copy = new int[nums.length];
System.arraycopy(nums, 0, copy, 0, nums.length);
return reversePairs(nums, copy, 0, nums.length-1);
}
public int reversePairs(int[] nums, int[] copy, int start, int end) {
if (start == end) {
copy[start] = nums[start];
return 0;
} else {
int middle = (end - start) >> 1;
int left = reversePairs(copy, nums, start, start+middle);
int right = reversePairs(copy, nums, start+middle+1, end);
return left + right + reversePairs(nums, copy, start, middle, end);
}
}
public int reversePairs(int[] nums, int[] copy, int start, int middle, int end) {
int i = start + middle;
int j = end;
int copyIndex = end;
int count = 0;
while (i >= start && j >= start+middle+1) {
if (nums[i] > nums[j]) {
copy[copyIndex--] = nums[i--];
count += (j - start - middle);
} else {
copy[copyIndex--] = nums[j--];
}
}
for (;i >= start; i--) {
copy[copyIndex--] = nums[i];
}
for (;j >= start+middle+1; j--) {
copy[copyIndex--] = nums[j];
}
return count;
}
public void checkArguments(int[] array) {
if (array == null || array.length <= 1) {
throw new RuntimeException("Invalid array");
}
} 面试题52：两个链表的第一个公共结点
题目：输入两个链表，找出它们的第一个公共结点。
- 算法：
- LeetCode Discuss
- 使用两个指针进行遍历，当一个指针到头时，就重置它为另一个链表的头节点
- 当两个链表长度相同时：不到一轮遍历既能找到答案
- 当两个链表长度不同时：不到二轮遍历既能找到答案
public ListNode getIntersectionNode(ListNode l1, ListNode l2) {
// checkArguments(l1, l2); // l1 == null; l2 == null;
ListNode move1 = l1;
ListNode move2 = l2;
while (move1 != move2) {
move1 = (move1 == null ? l2 : move1.next);
move2 = (move2 == null ? l1 : move2.next);
}
return move1;
} - 算法：
- 首先遍历计算两个链表长度之差lengthDiff
- 然后长链表先走lengthDiff步
- 最后一起遍历直到找到公共结点
- O(m+n)
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
checkArguments(headA);
checkArguments(headB);
int lengthA = getLengthOfList(headA);
int lengthB = getLengthOfList(headB);
int lengthDiff = lengthA > lengthB ? (lengthA - lengthB) : (lengthB - lengthA);
ListNode longList = lengthA > lengthB ? headA : headB;
ListNode shortList = lengthA > lengthB ? headB : headA;
for (int i = 0; i < lengthDiff; i++) {
longList = longList.next;
}
while (longList != null && shortList != null && (longList != shortList)) {
longList = longList.next;
shortList = shortList.next;
}
return longList;
}
public int getLengthOfList(ListNode head) {
int length = 0;
while (head != null) {
length++;
head = head.next;
}
return length;
} - 算法：
- 使用两个辅助栈把两个链表结点顺序入栈
- 这样出栈时就可以从尾部往头部遍历结点以此找到公共结点
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
checkArguments(headA);
checkArguments(headB);
Stack<ListNode> stackA = new Stack<>();
Stack<ListNode> stackB = new Stack<>();
while (headA != null) {
stackA.push(headA);
headA = headA.next;
}
while (headB != null) {
stackB.push(headB);
headB = headB.next;
}
ListNode result = null;
while (!stackA.isEmpty() && !stackB.isEmpty()) {
ListNode nodeA = stackA.pop();
ListNode nodeB = stackB.pop();
if (nodeA != nodeB) {
return result;
}
result = nodeA;
}
return result;
} 
京公网安备 11010502036488号