LeetCode每周刷题总结3.06-3.12
第三周力扣记录总结：
704. 二分查找
704. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
解题思路：典中典的二分查找。定义左、右分别为数组的首位两端， mid即为中间值。通过比较mid与目标值的大小不断更新左右两端，最终返回查找值的位置。
class Solution {
public:int search(vector& nums, int target) {int l=0,r=nums.size()-1;while(l<=r){int mid=(l+r)/2;if(nums[mid]==target)return mid;if(nums[mid]l=mid+1;}if(nums[mid]>target){r=mid-1;}}return -1;}
};
136. 只出现一次的数字
136. 只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
解题思路：
- 交换律：a ^ b ^ c <=> a ^ c ^ b
- 任何数于0异或为任何数 0 ^ n => n
- 相同的数异或为0: n ^ n => 0
class Solution {
public:int singleNumber(vector& nums) {int ans = 0;for(auto x :nums)ans^=x;return ans;}
};
338. 比特位计数
338. 比特位计数
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
解题思路：
学习到了新东西——Brian Kernighan 算法。
Brian Kernighan 算法的原理是：对于任意整数 x，令 x=x & (x−1)，该运算将 x 的二进制表示的最后一个 1 变成 0。因此，对 x重复该操作，直到 x 变成 0，则操作次数即为 x 的「一比特数」。
class Solution {
public:int fun(int x){int cnt =0;while(x>0){x&=(x-1);cnt++;}return cnt;}vector countBits(int n) {vector v(n+1);for(int i =0;i<=n;i++){v[i]=fun(i);}return v;}
};
461. 汉明距离
461. 汉明距离
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
解题思路：仍然可以用上题介绍的Brian Kernighan 算法来解决。
class Solution {
public:int hammingDistance(int x, int y) {int ans= 0 ;for(int i = x^y;i!=0;i&=(i-1)){ans++;}return ans;}
};
20. 有效的括号
20. 有效的括号
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
解题思路：如果字符串为奇数列，那必定不能完全匹配。若为偶数列，将左边括号压入栈内，如果匹配则弹出否则讲返回false。
class Solution {
public:bool isValid(string s) {if(s.size() % 2 == 1)return false;stack st;for(auto x: s) {if(x == '(' || x == '{' || x == '[') st.push(x);else {if(st.empty()) return false;char left = st.top();if(x == ')') {if(left == '(') st.pop();elsereturn false;}else if (x == '}') {if(left == '{')st.pop();elsereturn false;}else if (x == ']') {if(left == '[') st.pop();else return false;}}}return st.empty();}
};
53. 最大子数组和
53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
解题思路：经典dp。
状态转移方程：
class Solution {
public:int maxSubArray(vector& nums) {int res= 0 ;int N=nums.size();vector dp(N);dp[0]=nums[0];res = dp[0];for(int i= 1 ;idp[i]=max(dp[i-1]+nums[i],nums[i]);if(res 100. 相同的树
100. 相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
解题思路：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:bool isSameTree(TreeNode* p, TreeNode* q) {if(p==nullptr&&q==nullptr)return true;else if(p==nullptr||q==nullptr)return false;else if(p->val!=q->val)return false; else return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);}
};
108. 将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
解题思路：
中序遍历，总是选择中间位置左边的数字作为根节点。选择中间位置左边的数字作为根节点，则根节点的下标为 mid=(left+right)/2。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* sortedArrayToBST(vector& nums) {return func(nums,0,nums.size()-1);}TreeNode* func(vector& nums,int left,int right){ if(left>right)return nullptr;int mid = (left+right)/2;TreeNode* root = new TreeNode(nums[mid]);root->left = func(nums,left,mid-1);root->right = func(nums,mid+1,right);return root;}
};
111. 二叉树的最小深度
111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
解题思路：
特判只有根节点的情况。
最小值初始最大化，依次与左子树和右子树相比，获得最小的值。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int minDepth(TreeNode* root) {if(root==nullptr)return 0;if(root->left==nullptr&&root->right==nullptr)return 1;int Min =INT_MAX;if(root->left!=nullptr)Min= min(minDepth(root->left),Min);if(root->right!=nullptr)Min= min(minDepth(root->right),Min);return ++Min;//Min++ 会错}
};
231. 2 的幂
231. 2 的幂
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
解题思路：
小技巧：n>0&&n&（-n）==n即为2的幂
class Solution {
public:bool isPowerOfTwo(int n) {return n>0 && (n&-n)==n;}
};
326. 3 的幂
326. 3 的幂
给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x
class Solution {
public:int MAX=1162261467;bool isPowerOfThree(int n) {return n>0&&MAX%n==0;}
};
9. 回文数
9. 回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。
解题思路：梦回大一社团集训。判断回文数字。
class Solution {
public:bool isPalindrome(int x) {if(x<0)return false;long long m =x;long long n = 0;while(x){int temp = x%10;n=n*10+temp;x/=10;}if(n==m)return true;else return false;}
};
169. 多数元素
169. 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
解题思路：利用map的特性。
class Solution {
public:int majorityElement(vector& nums) {int n = nums.size();map m;for(auto x : nums){m[x]++;if(m[x]>n/2)return x;}return -1;}
};
617. 合并二叉树
617. 合并二叉树
给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
解题思路：创建一个新树，将root1和root2上的值相加并递归回溯。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1==nullptr)return root2;if(root2==nullptr)return root1;auto root = new TreeNode(root1->val+root2->val);root->left= mergeTrees(root1->left,root2->left);root->right= mergeTrees(root1->right,root2->right);return root;}
};
本周有一两天因为身体原因和四级考试原因鸽了。下周数据结构复习提上日程，因此下周不会再鸽了。感谢大家观看。