“This is the 20th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

takeaway

Fat friends in order to better help new students adapt to the algorithm and questions, recently we began a special assault step by step. We’re going to start with one of the most frustrating types of algorithms, dynamic programming and we’re going to do a 21-day incubation program. What are you waiting for? Come and join us for 21 days of dynamic programming challenge!!

21 Days Dynamic Planning Introduction

You are a product manager, currently leading a team to develop a new product. Unfortunately, the latest version of your product did not pass the quality test. Since each version is based on the previous version, all versions after the incorrect version are incorrect.

Suppose you have n versions [1, 2… n] and you want to find the first incorrect version that causes all subsequent versions to fail.

You can tell if version failed in unit tests by calling the bool isBadVersion(version) interface. Implement a function to find the first incorrect version. You should minimize the number of calls to the API.

The sample1: Enter: n =5, bad = 4Output:4Explanation: Call isBadVersion(3) -> false call isBadVersion(5) -> true calls isBadVersion(4) -> true4It's the first incorrect version.Copy the code
The sample2: Enter: n =1, bad = 1Output:1
Copy the code
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1.right = n;
        while (left < right) {// loop until the left and right endpoints of the interval are the same int mid =left + (right - left) / 2; If (isBadVersion(mid)) {right= mid; // The answer is in the interval[left, mid]In} else {left = mid + 1; // The answer is in the interval[mid+1, right]}} // Now there isleft= =right, the interval is reduced to one point, that is, the answer returnleft; }}Copy the code

Given a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted in order.

You must use an O(log n) time complexity algorithm.

The sample1: Input: nums = [1.3.5.6], target = 5Output:2
Copy the code
The sample2: Input: nums = [1.3.5.6], target = 2Output:1
Copy the code
The sample3: Input: nums = [1.3.5.6], target = 7Output:4
Copy the code
The sample4: Input: nums = [1.3.5.6], target = 0Output:0
Copy the code
The sample5: Input: nums = [1], target = 0Output:0
Copy the code
// The main idea is binary search
class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1; }}returnans; }}Copy the code

The interview questions

3. What is the capacity expansion mechanism of HashMap? In general, expansion is triggered when the number of elements exceeds the threshold. Each capacity expansion doubles the previous capacity. The capacity of a HashMap must be smaller than 1<<30, that is, 1073741824. If the capacity exceeds this number, it does not grow and the threshold is set to integer.max_value. The capacity expansion mechanism in JDK7 pays for an empty parameter, which initializes an array using the default capacity, default load factor, and default threshold. The inner array is a null array. Factor a parameter constructor: Determines the capacity, load factor, threshold, and so on based on the parameters. A put, for the first time, initializes an array whose capacity is at least a power of 2, and determines a threshold based on the load factor. At the same time, if the system is not expanded for the first time, the new capacity = old capacity x 2, and the new threshold = new capacity x load factor. The JDK8 expansion mechanism pays for an empty argument constructor: the instantiated HashMap defaults to null, meaning it is not instantiated. When the put method is called for the first time, the first initial expansion of 16 characters begins. Function functions according to the principle. The argument constructor: specifies the capacity. The specified positive integer is used to find a power of 2 that is not less than the specified capacity, and this number setting is assigned to the threshold. The first time the PUT method is called, the threshold is assigned to the capacity, and then the threshold is set to capacity x load factor. At the same time, if you do not expand the system for the first time, you double the capacity and double the threshold. (The load factor remains the same when the capacity and threshold are doubled). There are also a few details to note: when a PUT is put for the first time, a user automatically triggers expansion (sort of initialization), saves data, and decides whether they need to expand. Anyway, if something is not put for the first time, users stop initializing, save data directly, and decide whether to expand the system.