面试资料

高精度加法给定两个正整数（不含前导 0），计算它们的和。 输入格式给定两个正整数（不含前导 00），计算它们的和。 输出格式共一行，包含所求的和。 数据范围1≤整数长度≤100000 这个算法用来计算大数之间的加法。 例：计算 567+28 用 a, b 两个字符串存储输入。a = 567, b = 28 为了将个位对齐，两个加数需要倒序存放在 A， B 两个整数数组中。 A = [7, 6, 5], B = [8, 2] 新建整数数组 C 保存结果，整型变量 t 保存进位，初始 t = 0. 将各个位上的数字相加，求出结果对应位上的数字和进位。 例如对个位计算： A[0] + B[0] = 7 + 8 = 15, 结果个位上是 5， 进位是 1. 所以C[0] = 5, 进位t = 1 最后把结果数组 C 中就保存了计算倒序结果，倒序输出就是答案 12345678910111213141516171819202122232425262728293031323334#include<iostream>#include<vector ...

反转字符串中的单词给你一个字符串 s ，请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。 示例 1： 12输入：s = "the sky is blue"输出："blue is sky the" 示例 2： 123输入：s = " hello world "输出："world hello"解释：反转后的字符串中不能存在前导空格和尾随空格。 示例 3： 123输入：s = "a good example"输出："example good a"解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。 这道题的关键就是去掉多余的空格。用双指针找出每个单词就可 ...

最长公共前缀编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ""。 示例 1： 12输入：strs = ["flower","flow","flight"]输出："fl" 示例 2： 123输入：strs = ["dog","racecar","car"]输出：""解释：输入不存在公共前缀。 以第一个字符串strs[0]为基准，逐个字符与其他字符串比较，直到找到不匹配的字符为止。 设置两层循环，第一层循环strs[0]的长度，第二层循环每一个字符串。 12345678910111213141516class Solution {public: string longestCommonPrefix(vector<string>& strs) { int n=strs.size(); if(!n) r ...

最后一个单词的长度给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串 示例 1： 123输入：s = "Hello World"输出：5解释：最后一个单词是“World”，长度为5。 非常简单。倒序处理，注意最后的空格 12345678910111213class Solution {public: int lengthOfLastWord(string s) { int n=s.size()-1; int ans=0; while(s[n]==' ') n--; while(n>=0&&s[n]!=' '){ //第一次把n>=0这个判断条件放在&&后边导致报错，一定注意。 ans++; n--; } ...

整数转罗马数字罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。 12345678字符 数值I 1V 5X 10L 50C 100D 500M 1000 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况： I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来表 ...

罗马数字转整形罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 12345678字符 数值I 1V 5X 10L 50C 100D 500M 1000 例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况： I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来 ...

接雨水给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 按列来计算，第i列接到的雨水等于min(i左边最大高度，i右边最大高度)-height[i]. 所以问题的关键就变成了求i左右两边的最大高度。这是一个非常简单的动态规划问题。 定义left数组，left[i]表示i左边最大高度（包括i，如果i左边最大高度就是height[i],则第i列接不到雨水，右边同理）。初始化left[0]=height[0] left[i]=max(left[i-1],height[i]) 定义right数组，right[i]表示i右边最大高度。 初始化right[n-1]=height[n-1] right[i]=max(right[i+1],height[i]) 注意： right数组必须从后往前遍历。第一 ...

数的三次方根给定一个浮点数n，求它的三次方根 输入格式共一行，包含一个浮点数 n。 输出格式共一行，包含一个浮点数，表示问题的解。 注意，结果保留 6 位小数。 数据范围-10000<=n<=10000 注意符号类型为double型，所以边界问题很简单。 123456789101112131415161718192021#include<iostream>using namespace std;double square3(double n){ double l=-10000; double r=10000; while(r-l>1e-8){ double mid=(l+r)/2; if(mid*mid*mid<n) l=mid; else r=mid; } return l;}int main(){ double n; cin>>n; printf("%.6f\n",squar ...

分发糖果n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求，给这些孩子分发糖果： 每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。 初始化数组vector<int>t(n,1)存储每个孩子的糖果数量。 分两次遍历数组 从左到右遍历数组，使得右边孩子的评分数大于左边孩子评分数，则右边孩子糖果数比左边孩子多1。 从右到左遍历数组，如果左边孩子的评分数大于右边孩子评分数，则左边孩子糖果数等于max(t[i],t[i+1]+1)。 123456789101112131415161718class Solution {public: int candy(vector<int>& ratings) { int n=ratings.size(); vector<int>t(n,1); for(int i=1;i<n;i++){ ...

加油站在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。 给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。 这个题上学期的算法课老师出过一个简易版的，只有一个数组既是gas又是cost。而且测试数据很简单所以直接ac了。这个题就直接写不出来了 123456789101112131415161718192021222324class Solution {public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { int n = gas.size(); int cur_gas = 0; int start_index = 0 ...