算法编程（五）

一、指定一个正序排列的数组和目标数字S，从数组中找到两个元素它们的和值为S（数字不重复，如果有多个，只需要得到一组即可）

    题目很好理解，比如输入数组{1,3,4,6,8,11,20}和目标数字11，那么其中3、8的和值为11，找到它们即可。

    这个题目最粗暴的解法就是逐个元素遍历数组，逐个相加...比如从1开始，让1与此后的每个元素相加并判断和值是否等于11，直到相等或者和值大于11结束，当和值大于11时，则结束本次遍历，然后从3开始再开始一轮...时间复杂度很高。

 

    这个题的关键：数组是排序的，既然只需要找到一对元素即可，那么我们假定它的值是一个大数 + 小数；那么我们就可以定义两个指针，从数组的两端开始遍历。

数组：
1 3 4 6 8 11 20

1）
左端指针从1开始，右端指针从20开始。
2）
1 + 20 > 11
由此可见，大数太大了，所以右端指针向小数方向移动
3）
1 + 11 > 11，同理
4）
1 + 8 < 11
以为这我们的小数选的太小了，所以左端指针向大数方向移动
5）
2 + 8 < 11，同理
6）
3 + 8 = 11，找到结果了

 

    代码样例：

public static void find(int[] source,int target) {
    if(source.length == 0) {
        return;
    }
    int li = 0;
    int ri = source.length - 1;
    while (true) {
        if(li >= ri) {
            System.out.println("Not found");
            break;
        }
        int left = source[li];
        int right = source[ri];
        if(left + right == target) {
            System.out.println(left + "," + right);
            break;
        }else if(left + right > target) {
            ri--;
        }else {
            li++;
        }
    }
}

  

二、给定一个数字S，请找出和值为S的所有连续的数字列表，从1开始

    比如指定数字为9，那么其符合要求的连续数字包括：1 + 2 + 3 + 4 = 4 + 5。

    这个算法的实现，和第一题几乎如出一辙；我们要选定两个数字分别作为初始的大数和小数，small = 1，big = 2；因为 1 +2 < 9，所以big向后选择，直到4，此时和值为9；然后small向后选择、big也向后：2 + 3 +4 +5，此值和值大于9，那么small只能向后驱动（减少参加计算的数字），直到等于9或者剩余一个数字位置..

 

    代码样例：

public static void find(int[] source,int target) {
    if(source.length == 0) {
        return;
    }
    int small = 1;
    int big = 2;
    int current = big + small;
    while (true) {
        if(small == big) {
            break;
        }
        if(current == target ) {
            System.out.println(small + "~" + big);
            big++;
            current += big;
            current -= small;
            small++;
        }else if(current < target) {
            big++;
            current += big;
        }else {
            current -= small;
            small++;
        }
    }
}

 

三、将一个字符串中单词出现的顺序翻转

    比如字符串（字符数组）“I am a student!”，翻转成“student! a am I”，注意只是翻转单词出现的顺序，仍保持单词原样。

    这个题的解法非常多，特别是使用高级API的时候特别容易，但是我们此处有个要求，不能使用高级API，不能额外使用新的空间。该怎么办？

 

    这就限定程序只能在原有的字符数组上进行翻转顺序，思路：

    1）首先将整个字符数组翻转，得到“!tneduts a ma I”。

    2）然后遍历上述字符串，遇到空格分隔符时，利用相同的算法，将空格之间的字符数组翻转。比如遇到一个空格时，将“!tneduts”翻转成“student”。

 

    代码样例：

public static String reserveWords(String source) {
    if(source == null || source.isEmpty()) {
        return source;
    }
    char[] chars = source.toCharArray();
    reserve(chars,0,chars.length - 1);
    char space = ' ';
    int start = 0;
    for(int i=0; i < chars.length - 1; i++) {
        if(chars[i] == space) {
            reserve(chars,start,i - 1);
            start = i+1;
        }
    }
    return new String(chars);
}

private static void reserve(char[] source,int start,int end) {
    if(start >= end) {
        return;
    }
    while (true) {
        if(start >= end) {
            break;
        }
        char tmp = source[start];
        source[start] = source[end];
        source[end] = tmp;
        start++;
        end--;
    }
}

 

四、指定一个字符数组和位置，将此位置之前的字符串和其之后的字符串交换位置

     比如输入“abcdefg”和3，那么3对应的字符串为d，即将“abc”交换到“defg”之后，最终字符数组为“defgabc”。

     说实话，这个题我第一感觉也没思路，我想到的那个笨办法一定不是理想的。我们还需要参照上题，既然是反转字符串，基本思路相同。

原始字符串：abcdefg
分割点：d
1根据分割点，将字符数组分成2部分
abc|defg

2)分别对两部分反转
cba|gfed

3）然后在整体进行反转即可得到结果
defgabc

由此可见，整体思路与上题相同，但是分解过程正好相反。

 

    代码样例： 

public static String reserve(String sources,int position) {
    if(sources == null || sources.isEmpty()) {
        return null;
    }
    char[] chars = sources.toCharArray();
    if(position < 0 || position >= chars.length) {
        throw new RuntimeException("Error!");
    }
    reserve(chars,0,position - 1);
    reserve(chars,position,chars.length - 1);
    reserve(chars,0,chars.length - 1);
    return new String(chars);
}

private static void reserve(char[] source,int start,int end) {
    if(start >= end) {
        return;
    }
    while (true) {
        if(start >= end) {
            break;
        }
        char tmp = source[start];
        source[start] = source[end];
        source[end] = tmp;
        start++;
        end--;
    }
}