数据结构和算法之两数求和系列

580 次访问 2020-10-14

mood

两数之和

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

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

public int[] twoSum(int[] nums, int target) {
        int[] result=new int[2];
        Map<Integer,Integer> map=new HashMap();
        for(int i=0;i<nums.length;i++){
            /**
             * 当遇到【3，3】=6的情况来看呢
             * 先执行 map.put(nums[i],i);
             * 把map中以后的key3设置为0，第二次循环又把key3覆盖为1
             *  当进行俩数求和时候，containsKey判断存在key3，那么就行设置返回值
             *  发现result[0]=1了。result[1]也=1。这显然是不正确的，所以呢要把put数据后置
             */
            if(map.containsKey(target-nums[i])){
                result[0]=map.get(target-nums[i]);
                result[1]=i;
            }
            map.put(nums[i],i);

        }
        return result;

    }

两数相加

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

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

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

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

 /**
     * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 0 -> 8
     * 原因：342 + 465 = 807
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode result=new ListNode(0);
        ListNode ret=result;
        int carry=0;
        while (l1!=null||l2!=null){
            //抛去去进位得到的值
            int sum=((l1!=null?l1.val:0)+(l2!=null?l2.val:0)+carry)%10;
            //得到进位
            carry=((l1!=null?l1.val:0)+(l2!=null?l2.val:0)+carry)/10;
            ret.next=new ListNode(sum);
            ret=ret.next;
            if (l1!=null){
                l1=l1.next;
            }
            if (l2!=null){
                l2=l2.next;
            }
        }
        //考虑最后加完的进位
        if (carry>0){
            ret.next=new ListNode(carry);
        }
        return result.next;

    }

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。

示例:

输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

/**
    归并
    */
    public void merge(int[] A, int m, int[] B, int n) {
        int[] rsult=new int[m+n];
        for(int i=0,j=0,k=0;k<m+n;k++){
            if(i>=m){
                rsult[k]=B[j++];
            }else if(j>=n){
                rsult[k]=A[i++];
            }else if(A[i]>=B[j]){
                rsult[k]=B[j++];
            }else{
                rsult[k]=A[i++];
            }
        }
        for(int i=0;i<m+n;i++){
            A[i]=rsult[i];
        }
    }

  public void merge(int[] A, int m, int[] B, int n) {
        int a,b,c=m-1,n-1,m+n-1;
        while (b<=0){
            if(a<0||B[b]>=A[a]){
                A[c--]==B[b--];
            }else{
                A[c--]==A[a--];
            }
        }
    }