This is the 22nd day of my participation in the August Wen Challenge.More challenges in August
I went back to my hometown this weekend. It’s quite near. It’s an hour’s drive. In both cases, dida Chuxing received orders from hitchhikers. Strangely, dida Chuxing and Halo Chuxing found more passengers on their way than Didi. It may be that didi Hitch has a higher price for passengers, which leads to passengers placing orders on other platforms.
As a driver, I mainly consider the way, because the price of hitch is relatively low, it is not cost-effective to detour, which leads to a thought: how does the system calculate the matching degree of hitch?
In the simplest way, the navigation calculates the driver’s original route and the new route after receiving the order, and then directly calculates the difference between the two routes, and divides the mileage of the original route, which can be considered as the mismatch degree, and then the on-route matching degree = 1- mismatch degree.
But this way has a obvious shortcomings, extremely rational, because for the driver, at least for me, the current main direction is completely with me in the opposite direction of 3 km, 3 km and a vertical body feeling is different, in the opposite direction of the comparison of 3 km will make me feel I circle, and vertical direction, I would feel much. Therefore, another dimension that may need to be considered is the included Angle of the direction vectors to weight the distance. Of course, it would be better if the road conditions of this distance could be taken into account during the expected travel time.
The above is due to the two hitchhiking experiences back home this weekend, random thoughts on the matching calculation along the way, or back to Leetcode, continue to do problem 33 today.
The title
The integer array NUMs is sorted in ascending order, with different values in the array.
Before passing to the function, nums is rotated on some previously unknown subscript k (0 <= k < nums.length), Make the array [nums [k], nums [k + 1),…, nums] [n – 1, nums [0], nums [1],…, nums [k – 1]] (subscript starting from 0). ,1,2,4,5,6,7 [0], for example, in the subscript 3 after rotation may become,5,6,7,0,1,2 [4].
Give you the rotated array nums and an integer target, return its subscript if nums contains the target value, otherwise -1.
Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
Example 2: input: nums = [4,5,6,7,0,1,2], target = 3 output: -1
Example 3: Input: nums = [1], target = 0 Output: -1
Train of thought
Searching a specified number in an ordered array is binary searching, isn’t it? The difference in this case is that the data is not completely ordered, because it has been rotated once, so the array is a concatenation of two separately ordered data, but the concatenation point is unknown, so what can we do? In fact, you can still use binary search, and the premise of binary search is not that the array is perfectly ordered, but after binary search, there’s a way to quickly determine which one is likely to be in one half. Although not bear on the complete order, but still can be judged, because can be found that after binary array, there must be a half is ordered, this is very important, since the half is orderly, that we can through the half of the head and tail to determine whether a target in the half, if in, then continue to find the half, if not, It’s in the other half, and then it recurses. The following is a schematic diagram of the half that must be completely ordered after two halves, and the blue box is the ordered half:
Java version code
class Solution { public int search(int[] nums, int target) { int len = nums.length; if (len == 0) { return -1; } int left = 0, right = len-1; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] == target) { return mid; } if (nums[0] <= nums[mid]) { if (target >= nums[left] && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } else { if (target > nums[mid] && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } } return -1; }}Copy the code