思路 双指针因为A的空间是足够大的，所以将A数组和B数组中的最大的依次放在A的最后 所以双指针，分别指向A和B的尾部，比较其大小，大的放在A的最后 代码 class Solution { public: void merge(int A[], int m, int B[], int n) { // A的空间大，所以放在A中 int i = m-1; int j = n-1; int k = m+n-1; while(i>=0 && j>=0){ if(...

思路 1、广度优先搜索2、pair<int, int> 保存坐标3、遍历每一个点，如果发现是1，那么count++，并将其置为0，然后把这个pos放在队列中（广度优先），当队列不为空的时候做下面的事情：取坐标、判断上下左右是否为1，若为1则加入到队列中并将其置为0（防止重复计数），直至遍历整个二维矩阵 代码 class Solution { public: /** * 判断岛屿数量 * @param grid char字符型vector<vector<>> * @return int整型 */ int...

思路 借助快排的Partition函数注意：1、是第K大，因此Partition返回的结果要和n-K比较！！！ 代码 class Solution { public: int Partition(vector<int>& arr, int L, int R ){ int right = R; int left = L; int key = arr[left]; while(left< right){ while(left< right && arr...

思路 参考《剑指offer》1、一个数字出现次数超过一半，那么排序后的中间位置的元素肯定就是这个要求的数字2、借助Partition函数，返回一个索引index，代表该位置的元素在排序后的数组中下标是index，比arr[index]小的都在左侧，比arr[index]大的都在右侧；3、根据index和middle的大小关系，更新start、end区间，继续Partition，直到index==middle 代码 class Solution { public: int Partition(vector<int>& arr, int L, int R){ ...

思路 参考剑指offer1、首先使用快排的思想，对一个数组进行分割，大于某个值的在其右侧，小于某个值的在其左侧，该函数(Partition)返回一个索引，代表选择的数字的下标（可能有点绕）。2、然后就是根据这个返回的索引和k-1（需要k个数，下标范围就是0~k-1）比较，若返回的index<k-1，那么说明第k-1小的数字在index的右侧，更新区间，计算新的index。 代码 class Solution { public: void swap(int& a, int& b){ int tmp = a; a = b; ...

树的子结构 思路 1、原始函数的功能是：判断root1的树中是否存在root2，因此当遇到节点值不相等的时候，判断root1的左子树是否包含root2 或者 root1的右子树是否包含root2的树（递归） 2、辅助函数的功能：判断以当前节点为根的树是否相等，若节点相等，则继续比较对应的左右节点是否相等（递归） 代码 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL...

思路 和按层打印二叉树一样，也是广度优先（队列实现）注意的是需要指定一个奇偶位置，根据这个奇偶来设置保存的方式（是否reverse） 代码 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: vector<vector<int> >...

丑数 思路 1、使用一个数组保存之前的丑数2、更新下一个丑数的时候只需要比较三个值即可3、所以，程序的核心就是维护好三个值（对应的下标） 代码 class Solution { public: bool isUgly(int x ){ while(x%2==0){ x = x/2; } while(x%3==0){ x=x/3; } while(x%5==0){ x=x/5; } return 1...

二分法查找 注意：1、升序--->二分2、先找到一个数，然后向两边找3、注意保存mid的值，方便作为反向查找的起点4、多次统计注意区分 代码 class Solution { public: int GetNumberOfK(vector<int> data ,int k) { int l = 0; int r = data.size()-1; int res = 0; while(l<=r){ int mid = (l+r)/2; if(data[m...

递归实现二叉树前、中、后序遍历 注意：三者的区别就是处理根节点的时间 代码 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 the root of binary tree * @return int整型vector<vector<>> */ ...

二分查找 注意：1、二分查找的while(left<=right)2、更新起始终止点：left = mid+1; right = mid-1; 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 如果目标值存在返回下标，否则返回 -1 * @param nums int整型vector * @param target int整型 * @return int整型 */ int search(vecto...