网站建设都包括什么,wordpress php5.3.5,网站ftp地址是什么,宿州住房和城乡建设局网站二进制求和
给两个字符串a和b#xff0c;以二进制字符串的形式返回它们的和。
示例 1#xff1a;
输入:a “11”, b “1” 输出#xff1a;“100” 示例 2#xff1a;
输入#xff1a;a “1010”, b “1011” 输出#xff1a;“10101”
提示#xff1a;
1 以二进制字符串的形式返回它们的和。
示例 1
输入:a “11”, b “1” 输出“100” 示例 2
输入a “1010”, b “1011” 输出“10101”
提示
1 a.length, b.length 104 a 和 b 仅由字符 ‘0’ 或 ‘1’ 组成 字符串如果不是 “0” 就不含前导零
列竖式
我们可以借鉴列竖式的方法末尾对齐逐位相加。 在十进制的计算中逢十进一二进制中逢二进一。
具体的可以取nmax{|a|,|b|}循环n次从最低位开始遍历。 使用一个变量carry表示上一个位置的进位初始值为0。
记当前位置对齐的两个位ai和bi则每一位的答案为(carryaibi)mod2下一位的进位为(carryaibi)/2。
重复上述步骤直到数字a和b每一位计算完毕最后如果carry的最高位不为0则将最高位添加到计算结果的末尾。
注意
为了让各个位置对齐可以先反转这个代表二进制数字的字符串。
class Solution{
public:string addBinary(string a, string b){string ans;int n max(a.size(),b.size());reverse(a.begin(),a.end());reverse(b.begin(),b.end());int carry 0;for(int i0; in; i){carry i a.size() ? a.at(i) 1 : 0;carry i b.size() ? b.at(i) 1 : 0;ans.push_back((carry%2)?1:0);carry/2;}if(carry){ans.push_back(1);}reverse(ans.begin(),ans.end());return ans;}
}x的平方根
给你一个非负整数 x 计算并返回 x 的 算术平方根 。
由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。
注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1
输入x 4 输出2 示例 2
输入x 8 输出2 解释8 的算术平方根是 2.82842…, 由于返回类型是整数小数部分将被舍去。
前言
本题是一道常见的面试题面试官一般会要求面试者在不使用 x\sqrt{x} x 函数的情况下得到 xxx 的平方根的整数部分。一般的思路会有以下几种
通过其它的数学函数代替平方根函数得到精确结果取整数部分作为答案
通过数学方法得到近似结果直接作为答案。
函数的情况下得到 xxx 的平方根的整数部分。一般的思路会有以下几种
通过其它的数学函数代替平方根函数得到精确结果取整数部分作为答案
通过数学方法得到近似结果直接作为答案。
二分查找法
class Solution {
public:int mySqrt(int x) {int left 0;int right x;int ans -1;while(left right){long mid (leftright)/2;if(mid * mid x){ans mid;left mid1;}else{right mid-1;}}return ans;}
};爬楼梯
假设正在爬楼梯需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
示例 1
输入n 2 输出2 解释有两种方法可以爬到楼顶。
1 阶 1 阶2 阶 示例 2
输入n 3 输出3 解释有三种方法可以爬到楼顶。 3. 1 阶 1 阶 1 阶 4. 1 阶 2 阶 5. 2 阶 1 阶
递归
用f(x)表示爬到第x阶台阶的方案数最后一步可能是跨了一级台阶也可能跨了两级台阶 f(x) f(x-1) f(x-2);
class Solution {
public:int climbStairs(int n) {if(n 1)return 1;else if(n 2)return 2;return climbStairs(n-1) climbStairs(n-2);}
};时间复杂度O(2n)
动态规划
class Solution {
public:int climbStairs(int n) {if(n2)return n;int first 1;int second 2;int ans 0;for(int i3; in; i){ans first second;first second;second ans;}return ans;}
};删除排序链表中的重复元素
class Solution {
public:ListNode *deleteDuplicates(ListNode *head) {if(!head){return head;}ListNode *cur head;while(!cur-next){if(cur-val cur-next-val){cur-next cur-next-next;}else{cur cur-next;}}return head;}
}合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。
示例 1
输入nums1 [1,2,3,0,0,0], m 3, nums2 [2,5,6], n 3 输出[1,2,2,3,5,6] 解释需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] 其中斜体加粗标注的为 nums1 中的元素。 示例 2
输入nums1 [1], m 1, nums2 [], n 0 输出[1] 解释需要合并 [1] 和 [] 。 合并结果是 [1] 。 示例 3
输入nums1 [0], m 0, nums2 [1], n 1 输出[1] 解释需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意因为 m 0 所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
直接合并排序
最直观的方法是将nums2放进数组nums1的尾部然后直接对整个数组进行排序。
class Solution {
public:void merge(vectorint nums1, int m, vectorint nums2, int n) {for(int i0; in; i){nums1[mi] nums2[i];}sort(nums1.begin(), nums1.end());}
};双指针
class Solution {
public:void merge(vectorint nums1, int m, vectorint nums2, int n) {int sorted[mn];int i0,j0,k0;while(im jn){if(nums1[i] nums2[j]){sorted[k] nums1[i];}else{sorted[k] nums2[j];}}while(i m-1)sorted[k] nums1[i];while(j n-1)sorted[k] nums2[j];for(i0; imn; i){nums1[i] sorted[i];}}
};时间复杂度O(mn)O(mn)O(mn)。 指针移动单调递增最多移动 mnmnmn 次因此时间复杂度为 O(mn)O(mn)O(mn)。
空间复杂度O(mn)O(mn)O(mn)。 需要建立长度为 mnmnmn 的中间数组 sorted\textit{sorted}sorted。
