leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0074.cpp (1651B)

0 class Solution { 1 public: 2 bool searchMatrix(vector<vector<int>> &matrix, int target) { 3 int n = matrix.size(), m = matrix[0].size(), row = n - 1; 4 for (int i = 0; i < n - 1; i++) { 5 if (matrix[i + 1][0] > target) { 6 row = i; 7 break; 8 } 9 } 10 11 int low = 0, high = m - 1; 12 while (low <= high) { 13 int mid = low + (high - low) / 2; 14 if (matrix[row][mid] == target) 15 return true; 16 else if (matrix[row][mid] < target) 17 low = mid + 1; 18 else 19 high = mid - 1; 20 } 21 return false; 22 } 23 }; 24 25 // Treat the matrix as a sorted list 26 class Solution { 27 public: 28 bool searchMatrix(vector<vector<int>> &matrix, int target) { 29 int n = matrix.size(), m = matrix[0].size(); 30 int low = 0, high = m * n - 1; 31 while (low <= high) { 32 int mid = low + (high - low) / 2; 33 if (matrix[mid / m][mid % m] == target) return true; 34 if (matrix[mid / m][mid % m] < target) 35 low = mid + 1; 36 else 37 high = mid - 1; 38 } 39 return false; 40 } 41 }; 42 43 // Binary Search Tree 44 class Solution { 45 public: 46 bool searchMatrix(vector<vector<int>> &matrix, int target) { 47 int n = matrix.size(), m = matrix[0].size(); 48 int row = 0, col = m - 1; 49 50 while (row < n && col > -1) { 51 if (matrix[row][col] == target) return true; 52 if (target > matrix[row][col]) 53 row++; 54 else 55 col--; 56 } 57 return false; 58 } 59 };