太多了,猛男落泪。

1.数组

1.1 求最大子数组之和

最笨的方法
(求出所有子数组的和,取最大值,应该是用不到…)

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;
}

时间复杂度O(n^2)

2.动态规划法
感到惊为天人。

F(i):以array[i]为末尾元素的子数组的和的最大值,子数组的元素的相对位置不变

F(i)=max(F(i-1)+array[i] , array[i])

res:所有子数组的和的最大值

res=max(res,F(i))

如数组[6, -3, -2, 7, -15, 1, 2, 2]

初始状态:

F(0)=6
res=6

i=1:

F(1)=max(F(0)-3,-3)=max(6-3,3)=3
res=max(F(1),res)=max(3,6)=6

i=2:

F(2)=max(F(1)-2,-2)=max(3-2,-2)=1
res=max(F(2),res)=max(1,6)=6

i=3:

F(3)=max(F(2)+7,7)=max(1+7,7)=8
res=max(F(2),res)=max(8,6)=8

i=4:

F(4)=max(F(3)-15,-15)=max(8-15,-15)=-7
res=max(F(4),res)=max(-7,8)=8

以此类推

最终res的值为8

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;
}

时间复杂度O(n)

1.2 找出数组中重复元素最多的数

使用Map映射表。通过引人Map映射表(Map提供一对一的数据处理能力,其中第一个为关键字,每个关键字只能在Map中出现一次,第二个称为该关键字的值)来记录每一个元素岀现的次数,然后判断次数大小,进而找出重复次数最多的元素。

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class Solution {
//先排序过的数组
public int serach(int[]arr) {
int result= 0;
int size = arr.length;
if(size==0)
return -1;
//记录每个元素出现的次数
Map<Integer, Integer>m = new HashMap<>();
for(int i = 0;i<size;i++) {
if(m.containsKey(arr[i])) {
m.put(arr[i], m.get(arr[i])+1);
}
else {
m.put(arr[i], 1);
}
}

//找出出现次数最多的元素
int most = 0;
Iterator iterator = m.entrySet().iterator();
while(iterator.hasNext()) {
Map.Entry entry = (Map.Entry ) iterator.next();
int key = (int) entry.getKey();
int val = (int) entry.getValue();
if(val>most) {
result = key;
most = val;
}

}
return result;
}
public static void main(String[] args) {
int array[] = {1,1,5,4,3,4,4,5,4,5,5,6,6,6,6,6} ;
Solution s = new Solution();
System.out.println( s.serach(array));
}
}

运行结果:6

1.3 求数组中两两相加等于20的组合种数

给定一个数组{1,7,17,2,6,3,14},这个数组中满足条件的有两对组合17+3=20和6+14=20

双重循环法(最容易想到)

public class Test {
public static void findSum(int[]a,int sum) {
int i,j;
for(i=0;i<a.length;i++) {
for(j=i;j<a.length;j++) {
if(a[i]+a[j]==sum)
System.out.println(a[i]+","+a[j]);
}
}
}

public static void main(String[] args) {
int[] array= {1,7,17,2,6,3,14};
findSum(array, 20);
}
}

运行结果:
17,3
6,14

排序法

先对数组元素进行排序,可以选用堆排序或快速排序,此时算法的时间复杂度为O(nlogn), 然后对排序后的数组分别从前到后和从后到前遍历,假设从前往后遍历的下标为begin,从后往前遍历的下标为end,那么当满足arr[begin] + arr[end] <20时,如果存在两个数的和为20,那么这两个数一定在[begin + 1,end]之间;当满足arr[ begin] + arr[end] >20时,如果存在两个数的和为20,那么这两个数一定在[begin,end+ 1]之间。这个过程的时间复杂度为0(n),因此整 算法的时间复杂度为O(nlogn)

public static void findsum(int[]a,int sum) {
Arrays.sort(a);
int begin = 0;
int end = a.length-1;
while(begin<end) {
if(a[begin]+a[end]<sum)
begin++;
else if(a[begin]+a[end]>sum)
end--;
else {
System.out.println(a[begin]+","+a[end]);
begin++;
end--;
}
}
}

1.4 把一个数组循环右移K位

把数组序列12345678右移2位变为78123456

设计算法如下:

1) 逆序数组子序列123456,数组序列的形式变为65432178。
2) 逆序数组子序列78,数组序列的形式变为65432187。
3) 全部逆序,数组序列的形式变为78123456。

public class Test {
public static void reverse(int[]a,int b,int e) {
for(;b<e;b++,e--) {
int tmp = a[e];
a[e] = a[b];
a[b] = tmp;
}
}

public static void shift_k(int[]a,int k) {
int n = a.length;
k = k%n;//为了防止k比n大,右移k位跟右移k%n位的结果是一样的
reverse(a, n-k, n-1);
reverse(a, 0, n-k-1);
reverse(a, 0, n-1);
}

public static void main(String[] args) {
int[] array= {1,2,3,4,5,6,7,8};
shift_k(array, 4);
for(int i = 0;i<array.length;i++) {
System.out.print(array[i]);
}
}
}

运行结果:67891234

时间复杂度O(n)

1.5 找出数组只中出现一次的数字

一个整型数组里除了一个数字之外,其他数字都岀现了两次。找出这个只岀现1次的数字。要求时间复杂度是0(n),空间复杂度是0(1)。

异或的运算方法是一个二进制运算,两者相等为0,不等为1

任何一个数字异或它自己都等于0,所以,如果从头到尾依次异或数组中的每一个 数字,那些出现两次的数字全部在异或中会被抵消掉,最终的结果刚好是这个只出现1次的数字。

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次,并且不用辅助存储空间。

采用数学求和法,因为只有一个数字重复1次,而又是连续的,根据累加和原理,对数组的所有项求和,然后减去1–N-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));
}
}

运行结果: 1

1.7 递归法求整数数组最大元素

对数组进行遍历,定义一个变量max为数组的第一 个元素,然后从第二个元素开始遍历,在遍历过程中,每个元素都与max的值进行比较,若该元素的值比max的值大,则把该元素的值赋给max。

public class Test {
private static int max(int a,int b) {
return a>b?a:b;
}

public static int maxnum(int[]a,int begin) {
int lenght = a.length-begin;
if(lenght==1)
return a[begin];
else {
return max(a[begin], maxnum(a, begin+1));
}
}
public static void main(String[] args) {
int[] array= {1,7,17,2,6,3,14};
System.out.println(maxnum(array, 0));
}
}

运行结果:17

1.8 求升序数组绝对值最小的数

三种情况:
①如果数组第一个元素为非负数,那么绝对值最小 的数肯定为数组的第一个元素
②如果数组最后一个元素为负数,那么绝对值最小的数肯定是 数组的最后一个元素
③数组中即有正数又有负数时,首先找到正数与负数的分界点,如果分 界点恰好为0,那么0就是绝对值最小的数,否则通过比较分界点左右的正数与负数的绝对值 来确定最小的数。

采用二分法来查找正数 与负数的分界点的方法。

public class Test {

public static int getMinAbsoluteValue(int[]a) {
if(a==null)
return Integer.MIN_VALUE;
int len = a.length;
if(len<1)
return Integer.MIN_VALUE;
//数组中没有负数
if(a[0]>=0)
return a[0];
//数组中没有正数
if(a[len-1]<=0)
return a[len-1];

int mid =0;
int begin =0;
int end = len-1;
int absMin =0;
//数组中正负皆有
while(true) {
mid = begin+(end-begin)/2;
//如果值等于0,那么就是绝对值最小的值
if(a[mid]==0)
return 0;
//如果值大于0,那么正负数分界点在左半部分
else if(a[mid]>0) {
//继续在数组左半部分查找
if(a[mid-1]>0)
end = mid-1;
else if(a[mid-1]==0)
return 0;
//找到正负数的分界点
else
break;
}//如果值小于0,在数组右半部分查找
else {
if(a[mid+1]<0)
begin =mid+1;
else if(a[mid+1]==0)
return 0;
else
break;
}
}

//获取正负数分界点处绝对值最小额数
if(a[mid]>0) {
if(a[mid]<Math.abs(a[mid-1]))
absMin = a[mid];
else
absMin = a[mid]-1;
}else {
if(a[mid]<Math.abs(a[mid-1]))
absMin = a[mid];
else
absMin = a[mid+1];
}

return absMin;
}

public static void main(String[] args) {

int[]a1 = {-10,-5,-2,7,5,15};
int[]a2 = {2,4,6,8,27};
int[]a3 = {-13,-9,-7,-3};
int value = getMinAbsoluteValue(a1);
System.out.println(value);
value = getMinAbsoluteValue(a2);
System.out.println(value);
value = getMinAbsoluteValue(a3);
System.out.println(value);
}
}

运行结果:
-2
2
-3

1.9 求指定数字在数组中第一次出现的位置

给定数组a={3,4,5,6,5,6,7,8,9,8},这个数组中相邻元素之差都为1,给定数字9,它在数组中第一次岀现的位置的下标为8 (数组下标从0开始)。
两种方法

1.蛮力法
假设指定数字为t顺序遍历数组中每一个元素,并且将数组中的元素与t进行比较,判断两个值是否相等,若相等,则返回下标位置;若遍历完数组还没找到t, 则说明t在数组中不存在,返回-1。该方法的时间复杂度为O(n)。
这种方法显然没有用到题目中“这个数组中相邻元素之差的绝对值为1”这一条件

2.跳跃搜索法
规律:假设先从数组a中查找9出现的位置,首先用数组中第一个元素(数组下标为0)3与9进行比较,它们的差值为6,由于数组中相邻两个元素的差值为1,因此9在数组中出现的最早的位置必定为:第 1+6 =7个位置(数组下标为6)

根据这个特点可以得出算法的思路为:从数组第一个元素开始(i=0),把数组当前位置的值与t进行比较,如果相等,则返回数组下标,否则,从数组下标为i+ |t- a[i]|处继续査找。

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));
}
}

运行结果:7

1.10 计算两个有序整型数组的交集

假设两个含有n个元素的有序(非降序)整型数组a和b,其中a={0,1,2,3,4},b = {1,3,5,7,9),那么它们的交集为{1,3}。
数组的相对大小一般会影响算法的效率,所以需要根据两个数组的相对大小来确定采用的方法:

1.对于两个数组长度相当的情况
二路归并法。设两个数组分别为array1[n1]和array2[n2]分别以i,j从头开始遍历两个数组。

import java.util.ArrayList;
public class Test {

public static ArrayList<Integer>mixed(int array1[],int array2[]){
ArrayList<Integer>mix = new ArrayList<Integer>();
int i =0,j=0;
int n1 = array1.length;
int n2 = array2.length;
while(i<n1&&i<n2) {
if(array1[i]==array2[j]) {
mix.add(array1[i]);
i++;
j++;
}else if(array1[i]>array2[j]){
j++;
}else if(array1[i]<array2[j]) {
i++;
}
}

return mix;
}


public static void main(String[] args) {

int [] a = {0,1,2,3,4};
int [] b = {1,3,5,7,9};
ArrayList<Integer>mix = mixed(a, b);
for(int i=0;i<mix.size();i++)
System.out.print(mix.get(i)+" ");
}
}

运行结果:1 3

方法二:顺序遍历法。顺序遍历两个数组,将数组元素存放到哈希表中,同时对统计的数组元素进行计数,若为2,则为二者的交集元素。

2.字符串

2.1字符串反转

把一个句子中的单词进行反转,例如,“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));
}
}

运行结果:
! world hello

2.2 判断两个字符串是否由相同字符组成

由相同的字符组成是指组成两个字符串的字母以及各个字母的个数是一样的, 只是排列顺序不同而已,例如,“aaaabbc”与“abcbaaa”就由相同的字符组成的。

方法一:排序法。

import java.util.Arrays;
public class Test {

public static void compare(String s1,String s2) {
byte[]b1 = s1.getBytes();
byte[]b2 = s2.getBytes();
Arrays.sort(b1);
Arrays.sort(b2);
s1 = new String(b1);
s2 = new String(b2);
if(s1.equals(s2))
System.out.println("equal!");
else
System.out.println("not equal!");
}

public static void main(String[] args) {
String s1 = "aaaabbc";
String s2 = "abcbaaa";
compare(s1, s2);
String s3 = "aaabbc";
String s4 = "abcbaae";
compare(s3, s4);
}
}

运行结果:
equal!
not equal!

以上方法的时间复杂度取决于排序算法的时间复杂度,由于最快的排序算法的时间复杂度 为0(nlgn),因此,该方法的时间复杂度也为O(nlogn)。

2.3 删除字符串中重复字符

例如,“good”去掉重复的字符后就变为“god”。

方法一:“蛮力”法。
把这个字符串看作一个字符数组,对该数组使用双重循环进行遍历,如果发现有重复的字符,就把该字符置为‘\0’,最后再把这个字符数 组中的所有‘\0’ 去掉,此时得到的字符串就是删除重复字符后的目标字符串。

import java.util.Arrays;

public class Test {

public static String removeDuplicate(String str) {
char[]c = str.toCharArray();
int len = c.length;
for(int i=0;i<len;i++) {
if(c[i]=='\0')
continue;
for(int j=i+1;j<len;j++) {
if(c[j]=='\0')
continue;
//把重复的字符置为‘\0’
if(c[i]==c[j])
c[j]='\0';
}
}
int l = 0;
//去掉'\0'
for(int i=0;i<len;i++) {
if(c[i]!='\0')
c[l++]=c[i];
}
return new String(c, 0, l);
}

public static void main(String[] args) {
String str = "abcaabcde";
str = removeDuplicate(str);
System.out.println(str);
}
}

运行结果:
abcde

方法二:空间换时间
常见的字符只有256个,可以假设这道题字符串中不同的字符个数最多为256个,可以申请一个大小为256的int类型的数组来记录每个字符岀现的次数,初始化都为0,把这个字符的编码作为数组的下标,在遍历字符数组时,如果这个字 符岀现的次数为0 ,那么把它置为1 ;如果这个字符岀现的次数为1 ,说明这个字符在前面已经出现过了,就可以把这个字符置为‘ \ 0 ’ ,最后去掉所有‘ \ 0 ’ ,就实现了去重的目的。

2.4 统计一行中有多少单词

单词的数目可以由空格出现的次数决定

若测出某一个字符为非空格,而它的前面的字符是空格,则表示新的单词开始了,单词计数器count值加1 ;若当前字符为非空格而其前面的字符也是非空格,则意味着是原来那个单词的继续,count值不应再累加1。前面一个字符是否空格 可以从word的值看出来,若word等于0,则表示前一个字符是空格;若word等于1,意味着前一个字符为非空格。

public class Test {

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));
}
}

运行结果:
单词个数为:3

2.5 输出字符串的所有组合

假设字符串中耳朵字符丢不重复,例如输入“abc”,输出a,b,c,ab,ac,bc,abc总共七种组合。

如果字符串中有n个字符,那么就有2^n-1种组合。


public class Test {

public static void Combine(char[] c,int begin,int len,StringBuffer sb) {
if(len==0) {
System.out.print(sb+" ");
return;
}
if(begin==c.length)
return;

sb.append(c[begin]);
Combine(c, begin+1, len-1, sb);
sb.deleteCharAt(sb.length()-1);
Combine(c, begin+1, len, sb);
}

public static void main(String[] args) {
String s = "abc";
char[]c = s.toCharArray();
StringBuffer sb = new StringBuffer("");
int len = c.length;
for(int i=1;i<=len;i++) {
Combine(c, 0, i,sb);
}
}
}

3. 二叉树