[Algorithm Progress 213/400 (‘▽’)]
136. A number that appears only once
Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once.
Note: Your algorithm should have linear time complexity. Can you do it without using extra space?
Example 1: input: [2, 2, 1] output: 1 example 2: input:,1,2,1,2 [4] output: 4Copy the codeHash table
/ * * *@param {number[]} nums
* @return {number}* /
var singleNumber = function (nums) {
let hash = {}
for (let i = 0; i < nums.length; i++) {
hash[nums[i]] ? hash[nums[i]]++ : hash[nums[i]] = 1
}
for (let j in hash) {
if (hash[j] === 1) {
return j
}
}
};
Copy the codeExclusive or
var singleNumber = function (nums) {
let ans = nums[0]
for (let i = 1; i < nums.length; i++) {
ans = ans ^ nums[i]
}
return ans
};
Copy the code278. The first incorrect version
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.
Example 1: Input: n = 5, bad = 4 Output: 4 explanation: Call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true so, 4 is the version with the first error. Example 2: Input: n = 1, bad = 1 Output: 1Copy the codedichotomy
var solution = function (isBadVersion) {
return function (n) {
let left = 1, right = n
while (left < right) {
const mid = Math.floor(left + (right - left) / 2)
if (isBadVersion(mid)) {
right = mid
} else {
left = mid + 1}}return left
};
};
Copy the codeBinary search
Given an ordered (ascending) integer array nums with n elements and a target value, write a function to search for target in NUMs, returning a subscript if the target value exists, and -1 otherwise.
Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 appears in nums with subscript 4 Example 2: Input: Nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in NUMS so return -1 Hint: You can assume that all elements in NUMS are not repeated. N will be between [1, 10000]. Each element of nums will be between [-9999, 9999].Copy the codedichotomy
var search = function (nums, target) {
let low = 0, high = nums.length - 1
while (low <= high) {
const mid = Math.floor((high - low) / 2) + low
const num = nums[mid]
if (num === target) {
return mid
} else if (num > target) {
high = mid - 1
} else if (num < target) {
low = mid + 1}}return -1
};
Copy the codefindIndex
var search = function(nums, target) {
return nums.findIndex(v=>v===target)
};
Copy the codeindexOf
var search = function(nums, target) {
return nums.indexOf(target)
};
Copy the codeThe for loop
var search = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
if(nums[i] === target) return i
}
return -1
};
Copy the code35. Search for insertion locations
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:2The sample2: Input: nums = [1.3.5.6], target = 2Output:1The sample3: Input: nums = [1.3.5.6], target = 7Output:4The sample4: Input: nums = [1.3.5.6], target = 0Output:0The sample5: Input: nums = [1], target = 0Output:0Tip:1 <= nums.length <= 104
-104 <= nums[i] <= 104Nums is an ascending array of non-repeating elements -104 <= target <= 104
Copy the codefilter
var searchInsert = function (nums, target) {
return nums.filter(v= > v < target).length
};
Copy the codedichotomy
var searchInsert = function (nums, target) {
let len = nums.length
if (len === 0) return 0
let left = 0, right = len-1
while (left < right) {
// const mid = (left + right) >> 1
const mid = Math.floor((right - left) / 2 + left)
if (nums[mid] >= target) {
right = mid
} else if(nums[mid] < target) {
left = mid + 1}}if (nums[right] < target) {
return right + 1
}
return right
};
Copy the code977. Square of an ordered array
Given an array of integers sorted in non-descending order, nums returns a new array of the squares of each number, also sorted in non-descending order.
Example 1: input: nums = [-4,-1,0,3,10] output: [0,1,9,16 100] description: after the square is squared, the array becomes [16,1,0,9, 9,100] after the sort, the array becomes [0,1,9,16,100] example 2: input: 1 <= nums.length <= 104-104 <= nums[I] <= 104 Nums are sorted in non-descending order: Please design an algorithm with O(n) time complexity to solve this problemCopy the codeDouble pointer
var sortedSquares = function (nums) {
let i = 0, j = nums.length - 1, res = [], k = nums.length - 1
while (i <= j) {
if (nums[i] * nums[i] > nums[j] * nums[j]) {
res[k--] = nums[i] * nums[i++]
} else {
res[k--] = nums[j] * nums[j--]
}
}
return res
};
Copy the codereduce+sort
var sortedSquares = function (nums) {
return nums.reduce((acc, prev) = > acc.concat(prev * prev), []).sort((a,b) = >a-b)
};
Copy the code896. Monotone sequence
An array is monotone if it is monotonically increasing or monotonically decreasing. If for all I <= j, A[I] <= A[j], then array A is monotonically increasing. If for all I <= j, A[I]> = A[j], then array A is monotonically decreasing. Return true if the given array A is monotonic, false otherwise.
Example 1: input: [1,2,2,3] output: true example 2: input: [6,5,4,4] output: true example 3: input: [1,3,2] output: false example 4: input: [1,2,4,5] output: true example 5: input: 1 <= a.length <= 50,000-100000 <= A[I] <= 100000Copy the codevar isMonotonic = function (nums) {
let inc =true,dec = true
for(let i=0; i<nums.length; i++){if(nums[i+1]-nums[i]>0){
dec = false
}
if(nums[i]-nums[i+1] >0){
inc = false}}return dec || inc
};
Copy the code941. Valid array of mountains
Given an integer array arr, return true if it is a valid array of mountains, false otherwise.
Let’s recall that A is an array of mountains if it satisfies the following conditions:
Arr. Length >= 3 In the case of 0 < I < arr. Length - 1, there exists I such that: arr[0] < arr[1] <... arr[i-1] < arr[i] arr[i] > arr[i+1] > ... > arr[arr.length - 1]Copy the codeExample 1: input: arr = [2,1] output: false example 2: input: arr = [3,5,5] output: false example 3: input: arr = [0,3,2,1] output: true warning: 1 <= arr.length <= 104 0 <= arr[i] <= 104Copy the codeDouble pointer
const validMountainArray = (A) = > {
const n = A.length;
let i = 0;
let j = n - 1;
while (i + 1 < n && A[i] < A[i + 1]) {
i++;
}
while (j - 1> =0 && A[j - 1] > A[j]) {
j--;
}
if(i ! =0&& i == j && j ! = n -1) {
return true;
}
return false;
};
Copy the code167. Sum of two numbers II – Enter ordered array
Given an array of integers in non-decreasing order numbers, find two numbers that add up to the target number.
The function should return the subscript values of these two numbers as an array of integers of length 2. The subscript of numbers starts at 1, so the answer array should be 1 <= answer[0] < answer[1] <= numbers. Length.
You can assume that each input corresponds to a unique answer, and you can’t reuse the same elements.
Example 1: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 equals the target number 9. So index1 = 1, index2 = 2. Example 2: Input: numbers = [2,3,4] target = 6 Output: [1,3] Example 3: Input: numbers = [-1,0] Target = -1 Output: [1,2] Hint: 2 <= numbers. Length <= 3 * 104-1000 <= numbers[I] <= 1000 numbers in non-decreasing order -1000 <= target <= 1000 Only one valid answer existsCopy the codeDouble pointer
var twoSum = function (numbers, target) {
let i = 0, j = numbers.length-1;
while (i <= j) {
if (numbers[i] + numbers[j] > target) {
j--
} else if (numbers[i] + numbers[j] === target) {
return [++i, ++j]
} else {
i++
}
}
};
Copy the code1984. Minimum difference in student scores
You are given an array of integers with subscripts starting at 0, nums[I], where nums represents the grade of the ith student. I’ll give you another integer k.
Pick the scores of any k students from the array to minimize the difference between the highest and lowest scores of the k students. Returns the smallest possible difference.
Example 1: Input: nums = [90], k = 1 Output: 0 Explanation: There is only 1 way to select a student's score: - [90] The difference between the highest and lowest score is 90-90 = 0 The lowest possible difference is 0 Example 2: Input: Nums = [9,4,1,7], k = 2 - [9,4,1,7] The difference between the highest and lowest scores is 9-4 = 5 - [9,4,1,7] The difference between the highest and lowest scores is 9-1 = 8 - [9,4,1,7] the difference between the highest and lowest scores is 9-7 = 2 - [9,4,1,7] The difference between the highest score and the lowest score is 4-1 = 3 - [9,4,1,7] the difference between the highest score and the lowest score is 7-4 = 3 - [9,4,1,7] the difference between the highest score and the lowest score is 7-1 = 6. 1 <= k <= nums.length <= 1000 0 <= nums[i] <= 1Copy the codevar minimumDifference = function (nums, k) {
nums = nums.sort((a, b) = > a - b)
let ret = Infinity
for (let i = 0; i + k - 1 < nums.length; i++) {
if (nums[i + k - 1] - nums[i] < ret) {
ret = nums[i + k - 1] - nums[i]; }}return ret
};
Copy the code1436. Tour terminus
Paths [I] = [cityAi, cityBi] indicates that the paths will go directly from cityAi to cityBi. Find the final destination of the tour, a city that does not have any route to any other city.
The problem data guarantees that the route diagram will form a circuit with no loops, so that there is exactly one travel destination.
Example 1: Enter: Paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"] It starts at London and ends at Sao Paulo. The itinerary for this trip is "London" -> "New York" -> "Lima" -> "Sao Paulo". Example 2: input: paths = [[" B ", "C"], [" D ", "B"], [" C ", "A"]] output: "A" explanation: all possible routes are: "D" -> "B" -> "C" -> "A". "B" -> "C" -> "A". "C" -> "A". "A". Obviously, the end of the trip is "A". Example 3: Enter: Paths = [["A","Z"]] 1 <= paths.length <= 100 paths[i].length == 2 1 <= cityAi.length, cityBi.length <= 10 cityAi ! = cityBi All characters consist of uppercase and lowercase letters and Spaces.Copy the codeSet
var destCity = function(paths) {
let ans = new Set(a)for(let i of paths){
ans.add(i[0])}for(let j of paths){
if(! ans.has(j[1])){
return j[1]}}return ' '
};
Copy the codeThe middle node of a linked list
Given a non-empty singly linked list with head, return the middle node of the list.
If there are two intermediate nodes, the second intermediate node is returned.
Example 1: Input: [1,2,3,4,5] Output: Node 3 in this list (serialized form: [3,4,5]) returns the value of node 3. (the serialization statement of this node in the evaluation system is [3,4,5]). Val = 3, ans.next-val = 4, ans.next-next-val = 5, and ans.next-next-next = NULL. Example 2: input: [1,2,3,4,5,6] output: node 4 in this list (serialized form: [4,5,6]) since the list has two intermediate nodes with values 3 and 4, we return the second node. Tip: The number of nodes in a given linked list is between 1 and 100.Copy the codevar middleNode = function(head) {
let slow = head,fast = head;
while(fast! = =null&& fast.next! = =null){
slow = slow.next;
fast = fast.next.next;
}
return slow
};
Copy the code374. Guess the number size
374. Guess the number size
The rules of the number guessing game are as follows: In each round, I choose a random number from 1 to N. Guess which number you picked. If you’re wrong, I’ll tell you if your guess is bigger or smaller than my pick.
You can get the guess result by calling a predefined interface int guess(int num), which returns a total of three possible values (-1, 1 or 0) : -1: I picked a smaller number than you guessed pick < num 1: I picked a larger number than you guessed 0: I picked the same number as you guessed. A: congratulations! You guessed it! pick == num
Returns the number I selected.
Example 1: Input: n = 10, pick = 6 Output: 6 Example 2: Input: n = 1, pick = 1 Output: 1 Example 3: Input: n = 2, pick = 1 Output: 1 Example 4: Input: n = 2, pick = 2 Output: 2 Tips: 1 <= n <= 231-1 1 <= pick <= nCopy the codedichotomy
var guessNumber = function (n) {
let left = 1, right = n
while (left < right) {
const mid = Math.floor((right - left) / 2 + left)
if (guess(mid) <= 0) {
right = mid
} else {
left = mid + 1}}return left
};
Copy the code405. Convert digits to hexadecimal numbers
405. Convert digits to hexadecimal numbers
Given an integer, write an algorithm to convert the number to hexadecimal. For negative integers, we usually use complement operations.
Note:
All hexadecimal letters (a-f) must be lowercase. A hexadecimal string cannot contain redundant leading zeros. If the number to be converted is 0, it is represented by a single character '0'. In other cases, the first character in a hexadecimal string will not be a 0 character. The given number is guaranteed to be within the range of 32-bit signed integers. You cannot use any of the methods provided by the library to convert or format numbers directly into hexadecimal.Copy the codeExample 1: Input: 26 Output: "1A" Example 2: Input: -1 Output: "FFFFFFFF"Copy the codevar toHex = function (num) {
const hex = [0.1.2.3.4.5.6.7.8.9.'a'.'b'.'c'.'d'.'e'.'f']
if (num === 0) {
return '0'
}
let ans = "";
if (num < 0) {
num = Math.pow(2.32) - Math.abs(num);
}
while (num) {
ans += hex[num % 16];
num = Math.floor(num / 16);
}
return ans.split("").reverse().join("");
};
Copy the code643. Maximum mean of subarray I
You are given an integer array of n elements nums and an integer k. Find a continuous subarray with the maximum mean of length K and print that maximum mean.
Any answer less than 10-5 will be considered correct.
Example 1: Input: nums = [1,12,-5,-6,50,3], k = 4 Output: 12.75 Description: Maximum average (12-5-6+50)/4 = 51/4 = 12.75 Example 2: Input: nums = [5], k = 1 Output: N == nums.length 1 <= k <= n <= 105-104 <= nums[I] <= 104Copy the codevar findMaxAverage = function (nums, k) {
let max = ans = [...nums].slice(0, k).reduce((acc, prev) = > acc += prev);
for (let i = 1; i <= nums.length - k; i++) {
ans = ans - nums[i - 1] + nums[i + k - 1]
max = Math.max(ans, max)
}
return max / k
};
Copy the code283. Move the zero
Given an array nums, write a function to move all zeros to the end of the array while preserving the relative order of the non-zero elements.
Example: input: [0,1,0,3,12] output: [1,3,12,0,0] note: you must operate on the original array and cannot copy additional arrays. Minimize the number of operations.Copy the codevar moveZeroes = function (nums) {
let i = 0, j = 0;
while (i < nums.length) {
if(nums[i] ! =0) {
nums[j++] = nums[i]
}
i++
}
for (let a = j; a < nums.length; a++) {
nums[a] = 0
}
return nums
};
Copy the codeKeep it up, keep it up!