public class Test { public static int maxSubArray(int arr[]) { int n = arr.length; int ThisSum = 0,MaxSum = 0,i,j,k; for(i=0;i<n;i++) { for(j=i;j<n;j++) { ThisSum = 0;//重置为0 for(k=i;k<j;k++) { ThisSum +=arr[k]; } if(MaxSum<ThisSum) MaxSum = ThisSum; } } return MaxSum; } public static void main(String[] args) { // TODO 自动生成的方法存根 int [] arr = {1,-2,4,8,-4,7,-1,-5}; System.out.println(maxSubArray(arr)); } }
运行结果:15 时间复杂度:O(n^3)直接洗洗睡吧。
优化:过多子数组都重复计算,利用已经计算的子数组和
public static int maxSubArray(int arr[]) { int n = arr.length; int MaxSum = Integer.MIN_VALUE; int i,j; for(i=0;i<n;i++) { int sum = 0; for(j=i;j<n;j++) { sum+=arr[j]; if(sum>MaxSum) MaxSum = sum; } } return MaxSum; }
public static int FindGreatestSumOfSubArray(int[] array) { int res = array[0]; int max = array[0]; for(int i = 1;i<array.length;i++) { max = Math.max(max+array[i], array[i]); res = Math.max(max, res); } return res; }
public class Test { public static int findNotDouble(int[] a) { int n = a.length; int result = a[0]; int i; for(i=1;i<n;i++) { result = result^a[i]; } return result; } public static void main(String[] args) { int[]arr = {1,2,3,2,4,3,5,4,1}; int num = findNotDouble(arr); System.out.println(num); } }
运行结果:5
1.6 找出数组中的唯一重复元素
数组a [N ],1– N -1这N -1个数存放在a [N ]中,其中某个数重复1次。写一个函数,找出被重复的数字。要求每个数组元素只能访问1次,并且不用辅助存储空间。
public class Test { public static int findDup(int[]a) { int n=a.length; int tmp1 = 0; int tmp2 = 0; for(int i = 0;i<n-1;i++) { tmp1 +=(i+1); tmp2 +=a[i]; } tmp2 +=a[n-1]; return tmp2-tmp1; } public static void main(String[] args) { int[]a = {1,2,1,3,4,5}; System.out.println(findDup(a)); } }
public class Test { public static int findIndex(int a[],int t) { if(a==null) return -1; int len = a.length; int i = 0; while(i<len) { if(a[i]==t) return i; else i +=Math.abs(t-a[i]); } return -1; } public static void main(String[] args) { int a[]= {3,4,5,6,5,7,8,9,8}; System.out.println(findIndex(a, 9)); } }
把一个句子中的单词进行反转,例如,“hello world !”,进行反转后“! world hello” 只需要进行两次字符反转的操作即可,第一次对整个字符串中的字符进行反转, “!dlrowolleh”,通过这一次的反转已经实现了单词顺序的反转,只不过每个单词中字符的顺序反了,接下来只需要对每个单词进行字符反转即可得到想要 的结果
public class Test { public void swap(char[]cArr,int front,int end) { while(front<end) { char temp = cArr[end]; cArr[end] = cArr[front]; cArr[front] = temp; front++; end--; } } public String swapWords(String s) { char[]cArr = s.toCharArray(); //对整个字符串进行字符反转操作 swap(cArr, 0, cArr.length-1); int begin = 0; //对每个单词进行字符反转操作 for(int i=1;i<cArr.length;i++) { if(cArr[i]==' ') { swap(cArr, begin, i-1); begin =i+1; } } swap(cArr, begin, cArr.length-1); return new String(cArr); } public static void main(String[] args) { String str = "hello world !"; System.out.println(new Test().swapWords(str)); } }
public static int wordCount(String s) { int word = 0; int count = 0; for(int i=0;i<s.length();i++) { if(s.charAt(i)==' ') word = 0; else if(word==0) { word=1; count++; } } return count; } public static void main(String[] args) { String s = "i am ironman"; System.out.println("单词个数为:"+wordCount(s)); } }