給你一個整數(shù)數(shù)組 nums 姚建，判斷這個數(shù)組中是否存在長度為 3 的遞增子序列矫俺。
如果存在這樣的三元組下標 (i, j, k) 且滿足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true 厘托；否則友雳，返回 false 。
示例 1：
輸入：nums = [1,2,3,4,5]
輸出：true
解釋：任何 i < j < k 的三元組都滿足題意
var increasingTriplet = function(nums) {
let len = nums.length
let left_first = nums[len-1]
let left_second = -Infinity
for(var i=len-2;i>=0;i--){
if(nums[i]<left_second){
return true
}
nums[i]>=left_first?left_first = nums[i]:left_second = nums[i]
}
return false
};
240. 搜索二維矩陣 II
編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標值 target 铅匹。該矩陣具有以下特性：
每行的元素從左到右升序排列押赊。
每列的元素從上到下升序排列。
示例 1：
輸入：matrix = [[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]], target = 5
輸出：true
看了大神的題解包斑，自己也畫了圖
var searchMatrix = function(matrix, target) {
if(matrix.length==0){return false}
let [bottom,left] = [0, matrix[0].length-1]
while(left>=0&&bottom<matrix.length){
if(matrix[bottom][left]>target){
left--
}else if(matrix[bottom][left]<target){
bottom++
}else{
console.log('11')
return true
}
}
console.log('22')
return false
}
matrix = [[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]]
target = 5
searchMatrix(matrix, target)
除自身以外數(shù)組的乘積
除自身以外數(shù)組的乘積
給你一個長度為 n 的整數(shù)數(shù)組 nums流礁，其中 n > 1，返回輸出數(shù)組 output 舰始，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘積崇棠。
示例:
輸入: [1,2,3,4]
輸出: [24,12,8,6]
提示：題目數(shù)據(jù)保證數(shù)組之中任意元素的全部前綴元素和后綴（甚至是整個數(shù)組）的乘積都在 32 位整數(shù)范圍內(nèi)。
說明: 請不要使用除法丸卷，且在 O(n) 時間復雜度內(nèi)完成此題枕稀。
進階：
你可以在常數(shù)空間復雜度內(nèi)完成這個題目嗎？（ 出于對空間復雜度分析的目的谜嫉，輸出數(shù)組不被視為額外空間萎坷。）
var productExceptSelf = function(nums) {
let i = 0
let len = nums.length
let resArr = []
while(i<len){
let res = 1
for(var j=0;j<len;j++){
if(j!=i){
res = res*nums[j]
}
}
resArr.push(res)
i++
}
return resArr
console.log(resArr)
};
nums=[1,2,3,4]
productExceptSelf(nums)
空間復雜度o(n),時間復雜度o(n^2)
優(yōu)化時間復雜度
先算出nums[i]的左邊值，再算出nums[i]的右邊值沐兰，然后相乘
var productExceptSelf = function(nums) {
let len = nums.length
let resArr = []
let resArr1 = []
resArr[0] = 1
resArr1[len-1] = 1
for(var i=1;i<len;i++){
resArr[i]=resArr[i-1]*nums[i-1]
}
for(var j=len-2;j>=0;j--){
resArr1[j] = resArr1[j+1]*nums[j+1]
}
for(var m=0;m<len;m++){
resArr[m] = resArr[m]*resArr1[m]
}
return resArr
};
nums=[1,2,3,4]
// [ 1,1, 2, 6 ]
// [ 24, 12, 4, 1 ]
// [24,12,8,6]
productExceptSelf(nums)
時間復雜度o(2n) = o(n)
優(yōu)化上面的空間復雜度
先算出nums[i]的左邊值哆档，nums[i]的右邊值賦給一個變量，然后與左邊值相乘
var productExceptSelf = function(nums) {
let len = nums.length
let resArr = []
resArr[0] = 1
for(var i=1;i<len;i++){
resArr[i]=resArr[i-1]*nums[i-1]
}
let right_count = 1//保存右邊積
for(var j=len-2;j>=0;j--){
right_count = right_count*nums[j+1]
resArr[j] = right_count*resArr[j]
}
return resArr
};
