一、第k小数问题

题目描述

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

思路

• 题目要求在O(log(m+n))时间内完成，可以转换为找到假设两个数组合并后的第（m+n)/2小的数。
• 这里先忽略奇偶问题，具体实现代码中会有不同。先假设A和B中的数都大于k/2,比较A[k/2-1]和B[k/2-1]（减1是因为数组下标从零开始）如果A[k/2-1]

代码

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        //奇偶数不会有影响，最后中位数就是平均值
        int m = A.length,n = B.length;
        int l = (m+n+1)/2;
        int r = (m+n+2)/2;
        
        return (findKthNum(A,B,0,0,l)+findKthNum(A,B,0,0,r))/2.0;
    }
    private double findKthNum(int [] A,int [] B,int Astart,int Bstart,int k){
        int lenA = A.length;
        int lenB = B.length;
        if(Astart>=lenA){
            return B[Bstart+k-1];
        }
        if(Bstart>=lenB){
            return A[Astart+k-1];
        }
        if(k==1){
            return Math.min(A[Astart],B[Bstart]);
        }
        int minA = Integer.MAX_VALUE;
        int minB = Integer.MAX_VALUE;
        if(Astart+k/2-1<A.length){
            //如果这里超过了A数组的范围，那就说明A中有将A、B合并后一半以上的
            //数，也就是说中位数肯定在A中。那后面的minB<minA(MAX_VALUE)，就会成立，从而舍弃B中的前一些无关的数
            minA = A[Astart+k/2-1];
        }
        if(Bstart+k/2-1<B.length){
            minB = B[Bstart+k/2-1];
        }
        if(minA<minB){
            return findKthNum(A,B,Astart+k/2,Bstart,k-k/2);
        }
        else{
            return findKthNum(A,B,Astart,Bstart+k/2,k-k/2);
        }
    }
}

二、map映射

题目描述

Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

思路

• 给一列数，给一个目标值，找出数列中两个数和为这个值的下标。因为数没有排序，可以考虑用map来构建数值和下标的映射，更狠一点，在遍历数组的同时，用map构建目标值减去当前这个数的值与当前下标的映射，然后对每一个遍历到的数判断是否已存在在map中。

代码

import java.util.HashMap;

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        int [] res = new int [2];
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0 ;i<n;i++){
            if(map.containsKey(numbers[i])){
                res[0]=map.get(numbers[i])+1;
                res[1]=i+1;
                break;
            }
            else{
                map.put(target-numbers[i],i);
            }
        }
        return res;
    }
}

三、动态规划

题目描述

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

思路

• 题目提示了用动态规划来解，那自然想到从step 1,2,3,.。于是慢慢推了看看，看是否能得到状态转移方程。写了几个，发现：dp[i]=dp[i-1]+dp[i-2];

代码

public class Solution {
    public int climbStairs(int n) {
        int [] dp = new int[n+2];
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

//优化一下空间复杂度
public class Solution {
    public int climbStairs(int n) {
        if(n<=2){
            return n;
        }
        int one_step_before=2;
        int two_step_before=1;
        for(int i=3;i<=n;i++){
            int cur = one_step_before+two_step_before;
            two_step_before = one_step_before;
            one_step_before = cur;
        }
        return one_step_before;
    }
}