An increasing triadic subsequence
Given an array of integers, nums, determine if there is an increasing subsequence of length 3 in the array. Return true if such a triplet subscript (I, j, k) exists and I < j < k such that nums[I] < nums[j] < nums[k]; Otherwise, return false.
Example 1:
Enter: nums = [1.2.3.4.5] output:trueAny triplet of I < j < k satisfies the above descriptionCopy the codeExample 2:
Enter: nums = [5.4.3.2.1] output:falseExplanation: There are no triples that satisfy the questionCopy the codeExample 3:
Enter: nums = [2.1.5.0.4.6] output:trueExplanation: Triples (3.4.5) 满足题意，因为 nums[3] = =0 < nums[4] = =4 < nums[5] = =6
Copy the codeTip:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
Copy the codeAdvanced: Can you implement a time complexity O(n), space complexity O(1) solution?
Idea one
1. Find the smallest and subsmallest values and compare them to the current element; 2. Update the minimum and subminimum values. 2
// Import the Math library
import (
"math"
)
func increasingTriplet(nums []int) bool {
// Record the smallest and second smallest values
m1, m2 := math.MaxInt32, math.MaxInt32
for _, v := range nums {
// Find the first element of the subsequence
if m1 >= v {
m1 = v
} else if m2 >= v {
// Find the second element of the subsequence
m2 = v
} else {
// Find the third one
return true}}return false
}
Copy the codeJavascript
/ * * *@param {number[]} nums
* @return {boolean}* /
var increasingTriplet = function (nums) {
let min = nums[0], temp = Number.MAX_VALUE
// Minimum value, intermediate value
for (let i = 1; i < nums.length-1; i++) {
// Find the minimum value
min = Math.min(min, nums[i])
// Find the median
if (nums[i] > min) {
temp = nums[i]
}
// Find the third value
if (temp < nums[i + 1]) {
return true}}return false
};
Copy the codeWrite an efficient algorithm to determine whether there is a target value in an M x n matrix. The matrix has the following characteristics:
The integers in each row are arranged in ascending order from left to right. The first integer in each line is greater than the last integer in the previous line. Example 1:
Input: matrix = [[1.3.5.7], [10.11.16.20], [23.30.34.60]], target = 3Output:true
Copy the codeExample 2:
Input: matrix = [[1.3.5.7], [10.11.16.20], [23.30.34.60]], target = 13Output:false
Copy the codeTip:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-104 <= matrix[i][j], target <= 104
Copy the codeGo array lookup
func searchMatrix(matrix [][]int, target int) bool {
m := len(matrix)
n := len(matrix[0])
var i = 0
for i < m && n > 0 {
if target == matrix[i][n- 1] {
return true
} else if target < matrix[i][n- 1] {
n--
} else {
i++
}
}
return false
}
Copy the codeJavascript violent solution
/ * * *@param {number[][]} matrix
* @param {number} target
* @return {boolean}* /
var searchMatrix = function(matrix, target) {
for(let i=0; i<matrix.length; i++){for(let j=0; j<matrix[0].length; j++){if(matrix[i][j]===target){
return true}}}return false
};
Copy the codeJavascript array lookup
/ * * *@param {number[][]} matrix
* @param {number} target
* @return {boolean}* /
/* Use the lower left corner of the two-dimensional array as the origin of the rectangular axis. If the current number is greater than the search number, the search moves up one bit. If the current number is less than the search number, the search is moved one bit to the right. * /
var searchMatrix = function(matrix, target) {
let x = matrix.length-1,y = 0
while(x>=0 && y<matrix[0].length){
if(matrix[x][y]===target){
return true
}else if(matrix[x][y]>target){
x--
}else{
y++
}
}
return false
};
Copy the codeJavascript dichotomy
/ * * *@param {number[][]} matrix
* @param {number} target
* @return {boolean}* /
var searchMatrix = function(matrix, target) {
let m = matrix.length,n=matrix[0].length
let low = 0,high = m*n-1
while(low<=high){
let mid = Math.floor((high-low)/2)+low / / the median
let x = matrix[Math.floor(mid/n)][mid%n] // The value where
if(x<target){
low = mid+1
}else if(x>target){
high = mid-1
}else{
return true}}return false
};
Copy the codeBoth types of Typescript can also be changed to TS
function searchMatrix(matrix: number[][], target: number) :boolean {
let x: number = matrix.length - 1.y:number = 0
while (x >= 0 && y < matrix[0].length) {
if (matrix[x][y] === target) {
return true
} else if (matrix[x][y] > target) {
x--
} else {
y++
}
}
return false
};
Copy the codePython brute force solution
class Solution(object) :def searchMatrix(self.matrix.target) :for i in range(len(matrix)) :for j in range(len(matrix[0])) :if matrix[i] [j]==target:
return True
return False
Copy the codePython any function
The any() function checks whether a given iterable argument is all False, and returns False, or True if any of the iterable arguments is True. Elements count TRUE except for 0, null, and FALSE.
grammar
def any(可迭代) :
for element in iterable:
if element:
return True
return False
Copy the codesolution
class Solution(object) :
def searchMatrix(self, matrix, target) :
return any(target in row for row in matrix)
Copy the codeStupid factorial
In general, the factorial of a positive integer n is the product of all positive integers less than or equal to n. For example, factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1. Instead, we designed a clumsy factorial: in a descending sequence of integers, we replaced the original multiplication operators in turn with a fixed sequence of operators: multiplication (*), division (/), addition (+), and subtraction (-).
For example, clumsy(10) = 10 * 9/8 + 7-6 * 5/4 + 3-2 * 1. However, these operations still use the usual arithmetic order: we perform all the multiplication and division steps before any addition or subtraction steps, and process the multiplication and division steps from left to right.
Also, the division we’re using is floor division, so 10 times 9/8 is 11. This guarantees that the result is an integer.
Implement the stupid function defined above: given an integer N, it returns the stupid factorial of N.
Example 1:
Input:4Output:7Explanation:7 = 4 * 3 / 2 + 1
Copy the codeExample 2:
Input:10Output:12Explanation:12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1
Copy the codeTip:
1 <= N <= 10000
-2^31 <= answer <= 2^31 - 1The answer is guaranteed to match32An integer.Copy the codeGOLang
func clumsy(N int) int {
if N == 1 {
return 1
} else if N == 2 {
return 2
} else if N == 3 {
return 6
} else if N == 4 {
return 7
}
if N%4= =0 {
return N + 1
} else if N%4< =2 {
return N + 2
} else {
return N - 1}}Copy the codejavascript
/ * * *@param {number} N
* @return {number}* /
var clumsy = function (N) {
if (N === 1) {
return 1
} else if (N === 2) {
return 2
} else if (N === 3) {
return 6
} else if (N === 4) {
return 7
}
if (N % 4= = =0) {
return N + 1
} else if (N % 4< =2) {
return N + 2
} else {
return N - 1}};Copy the codepython
class Solution(object) :
def clumsy(self, N) :
""" :type N: int :rtype: int """
if N == 1:
return 1
elif N == 2:
return 2
elif N == 3:
return 6
elif N == 4:
return 7
if N % 4= =0:
return N + 1
elif N % 4< =2:
return N + 2
else:
return N - 1
Copy the codetypescript
function clumsy(N: number) :number {
if (N === 1) {
return 1
} else if (N === 2) {
return 2
} else if (N === 3) {
return 6
} else if (N === 4) {
return 7
}
if (N % 4= = =0) {
return N + 1
} else if (N % 4< =2) {
return N + 2
} else {
return N - 1}};Copy the code17.21. Water volume of the histogram
Difficulty :[difficulty]
Given a histogram (also known as a bar chart), suppose someone poured water from it in a steady stream. How much water could the histogram eventually hold? The width of the histogram is 1.
Above is the histogram represented by the array [0,1,0,2,1,0,1,3,2,1,2,1,1], which in this case can be followed by six units of water (the blue part represents water). Thanks to Marcos for contributing this image.
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1,1] output: 6Copy the code【 idea 】 Dynamic planning
1. Record each element in height, scanning from left to right and recording the maximum height on the right; 2. Record each element in height, scanning from right to left and recording the maximum height on the right; 3. Compare the left and right elements to the smallest element and subtract the height of the current element.
Scan from left to right and record the maximum height on the right
Scan from right to left and record the maximum height on the right
Take the minimum height
go
func trap(height []int) int {
n := len(height)
if n == 0 {
return 0
}
// Record the maximum height of each element on the left
leftMax := make([]int, n)
leftMax[0] = height[0]
for i := 1; i < n; i++ {
leftMax[i] = max(leftMax[i- 1], height[i])
}
// Record the maximum height of each element on the left
rightMax := make([]int, n)
rightMax[n- 1] = height[n- 1]
for i := n - 2; i >= 0; i-- {
rightMax[i] = max(rightMax[i+1], height[i])
}
fmt.Println(leftMax, rightMax)
ret := 0
for j := 0; j < n; j++ {
ret += (min(leftMax[j], rightMax[j]) - height[j])
}
return ret
}
// Since there is no Max () in Go,min() needs to implement one of its own
func max(a, b int) int {
if a-b > 0 {
return a
}
return b
}
func min(a, b int) int {
if a-b > 0 {
return b
}
return a
}
Copy the codeJavascript
var trap = function (height) {
let len = height.length
if (len === 0) return 0
// Record the maximum height of each rectangle on the left
let left = Array(len).fill(0)
left[0] = height[0]
for (let i = 1; i < len; ++i) {
left[i] = Math.max(left[i - 1], height[i])
}
// Record the maximum height of each rectangle on the right
let right = Array(len).fill(0)
right[len - 1] = height[len - 1]
for (let i = len - 2; i >= 0; --i) {
right[i] = Math.max(right[i + 1], height[i])
}
// Record the result
let ret = 0
for (let i = 0; i < len; ++i) {
// Subtract the height of the current rectangle
ret += Math.min(left[i], right[i]) - height[i]
}
return ret
};
Copy the codeTypescript
function trap(height) {
var len = height.length;
if (len === 0)
return 0;
// Record the maximum height of each rectangle on the left
var left = Array(len);
left[0] = height[0];
for (var i = 1; i < len; ++i) {
left[i] = Math.max(left[i - 1], height[i]);
}
// Record the maximum height of each rectangle on the right
var right = Array(len);
right[len - 1] = height[len - 1];
for (var i = len - 2; i >= 0; --i) {
right[i] = Math.max(right[i + 1], height[i]);
}
// Record the result
var ret = 0;
for (var i = 0; i < len; ++i) {
// Subtract the height of the current rectangle
ret += Math.min(left[i], right[i]) - height[i];
}
return ret;
}
Copy the codepython
class Solution(object) :
def trap(self, height) :
""" :type height: List[int] :rtype: int """
if not height:
return 0
Array length
n = len(height)
Record the maximum height of each rectangle on the left
left = [0]*n
left[0] = height[0]
for i in range(1,n):
left[i] = max(left[i - 1], height[i])
Record the maximum height of each rectangle on the right
right = [0]*n
right[n - 1] = height[n - 1]
for i in range(n-2, -1, -1):
right[i] = max(right[i + 1], height[i])
# record results
ret = sum(min(left[i], right[i]) - height[i] for i in range(n))
return ret
Copy the codeKeep it up!