Sword finger offer:3-7 records

Find duplicate numbers in the array.


All numbers in an array nums of length n are in the range of 0-n-1.Some numbers in the array are duplicated, but you do not know how many numbers are duplicated or how many times each number is repeated.Find any duplicate number in the array.

Example 1:

Input:
[2, 3, 1, 0, 2, 5, 3]
Output: 2 or 3

Idea: Just a set record.

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            if (!set.add(num)) {
                return num;
            }
        }
        return -1;
    }
}

In a two-dimensional array of n * m, each row is sorted in increasing order from left to right, and each column is sorted in increasing order from top to bottom.Please complete a function, enter such a two-dimensional array and an integer to determine if the array contains the integer.

 

Example:

The existing matrix matrix is as follows:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
Given target = 5, returns true.

Given target = 20, returns false.

 

Restrictions:

0 <= n <= 1000

0 <= m <= 1000

Think: You can exclude one row or column at a time by examining from the lower left or upper right corner.

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int len = matrix.length;
        int row = 0, column = matrix[0].length - 1;
        while (row < len && column >= 0) {
            int num = matrix[row][column];
            if (num == target) {
                return true;
            } else if (num > target) {
                column--;
            } else {
                row++;
            }
        }
        return false;
    }
}

Please implement a function that replaces each space in string s with'%20'.

 

Example 1:

Input: s = "We are happy."
Output: "We%20are%20happy."

Think: Fill in backwards and forwards. Unfilled numbers will not be overwritten. Each letter needs to be assigned only once.(Otherwise, replace the characters that need to be moved after going back)

class Solution {
    public String replaceSpace(String s) {
        int length = s.length();
        char[] array = new char[length * 3];
        int size = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                array[size++] = '%';
                array[size++] = '2';
                array[size++] = '0';
            } else {
                array[size++] = c;
            }
            
        }
        String newStr = new String(array, 0, size);
        return newStr;
    }
}

Enter the head node of a list of chains and return the value of each node (in an array) from the end to the end.

 

Example 1:

Input: head = [1,3,2]
Output: [2,3,1]
 

Restrictions:

0 <=Link List Length <= 10000

Think: Pour it out of the stack.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        int size = stack.size();
        int[] arr = new int[size];
        for (int i = 0; i < size; i++) {
            arr[i] = stack.pop().val;
        }
        return arr;
    }
}

Enter the results of a binary tree's prefix and median traversals, and rebuild the binary tree.Assume that no duplicate numbers are included in the results of the preceding and middle traversals of the inputs.

 

For example, given

Pre-order traversal preorder = [3,9,20,15,7]
Intermediate traversal inorder = [9,3,15,20,7]
Returns the following binary tree:

    3
   / \
  9  20
    /  \
   15   7
 

Restrictions:

0 <=Number of nodes <= 5000

Ideas:

1. The first element of the sequence is the root

2. Find the position of the root in the ordered sequence

3. Repeat the above process.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        if (n == 0)
            return null;
        int rootVal = preorder[0], rootIndex = 0;
        for (int i = 0; i < n; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }
        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(Arrays.copyOfRange(preorder, 1, 1 + rootIndex), Arrays.copyOfRange(inorder, 0, rootIndex));
        root.right = buildTree(Arrays.copyOfRange(preorder, 1 + rootIndex, n), Arrays.copyOfRange(inorder, rootIndex + 1, n));

        return root;
    }
}

 

618 original articles were published with 10,000 appreciations and 1.54 million visits.
His message board follow

Posted on Sun, 08 Mar 2020 19:27:12 -0700 by louis_coetzee