2.两数相加
题目描述：给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
解法:本题的难点在于满十进一的转换，我们的思路是从第二低位开始 p.next.var+=p.var/10;p.var=p%10;
while(p3->next!=NULL){//满十进一
p3->next->val+=p3->val/R;
p3->val=p3->val%R;
p3=p3->next;
}
while (p3->next == NULL && p3->val >= R) {//最高位是大于10的数
p3->next = new ListNode(p3->val / R);
p3->val %= R;
p3 = p3->next;
}
总体代码
/**
* 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) {
static const int R=10;
ListNode *p1,*p2,*p3,*h3,*t3;
p1=l1;
p2=l2;
h3=t3=NULL;
//开加
while(p1&&p2){
p3=new ListNode(p1->val+p2->val);
if(t3==NULL){
h3=t3=p3;
}else{
t3->next=p3;
t3=p3;
}
p1=p1->next;
p2=p2->next;
}
while(p1){
t3->next=p1;
t3=t3->next;
p1=p1->next;
}
while(p2){
t3->next=p2;
t3=t3->next;
p2=p2->next;
}
p3=h3;
while(p3->next!=NULL){//满十进一
p3->next->val+=p3->val/R;
p3->val=p3->val%R;
p3=p3->next;
}
while (p3->next == NULL && p3->val >= R) {//最高位是大于10的数
p3->next = new ListNode(p3->val / R);
p3->val %= R;
p3 = p3->next;
}
return h3;
}
};
3.无重复字符的最长字符串
题目描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例：
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
解法：
#include <stdio.h>
#include <string.h>
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int max_line=0;
int i=0;
for(int j=0;j<s.size();j++){
for(int k=i;k<j;k++){
if(s[k]==s[j]){
i=k+1;
break;
}
}
if(j-i+1>max_line){
max_line=j-i+1;
}
}
return max_line;
}
};
5.最长回文串
题目描述：输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
解法：动态规划：设当前字符为中心字符，分别比较当前值左边和右边的字符是否相同，如果相同则将当前的三个字符设为中心字符，继续左向和右向比较。
有一个小小的bug就是当给定字符有“bb”这种子串时，我们利用相同的思路将“bb"设为中心字符。
#include <string>
using std::string;
class Solution {
public:
string longestPalindrome(string s) {
string res="";
int max_line=0;
int center=1;
for(int center=0;center<s.size();center++){//不存在两个连续的字符
findPal(s,center-1,center+1,res,max_line);
}
return res;
}
private:
void findPal(string s,int cen_left,int cen_right,string &res,int &max_line){
while(cen_left>=0&&s[cen_left]==s[cen_left+1]){//左边与中间相同
cen_left--;
}
while(cen_right<s.size()&&s[cen_right]==s[cen_right-1]){//右边与中间相同
cen_right++;
}
while(cen_left>=0&&cen_right<s.size()&&s[cen_left]==s[cen_right]){
cen_left--;
cen_right++;
}
if(cen_right-cen_left-1>max_line){
max_line=cen_right-cen_left-1;
res=s.substr(cen_left+1,max_line);
}
}
};
6.Z字变换
题目描述：将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zigzag-conversion
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例：输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
解法：找规律，遍历s中每一个字符，分别写入数组row[currentRow]中对应的行中，一旦当前行为第零行或者最后一行时，则改变写入方向；
最后按行读取row就可以了
#include "algorithm"
#include "string"
#include "stdio.h"
class Solution {
public:
string convert(string s, int numRows) {
if(numRows==1) return s;
int len=s.size();
vector<string> row(min(numRows,len));//避免输入的行数超过字符串的长度
int currentRow=0;
bool goingdown=false;//当goingdown为true 向下写入。
for(char c:s){
row[currentRow]+=c;
if(currentRow==0||currentRow==numRows-1){
goingdown=!goingdown;
}
currentRow+=goingdown?1:-1;
}
string result;
for(string row_:row){
result+=row_;
}
return result;
}
};
11.盛水最多的容器
题目描述:给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法：1.首先确定最大底，再考虑最大高
2.较低高向较高高移动。
class Solution {
public:
int maxArea(vector<int>& height) {
if(height.size()<=1) return -1;
int i=0,j=height.size()-1;
int maxarea=0;
while(i<j){
int h=min(height[i],height[j]);
maxarea=max(maxarea,h*(j-i));
if(height[i]<height[j]){
++i;
}else{
--j;
}
}
return maxarea;
}
};
12.整数转罗马数字
题目描述：罗马数字包含以下七种字符： 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。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内
示例:输入: 3
输出: "III"
解法:官网给的解法是贪心算法，找规律，从最大的罗马数开始比较；
class Solution {
public:
string intToRoman(int num) {
int num_[13]={1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
string roman[13]={"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
string result="";
int index=0;
while(index<13){
while(num>=num_[index]){
result.append(roman[index]);
num=num-num_[index];
}
index++;
}
return result;
}
};
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-to-roman
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
----------------很久没有更新了（主要一边在了解C++的头文件，一边写算法题有一点不舒服，所以打算从现在开始用java写了）------------------
15 三数之和（这个题目与第一题的两数之和有点相似）
题目描述：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法：个人在去重这一方面想了很久也没有想到一个很好的方法去重，看了一个精选的解法才明白。
（1）我们先将这个数组进行排序，排序过后就简化了很多的操作（学到了，以后对数组进行操作时一定先排好序，一下省了太多步骤了）
（2）我们的思路是 先选取一个没有被选取的最小的数A，然后再选定一个最大B的数和除去A以及A之前的数中的最小数C；
如果A+B+C=0，那么恭喜你一个符合标准的数组就选好了。
如果A+B+C>0,那么说明C这个数取大了，则令C等于一个较小的数。
如果A+B+C<0,那么说明B这个数取大了，则令B等于一个较大的数。
如此一来 遍历数组后就可以得到答案
总体代码：
class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> answer=new ArrayList();
int len=nums.length;
if(len<3){//不足三个数
return answer;
}
Arrays.sort(nums);//排序这一步很重要，为之后的去重和结束循环的判断做好了铺垫
for(int i=0;i<len;i++){
if(nums[i]>0){
break;//如果当前数大于0 （此时的当前数z是指三个数中最小的数） 那么就不用继续比较了
}
if(i>0&&nums[i]==nums[i-1]) continue;//去重
int L=i+1,R=len-1;
while(L<R){
if((nums[i]+nums[L]+nums[R])==0){//找到了满足条件的一组数
answer.add(Arrays.asList(nums[i],nums[L],nums[R]));
//接下来就是判断指针的走向了
while (L<R && nums[L] == nums[L+1]) L++; // 去重
while (L<R && nums[R] == nums[R-1]) R--; // 去重
L++;
R--;
}else if((nums[i]+nums[L]+nums[R])<0){
//较小的那个匹配数应该变大一些 即L右移
L++;
}else{
//较大的那个匹配数左移
R--;
}
}
}
return answer;
}
}
17.电话号码的字母组合
题目描述：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例：
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
解法：
1.这种类型的题目第一步当然是做好准备工作，需要将9个数字对应的字符序列先配对起来，这里选用的是键值对的方式使数组和字符的对应。
//初始化一个hash表
Map<Character, String> map = new HashMap<Character, String>() {{
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}};
2.对于自由组合的题目大多采用递归回溯的方法，这题也不例外
对于实例输入“23”
首先选中2的第一个字符 分别和3的每一个字符配对 配对结束后就回溯的2的第二个字符和3的每一个字符配对。。。依次类推
public void backforword(List<String> combinations,StringBuffer combination,Map<Character, String> map
,int index,String digits){
if(index == digits.length()){
combinations.add(combination.toString());
}else{
char digit=digits.charAt(index);
String letters=map.get(digit);
for(int i=0;i<letters.length();i++){
combination.append(letters.charAt(i));
backforword(combinations, combination,map,index+1,digits);
combination.deleteCharAt(index);
}
}
}
完整代码：
class Solution {
public List<String> letterCombinations(String digits) {
List<String> combinations=new ArrayList();
if(digits.length()==0){
return combinations;
}
//初始化一个hash表
Map<Character, String> map = new HashMap<Character, String>() {{
put('2', "abc");
put('3', "def");
put('4', "ghi");
put('5', "jkl");
put('6', "mno");
put('7', "pqrs");
put('8', "tuv");
put('9', "wxyz");
}};
StringBuffer combination=new StringBuffer();
backforword(combinations,combination,map,0,digits);
return combinations;
}
public void backforword(List<String> combinations,StringBuffer combination,Map<Character, String> map
,int index,String digits){
if(index == digits.length()){
combinations.add(combination.toString());
}else{
char digit=digits.charAt(index);
String letters=map.get(digit);
for(int i=0;i<letters.length();i++){
combination.append(letters.charAt(i));
backforword(combinations, combination,map,index+1,digits);
combination.deleteCharAt(index);
}
}
}
}
待更。。。。
