面试题目memo

题目都是网上看到的。试着解答一下，全当脑力训练。以后会陆续追加，持续更新本帖。

95.华为面试题
1 判断一字符串是不是对称的，如：abccba
[color=darkblue]思路：题目的解答是一目了然的。如下伪代码。

boolean check(str){
    for(int i=str的开始索引,j=str的末尾索引;i < j;i++,j--){
        if(str[i] != str[j]){
            return false;
        }
    }
    return true;
}

[/color]

2.用递归的方法判断整数组a[N]是不是升序排列
[color=darkblue]思路：先判断当前元素以后的子数组是否为升序，若是则只需判断当前元素是否<=子数组的第一个元素即可。如下伪代码。

boolean check(int arr[], int s){
    if(s>=arr.length - 1) return true;
    if(check(arr, s+1)){
      if(arr[s] <= arr[s+1])  return true;    
    }
    return false;
}

[/color]


3. 给出一个函数来输出一个字符串的所有排列。
思路：先给一个例子，aabc，则所有的排序如下：
a开头：aabc, aacb, abac, abca, acab, acba
b开头：baac, baca, bcaa
c开头：caab, caba, cbaa
算法描述：
1、对字符串进行预处理，得到不重复字符集以及各个字符出现频率。
   例如得到[a,b,c], [2,1,1]
2、设字符集的第一个元素作为当前元素。例如元素a。
3、如果当前元素频率大于0，则把当前元素放入结果缓存里，此时字符的频率需要-1。
   如果当前元素频率等于0， 执行5步。 
  
   例如取出a放入结果缓存，则各个变量变成如下：
   频率集：[1,1,1]
   结果缓存：[a]
4、3步处理后，结果缓存长度会增加1，只需计算剩余字符集以及其相应频率条件的下的所有排列，
   把每个排序加到当前结果缓存后面，即可得到以当前结果缓存为前缀的所有结果排列。
   【计算剩余字符集以及其相应频率条件的下的所有排列】为原问题的子问题，只需递归执行除1步外的各步即可。
   具体操作为：
   1）拷贝当前频率集作为递归参数。
   2）执行递归处理
5、把字符集的下一个元素设为当前元素，重复3步的处理

4. 最大子数组和
递归算法：

public class MaxSubArraySum {
	private int result = 0;
	private int maxSumIncludeN = 0;

	public int execute( int[] a ) {
		maxSubArraySum( a, a.length );

		return result;
	}

	private void maxSubArraySum( int[] a, int n ) {
		if ( n == 1 ) {
			if ( a[n - 1] > result ) {
				result = a[n - 1];
			}
			if ( a[n - 1] > maxSumIncludeN ) {
				maxSumIncludeN = a[n - 1];
			}
			return;
		}

		maxSubArraySum( a, n - 1 );

		if ( a[n - 1] + maxSumIncludeN > a[n - 1] ) {
			maxSumIncludeN = a[n - 1] + maxSumIncludeN;
		}
		else {
			maxSumIncludeN = a[n - 1];
		}
		if ( result < maxSumIncludeN ) {
			result = maxSumIncludeN;
		}
	}
	
	public static void main(String[] args){
		int[] a = {1, -2, 3, 10, -4, 7, 2, -5};
		
		System.out.println("MaxSubArraySum=" + new MaxSubArraySum().execute( a ));
	}
}