昆明免费网站建设友链交易交易平台

1.最大子序和

//给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 
//
// 示例: 
//
// 输入: [-2,1,-3,4,-1,2,1,-5,4]
//输出: 6
//解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
// 
//
// 进阶: 
//
// 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 
// Related Topics 数组 分治算法 动态规划

 最大子序和可以采用两种方式来进行求解。第一种就是依次相加，从第一个开始，逐个累加比较，再从第二个开始逐个累加比较，知道比到最后一个数为止。这种方法的空间复杂度太高了，很明显是不实用的。答案给了一种比较巧妙的方法，就把之前的数的和设为pre，把当前数设为x，如果pre+x比x还小，那我们就直接把pre给放弃了，就直接把x变为新的pre。这种方式就大大降低了算法的空间复杂度。

public int maxSubArray(int[] nums) {/*int max = nums[0];int temp = 0;for (int i = 0; i < nums.length; i++) {temp = 0;for(int j = i; j < nums.length; j++){temp += nums[j];if(temp > max){max = temp;}}}return max;*/int pre = 0, maxAns = nums[0];for (int x : nums) {//这里就是这个方法的牛逼之处，当我们前面的加上x还会减小的时候，我们就直接放弃前面的了，//就直接再从x开始往后加pre = Math.max(pre + x, x);maxAns = Math.max(maxAns, pre);}return maxAns;}

2.最后一个单词长度 

//给定一个仅包含大小写字母和空格 ' ' 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。 
//
// 如果不存在最后一个单词，请返回 0 。 
//
// 说明：一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。 
//
// 
//
// 示例: 
//
// 输入: "Hello World"
//输出: 5
// 
// Related Topics 字符串

第二题主要是需要考虑到各种不同的情况，比如当为空串或者null的时候，还有最后一个字符为空格，这也是这类字符串的题都需要考虑到的几种情况。

public int lengthOfLastWord(String s) {int length = 0;if(s.length()==0 && s==null){return 0;}for (int i = s.length()-1; i >= 0; i--) {if(s.charAt(i) == ' '){if(length == 0){//这个continue就是为了解决最后一个字符是空格的情况continue;}break;}length++;}return length;}