- Violent cycle, timeout TAT
class Solution {
public int findRepeatNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length; j++) {
if (i != j && nums[i] == nums[j]) {
return nums[i];
}
}
}
return -1;
}
}
- Using the Set feature [non repeatable], you can also use list.contains(), but it will timeout!
class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (!set.add(num)) {
return num;
}
set.add(num);
}
return -1;
}
}
- Sorting + traversal
class Solution {
public int findRepeatNumber(int[] nums) {
Arrays.sort(nums);
for (int i = 1; i < nums.length; i++) {
if (nums[i - 1] == nums[i]) return nums[i];
}
return -1;
}
}
- General traversal of two-dimensional array lookup
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == target) return true;
}
}
return false;
}
}
- According to the left to right and top to bottom increment characteristics of the array, search from the top right
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
for (int i = 0; i < matrix.length; i++) {
for (int j = matrix[0].length - 1; j >= 0; j--) {
if (matrix[i][j] < target) {
break;
} else if (matrix[i][j] == target) {
return true;
}
}
}
return false;
}
}
- Call API: str.replace()
class Solution {
public String replaceSpace(String s) {
return s.replace(" ", "%20");
}
}
- Building StringBuilder splicing, traversing the string, encountered a space append ('% 20')
class Solution {
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == ' ') sb.append("%20");
else sb.append(c);
}
return sb.toString();
}
}
- Traverse the linked list to obtain the number of linked lists n, and create a new array with length n
Traverse the linked list and assign the value of the array in reverse (that is, the first value of the linked list is assigned to the last value of the array...)
class Solution {
public int[] reversePrint(ListNode head) {
int n = 0;
ListNode cur = head;
while (cur != null) {
n++;
cur = cur.next;
}
int[] arr = new int[n];
cur = head;
for (int i = n - 1; i >= 0; i--) {
arr[i] = cur.val;
cur = cur.next;
}
return arr;
}
}
- The preorder traversal and inorder traversal are given, and the binary tree is constructed
- Construct a binary tree according to the first middle order or the second middle order:
Preorder traversal: root left right
Middle order traversal: left root right
Post order traversal: left right root
- First find the pre order (first) or post order (last) of the root, and find the value of the root node
- Find the position where the root node is traversed in the middle order, and the record index is index
- It is known that in the middle order traversal, the left subtree is on the left side of index and the right subtree is on the right side of index
- The array remains unchanged. We control the construction of binary tree by changing the left and right pointers of the two arrays. Note that the number of left subtrees is obtained by means of leftSize = index - inStart, and leftSize is used as the value
- Just get? Just the value in
root.left = build(preorder, ?, ?, inorder, ?, ?);
root.right = build(preorder, ?, ?, inorder, ?, ?);
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
int len = preorder.length;
if (len == 0) return null;
int rootValue = preorder[0];
int rootIndex = 0;
for (int i = 0; i < len; i++) {
if (inorder[i] == rootValue) {
rootIndex = i;
break;
}
}
TreeNode root = new TreeNode(rootValue);
root.left = buildTree(Arrays.copyOfRange(preorder,1,rootIndex + 1),Arrays.copyOfRange(inorder,0,rootIndex));
root.right = buildTree(Arrays.copyOfRange(preorder,1+rootIndex,len),Arrays.copyOfRange(inorder,rootIndex+1,len));
return root;
}
}
- If you use Stack to do this problem, it will cause slow speed; The reason is that Stack inherits the Vector interface, and the underlying layer of Vector is an Object [] array. Therefore, space expansion and displacement should be considered
- LinkedList can be used as the container of Stack. Because LinkedList implements the Deque interface, LinkedList can do everything that Stack can do. Its structure is a two-way linked list with less expansion consumption
- However, it does not directly use a LinkedList as a queue, which is inconsistent with the meaning of the question
class CQueue {
LinkedList<Integer> stack1;
LinkedList<Integer> stack2;
public CQueue() {
stack1 = new LinkedList<>();
stack2 = new LinkedList<>();
}
public void appendTail(int value) {
stack1.add(value);
}
public int deleteHead() {
if (stack2.isEmpty()){
//Both stacks are null, indicating that there is no element at this time, and - 1 is returned
if (stack1.isEmpty()) return -1;
//Only stack2 is empty. Add the element of stack1 to stack2 and return the stack top value
while (!stack1.isEmpty()) {
stack2.add(stack1.pop());
}
return stack2.pop();
}
//stack2 is not empty. It directly returns the stack top value
return stack2.pop();
}
}
- recursion
class Solution {
public int fib(int n) {
if (n == 0 || n == 1) return n;
return fib(n - 1) + fib(n - 2);
}
}
- Define dp array, dynamic programming
class Solution {
public int fib(int n) {
if (n == 0 || n == 1) return n;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
}
return dp[n];
}
}
- Advanced: define three temporary traversal stored values without an array to save space
class Solution {
public int fib(int n) {
if (n == 0 || n == 1) return n;
int a = 0, b = 1, c = 0;
for (int i = 2; i <= n; i++) {
c = (a + b) % 1000000007;
a = b;
b = c;
}
return c;
}
}