简书 賈小強
转载请注明原创出处，谢谢！
数组即连续，同类型的一组数据，可以通过索引读写，索引以0开始，看似简单实际上可以演变出很多算法问题
基本
public class Test {
public static void main(String[] args) {
int[] a={5,4,1,2,4};
System.out.println(a[0]); //所得指定索引处的值
a[0]=10; //给指定索引的元素赋新值
System.out.println(a[0]);
}
}
外置
public class Test {
public static void main(String[] args) {
int[] a={5,4,1,2,4};
int count=0; //由于在循环体中的变量，每次都重置，放在外面就可起到记住的效果
for (int i = 0; i < a.length; i++) {
if(a[i]%2==0){
count++;
}
}
System.out.println(count);
}
}
这种外置的方式比如用于计数平均值最值
下面介绍另一种外置的算法，用于压缩字符串中的重复字符
public class Test4 {
private static String compress(String str) {
String mstr = "";
int count = 1;
char last = str.charAt(0); //这个外置起到了起头，记住的效果
for (int i = 1; i < str.length(); i++) {
if (last == str.charAt(i)) {
count++;
} else {
mstr = mstr + last + count;
count = 1; //外置的变量，可以根据需要重置
last = str.charAt(i);
}
}
return mstr + last + count;
}
public static void main(String[] args) {
String str = "aaabbc";
System.out.println(compress(str));
}
}
临时
public class Test2 {
// 一个非常基础的交换两个指定索引出元素的方法
private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) {
int[] a = { 5, 4, 1, 2, 3 };
swap(a, 0, 1);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
public class Test2 {
public static void main(String[] args) {
int[] a = { 5, 4, 1, 2, 3 };
//将一个数组赋值到一个临时数组
int[] temp=new int[a.length*2];
for (int i = 0; i < a.length; i++) {
temp[i]=a[i];
}
a=temp; //然原数组指向新扩容的数组
for (int i = 0; i < temp.length; i++) {
System.out.print(temp[i]+" ");
}
}
}
索引
public class Test2 {
private static void reverse(int[] a) {
//通过一个索引推论出另一个索引，实现数组元素的反转
for (int i = 0; i < a.length / 2; i++) {
int temp = a[i];
a[i] = a[a.length - 1 - i];
a[a.length - 1 - i] = temp;
}
}
public static void main(String[] args) {
int[] a = { 5, 4, 1, 2, 3 };
reverse(a);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
}
public class BinarySearch1 {
//根据值改变索引，多个索引，二分查找
private static int indexOf(int key, int[] a) {
int lo = 0;
int hi = a.length;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (key > a[mid]) {
lo = mid + 1;
} else if (key < a[mid]) {
hi = mid - 1;
} else {
return mid;
}
}
return -1;
}
public static void main(String[] args) {
int[] a = { 1, 2, 3, 4, 5 };
int key = 3;
System.out.println(BinarySearch1.indexOf(key, a));
}
}
循环
//冒泡排序，多层循环
public class BubbleSort {
private static void sort(int[] a) {
for (int i = 0; i < a.length; i++) {
for (int j = 1; j < a.length - i; j++) {
if (a[j - 1] > a[j]) {
int temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
}
}
}
}
public static void main(String[] args) {
int[] a = { 5, 3, 1, 2, 4 };
BubbleSort.sort(a);
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]+" ");
}
}
}
//逆序循环，数组元素复制，使一个url空格替换为%20
public class Test3 {
private static String replaceUrlSpace(String str, int trueLength) {
int sapceCount = 0;
for (int i = 0; i < trueLength; i++) {
if (str.charAt(i) == ' ') {
sapceCount++;
}
}
char[] a_str = str.toCharArray();
int newLength = trueLength + 2 * sapceCount;
for (int i = trueLength - 1; i >= 0; i--) {
char c = str.charAt(i);
if (c == ' ') {
a_str[newLength - 1] = '0';
a_str[newLength - 2] = '2';
a_str[newLength - 3] = '%';
newLength = newLength - 3;
} else {
a_str[newLength - 1] = c;
newLength--;
}
}
return String.valueOf(a_str);
}
public static void main(String[] args) {
String str = "bill jack ";
System.out.println(replaceUrlSpace(str, 9));
}
}
//一个矩阵转置算法，用于说明内层循环和外层循环的顺序
public class Ex13_alg {
public static void printTransposedMatrix(int[][] matrix) {
//外层循环遍历列索引
for (int i = 0; i < matrix[0].length; i++) {
//内层循环遍历行索引
for (int j = 0; j < matrix.length; j++) {
System.out.printf("%4d", matrix[j][i]); //根据列行索引获得元素
}
System.out.println();
}
}
public static void main(String[] args) {
int[][] a = { { 100, 200, 300 }, { 400, 500, 600 } };
printTransposedMatrix(a);
}
}
辅助数组
//字符串具的字符都是唯一的算法，布尔数组起到了唯一标记的作用
public class Test1 {
private static boolean isUniqueChar(String str) {
if (str.length() > 256) {
return false;
}
boolean[] char_set = new boolean[256]; //假设字符是ASCII码，然后利用这个辅助数组实现算法
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
if (char_set[val]) {
return false;
}
char_set[val] = true;
}
return true;
}
public static void main(String[] args) {
String str = "jack";
System.out.println(isUniqueChar(str));
}
}
//一个比较两个字符串具有的字符完全相同的算法，整数数组起到了字符计数的作用
public class Test2 {
private static boolean hasSameChar(String str1, String str2) {
if (str1.length() != str2.length()) {
return false;
}
int[] char_set = new int[256];
for (int i = 0; i < str1.length(); i++) {
int val = str1.charAt(i);
char_set[val]++;
}
for (int i = 0; i < str2.length(); i++) {
int val = str2.charAt(i);
if (--char_set[val] < 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String str1 = "bill";
String str2 = "jack";
System.out.println(hasSameChar(str1, str2));
}
}
数组这种数据结构看似简单，实际上有很多建立在其上的算法，上面的算法只冰山一角
Happy learning !!
网友评论