Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb702a48

Browse files
committed
solved search a 2D matrix problems
1 parent26f7fd6 commitb702a48

File tree

4 files changed

+109
-0
lines changed

4 files changed

+109
-0
lines changed
Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* function TreeNode(val) {
4+
* this.val = val;
5+
* this.left = this.right = null;
6+
* }
7+
*/
8+
/**
9+
*@param {TreeNode} root
10+
*@return {number[]}
11+
*/
12+
varrightSideView=function(root){
13+
if(!root)return[];
14+
varresult=[];
15+
varqueue=[root];
16+
17+
while(queue.length>0){
18+
result.push(queue[queue.length-1].val);
19+
varnextLevel=[];
20+
for(vari=0;i<queue.length;i++){
21+
if(queue[i].left){
22+
nextLevel.push(queue[i].left);
23+
}
24+
if(queue[i].right){
25+
nextLevel.push(queue[i].right);
26+
}
27+
}
28+
queue=nextLevel;
29+
}
30+
31+
returnresult;
32+
};
33+
34+
// more concise, no need to track each level.
35+
varrightSideView=function(root){
36+
if(!root)return[];
37+
varresult=[];
38+
varqueue=[root];
39+
40+
while(queue.length>0){
41+
result.push(queue[queue.length-1].val);
42+
varqueueLength=queue.length;
43+
for(vari=0;i<queueLength;i++){
44+
varnode=queue.shift();
45+
if(node.left){
46+
queue.push(node.left);
47+
}
48+
if(node.right){
49+
queue.push(node.right);
50+
}
51+
}
52+
}
53+
54+
returnresult;
55+
};

‎Medium/240-Search2DMatrixII.js‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
/**
2+
* Key: Start from top right, if target is less than the element, move left (col--);
3+
* if target is greater than the element, move down (row++);
4+
* O(m+n);
5+
*
6+
*@param {number[][]} matrix
7+
*@param {number} target
8+
*@return {boolean}
9+
*/
10+
varsearchMatrix=function(matrix,target){
11+
varrow=0;
12+
varcol=matrix[0].length-1;
13+
14+
while(row<=matrix.length-1&&col>=0){
15+
if(target<matrix[row][col]){
16+
col--;
17+
}elseif(target>matrix[row][col]){
18+
row++;
19+
}else{
20+
returntrue;
21+
}
22+
}
23+
returnfalse;
24+
};

‎Medium/74-search2DMatrix.js‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
/**
2+
*@param {number[][]} matrix
3+
*@param {number} target
4+
*@return {boolean}
5+
*/
6+
varsearchMatrix=function(matrix,target){
7+
varlow=0;
8+
varrows=matrix.length;
9+
varcols=matrix[0].length;
10+
varhigh=rows*cols-1;
11+
12+
while(low<=high){
13+
varmid=low+Math.floor((high-low)/2);
14+
varmidNumber=findElementByIndex(matrix,mid,rows,cols);
15+
if(target<midNumber)high=mid-1;
16+
elseif(target>midNumber)low=mid+1;
17+
elsereturntrue;
18+
}
19+
20+
returnfalse;
21+
};
22+
23+
varfindElementByIndex=function(matrix,index,m,n){
24+
varrow=Math.floor(index/n);
25+
varcol=index-n*row;
26+
returnmatrix[row][col];
27+
};

‎README.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -76,6 +76,7 @@
7676
*[59. Spiral Matrix II](https://leetcode.com/problems/spiral-matrix-ii/) -[Solution](./Medium/59-spiralMatrixII.js)
7777
*[62.Unique Paths](https://leetcode.com/problems/unique-paths/) -[Solution](./Medium/62-uniquePaths.js)
7878
*[64.Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/) -[Solution](./Medium/64-minimumPathSum.js)
79+
*[74. Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/) -[Solution](./Medium/74-search2DMatrix.js)
7980
*[75. Sort Colors](https://leetcode.com/problems/sort-colors/) -[Solution](./Medium/75-sortColors.js)
8081
*[77.Combinations](https://leetcode.com/problems/combinations/) -[Solution](./Medium/77-combinations.js)
8182
*[89. Gray Code](https://leetcode.com/problems/gray-code/) -[Solution](./Medium/89-grayCode.js)
@@ -89,9 +90,11 @@
8990
*[141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/) -[Solution](./Medium/141-linkedListCycle.js)
9091
*[144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/) -[Solution](./Medium/144-binaryTreePreorder.js)
9192
*[153.Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/) -[Solution](./Medium/153-findMinimumInRotatedSortedArray.js)
93+
*[199. Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/) -[Solution](./Medium/199-binaryTreeRightSideView.js)
9294
*[213. House Robber II](https://leetcode.com/problems/house-robber-ii/) -[Solution](./Medium/213-houseRobberII.js)
9395
*[230. Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/) -[Solution](./Medium/230-kthSmallestElementinBST.js)
9496
*[238. Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/) -[Solution](./Medium/238-productExceptSelf.js)
97+
*[240. Search a 2D Matrix II](https://leetcode.com/problems/search-a-2d-matrix-ii/) -[Solution](./Medium/240-Search2DMatrixII.js)
9598
*[260. Single Number III](https://leetcode.com/problems/single-number-iii/) -[Solution](./Medium/260-singleNumberIII.js)
9699
*[268. Missing Number](https://leetcode.com/problems/missing-number/) -[Solution](./Medium/268-missingNumber.js)
97100
*[300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/) -[Solution](./Medium/300-longestIncreasingSubsequence.js)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp