【数据结构与算法经典问题解析--java语言描述】_第21章_学习记录
【数据结构与算法经典问题解析--java语言描述】_第21章_学习记录
問題1： 設計一個算法，安照螺旋順序依次輸出矩陣中的元素;
package p21;
import java.util.ArrayList;
import java.util.List;
/**
* 問題1： 設計一個算法，安照螺旋順序依次輸出矩陣中的元素;
* @author Guozhu Zhu
* @date 2018/10/3
* @version 1.0
*
*/
public class Demo01 {
public static void main(String[] args) {
int[][] matrix ={{0, 0, 0, 0},
{3, 4, 4, 1},
{3, 6, 5, 1},
{2, 2, 2, 1}};
List<Integer> resList = Spiral(matrix, 4, 4);
for (int i : resList) {
System.out.println(i);
}
}
//算法實現, 時間複雜度O(n) = n^2, 空間複雜度O(n) = 1;
public static List<Integer> Spiral(int[][] matrix, int m, int n) {
List<Integer> resList = new ArrayList<Integer>();
int xStart = 0;
int yStart = 0;
int xEnd = n-1;
int yEnd = m-1;
while (xStart <= xEnd && yStart <= yEnd) {
//left --> right;
for (int i = xStart; i <= xEnd; i++) {
resList.add(matrix[yStart][i]);
}
//up --> down
if (yEnd > yStart) {
for (int i = yStart+1; i <= yEnd; i++) {
resList.add(matrix[i][xEnd]);
}
}
//right --> left
if (yEnd > yStart && xStart < xEnd) {
for (int i = xEnd-1; i >= xStart; i--) {
resList.add(matrix[yEnd][i]);
}
}
//down --> up
if (yEnd > yStart+1 && xStart < xEnd) {
for (int i = yEnd-1; i >= yStart+1; i--) {
resList.add(matrix[i][xStart]);
}
}
xStart++;
xEnd--;
yStart++;
yEnd--;
}
return resList;
}
}
問題2： 基於反轉算法的數組旋轉問題。設計一個函數rotate(A[], d, n), 該函數將大小為n的數組旋轉d個元素。e.g, 數組1， 2， 3， 4， 5， 6， 7在經過2 個元素的旋轉后變為3, 4, 5, 6, 7, 1, 2;
package p21;
/**
* 問題2： 基於反轉算法的數組旋轉問題。設計一個函數rotate(A[], d, n), 該
* 函數將大小為n的數組旋轉d個元素。e.g, 數組1， 2， 3， 4， 5， 6， 7在經過2
* 個元素的旋轉后變為3, 4, 5, 6, 7, 1, 2;
* @author Guozhu Zhu
* @date 2018/10/3
* @version 1.0
*
*/
public class Demo03 {
/* ========== Test ========== */
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
rotate(arr, 2, 7);
for (int i : arr) {
System.out.print(i+",");
}
}
public static void rotate(int[] arr, int d, int n) {
reverse(arr, 0, d-1);
reverse(arr, d, n-1);
reverse(arr, 0, n-1);
}
public static void reverse(int[] arr, int start, int end) {
while (start < end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
}
問題3：字符串由詞和空格組成，設計一個程序將字符串中所有空格移動到字符串的最前面，要求僅遍歷數組一次，并且在原字符串中進行調整；
package p21;
/**
* 問題3：字符串由詞和空格組成，設計一個程序將字符串中所有空格移動到字符串的最
* 前面，要求僅遍歷數組一次，并且在原字符串中進行調整；
* @author Guozhu Zhu
* @date 2018/10/3
* @version 1.0
*
*/
public class Demo04 {
/* ========== Test ========== */
public static void main(String[] args) {
String str = "Hello World !!!";
String resStr = moveSpaceToBegin(str);
System.out.println(resStr);
}
public static String moveSpaceToBegin(String str) {
char[] ch = str.toCharArray();
int j = ch.length-1;
for (int i = ch.length-1; i >= 0; i--) {
if (ch[i] != ' ') {
ch[j--] = ch[i];
}
}
for (int k = 0; k <= j; k++) {
ch[k] = ' ';
}
return String.valueOf(ch);
}
}
問題4：設計一個程序將所有空格移動到字符串的末尾，要求僅遍歷數組一次，並且在原字符串中進行調整；
package p21;
/**
* 問題4：設計一個程序將所有空格移動到字符串的末尾，要求僅遍歷數組一次，並且在原字符串中進行調整；
* @author Guozhu Zhu
* @date 2018/10/3
* @version 1.0
*
*/
public class Demo05 {
/* ========== Test ========== */
public static void main(String[] args) {
String str = "Hello World !!!";
String resStr = moveSpaceToEnd(str);
System.out.println(resStr);
}
public static String moveSpaceToEnd(String str) {
char[] ch = str.toCharArray();
int j = 0;
for (int i = 0; i < ch.length; i++) {
if (ch[i] != ' ' ) {
ch[j++] = ch[i];
}
}
for (int k = j; k < ch.length; k++) {
ch[k] = ' ';
}
return String.valueOf(ch);
}
}
問題5：移動0到末尾；
package p21;
/**
* 問題5：移動0到末尾；
* @author Guozhu Zhu
* @date 2018/10/3
* @version 1.0
*
*/
public class Demo06 {
/* ========== Test ========== */
public static void main(String[] args) {
int[] arr = {1, 2, 0, 0, 3, 4, 0, 5};
moveZeroToEnd(arr);
for (int i : arr) {
System.out.print(i);
}
}
//雙指針的算法實現， 時間O(n)=n, 空間O(n)=1;
public static void moveZeroToEnd(int[] arr) {
int j = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 0) {
arr[j++] = arr[i];
}
}
for (int k = j; k < arr.length; k++) {
arr[k] = 0;
}
}
}
問題6：設計一個算法將正數和負數分開，要求正數和負數的相對順序保持不變
package p21;
/**
* 問題6：設計一個算法將正數和負數分開，要求正數和負數的相對順序保持不變
* @author Guozhu Zhu
* @date 2018/10/3
* @version 1.0
*
*/
public class Demo07 {
/* ========== Test ========== */
public static void main(String[] args) {
int[] arr = {1, 2, -1, 3, 4, -2, 5, -3};
solution(arr);
for (int i : arr) {
System.out.println(i);
}
}
public static void solution(int[] arr) {
int i, j;
for (i = 0, j = 0; i < arr.length; i++) {
if (arr[i] < 0) {
swap(arr, j++, i);
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}