普通版剑指 Offer 浅刷浅刷(16) _数组

& nums, int target) {int t = 0;for (int i = 0; i < nums.size(); i++) {if (target < nums[i]) {return t;}if (nums[i] == target) {t++;}}return t;}};//方法二：class Solution {public:int binarySearch (vector& nums, int target, bool lower) {int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();while (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;}int search (vector& nums, int target) {int leftIdx = binarySearch(nums, target, true);int rightIdx = binarySearch(nums, target, false) - 1;if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {return rightIdx - leftIdx + 1;}return 0;}};
方法一：暴力求解，找次数，比查找数的值大就直接停止查找。
方法二：二分查找要找数的两端，两端相减加一就是出现次数。
方法三：哈希表，懒得写了。
剑指 Offer 53 - II. 0～n-1中缺失的数字
//方法一：class Solution {public:int missingNumber(vector& nums) {int left = 0;int right = nums.size() - 1;while(left <= right) {int mid = (left + right) / 2;/* 如果相等说明 left 到 mid 中间肯定不少元素所以往右边二分查找 *///如果nums[mid] == mid，表示左侧区域没有数字缺失，向右缩短边界//如果nums[mid] > mid，表示左侧区域数字缺失，向左缩短边界if (nums[mid] == mid) {left = mid + 1;} else {right = mid - 1;}}return left;}};
方法一：二分法查找，若该数没问题的话，那么其索引一定为其值，以此为突破口，查找第一个索引与其值不同的位置，就是缺失数。
方法二：利用等差数列的求和公式（n*（n+1）/2），算出和，然后减去该数组总和，就是缺失数。
剑指 Offer 54. 二叉搜索树的第k大节点
/*** 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 myVector;int kthLargest(TreeNode* root, int k) {transTree(root);return myVector[myVector.size() - k];}private:void transTree(TreeNode *root) {if (!root) {return;}if (root->left) {transTree(root->left);}myVector.push_back(root->val);if (root->right) {transTree(root->right);}}};//方法二：class Solution {public:int ans = 0, count = 0;int kthLargest(TreeNode* root, int k) {transTree(root, k);return ans;}private:void transTree(TreeNode *root, int k) {if (root->right) {transTree(root->right, k);}if (++count == k) {ans = root->val;return;}if (root->left) {transTree(root->left, k);}}};
二叉树的遍历，中序遍历的话它返回的就是一个有序序列，左中右是升序，右中左是降序，所以我们只要将其存储起来，最后直接返回就行了。或者我们可以直接将要返回的数用全局变量存储起来，最后直接返回就行，如方法二，但是它没有第一种快，因为它其实到最后还是会将这个遍历走完的，也没用。
剑指 Offer 55 - I. 二叉树的深度
/*** 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:int maxDepth(TreeNode* root) {if (!root) {return 0;}return max(maxDepth(root->left), maxDepth(root->right)) + 1;}};//方法二：class Solution {public:int depth = 0;int maxDepth(TreeNode* root) {dfs(root, 0);return depth;}private:void dfs(TreeNode* root, int now) {if (!root) {return;}now++;if (now >= depth) {depth = now;}dfs(root->left, now);dfs(root->right, now);} };
没啥说的，递归。但是可能是因为不含有返回值的原因吧，第二种能比第一种快一点。

普通版 剑指 Offer 浅刷浅刷(16)

普通版剑指 Offer 浅刷浅刷(16)