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

剑指 Offer 55 - II. 平衡二叉树
/*** 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:bool isBalanced(TreeNode* root) {if (!root) {return 1;}return isBalanced(root->left) && isBalanced(root->right) && abs(dfs(root->left) - dfs(root->right)) < 2;}private://计算深度int dfs(TreeNode *root) {if (!root) {return 0;}return max(dfs(root->left), dfs(root->right)) + 1;}};
平衡二叉树的要求是，每个节点的左右子树深度差不超过1，那么我们就可以将其分为两步，一步是计算一个节点的高度差，另一步就是以平衡二叉树的条件遍历每一个节点，保证其每个节点都是平衡二叉树，这个数整体才是平衡二叉树。
剑指 Offer 56 - I. 数组中数字出现的次数
class Solution {public:vector singleNumbers(vector& nums) {//获取两个只出现一次的数字的 ^ 操作的值int x = 0;for (auto i : nums) {x ^= i;}// x & (-x)本身的作用是得到最低位的1，因为x是两个不同的数^操作的结果，所以其不可能在相同的二进制位上都是1，所以我们可以通过此特性将其分开，得到其中一个数，使用flag对数组进行&运算，获取最低位也是1的数，并给另一个变量result一直^该最低位也是1的数，因为相同的会抵消，所以最终result一定会是两个只出现一次的数的其中一个，我们有了这个数，又有了其与另一个只出现一次的数的^结果，那么它两个在进行^操作就是另一个数了。int flag = x & (-x), result = 0;for (auto i : nums) {//如果其&运算不为0，那么就一直给result进行^运算，并且相同的数^操作的值是相同的，第二次进行^操作那么就会抵消掉第一次的^操作if (flag & i) {result ^= i;}}return {result, x ^ result};}};
这里利用了抑或运算的特性，相同的数进行疑惑运算结果为0，那么我们对整个数组进行抑或运算就得到了两个只出现一次的数的抑或结果x 。此时的问题就成了怎么获取其中一个数，只要我们有了其中一个只出现一次的数，那么另一个数就可以使用之前的抑或结果x和其再进行一次抑或运算就能得出另一个数了。此时我们可以想到，因为x是所有数抑或操作后的结果，再根据抑或的特性，相同二进制位相同时为0，也就是说明这两个只出现一次的数在这个位上不可能都是1，即第一个数在这个位上是1，那么另一个数在这个位上必不是1 。那么就可以通过这个特性来获取其中之一的数了，我们这里使用flag存储x & (-x)操作的结果，x & (-x)本身的作用是得到最低位的1，所以我们对数组整体再进行遍历操作，判断条件就是如果和flag与运算之后不为0，即这个数在刚求出来的最低位上也是1，那么就将其和（初始化为0）进行抑或运算，一直到数组结束，还是因为上边所说的，相同的数进行抑或运算之后结果为0，所以遍历完一遍之后这个就是两个数其中的一个数了，剩下的操作上边也都说过了，这样就得到了这两个只出现一次的数了。
剑指 Offer 56 - II. 数组中数字出现的次数 II
方法一：class Solution {public:int singleNumber(vector& nums) {int ones = 0, twos = 0;for (int num : nums) {ones = ones ^ num & ~twos;twos = twos ^ num & ~ones;}return ones;}};
方法一：自己创建一个三进制方法，看不太懂。
方法二：如果一个数字出现3次，它的二进制每一位也出现的3次。如果把所有的出现三次的数字的二进制表示的每一位都分别加起来，那么每一位都能被3整除。我们把数组中所有的数字的二进制表示的每一位都加起来。如果某一位能被3整除，那么这一位对只出现一次的那个数的这一肯定为0 。如果某一位不能被3整除，那么只出现一次的那个数字的该位置一定为1 。

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

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