给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。 异或、位运算。 有一个简化版的题目： 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。…
剑指offer67题-No40.数组中只出现一次的数字
剑指offer67题-No38-39.二叉树的深度、平衡二叉树
No38：二叉树的深度 简单递归或者层次遍历 class Solution { public: int maxDeep = 0; int curDeep = 0; void dfs(TreeNode* root){ if(root == nullptr) return; curDeep++; maxDeep = max(curDeep, maxDe…
剑指offer67题-No37.第一个只出现一次的字符
用两个二分板子，分别是找左边界和右边界的二分。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param k int整型 * @return int整型 */ int GetNumberOfK(…
剑指offer67题-No36.两个链表的第一个公共节点
双指针算法 法1： 计算 List1 和 List2 的长度 len1 和 len2。 让较长的链表的指针先走 |len1 - len2| 步。 然后两个指针一起走，直到相遇或到达 NULL。 struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode*…
剑指offer67题-No35.数组中的逆序对
归并排序 在合并数组的时候，当发现右边的小于左边的时候，此时可以直接求出当前产生的逆序对的个数。可以参考acwing的题解：AcWing 788. 【算法基础课】逆序对的数量（归并排序） - AcWing #include <vector> class Solution { public: long long merge(vector<…
剑指offer67题-No33.第N个丑数
数学模拟题， 只包含质因子2、3和5的数称作丑数，所以丑数的形式实质上是：2x3y5z。 对于x、y、z的理解，把他们视作三个独立维护的指针，可以想象有三个队列： 队列2: 1×2 → 2×2 → 3×2 → 4×2 → ...队列3: 1×3 → 2×3 → 3×3 → 4×3 → ...队列5: 1×5 → 2×5 → 3×5 → 4×5 → …
剑指offer67题-No31.整数中1出现的次数
感觉像是模拟题，法1，暴力遍历，时间复杂度应该是On class Solution { public: int get1(int x){ int sum = 0; while(x){ if(x % 10 == 1){ sum++; } x = x / 10; } return sum; } int NumberOf1Between1AndN_Sol…
剑指offer67题-No30.连续子树的最大和
动态规划 方法1，可以通过暴力On^2的方法，循环两次求出每个子数组的和对比。 法2.DP 设dp[i]，dp[i]代表以array[i]为结尾的连续子数组最大和。 转移方程为，dp[i] = max(array[i]，dp[i-1] + array[i])，理解如下： 因为以第n个数为结尾，所以array[n]是必然被选择的 基于dp[n-1]的…