leetcode简单难度题解法

1. 两数之和 https://leetcode-cn.com/problems/two-sum/ 难度：☆☆

题目<!https://leetcode-cn.com/articles/two-sum/>:
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的两个整数。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

1
2
3

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

自己解法

public   int[] twoSum(int[] nums, int target) {
    int[] x=new int[2];
    for(int i=0;i<nums.length;i++)
    {
        for(int j=nums.length-1;j>=0;j--)
        {
            if(nums[i]+nums[j]==target && i!=j)
            {
                 x[0]=i;x[1]=j;
                 return x;
            }
        }
    }
    throw new Exception("没有符合条件的数");;
}

最优解法

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");
}

1.1 求数字的根有趣的题目<来自知乎>

求一个十进制数字的根

1	f(12345) -> 1+2+3+4+5 =15 -> 1+5=6 12345的根为6

数学公式写法

1
2
3

function f(n){
	return (n-1)%9 +1 ;
}

解释：
ab写成：10a+b=9a+a+b，这和a+b相差 9a，也就是9的倍数。如果大一点也是一样，abc写成：100a+10b+c=99a+9b+a+b+c,和a+b+c相差9的倍数99a+9b=9（11a+b）。所以abcde…把所有的位数相加结果就是9的倍数取余。
abcde=10000a+1000b+100c+10d+e=9999a +a+ 999b+ b+99c+c +9d +d +e = 9999a +999b +99c +9d +a+b+c+d+e
另外先减一再加一的原因结果不会等于0，如果可以被9整除，直接取余就会是0,这样在计算过程中，先保证所有位数相加是取余是0-8，这样在结果+1时候，就会是1-9.不会出现0值。非常完美的数学算法
这里之所以写成(n-1)%9 +1 不写成 n %9 ，是要改变返回值的值域。(n-1)%9 +1 的值域是 [1,9] ,n %9的值域是[0,8];
f(n) =n%9

2. 两数相加 https://leetcode-cn.com/problems/add-two-numbers/ 难度：☆☆☆☆☆

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：

1
2
3

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

自己第一次未解出来

自己看过解析后，重新做的解答

/**
 * Definition for singly-linked list.
 * public class 
 {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int temp=0;
        ListNode result=new ListNode(0);  
        result.next=new ListNode(0);  
        ListNode tempNode= result.next;
        while(l1!=null||l2!=null){
            int a =0,b=0;
            if(l1==null){a=0;}else{a=l1.val;}
            if(l2==null){b=0;}else{b=l2.val;}
            int i  = a+b+temp;            
            int j=i%10;
            tempNode.next=new ListNode(j );
            if(i>=10 ){temp=1; }else{temp=0;}
            if(l1!=null) {l1=l1.next;}
            if(l2!=null) {l2=l2.next;}
            tempNode=tempNode.next;
        }
        if(temp==1){
            tempNode.next=new ListNode(1);  
        }
        return result.next.next;
    }
}

标准答案

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

自己问题难点：没有理解ListNode代表的含义，对链表类的对象没有操作经验。new ListNode(x) 表示的是当前位数上的数字为X,new ListNode(x).next,表示的是下一位上的数字。自己考虑到了10位进1，后面位数上为null的情况，但是不知道怎么使用代码写出来。
这里可以给l1 ,l2 重新赋值临时变量，他的下一位在赋值给他本身。第一个dummyHead是需要返回的值。用curr来表示他的属性，不断的往后赋值，但是不会改变dummyHead对象本身。这里需要注意的是，两位数加两位数可能等于三位数，这里在最后就要多加一次carry值的判断。

3.宝石与石头 https://leetcode-cn.com/problems/jewels-and-stones/comments/ 难度：☆

给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此”a”和”A”是不同类型的石头。
示例 1:

1 2	输入: J = "aA", S = "aAAbbbb" 输出: 3

自己的解法

class Solution {
    public int numJewelsInStones(String J, String S) {
        int x=0;
        byte[] sArray=S.getBytes();
         for(int i=0;i<sArray.length;i++)
         {
             if(J.indexOf(sArray[i])!=-1)
             {
                 x++;
             }             
         }
        return x;
    }
}

此题暂时没有最优解法。可自由发挥。

4. 回文数 https://leetcode-cn.com/problems/palindrome-number/ 难度：☆☆

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

1 2	输入: 121 输出: true

自己的解法

class Solution {
    public boolean isPalindrome(int x) {
        if(x<0) return false;       
        if(x>=0){
            String y=x+"";
            byte[]  yArray =y.getBytes();
            boolean flag=true;
            for(int i=0;i<yArray.length;i++){
                if(yArray[i]!=yArray[yArray.length-i-1]){
                    flag=false;
                }
            }
            return flag; 
        }
        return false;
    }
}

4.1 上述回文数中不使用字符串该如何解决难度：☆☆☆☆☆

解析：不使用字符串，首先想到的是，是否有现成的数据公示可以用，想了想，目前接触的没有可以用的，只能想想其他方法。
因为数字的特殊性，在程序中经常用到，想一想是否能否算出各个位数上的数字。
比如12345，长度可以用12345/(10^i)算出来。
要计算12345的第三位上的数字。可以先用12345减去第三位前面的数字，再除以10^2，取整数。即可算出第三位上的数字。
第三位前面的数字如何计算。可以用12345 除以10^3，取整数，再乘以10^3，即可算出第三位前面的数字为 12000。
用12345减去 12000 为345。 345 除以10^2，取整为3。
这样就可以算出各个位数上的数字。再用来比较就可以了。

自己解法

 public static boolean isPalindrome(int x) {
	if(x<0) return false;
	if(x<10) return true;
	//计算出x长度
	int y=0;
	for(int j=1;j<22;j++){
		int temp=(int) (x/(Math.pow(10,j)));
		if(temp>0&&temp<10){
			y=j+1;
		}
	}
	boolean flag=true;
	for(int i=1;i<=y;i++){
		//第i位数字
		int tempA1=(int) (x/(Math.pow( 10,i)));
		int after= (int) ( (x- tempA1 *(Math.pow( 10,i)))/(Math.pow( 10,i-1)) );
		// //第y-i-1位数字(倒数i位数字)
		int tempB1=(int) (x/( Math.pow( 10,(y-i+1))));
		int before= (int) ( (x- tempB1 *(Math.pow( 10,(y-i+1))))/(Math.pow( 10,(y-i-1+1))) );	            
		if(before == after){
			//flag=true;
		} else  {
			flag=false;
		}
	}
	return flag;
}

4.2 软通笔试题

长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的交换，完成以下函数

public class Solution {
    /**
     * 交换数组里n和0的位置
     *
     * @param array
     *            数组
     * @param len
     *            数组长度
     * @param n
     *            和0交换的数
     */
    // 不要修改以下函数内容
    public void swapWithZero(int[] array, int len, int n) {
        Main.SwapWithZero(array, len, n);
    }
    // 不要修改以上函数内容
 
    /**
     * 通过调用swapWithZero方法来排
     *
     * @param array
     *            存储有[0,n)的数组
     * @param len
     *            数组长度
     */
    public void sort(int[] array, int len) {
        // 完成这个函数
         for(int i = len-1;i>=0; i--){
				if(array[i] == i)                        //判断是否在正确位置
					continue;
                swapWithZero(array,len,array[i]);
                swapWithZero(array,len,i);
        }
    }
}
``` 

在网上看到有人说为什么要用swapWithZero()这个方法，直接赋值更快，如下：

for(int i = 0; i < len; i++){
array[i]=i;
}
`