21.给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1" 输出: "100"
示例 2:
输入: a = "1010", b = "1011" 输出: "10101"
class Solution {
public:
string addBinary(string a, string b) {
int la = a.size();
int lb = b.size();
if(la < lb){
swap(a, b);
swap(la, lb);
}
if(la - lb > 0)
b.insert(0, la - lb, '0');
int pre = 0, cur = 0;
string res;
for(int i = la - 1; i >= 0; i--){
int ia = a[i] - '0';
int ib = b[i] - '0';
cur = ia ^ ib ^ pre; // 二进制数相加结果与异或结果相同
if(ia + ib + pre >= 2) pre = 1;
else pre = 0;
res.insert(0, 1, cur + '0');
}
if(pre) // 最高位的进位单独处理
res.insert(0, 1, pre + '0');
return res;
}
};
22.实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4 输出: 2
示例 2:
输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
class Solution {
public:
int mySqrt(int x) {
// 牛顿法
// f(x) = x^2 - a
// 求解 a 的平方根, 即求解 f(x) = 0 的解
// f(x) ~= f(x0) + f'(x0)*(x - x0) ;
// 令 f(x)=0 => x=(x0 +a/x0)/2
long res=x;
while(res*res>x)
res=(res+x/res)/2;
return (int)res;
}
};
23.假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
class Solution {
public:
int climbStairs(int n) {
if(n<=3)
return n;
long t;
long a=1,b=2;
for(int i=1;i<n;i++)
{
t=a+b;
a=b;
b=t;
}
return a;
}
};
24.给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
//我自己的菜逼解法
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> res(m+n);
int i=0,j=0,k=0;
for(;i<m&&j<n;k++)
res[k]=nums1[i]<=nums2[j]?nums1[i++]:nums2[j++];
while(i<m)
res[k++]=nums1[i++];
while(j<n)
res[k++]=nums2[j++];
nums1=res;
}
};
//参考大佬答案后的高级解法
//从后往前数则不需要考虑nums1比较剩余下来的一些数
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p=m-- + n-- -1;
while(m>=0&&n>=0)
nums1[p--]=nums1[m]>nums2[n]:nums1[m--]:nums2[n--];
while(n>=0)
nums1[p--]=nums2[n--];
}
};
25.给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入: 1 1
/ \ /
2 3 2 3
[1,2,3], [1,2,3]
输出: true
示例 2:
输入: 1 1
/
2 2
[1,2], [1,null,2]
输出: false
示例 3:
输入: 1 1
/ \ /
2 1 1 2
[1,2,1], [1,1,2]
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(!(p&&q)&&(p||q))
return false;
if(!(p||q))
return true;
return (p->val==q->val)&&(isSameTree(p->left,q->left))&&(isSameTree(p->right,q->right));
}
};
26.给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/
2 2
/ \ /
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/
2 2
\
3 3
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(!root)
return true;
return isMirror(root->left,root->right);
}
bool isMirror(TreeNode* p, TreeNode* q) {
if(!(p&&q)&&(p||q))
return false;
if(!(p||q))
return true;
return (p->val==q->val)&&(isMirror(p->left,q->right))&&(isMirror(p->right,q->left));
}
};
27.给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例： 给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20
/
15 7
返回它的最大深度 3 。
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root)
return 0;
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};
28.将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9 / / -10 5
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
cout<<endl;
TreeNode *res=new TreeNode(0);
if(nums.size()<1)
return NULL;
int n=nums.size();
vector<int> nums1(n/2),nums2(n-n/2-1);
for(int i=0;i<n/2;i++)
nums1[i]=(nums[i]);
for(int i=nums.size()/2+1,j=0;i<n;i++)
nums2[j++]=(nums[i]);
res->val=nums[n/2];
res->left=sortedArrayToBST(nums1);
res->right=sortedArrayToBST(nums2);
return res;
}
};
29.给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/
9 20
/
15 7
返回 true 。
class Solution {
public:
int flag=0;
bool isBalanced(TreeNode* root) {
return high(root)+1;
}
int high(TreeNode* root)
{
if(root==NULL)
return 0;
int lhigh=high(root->left);
int rhigh=high(root->right);
if(abs(lhigh-rhigh)>1||lhigh==-1||rhigh==-1)
return -1;
return max(lhigh,rhigh)+1;
}
};
30.给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回它的最小深度 2.
class Solution {
public:
int minDepth(TreeNode* root) {
if(!root)
return 0;
int left=minDepth(root->left),right=minDepth(root->right);
return (left && right) ? 1+min(left,right):1+left+right;
}
};
31.给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例: 给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root==NULL)
return false;
if (root->left==NULL&&root->right==NULL)
return sum-root->val==0;
return hasPathSum(root->left,sum-root->val)||hasPathSum(root->right,sum-root->val);
}
};
32.给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int k=0;
int max=0;
for(int i=0;i<prices.size();i++)
{
if(prices[i]-prices[k]>max)
max=prices[i]-prices[k];
if(prices[k]>prices[i])
k=i;
}
return max;
}
};
33.给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4] 输出: 7
class Solution {
public:
int maxProfit(vector<int>& prices) {
int sum=0;
for(int i=1;i<prices.size();i++)
sum+=max(0,prices[i]-prices[i-1]);
return sum;
}
};
34.给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1] 输出: 1
示例 2:
输入: [4,1,2,1,2] 输出: 4
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res=0;
for(int i=0;i<nums.size();i++)
res^=nums[i];
return res;
}
};
35.给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *p=head;
while(p&&p->next)
{
head=head->next;
p=p->next->next;
if(p==head)
return true;
}
return false;
}
};
36.给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。
/*假设p为慢指针，q为快指针
设从头到环的长度为a,环的长度为b
则
p=a+x(x为在环里面走的长度)
q=a+x+mb=2a+2x(m为正整数)
：mb=a+x
q+a=2a+x+mb=a+2mb
所以只要将p在设为head,p和q每次走一步，再次相遇就是环的初始节点*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *p=head,*q=head;
while(q&&q->next)
{
p=p->next;
q=q->next->next;
if(q==p)
{
p=head;
while(p!=q)
{
p=p->next;
q=q->next;
}
return p;
}
}
return NULL;
}
};
37.编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
在节点 c1 开始相交。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Reference of the node with value = 8 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
解法1：计算两个链表的长度相减，然后更长的那个来走一段路长，再用双指针判断
解法2：map映射
解法3：使用两个栈
解法4：将某个链表结尾指向头部，使得形成环，再用上题的方式来解决
下面贴出解法2的代码：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
map<ListNode*, bool> vis;
while(headA != NULL){
vis[headA] = true;
headA = headA->next;
}
while(headB!=NULL){
if(vis[headB]) return headB;
vis[headB] = true;
headB = headB->next;
}
return NULL;
}
};
38.给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
//考虑子问题，若总和太大则一定是后面的太大，因为无路可走了，所以排除后面一个后更新整个结构，不再考虑后面的
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int l=0,r=numbers.size()-1;
int ret[2];
while (l<r){
if (numbers[l]+numbers[r]==target){
ret[0]=l+1;
ret[1]=r+1;
break;
} else if(numbers[l]+numbers[r]<target)
l++;
else
r--;
}
return vector<int>(ret,ret+2);
}
};
39.给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3] 输出: 3
示例 2:
输入: [2,2,1,1,1,2,2] 输出: 2
//这题的主要重点是众数的数量大于n/2,即即使减去所有的不相同的数的数量留存的依旧是众数
class Solution {
public:
int majorityElement(vector<int>& nums) {
int k=0;
int res=0;
for(int i=0;i<nums.size();i++)
{
if(!k)
{
res=i;
k=1;
}
else
{
if(nums[res]==nums[i])
k++;
else
k--;
}
}
return nums[res];
}
};
40.给定一个整数 n，返回 n! 结果尾数中零的数量。
示例 1:
输入: 3 输出: 0 解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5 输出: 1 解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。
//2*5=10，2的数量一定比5的多，问题转换为求所有的乘法因子中所有5的数量
class Solution {
public:
int trailingZeroes(int n) {
int count=0;
while(n>=5)
{
count+=n/5;
n=n/5;
}
return count;
}
};
