Problem 16 — Number raised to an integer power
Double Power(double base, int exponent) I’m going to take base exponent. Library functions should not be used and large numbers should not be considered.
This chapter seems to be all about code quality, meaning that the problem itself is not difficult to solve, but the boundary conditions, exceptions, and so on are full of minefields.
So this problem, for example,
-
The first thing we should consider is the large number problem, and if the problem doesn’t mention that we can ignore the large number problem, then we also need to implement a large number type multiplication.
-
And then the next thing we need to worry about is 0 to the 2, 0 to the minus 2, 5 to the minus 2, when base is 0, when exponent is negative. Put all that together and you get the code.
-
Finally, when solving the power operation, we can think of dichotomy to reduce the time complexity.
public class Solution {
public double power(double base, int exponent) {
boolean negative = exponent < 0;
if (exponent == 0) {
return 1; // note: include 0^0
}
if (base == 0) {
return 0; // note: include 0^(-2)
}
int unsignedExponent = Math.abs(exponent);
double rawResult = powerWithUnsignedExponent(base, unsignedExponent);
return negative ? (1 / rawResult) : rawResult;
}
private double powerWithUnsignedExponent(double base, int unsignedExponent) {
if (unsignedExponent == 1) {
return base;
}
int halfExponent = unsignedExponent >> 1;
double halfResult = powerWithUnsignedExponent(base, halfExponent);
if ((unsignedExponent & 1) = =1) {
return base * halfResult * halfResult;
} else {
returnhalfResult * halfResult; }}}Copy the codeProblem 17 — Prints n digits from 1 to the largest
Title: Enter the number n and print the largest n decimal numbers in order. For example, if you type 3, you print 1, 2, 3, up to the maximum three-digit number 999.
If n is large enough, then neither int, long, nor long long can withstand such a large number. So you need to realize the addition of array analog numbers, or the full array of arrays
Use arrays to simulate the addition of numbers
Carry does not overflow
Carry the overflow
public class Solution {
public void printToMaxOfDigits(int n) {
if (n <= 0) {
return;
}
int[] number = new int[n];
while(increment(number)) { printNumber(number); }}private void printNumber(int[] number) {
boolean isBeginning0 = true;
for (int i = 0; i < number.length; i++) {
if(isBeginning0 && number[i] ! =0) {
isBeginning0 = false;
}
if(! isBeginning0) { System.out.print(number[i]); } } System.out.println(); }private boolean increment(int[] number) {
for (int i = number.length - 1; i >= 0; i--) {
if (number[i] + 1= =10) {
number[i] = 0;
} else {
number[i]++;
return true; }}return false; }}Copy the code
Full permutation of arrays (recursive)
public class Solution2 {
public void printToMaxOfDigits(int n) {
if (n <= 0) {
return;
}
int[] number = new int[n];
printToMaxOfDigitsRecursively(number, 0);
}
private void printToMaxOfDigitsRecursively(int[] number, int index) {
if (index == number.length) {
printNumber(number);
return;
}
for (int i = 0; i < 10; i++) {
number[index] = i;
printToMaxOfDigitsRecursively(number, index+1); }}private void printNumber(int[] number) {
boolean isBeginningZero = true;
for (int i = 0; i < number.length; i++) {
if(isBeginningZero && number[i] ! =0) {
isBeginningZero = false;
}
if (!isBeginningZero) {
System.out.print(number[i]);
}
}
if(! isBeginningZero) { System.out.println(); }}}Copy the codeInterview question 18 — Delete the nodes of the linked list
Topic 1: Delete a linked list node in O(1) time
Topic 1: Delete a linked list node in O(1) time. Given a head pointer and a node pointer to a one-way linked list, define a function to delete the node in O(1) time.
public class Solution {
private static class ListNode {
int value;
ListNode next;
ListNode(int value) {
this.value = value; }}// require caller to ensure nodeToBeDeleted is in listHead.
public void deleteNode(ListNode listHead, ListNode nodeToBeDeleted) {
if (listHead == null || nodeToBeDeleted == null || listHead.next == null) {
return;
}
if (nodeToBeDeleted.next == null) {
ListNode node = listHead;
// if nodeToBeDeleted is tail, we have to iterate whole list
while(node.next ! =null) {
if (node.next == nodeToBeDeleted) {
node.next = null;
return;
}
node = node.next;
}
throw new IllegalStateException("nodeToBeDeleted is not in list!");
} else {
ListNode nextNode = nodeToBeDeleted.next;
nodeToBeDeleted.value = nextNode.value;
nodeToBeDeleted.next = nextNode.next;
nextNode.next = null; // not important}}private static void printNode(ListNode head) {
ListNode node = head.next;
while(node ! =null) {
System.out.print(node.value + "-- >");
node = node.next;
}
System.out.println("null");
}
public static void main(String[] args) {
ListNode head = new ListNode(0);
head.next = new ListNode(1);
head.next.next = new ListNode(2);
head.next.next.next = new ListNode(3);
printNode(head);
Solution solution = newSolution(); solution.deleteNode(head, head.next.next); printNode(head); solution.deleteNode(head, head.next.next); printNode(head); solution.deleteNode(head, head.next); printNode(head); }}Copy the codeTopic 2: Delete duplicate nodes in the linked list
In a sorted linked list, how do I delete duplicate nodes? For example, after the duplicate nodes in the figure are deleted, the linked list looks like this.
- Think of test cases before you start and write them in comments
- Mark special input parameter TOdo
- Figure out how to do it and write code prototypes
- Fill in the details
- Write back todo, in-brain compile and execute test cases, in-brain debug
Control the three Pointers well
public void deleteDuplicateNode(ListNode head) {
if (head == null || head.next == null) {
return;
}
ListNode preNode = head;
ListNode node = head.next;
while(node ! =null) {
boolean findDuplicate = false;
ListNode nextNode = node.next;
while(nextNode ! =null && nextNode.value == node.value) {
findDuplicate = true;
nextNode = nextNode.next;
}
// conjunct node and nextNode if find duplicated
if(findDuplicate) { node.next = nextNode; } node = node.next; preNode = preNode.next; }}Copy the codeInterview question 19 — Regular expression matching
Implement a function to match regular expressions containing ‘.’ and ‘*’. The character ‘.’ in the pattern represents any character, while the character ‘*’ indicates that the character preceding it can occur any number of times (up to zero). In this case, matching means that all characters in a string match the entire pattern. For example, the string “aaa” matches the patterns “A.a” and “ab* AC *a”, but not “aa.a” and “ab*a”.
This is a State Machine problem. The string “aaa” matches the regular expression “ab*ac*a”.
The state machine of the regular expression ab*ac*a can be expressed as follows:
There are several situations you might encounter during a regular match:
#Match to the# *- If the string input
#And the pattern of#equal- Consider it a match
# *, string input forward +1, pattern forward +2 (skip# *) ==> State 2 to State 3 - Matched once
# *After that, it should continue to match for several times. The input string is +1 forward, and the status 2 of pattern is unchanged # *If the match fails, that is, 0 times is matched, the input string does not move, and the pattern string pattern changes from state 2 to state 3
- Consider it a match
- If the string input
#And the pattern of#Not equal to the- Can only be used as pattern
# *After matching 0 times, the input string is unchanged, and the pattern string pattern changes from state 2 to state 3
- Can only be used as pattern
- If the string input
#matching#Compare for equality
public class Solution {
public boolean matchPattern(String input, String pattern) {
if (input == null || pattern == null) {
return false;
}
return matchPatternCore(input, 0, pattern, 0);
}
private boolean matchPatternCore(String input, int inputIndex, String pattern, int patternIndex) {
if (inputIndex == input.length() && patternIndex == pattern.length()) {
return true;
}
if (inputIndex < input.length() && patternIndex == pattern.length()) {
return false;
}
if (pattern.charAt(patternIndex + 1) = =The '*') {
if (inputIndex < input.length() && isEqual(input.charAt(inputIndex), pattern.charAt(patternIndex))) {
// 1. move on the next state
// 2. stay on the current state
// 3. ignore 'a*'
return matchPatternCore(input, inputIndex + 1, pattern, patternIndex + 2)
|| matchPatternCore(input, inputIndex + 1, pattern, patternIndex)
|| matchPatternCore(input, inputIndex, pattern, patternIndex + 2);
} else {
// not equal(include input is over), we can only try ignore
return matchPatternCore(input, inputIndex, pattern, patternIndex + 2); }}else if (isEqual(input.charAt(inputIndex), pattern.charAt(patternIndex))) {
return matchPatternCore(input, inputIndex + 1, pattern, patternIndex + 1);
} else {
return false; }}private boolean isEqual(char ch, char patternChar) {
return ch == patternChar || patternChar == '. '; }}Copy the codeIn addition, there is another solution to dynamic programming, which is to reverse the recursive process and build a two-dimensional array DP. Dp [I][j] indicates whether the input up to I matches pattern up to J. Through judgment of various situations (including processing logic after meeting *), the DP array is gradually filled up and the result is calculated.
Leetcode solution – line by line, from simple to deep, dp and recursive two ideas
Interview question 20 — A numeric string
Implement a function to determine whether a string represents a numeric value (both integer and decimal). For example, the string “+ 100”, “5 e2”, “123”, “3.1416” and “1 e – 16” said values, but 12 “e”, “1 a3. 14”, “1.2.3”, “+ 5” and “12 e + 5.4” is not.
The solution in the book is as follows: Use ‘.’ and ‘e’ as delimiters to divide the string into three parts: A, B, and C, and determine whether each part is A valid number.
The implementation details don’t have to be split. Instead, the string is traversed through the string, which is A part of A until an illegal character is encountered, then B or C after ‘.’ or ‘E’, and finally the index is used to determine whether the entire string is traversed properly.
public class Solution {
private int index = 0;
public boolean isNumber(String s) {
if (s == null || s.length() == 0) {
return false;
}
s = s.trim();
boolean numeric = scanInteger(s);
if (index < s.length() && s.charAt(index) == '. ') {
index++;
numeric = scanUnsignedInteger(s) || numeric;
}
if (index < s.length() && isExponent(s.charAt(index))) {
index++;
numeric = numeric && scanInteger(s);
}
return numeric && index == s.length();
}
private boolean scanInteger(String s) {
if (index < s.length() && isPlusMinus(s.charAt(index))) {
index++;
}
return scanUnsignedInteger(s);
}
private boolean scanUnsignedInteger(String s) {
int before = index;
while(index < s.length() && isDigit(s.charAt(index))) {
index++;
}
return index > before;
}
private boolean isDigit(char c) {
return c >= '0' && c <= '9';
}
private boolean isPlusMinus(char c) {
return c == '+' || c == The '-';
}
private boolean isExponent(char c) {
return c == 'e' || c == 'E'; }}Copy the codeThere is a state machine based solution mentioned in The Leetcode solution, which is more understandable to the individual, that is, no brain enumerates all possible state transitions and is done.
Interview question 20. Numeric strings (Finite state automata, clear diagram)
Interview question 21 — Reorder the array so that the odd number precedes the even number
Implement a function to adjust the order of the numbers in the array so that all odd numbers are in the first half of the array and all even numbers are in the last half of the array.
It is easy to associate from experience with the partition method of fast sorting, dividing the heap between odd and even numbers, traversing the NUMS array through the precursor node I, throwing odd numbers to the left and even numbers to the right. (Similar to the principle in the book that the left and right Pointers move toward the center, it is stated that (nums[I] &1) == 1 is abstracted from the function pointer for easy extension, which can be implemented in Java using lambda expressions)
public class Solution {
// normal: 1 2 3 4 5
// all odd: 1 3 5
// all even: 2 4 6
public int[] exchange(int[] nums) {
if (nums == null || nums.length == 0) {
return nums;
}
int firstEven = 0;
for (int i = 0; i < nums.length; i++) {
if ((nums[i] & 1) = =1) { // oddswap(nums, i, firstEven); firstEven++; }}return nums;
}
private void swap(int[] nums, int i, int j) {
inttemp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}Copy the codeInterview question 22 — The KTH node from the bottom of the list
Title: Input a linked list and output the KTH last node in the list. In order to conform to the convention of most people, this case counts from 1, i.e. the last node of the list is the last node from the last. For example, a linked list has six nodes, starting with the head node, whose values are 1, 2, 3, 4, 5, and 6. The third to last node of the list is the one with the value 4.
It’s a very simple problem, and as the book says, the point is to think about robustness
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; }} * * /
class Solution {
// 1 -> 2 -> 3 -> 4 -> 5 -> 6, k=3
// 1, k=3
public ListNode getKthFromEnd(ListNode head, int k) {
if (head == null || k <= 0) {
return null;
}
ListNode node = head;
for (int i = 0; i < k; i++) {
if (node == null) {
return null; // size of list is less than k.
}
node = node.next;
}
ListNode kthNode = head;
while(node ! =null) {
node = node.next;
kthNode = kthNode.next;
}
returnkthNode; }}Copy the codeInterview question 23 — Entry node in the middle of a linked list
Title: If a linked list contains rings, how do I find the entry node of the ring? For example, in the linked list shown, the entry node of the ring is node 3.
public class Solution {
private static class ListNode {
int val;
ListNode next;
ListNode(intx) { val = x; }}public ListNode entryNodeOfLoop(ListNode head) {
if (head == null) {
return null;
}
ListNode meetingNode = findMeetingNode(head);
if (meetingNode == null) {
return null; // means there is no loop in list
}
int nodeCountOfLoop = getNodeCountOfLoop(meetingNode);
ListNode foreNode = head;
for (int i = 0; i < nodeCountOfLoop; i++) {
foreNode = foreNode.next;
}
ListNode behindNode = head;
while(foreNode ! = behindNode) { foreNode = foreNode.next; behindNode = behindNode.next; }return behindNode;
}
private ListNode findMeetingNode(ListNode head) {
// assert head is not null
ListNode slow = head;
ListNode fast = head;
while(slow ! =null&& fast.next ! =null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
returnslow; }}return null;
}
private int getNodeCountOfLoop(ListNode meetingNode) {
// assert meetingNode is a loop which means there's no null in list
ListNode node = meetingNode.next;
int i = 1;
while(node ! = meetingNode) { i++; node = node.next; }returni; }}Copy the codeInterview question 24 — Reverse the linked list
Define a function that takes the head node of a linked list, reverses the list, and outputs the head node of the reversed list.
Node is used to iterate, before is used to set node.next=before, after is used to find the next node after node adjustment, so that the iterate continues.
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode before = null;
ListNode node = head;
ListNode after = head.next;
while(node ! =null) {
node.next = before;
if (after == null) {
return node;
}
before = node;
after = after.next;
node = after;
}
throw new IllegalStateException("not supposed to be here.");
}
Copy the codeInterview question 25 — Merge two sorted linked lists
Title: Enter two incrementally sorted lists and merge them so that the nodes in the new list are still incrementally sorted.
The same problem is not difficult, but need to control the pointer adjustment, to prevent the occurrence of pointer pointing does not meet the expected bug. We can solve it with loops and recursion.
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) {
return l1 == null ? l2 : l1;
}
ListNode baseList = l1.val < l2.val ? l1 : l2;
ListNode branchList = baseList == l1 ? l2 : l1;
ListNode baseNode = baseList.next;
ListNode foreNode = baseList;
ListNode branchNode = branchList;
while(baseNode ! =null&& branchNode ! =null) {
if (baseNode.val <= branchNode.val) {
foreNode = foreNode.next; // baseNode & foreNode walk forward
baseNode = baseNode.next;
} else {
foreNode.next = branchNode; // merge branchNode into baseList and walk forwardbranchNode = branchNode.next; foreNode.next.next = baseNode; foreNode = foreNode.next; }}if(branchNode ! =null) {
foreNode.next = branchNode;
}
return baseList;
}
public ListNode mergeTwoListsInBook(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) {
return l1 == null ? l2 : l1;
}
ListNode mergedHead;
if (l1.val < l2.val) {
mergedHead = l1;
mergedHead.next = mergeTwoListsInBook(l1.next, l2);
} else {
mergedHead = l2;
mergedHead.next = mergeTwoListsInBook(l1, l2.next);
}
return mergedHead;
}
Copy the codeInterview question 26 — Tree substructure
Input two binary trees A and B to determine whether B is A substructure of A.
B is A substructure of A. the structure of B can be matched at any position of A
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (B == null) {
return false;
} else if (A == null) {
return false;
}
// pre-order traverse to find if B is-root-substructure of A
return isRootSubStructure(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
private boolean isRootSubStructure(TreeNode A, TreeNode B) {
if (B == null) {
return true;
} else if (A == null) {
return false;
}
return A.val == B.val && isRootSubStructure(A.left, B.left) && isRootSubStructure(A.right, B.right);
}
Copy the code