1-10截图

1.两数之合

题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
解题思路

主要的做题思路是遍历每个对象，如果target减去当前的值A得到的B在map中，那就找到了！

就把这两个位置(一个map中，一个当前位置)返回去。

如果没有找到，就把遍历到的（位置，值）放到map中

//以下为一个战胜100%的java代码，99%之类的用的是Map，看来以下这样写的效率应该高一点点

class Solution {
    public int[] twoSum(int[] nums, int target) {
       int maxValue = 2048;//样例中nums数组的大小应该不比2048大
       int[] map = new int[maxValue];//和Hashmap一样的作用，存入的值是（位置，值）
       int tool = maxValue - 1;//2的11次方减1，大概是用于做hash的作用
       for (int i = 0; i < nums.length; i++) {//遍历每个对象
            int num = nums[i];
            int pos = map[(target - num) & tool];
            if (pos != 0) {
                //如果target减去当前的值A得到的B在map中，那就找到了
                //就把这两个位置(一个map中，一个当前位置)返回去                
                return new int[]{pos - 1, i};
            }
            map[num & tool] = i + 1;//如果没有找到，就把遍历到的（位置，值）放到map中
        }
		return null;
    }
}

2.两数相加

https://leetcode-cn.com/problems/longest-palindromic-substring/

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
1
2
3
4
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

题解很简单，就是遍历两个链表，设置一个carry作为进位

/**
 * Definition for singly-linked list.
 * public class ListNode {//这是定义了链表的节点
 *     int val;//节点有值
 *     ListNode next;//节点指向的下个节点
 *     ListNode(int x) { val = x; }//节点的构造器，初始化val为传入x
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result=new ListNode(0);//做一个0值头指针
        ListNode resultA=result;
        int carry=0;//进位值
        int i1,i2;//遍历链表的值
        int sum;//总数
        //carry!=0（carry=）是为了链表节点数一样，但是有进位的情况
        while(l1!=null|l2!=null|carry!=0)//链表还有下一个节点、或者还有下个进位就继续
        {
            //这里是为了判断链表数不一样的情况
            i1=l1!=null?l1.val:0;
            i2=l2!=null?l2.val:0;
            System.out.print(i1);        
            sum=i1+i2+carry;
            carry=sum/10;//把sum的进位留到下一个节点
            ListNode newNode=new ListNode(sum%10);//余数就放在当前新建节点       
            result.next=newNode;
            result=newNode;
            l1=l1!=null?l1.next:null;//遍历链表1
            l2=l2!=null?l2.next:null;//遍历链表2
        }
        return resultA.next;//返回0值头指针所指向的链表
    }
}

5. 最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：
1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

主要的思路，就是遍历字符串的每个字符。

每个字符串从中间往外面寻找是否是回文，是的话继续寻找，直到两边字符不再相同，就停止。

class Solution {
    public String longestPalindrome(String s) {
        int length_s=s.length(),length_Palin=1;
        String result="";
        int first,second,first_next,second_next;
        if(length_s==1) return s;//判断是否为一个字符，直接返回
        else if(length_s>1) result=s.substring(0,1);//把第一个字符放进来，使得最少为一个字符
        
        //用两个指针遍历
        for(first=0,second=1;second<length_s;first++,second++){
            //这是两个指针判断的回文
            if(s.charAt(first)==s.charAt(second)){
                first_next=first;second_next=second;
                    while(first_next-1>=0 && second_next+1<length_s && s.charAt(first_next-1)==s.charAt(second_next+1)){
                    first_next--;
                    second_next++;
                }
                if(result.length()<second_next-first_next+1){
                    result=s.substring(first_next, second_next+1);
                }
            }
           	//这是一个指针判断的两侧回文
            if(second<=length_s-2&&s.charAt(second-1)==s.charAt(second+1))
            {
                first_next=second-1;second_next=second+1;
                while(first_next-1>=0 && second_next+1<length_s && s.charAt(first_next-1)==s.charAt(second_next+1)){
                    first_next--;
                    second_next++;
                }
                if(result.length()<second_next-first_next+1){
                    result=s.substring(first_next, second_next+1);
                }
            }
        }
        return result;
    }
}

9.回文数

https://leetcode-cn.com/problems/palindrome-number/

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:
1
2
输入: 121
输出: true

主要是借鉴了评论区高赞老哥的思路，因为x是int型,若逆序后(即12345->54321)溢出则不是回文序列。

分三种情况

1)x为负数,false
2)x逆序后,与原来x不同,溢出或非回文,false
3)x逆序后与原来x相同,回文,true

class Solution {
    public boolean isPalindrome(int x) {
        if(x<0) return false;
        int x_origin=x;
        long reserve=0;
        while(x!=0){
            reserve=reserve*10+x%10;
            x=x/10;
        }
        if((int)reserve!=x_origin) return false;
        else return true;
    }
}