1.两数之和
题目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
知识点
一、什么是vector？
向量（Vector）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。
二、容器特性
1.顺序序列
顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。
2.动态数组
支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算述进行该操作。操供了在序列末尾相对快速地添加/删除元素的操作。
三、函数
1.push_back 在数组的最后添加一个数据
2.pop_back 去掉数组的最后一个数据
3.size 当前使用数据的大小
解决过程
#include <vector>
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int>res;
for(int i=0;i<nums.size();i++){
nums[i]=target-nums[i];
for(int j=i+1;j<nums.size();j++){
if(nums[i]==nums[j]){
res.push_back(i);
res.push_back(j);
}
}
}
return res;
}
};
结果
难点
- vector类型、函数的基础知识
7.整数反转
题目
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
知识点
一、整数转字符串：itoa()
二、整数转字符串 stringstream
解决过程
一、求整数位数
#include <stdlib.h>
#include <cmath>
class Solution {
public:
int reverse(int x) {
int y=0;//res
int num=1;//位数
int a=0;//0为正，1为负
int e=0;
if(x<0){
a=1;
}
x=abs(x);
double u=pow(10,num);
while(x!=x%u){
num+=1;
u=pow(10,num);
}
for(int i=0;i<num;i++){
y+=pow(10,i)*(x/int(pow(10,num-1-i)));
e=pow(10,num-1-i);
x=x%e;
}
if(a==0){
return y;
}
else{
return -y;
}
}
};
Line 15: Char 19: fatal error: invalid operands to binary expression ('int' and 'double')
while(x!=x%u){
~^~
1 error generated.
二、itoa() 整数转字符串，求字符串长度
#include <cstdlib>
#include <cmath>
#include <cstdio>
class Solution {
public:
int reverse(int x) {
int y=0;//res
int num=1;//位数
int a=0;//0为正，1为负
int e=0;
if(x<0){
a=1;
}
x=abs(x);
// double u=pow(10,num);
// while(x!=x%int(u)){
// num+=1;
// u=pow(10,num);
// }
char str[32];
itoa(x,str,10);
for(int i=0;i<str.length();i++){
y+=pow(10,i)*(x/int(pow(10,num-1-i)));
e=pow(10,num-1-i);
x=x%e;
}
if(a==0){
return y;
}
else{
return -y;
}
}
};
Line 22: Char 9: fatal error: use of undeclared identifier 'itoa'
itoa(x,str,10);
^
1 error generated.
itoa是广泛使用的非知标准C语言和C++语言扩展功能。但因为它是一个非标准的C / C++语言功能,因此不能被所有编译器使用。在大多数Windows下的编译器通常在内头文件包含容非标准函数。
三、stringstream 整数转字符串，求字符串长度
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <sstream>
class Solution {
public:
int reverse(int x) {
int y=0;//res
int num=1;//位数
int a=0;//0为正，1为负
int e=0;
if(x<0){
a=1;
}
x=abs(x);
// double u=pow(10,num);
// while(x!=x%int(u)){
// num+=1;
// u=pow(10,num);
// }
// char str[32];
// itoa(x,str,10);
stringstream ss;
ss << x;
string str = ss.str();
for(int i=0;i<str.length();i++){
//cout<<x/pow(10,str.length()-1-i)<<endl;
y+=pow(10,i)*(x/int(pow(10,str.length()-1-i)));
e=pow(10,str.length()-1-i);
x=x%e;
}
if(a==0){
return y;
}
else{
return -y;
}
}
};
Line 30: Char 14: runtime error: 9.64632e+09 is outside the range of representable values of type 'int' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:40:14
double必须要转换成int，不然整除符号/ 不起作用。
for(int i=0;i<str.length();i++){
cout<<x/pow(10,str.length()-1-i)<<endl;
y+=pow(10,i)*(x/int(pow(10,str.length()-1-i)));
e=pow(10,str.length()-1-i);
x=x%e;
}
for(int i=0;i<str.length();i++){
cout<<x/int(pow(10,str.length()-1-i))<<endl;
y+=pow(10,i)*(x/int(pow(10,str.length()-1-i)));
e=pow(10,str.length()-1-i);
x=x%e;
}
但是，如果对于一个很大的数，double转成int，会超出10的10次方限制。一个数，1526383749逆序，则是9.47383e+09，超出可以转化的范围，报错。
double转int的矛盾我暂时没有找到解决方法。
四、看题解得，放弃计算长度，直接while循环判断是否计算结束。取余+整除10，进入while循环取余+整除10。
class Solution {
public:
int reverse(int x) {
if(x<10&&x>-10){
return x;
}
int temp=x%10;
x=x/10;
while(x>=1||x<=-1){
temp=temp*10+x%10;
x=x/10;
if(temp > INT_MAX/10 || temp < INT_MIN/10) //检查溢出
return 0;
}
return temp;
}
};
整型一定是小于等于整型最大解的，所以就算溢出了，我们也不知道，取不到溢出值，所以判断失误。
五、基于四进行修改，将temp定义为long long类型，就可以取到整型溢出值，从而判断整型是否溢出。
class Solution {
public:
int reverse(int x) {
if(x<10&&x>-10){
return x;
}
long long temp=x%10;
x=x/10;
while(x>=1||x<=-1||x!=0){
temp=temp*10+x%10;
x=x/10;
if(temp > INT_MAX || temp < INT_MIN) //检查溢出
return 0;
}
return temp;
}
};
六、原题解。判断temp* 10 是否溢出，这样int temp是可以渠道某一个值的。但是不是很严谨，因为在最后一步，temp* 10+x，我们之前判断的是temp* 10是否溢出，而不是判断temp* 10+x是否溢出。
class Solution {
public:
int reverse(int x) {
if(x<10&&x>-10){
return x;
}
int temp=x%10;
x=x/10;
while(x>=10||x<=-10){
temp=temp*10+x%10;
x=x/10;
if(temp > INT_MAX/10 || temp < INT_MIN/10) //检查溢出
return 0;
}
temp=temp*10+x;
return temp;
}
};
结果
难点
求整数反转本身
- 取余，整除10，循环。
- 如果整数太大，不要用整数长度for循环。
整型溢出问题，如何正确判断。有两种办法：
- 把值设为long long类型，可以直接用最终值判断溢出。
- 从最终值的前一步入手，判断下一步是否溢出。