1. 除法（原題）

👨?🏫 實驗二：1.簡單枚舉
輸入正整數n，按從小到大的順序輸出所有形如abcde/fghij= n的表達式，其中a～j恰好為數字0～9的一個排列（可以有前導0），2≤n≤79。

樣例輸入：

62

樣例輸出：

79546 / 01283 = 62

💖 Main1.java

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;//文件名：Main1.javapublic class Main1
{static int n;static Set<Integer> set = new HashSet<>();// 用于數字去重public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();for (int i = 1234; i < 100000; i++){if (repeat(i))continue;int y = cal(i);if (y != -1){System.out.print(y + "/");System.out.printf("%05d", i);System.out.println(" = " + n);}set.clear();}}/*** * @param x* @return 返回 x 對應的 x*n，非法值則返回 -1*/private static int cal(int x){int y = x * n;if (value(y))return y;return -1;}//返回 y 是否為有效值private static boolean value(int y){if (y < 10000 || y >= 100000)return false;Set<Integer> tmpSet = new HashSet<>();while (y != 0){int t = y % 10;if (tmpSet.contains(t) || set.contains(t))return false;tmpSet.add(t);y /= 10;}return true;}//返回 x 的每一位是否有重復的數字，有則返回 trueprivate static boolean repeat(int x){if ((x + "").length() == 4)x *= 10;while (x != 0){int t = x % 10;if (set.contains(t)){set.clear();return true;}set.add(t);x /= 10;}return false;}
}

2. 求逆序對（原題）

👨?🏫 實驗七：4. 求逆序對

輸入一個序列{a1, a2, a3,…, an}，交換任意兩個相鄰元素，不超過k次。交換之后，問最少的逆序對有多少個。

序列中的一個逆序對，是指存在兩個數ai和aj，有ai > aj且1≤i<j≤n。也就是說，大的數排在小的數前面。

輸入：第一行是n和k，1 ≤ n ≤ 105，0 ≤ k ≤ 109；第二行包括n個整數{a1, a2, a3,…, an}，0≤ ai ≤109。

輸出：最少的逆序對數量。

Sample Input：

3 1
2 2 1

Sample Output：

1

💖 Main2.java

import java.util.Scanner;public class Main2
{static int N = 100010;static int[] q = new int[N], tmp = new int[N];public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();for (int i = 0; i < n; i++)q[i] = sc.nextInt();long cnt = mergeSort(0, n - 1);System.out.println(Math.max(0, cnt - k));}/*** @param l 區間左邊界* @param r 區間右邊界* @return long 類型的區間內的逆序對*/private static long mergeSort(int l, int r){if (l >= r)return 0;int mid = l + r >> 1;long res = mergeSort(l, mid) + mergeSort(mid + 1, r);int k = 0;// 臨時數組指針int i = l;// 左區間指針int j = mid + 1;// 右區間指針while (i <= mid && j <= r){if (q[i] <= q[j])// 無逆序對tmp[k++] = q[i++];else{tmp[k++] = q[j++];res += mid - i + 1;}}if (i <= mid)tmp[k++] = q[i++];if (j <= r)tmp[k++] = q[j++];for (i = l, j = 0; i <= r; i++, j++){q[i] = tmp[j];}return res;}
}

3. 求最大子段和（分治法）

👨?🏫 力扣題解：53.最大子數組和

給出一個長度為 n的序列 a，選出其中連續且非空的一段使得這段和最大。

輸入格式
第一行是一個整數，表示序列的長度 n。

第二行有 n 個整數，第 i 個整數表示序列的第 i個數字 ai。

輸出格式
輸出一行一個整數表示答案。

輸入

7
2 -4 3 -1 2 -4 3

輸出

4

💖 源代碼

import java.util.Scanner;public class Main3
{public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] nums = new int[n];for (int i = 0; i < n; i++)nums[i] = sc.nextInt();int ans = maxSubArray(nums);System.out.println(ans);}public static int maxSubArray(int[] nums){int len = nums.length;if (len == 0){return 0;}return maxSubArraySum(nums, 0, len - 1);}private static int maxCrossingSum(int[] nums, int left, int mid, int right){// 一定會包含 nums[mid] 這個元素int sum = 0;int leftSum = Integer.MIN_VALUE;// 左半邊包含 nums[mid] 元素，最多可以到什么地方// 走到最邊界，看看最值是什么// 計算以 mid 結尾的最大的子數組的和for (int i = mid; i >= left; i--){sum += nums[i];if (sum > leftSum){leftSum = sum;}}sum = 0;int rightSum = Integer.MIN_VALUE;// 右半邊不包含 nums[mid] 元素，最多可以到什么地方// 計算以 mid+1 開始的最大的子數組的和for (int i = mid + 1; i <= right; i++){sum += nums[i];if (sum > rightSum){rightSum = sum;}}return leftSum + rightSum;}private static int maxSubArraySum(int[] nums, int left, int right){if (left == right){return nums[left];}int mid = left + (right - left) / 2;return max3(maxSubArraySum(nums, left, mid), maxSubArraySum(nums, mid + 1, right),maxCrossingSum(nums, left, mid, right));}private static int max3(int num1, int num2, int num3){return Math.max(num1, Math.max(num2, num3));}
}