1、Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
#include <iostream>
#include <stddef.h>
using namespace std;
int* twosum(int arr[],int target,int len)
{
int result[2]= {0};
if(len > 1)
{
for(int i = 0;i<len;i++)
{
for(int j=i+1;j<len;j++)
{
if(arr[i]+arr[j] == target)
{
cout<<"arr[i]= "<<arr[i]<<endl;
cout<<"arr[j]= "<<arr[j]<<endl;
result[0]=arr[i];
result[1]=arr[j];
}
}
}
}
return result;
}
int main()
{
int arr[] = {2,5,7,3,9,1};
int target = 10;
int len = sizeof(arr)/sizeof(int);
cout<<len<<endl;
//cout<<target<<endl;
twosum(arr,target,len);
return 0;
}3、Longest Substring Without Repeating Characters
Description:
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3.
思路：记录最长字串的起始位置p1和结束位置p2,使用count来记录字串的长度
#include <iostream>
#include <string>
#include <set>
using namespace std;
int lengthOfLongestSubstring(string str)
{
string sub_str;
int len =str.length();
int p1=0,p2=0;
int count = 0;
for(int i = 0;i<len;i++)
{
string str_temp="";
for(int j = i+1;j<len;j++)
{
if(str.at(i) != str.at(j) && str.at(j-1) != str.at(j))
{
if(str_temp.find(str.at(j)))//这是为了保证从j开始的位置后面的字符中没有重复出现字符
{
str_temp.push_back(str.at(j));//如果没有找到，就把字符加进来
}else{
cout<<"str_temp="<<str_temp<<endl;
break;//如果找到这个字符
}
if(count<(j-i))
{
count = j-i;
p1 = i;
p2 = j;
}
}
else{
break;
}
}
}
cout<<"p1 = "<<p1<<endl;
cout<<"p2 = "<<p2<<endl;
cout<<"count = "<<count+1<<endl;
if(count == 0)
{
sub_str.assign(str,0,1);
}else{
sub_str.assign(str,p1,p2-p1+1);
}
cout<<"sub_str = "<<sub_str<<endl;
return 0;
}
int main()
{
string str1 ="abcabcbb";
string str2 ="bbbbb";
string str3 ="1234pwwkew";
//string str3 ="pwwkew";
lengthOfLongestSubstring(str1);
cout<<"____________"<<endl;
lengthOfLongestSubstring(str2);
cout<<"____________"<<endl;
lengthOfLongestSubstring(str3);
return 0;
}运行结果：
str_temp=bc
p1 = 0
p2 = 2
count = 3
sub_str = abc
____________
p1 = 0
p2 = 0
count = 1
sub_str = b
____________
p1 = 0
p2 = 5
count = 6
sub_str = 1234pw其实上面的程序是有bug的leecode上测试没有通过，需要下面一样来修改。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len =s.length();
int p1=0,p2=0;
int count = 0;
if(len == 0)
{
return 0;
}
for(int i = 0;i<len;i++)
{
string str_temp="";
for(int j=i+1;j<len;j++)
{
if(s.at(i) != s.at(j) && s.at(j-1) != s.at(j))
{
std::size_t found = str_temp.find(s.at(j));
if (found == std::string::npos) //如果没找到就加入str_temp进去
{
str_temp.push_back(s.at(j));
}else{
break;//如果找到说明重复了
}
if(count<(j-i))
{
p1 = i;
p2 = j;
count =j-i;
}
}else{
break;
}
}
}
if(count == 0)
{
return 1;
}else{
return count+1;
}
}
};
题目：给出一个数组代表围柱的高度，求能围柱的最大的水量，例如数组{ 5，2，3，2，4 }，最大水量为5。
如下图：黄色部分为围柱，绿色部分是能够围住的水，图中围柱的高度依次为 5，2，3，2，4最多能围住的水量是5。
思路：求出每个柱子上面能够存多少水，然后将每根柱子的存水量相加便能得到总的存水量，为求出每根柱子上能够存多少水，就要求出每根柱子左边最高的和右边最高柱子，然后用两者的最小值减去当前柱子的高度。 例如图中从左到右第二根柱子的高度为2，它左边最高柱子的值为5，右边最高柱子的值为4，因此它的最大存水量为 Min（4，5）-2=2。
上面算法的流程：
①从左到右遍历一次求出每个元素左边的最大值，保存在 left 数组中。
②从右到左遍历一次求出每个元素右边的最大值，保存在right数组中。
③最后一次遍历求出每个元素（每根柱子）的存水量。
53. 最大子序和
难度简单2005
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
思路：
原来的数组： [-2,1,-3,4,-1,2,1,-5,4]
i
计算后的数组 v1 [-2 ,1,-2,4,3,5,6,1,5]
思路： -2=-2 、1=-2+1 、 -2 =1 + -3 、 4 =4 、 3 = 4+-1 、...
如果数组长度大于1
先把源数组第一位插入到v1中，
如果v1数组的第i-1为数是正数，那么v1数组的第i个元素= 源数组的第i个元素 + v1数组的第i-1个元素
如果v1数组的第i-1为数是负数，那么v1数组的第i个元素= 源数组的第i个元素
这样下面一个数组v1的最大值，就是源数组的最大连续子序列之和。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int> v1;
int len = nums.size();
if(len == 1)
return nums[0];
if(len > 0)
{
v1.push_back(nums[0]);
for(int i = 1;i<len;i++)
{
if(v1[i-1]>0)
{
v1.push_back(v1[i-1]+nums[i]);
}else{
v1.push_back(nums[i]);
}
}
int max = -999;
for( auto i : v1)
{
if(max < i)
{
max =i;
}
}
return max;
}else
{
return 0;
}
}
};
67. 二进制求和
难度简单369
给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100" 示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
提示：
'0' 或 '1' 组成。1 <= a.length, b.length <= 10^4"0" ，就都不含前导零。class Solution {
public:
string addBinary(string a, string b) {
int len1= a.size()-1;
int len2 = b.size()-1;
while(len1 > len2)//把a和b长度修改成一样的，前面用0补
{
b='0'+b;
len2++;
}
while(len2 > len1)
{
a='0'+a;
len1++;
}
string result;
int flag =0;//进位标志
for(int i=len1;i>=0;i--)
{
if((a[i]-'0'+b[i]-'0'+flag)==0)
{
result = '0'+result;
flag = 0;
}else if((a[i]-'0'+b[i]-'0'+flag)==1)
{
result = '1'+result;
flag = 0;
}else if((a[i]-'0'+b[i]-'0'+flag)==2)
{
result = '0'+result;
flag = 1;
}else if((a[i]-'0'+b[i]-'0'+flag)==3)
{
result = '1'+result;
flag = 1;
}
}
if(flag == 1)
{
result = '1'+result;
}
return result;
}
};