1.两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
我通过的代码(C++)：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result(2,0);
for(int a=0;a<nums.size();a++)
{
for(int b=a+1;b<nums.size();b++)
{
if((nums[a]+nums[b])==target)
{
result[0]=a;
result[1]=b;
break;
}
}
}
return result;
}
};
更好的解答(java)：
方法一：暴力法。
遍历每个元素 xx，并查找是否存在一个值与 target - xtarget−x 相等的目标元素。
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
方法二：一遍哈希表。
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
2.两数相加
给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
思路：
1.相加的过程中可能存在进位的操作，所以需要采用一个变量carry来记录进位的情况，初始化carry = 0;
2.因为链表的数字是倒着放的，所以相加起来很方便，将两个链表从头到尾一起遍历，如果有值的话就将它们的值相加sum = val1+val2+carry。
3.如果是两个长度不一样的链表，则需要注意将不再继续向后，且让相应位的和为val1+0.
4.carry的更新，carry = sum/10, 而当前节点和 curr->val = sum%10.
5.循环直至l1,l2都为空。
6.遍历完之后如果carry == 1, 新建一个节点存在进位。
我通过的代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* p=l1;
ListNode* q=l2;
ListNode* result=new ListNode(0);
ListNode* cur=result;
int carry=0;
while(p||q){
int x=0,y=0,sum=0;
if(p!=NULL){
x=p->val;
p=p->next;
}
if(q!=NULL){
y=q->val;
q=q->next;
}
sum=x+y+carry;
carry=sum/10;
cur->next=new ListNode(sum%10);
cur=cur->next;
}
if(carry)
cur->next=new ListNode(carry);
return result->next;
}
};
3.无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。
提交的错误代码：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int max=0,k=0;
for(int i=0;i<s.size();i++){
for(int index=k;index<i;index++)
{
if(s[index]==s[i]){
k=index+1;
break;
}
if(i-k+1>max)
max=i-k+1;
}
}
return max;
}
};
提交通过的代码：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int size,max=0,k=0,index;
size=s.size();
for(int i=0;i<size;i++){
for(index=k;index<i;index++)
if(s[index]==s[i]){
k=index+1;
break;
}
if(i-k+1>max)
max=i-k+1;
}
return max;
}
};
4.整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31−1]。请根据这个假设，如果反转后整数溢出那么就返回0。
class Solution {
public:
int reverse(int x) {
int reverse=0;
int y=0;
while(x)
{
reverse=reverse*10+y;
y=x%10;
x=x/10;
}
reverse=reverse*10+y;
return reverse;
}
};
提交错误：
更改后通过：
class Solution {
public:
int reverse(int x) {
long int reverse=0;
int y=0;
while(x)
{
y=x%10;
x=x/10;
reverse=reverse*10+y;
if(reverse<-2147483648||reverse>2147483647||reverse==2147483647||reverse==2147483647)
return 0;
}
return reverse;
}
};
5. Z字形变换
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:
L D R
E O E I I
E C I H N
T S G
class Solution {
public:
string convert(string s, int numRows) {
string ret;
int cycle=2*numRows-2;
int i,j;
if(numRows==1)
return s;
for(i=0;i<numRows;i++)
{
for(j=0;i+j<s.size();j+=cycle)
{
ret +=s[i+j];
if(i!=0&&j+cycle-i<s.size()&&i!=numRows-1)
ret +=s[j+cycle-i];
}
}
return ret;
}
};
11. 盛最多水的容器
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
第一次提交的代码（暴力算法）：
class Solution {
public:
int maxArea(vector<int>& height) {
int i,j;
long s=0,max=0;
for(i=0;i<height.size();i++)
for(j=height.size()-1;j>i;j--)
{
if(height[i]<height[j])
s=height[i]*(j-i);
else s=height[j]*(j-i);
if(s>max)
max=s;
}
return max;
}
};
当遇到最后一次算例[15000,14999,14998,14997,14996,14995,14994,14993,....,6014,6013,6012,6011,6010,6009,6008,6007,6006,6005,6004,6003,6002,600... 28895 more chars]时报：超出时间限制。
更改通过：
class Solution {
public:
int maxArea(vector<int>& height) {
int i=0,j=height.size()-1;
int s=0;
while(i<j)
{
s = max(s,min(height[i], height[j]) * (j-i));
if(height[i]<height[j])
i++;
else j--;
}
return s;
}
};
12.整数转罗马数字
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
例如， 罗马数字 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) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
示例 1:
输入: 3
输出: "III"
示例 2:
输入: 4
输出: "IV"
示例 3:
输入: 9
输出: "IX"
示例 4:
输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.
我的沙雕方法：
class Solution {
public:
string intToRoman(int num) {
if(num==0) return "0";
string res;
while(num)
{
if(num>=1000)
{
res+="M";
num-=1000;
}
if(num<1000&&num>=900)
{
res+="CM";
num-=900;
}
if(num<900&&num>=500)
{
res+="D";
num-=500;
}
if(num<500&&num>=400)
{
res+="CD";
num-=400;
}
if(num<400&&num>=100)
{
res+="C";
num-=100;
}
if(num<100&&num>=90)
{
res+="XC";
num-=90;
}
if(num<90&&num>=50)
{
res+="L";
num-=50;
}
if(num<50&&num>=40)
{
res+="XL";
num-=40;
}
if(num<40&&num>=10)
{
res+="X";
num-=10;
}
if(num<10&&num>=9)
{
res+="IX";
num-=9;
}
if(num<9&&num>=5)
{
res+="V";
num-=5;
}
if(num<5&&num>=4)
{
res+="IV";
num-=4;
}
if(num<4&&num>=1)
{
res+="I";
num-=1;
}
}
return res;
}
};
更好的方法：
class Solution {
public:
string intToRoman(int num) {
int values[]={1000,900,500,400,100,90,50,40,10,9,5,4,1};
string reps[]={"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
string res;
for(int i=0; i<13; i++){
while(num>=values[i]){
num -= values[i];
res += reps[i];
}
}
return res;
}
};
13.罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 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) 的左边，来表示 400 和 900。
class Solution {
public:
int romanToInt(string s) {
vector<string> roma {"CM","M","CD","D",
"XC","C","XL","L",
"IX","X","IV","V",
"I"};
vector<int> nums {900,1000,400,500,
90,100,40,50,
9,10,4,5,
1};
int res = 0;
for(int i = 0;i<13;i++)
{
while(s.find(roma[i])!= string::npos)
{
s.erase(s.find(roma[i]),roma[i].size());
res+=nums[i];
}
}
return res;
}
};
136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
我的代码：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int i,aa=0;
for(i=0;i<=nums.size();++i)
{
if(nums[i]!=nums[i+1])
{
aa=nums[i];
break;
}
}
return nums[i+1];
}
};
网上的答案：一个数字异或它自己结果为0，异或0结果为它自己即a ^ a=0，a ^ 0=a，且异或满足a ^ b ^ c=a ^ (b ^ c)。因此我们可以设置一个ret异或每个数组元素，最后相同的都抵消为0，那个唯一的数字异或0为它自己即为答案。
int singleNumber(vector<int>& nums) {
int tmp = 0;
for(int i = 0;i < nums.size();i++){
tmp = tmp ^ nums[i];
}
return tmp;
}
605. 种花问题
假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。
示例 1:
输入: flowerbed = [1,0,0,0,1], n = 1
输出: True
示例 2:
输入: flowerbed = [1,0,0,0,1], n = 2
输出: False
我的沙雕方法：
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int i,length=0,j=0;
/**
数组中只有一个数（只有一个花坛）的情况：
[1] 1:False
[1] 0:True
[0] 1:True
[0] 0:True
**/
if(flowerbed.size()==1)
{
if(flowerbed[0]==0)
return(n<=1);
else
return(n<1);
}
/**
更改数组：遇到是1的元素就将前后元素都变为1
**/
for(i=0;i<flowerbed.size();)
{
if(flowerbed[i]==0)
{
i++;
continue;
}
if(flowerbed[i]==1)
{
if(i!=0)
flowerbed[i-1]=1;
if(i!=flowerbed.size()-1)
flowerbed[i+1]=1;
if(i==flowerbed.size()-1)
{
flowerbed[i-1]=1;
break;
}
i=i+2;
}
}
/**
对更改完的数组进行累加计算：计算连续的0的个数以推得能种花数
**/
for(i=0;i<flowerbed.size();i++)
{
if(flowerbed[i]==0)
length++;
if(flowerbed[i]==1)
{
j+=(int)(length+1)/2;
length=0;
}
}
if(length!=0)
j+=(int)(length+1)/2;
if(j>=n) return true;
else return false;
}
};
