目前是一個編程小白，現在將一些刷題想法記錄下來，方便以后查看，現在還只能做到一題一解，希望以后可以一題多解，
—— 于2021年11月2日
例1：在一個 n * m 的二維陣列中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序，請完成一個高效的函式，輸入這樣的一個二維陣列和一個整數，判斷陣列中是否含有該整數，
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0 || matrix[0].size() == 0) //判斷不為空陣列
{
return false;
}
else
{
int n = matrix.size();
int m = matrix[0].size();
int left;
int right;
int left_index;
int right_index;
int mid_index;
for (int i = 0; i < n; i++)
{
left = matrix[i][0];
right = matrix[i][m-1];
left_index = 0;
right_index = m-1;
mid_index = 0;
while ((left <= right) && (matrix[i][0] <= target)
&& (matrix[i][m-1] >= target))
//思路是逐行進行二分法查找，滿足二分法left<=right的同時，
//要求第一個元素比target小，最后一個元素比target大
{
mid_index = (left_index + right_index)*0.5;
if (matrix[i][mid_index] < target)
{
left_index = mid_index + 1;
left = matrix[i][left_index];
}
else if (matrix[i][mid_index] > target)
{
right_index = mid_index - 1;
right = matrix[i][right_index];
}
else
{
return true;
}
}
}
}
return false;
}
};
才剛學了二分法，里面比較關鍵的點是，判斷陣列不為空，以及比較常用的vector的大小
int n = matrix.size(); //行
int m = matrix[0].size(); //列
對應的不為空，就是行列數不為0；再有一個需要注意的是 “==” 讀等于，“=” 讀賦值為，
例2：二叉樹的遍歷
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
//層序遍歷
class Solution {
public:
vector<int> levelOrder(TreeNode* root)
{
vector<int> res; //輸出的話為空陣列 []
if(root == NULL) //判斷是否為空樹
return res;
queue<TreeNode*> q; //定義一個佇列 里面存的資料結構上面有定義
q.push(root); //第一個元素
while(q.size()) //不為空
{
TreeNode* node=q.front(); //佇列第一個
q.pop(); //彈出
res.push_back(node->val); //res后面添加值
if(node->left) //如果存在
q.push(node->left);
if(node->right)
q.push(node->right);
}
return res;
}
};來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/345652.html
標籤：其他
上一篇：145. 二叉樹的后序遍歷
下一篇：非正式第十三屆藍橋杯大賽