acwing-高精度乘法
高精度乘法给定两个非负整数(不含前导 00) A和 B,请你计算 A×B 的值。
输入格式共两行,第一行包含整数 A,第二行包含整数 B。
输出格式共一行,包含 A×B 的值。
数据范围1≤A的长度≤1000001≤的长度≤100000,0≤B≤100000≤≤10000
输入样例:1223
输出样例:16
大数乘小数的模板。
大数的每一位和小数相乘,将得到的乘积相加。
123456789101112131415161718192021222324252627282930#include<iostream>#include<vector>using namespace std;vector<int> mul(vector<int> a,int b){ vector<int> c; int t=0; for(int i=0;i<a.size();i++){ t+=a[i]*b; c.push_back(t%10); t/=10; & ...
acwing-高精度减法
高精度减法给定两个正整数(不含前导 00),计算它们的差,计算结果可能为负数。
输入格式共两行,每行包含一个整数。
输出格式共一行,包含所求的差。
数据范围1≤整数长度≤1051≤整数长度≤105
输入样例:123211
输出样例:121
1234567891011121314151617181920212223242526272829303132333435363738394041#include<iostream>#include<vector>using namespace std;bool cmp(vector<int> a,vector<int> b){ //如果a大于等于b返回true if(a.size()!=b.size()) return a.size()>b.size(); for(int i=a.size()-1;i>=0;i--){ if(a[i]!=b[i]) return a[i]>b[i]; } return true ...
leetcode-76-最小覆盖子串
最小覆盖子串给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。
示例 1:
123输入:s = "ADOBECODEBANC", t = "ABC"输出:"BANC"解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2:
123输入:s = "a", t = "a"输出:"a"解释:整个字符串 s 是最小覆盖子串。
示例 3:
1234输入: s = "a", t = "aa"输出: ""解释: t 中两个字符 ...
leetcode-30. 串联所有单词的子串
串联所有单词的字串给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如,如果 words = ["ab","cd","ef"], 那么 "abcdef", "abefcd","cdabef", "cdefab","efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
示例 1:
123456输入:s = "barfoothefoobarman", words = ["foo","bar"]输出:[0,9]解释:因为 words.length == 2 ...
leetcode-3. 无重复字符的最长子串
无重复字符的最长子串给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
123输入: s = "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
123输入: s = "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
1234输入: s = "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
满足某某条件的最长/最短/的子串/子序列。看到这几个关键字就要考虑滑动窗口。
设置左右两指针,每次将右指针的元素加入窗口时先判断该元素是否出现过, ...
leetcode-209. 长度最小的子数组
长度最小的子数组给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续
子数组
[numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例 1:
123输入:target = 7, nums = [2,3,1,2,4,3]输出:2解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:
12输入:target = 4, nums = [1,4,4]输出:1
示例 3:
12输入:target = 11, nums = [1,1,1,1,1,1,1,1]输出:0
提示:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
进阶:
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
先想一个暴力解法:固定一个起点i,j从i开始遍历,如果满足[i,j] ...
leetcode-303. 区域和检索 - 数组不可变
区域和检索 - 数组不可变给定一个整数数组 nums,处理以下类型的多个查询:
计算索引 left 和 right (包含 left 和 right)之间的 nums 元素的 和 ,其中 left <= right
实现 NumArray 类:
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ,包含 left 和 right 两点(也就是 nums[left] + nums[left + 1] + ... + nums[right] )
示例 1:
1234567891011输入:["NumArray", "sumRange", "sumRange", "sumRange"][[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]输出:[null, 1, -1, -3]解释:NumArray num ...
leetcode-15. 三数之和
三数之和给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
12345678输入:nums = [-1,0,1,2,-1,-4]输出:[[-1,-1,2],[-1,0,1]]解释:nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。注意,输出的顺序和三元组的顺序并不重要。
示例 2:
123输入:nums = [0,1,1]输出:[]解释:唯一可能的三元组和不为 0 。
示例 3:
123输入:nums = ...
leetcode-11. 盛最多水的容器
盛最多水的容器给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
示例 1:
123输入:[1,8,6,2,5,4,8,3,7]输出:49 解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
示例 2:
12输入:height = [1,1]输出:1
很容易发现[i,j]之间可以储存的最大水量是min(height[i],height[j])*(j-i).
直接两层循环,喜提TLE.
12345678910111213class Solution {public: int maxArea(vector<int>& height) { int n=height.size(); int ans=0; fo ...
leetcode-167. 两数之和 II - 输入有序数组
两数之和 II - 输入有序数组给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1:
123输入:numbers = [2,7,11,15], target = 9输出:[1,2]解释:2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2:
123输入:numbers = [2,3,4], target = 6输出:[1,3]解释:2 与 4 之和等于目标数 6 。因此 ind ...