算法刷题总结

1. 排序算法

1.1 快速排序算法

public abstract class Sort<T extends Comparable<T>> {public abstract void sort(T[] array);protected boolean less(T first, T two) {return first.compareTo(two) < 0;}protected void swap(T[] array, int i, int j) {T temp = array[i];array[i] = array[j];array[j] = temp;}
}

/*** 快速排序** 快速排序通过一个切分元素将数组分为左右两个数组，* 左数组元素小于等于切分元素，右数组大于等于切分元素，* 将左右子数组排序，整个数组也就有序了** 平均情况为O(nlog(n)),最差情况O(n~2),存储空间O(log(n))* V1.1.0 sort、partition写法参照<<程序员面试金典>>重写**/
public class QuitSort<T extends Comparable<T>> extends Sort<T> {@Overridepublic void sort(@NotNull T[] arr) {shuffle(arr);sort(arr, 0 , arr.length - 1);}private void sort(T[] arr, int left, int right) {int index = partition(arr, left, right);if (left < index - 1) { // 排序左半部分sort(arr, left, index - 1);}if (index < right) { // 排序右半部分sort(arr, index, right);}}private int partition(T[] arr, int left, int right) {T pivot = arr[(left + right) / 2]; // 挑选一个基准点while (left <= right) {// 找到左边应被放到右边的元素while (arr[left].compareTo(pivot) < 0) {left++;}// 找到右边应被放到左边的元素while (arr[right].compareTo(pivot) > 0) {right--;}if (left <= right) {swap(arr, left, right); // 交换元素left++;right--;}}return left;}private void shuffle(T[] arr) {List<Comparable> list = Arrays.asList(arr);Collections.shuffle(list); // 防止最坏的情况，第一次从最小的元素切分，第二次从次小的元素切分。时间复杂度N^2list.toArray(arr);}public static void main(String[] args) {Sort sort = new QuitSort();Integer[] arr = new Integer[]{2, 1, 4, 6, 3, 7, 3};sort.sort(arr);System.out.println(Arrays.asList(arr));}
}

1.2 归并排序

/*** 归并排序** @author Jian Shen* @version V1.0.0* @date 2019/7/21*/
public abstract class MergeSort<T extends Comparable<T>> extends Sort<T> {protected T[] assist; // 辅助数组/*** 将数组中已经排好序的两个部分[左侧部分、右侧部分]合并** @param array* @param left* @param middle* @param right*/protected void merge(@NotNull T[] array, int left, int middle, int right) {int i = left;int j = middle + 1;for (int k = left; k <= right; k++) {assist[k] = array[k];}for (int k = left; k <= right; k++) {if (i > middle) { // 说明左侧部分已经完成合并，仅需合并右侧部分array[k] = assist[j++];} else if (j > right) { // 说明右侧部分已经完成合并，仅需合并左侧部分array[k] = assist[i++];} else if (assist[i].compareTo(assist[j]) <= 0) {array[k] = assist[i++];} else {array[k] = assist[j++];}}}
}

/*** 自顶向下归并排序** 将数组分成两个部分，分别进行排序，然后归并起来* 这种对半分的复杂度为O(NlogN)** @author Jian Shen* @version V1.0.0* @date 2019/7/21*/
public class Up2DownMergeSort<T extends Comparable<T>> extends MergeSort<T> {@Overridepublic void sort(T[] array) {assist = (T[]) new Comparable[array.length];sort(array, 0, array.length - 1);}private void sort(T[] array, int left, int right) {if (left >= right) {return ;}int middle = left + (right - left) / 2;sort(array, left, middle);sort(array, middle + 1, right);merge(array, left, middle, right);}public static void main(String[] args) {Sort sort = new Up2DownMergeSort();Integer[] array = new Integer[]{1, 3, 2, 4, 4, 9, 10, 3, 3};sort.sort(array);System.out.println(Arrays.asList(array));}
}

1.3 插入排序

/*** 插入排序** 每次将当前元素插入到左侧已经排序的数组中，插入之后左侧数组依然有序。* 对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，* 插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量** @author Jian Shen* @version V1.0.0* @date 2019/7/20*/
public class InsertSort<T extends Comparable<T>> extends Sort<T> {@Overridepublic void sort(T[] array) {int length = array.length;for (int i = 1; i < length; i++) {for (int j = i; j > 0; j--) {if (less(array[j], array[j - 1])) {swap(array, j, j -1);}}}}public static void main(String[] args) {Sort sort = new InsertSort();Integer[] array = new Integer[]{3, 5, 2, 4, 1, 1};sort.sort(array);System.out.println(Arrays.asList(array));}
}

1.4 冒泡排序

/*** 冒泡排序* * 从左到右不断交换相邻逆序的元素，在一轮循环后，可以让未排序的最大元素上浮至最右侧* 在一轮循环中，如果没有发生交换，则说明此时数组已经有序，可以直接退出** @author Jian Shen* @version V1.0.0* @date 2019/7/20*/
public class BubbleSort<T extends Comparable<T>> extends Sort<T> {@Overridepublic void sort(@NotNull T[] array) {int length = array.length;boolean sorted = false;for (int i = length - 1; i > 0 && !sorted; i--) {sorted = true;for (int j = 0; j < i; j++) {if (less(array[j + 1], array[j])) {sorted = false;swap(array, j, j + 1);}}}}public static void main(String[] args) {Sort sort = new BubbleSort();Integer[] array = new Integer[]{1, 3, 2, 4, 4, 9, 10, 3};sort.sort(array);System.out.println(Arrays.asList(array));}
}

1.5 希尔排序

/*** 希尔排序** 对于大规模的数组，插入排序很慢，因为每次只能将逆序数量减1，* 希尔排序交换不相邻的元素，每次可以将逆序数量减少大于1* 希尔排序使用插入排序对间隔h的序列进行排序，通过不断减小h至1，就可以使得数组是有序的** @author Jian Shen* @version V1.0.0* @date 2019/7/21*/
public class ShellSort<T extends Comparable<T>> extends Sort<T> {@Overridepublic void sort(@NotNull T[] array) {int length = array.length;int h = 1;while (h < length / 3) {h = 3 * h + 1;}while (h >= 1) {for (int i = h; i < length; i++) {for (int j = i; j >= h; j -= h) {if (less(array[j], array[j - h])) {swap(array, j, j - h);}}}h /= 3;}}public static void main(String[] args) {Sort sort = new ShellSort();Integer[] array = new Integer[]{3, 5, 3, 4, 1, 1};sort.sort(array);System.out.println(Arrays.asList(array));}
}

2. 当月日历打印

import java.util.*;public class CalendarStudy {public static void main(String[] args) {printCurrentMonthCalendar();}private static void printCurrentMonthCalendar() {/* 1.获取当前日期 月与日信息* 2.获取当前月 第一天信息(如第一天为星期几)* 3.循环开始打印，格式控制，结束条件日期不为当前月*/Calendar date = new GregorianCalendar();int nowMonth = date.get(Calendar.MONTH);int nowDay = date.get(Calendar.DAY_OF_MONTH);date.set(Calendar.DAY_OF_MONTH, 1);int firstWeekday = date.get(Calendar.DAY_OF_WEEK); // 当前月第一天为星期几System.out.println("星期日 星期一 星期二 星期三 星期四 星期五 星期六");for (int i = Calendar.SUNDAY; i < firstWeekday; i++) {System.out.printf("%7s", " ");}while (date.get(Calendar.MONTH) == nowMonth) {int day = date.get(Calendar.DAY_OF_MONTH);int weekDay = date.get(Calendar.DAY_OF_WEEK);System.out.printf("%6d", day);if (day != nowDay) {System.out.print(" ");} else {System.out.print("*");}if (weekDay == Calendar.SATURDAY) {System.out.println();}date.add(Calendar.DAY_OF_MONTH, 1);}}
}

这里写图片描述

3. 简单计算器实现

基本思路:边输入边计算，最后显示

import java.awt.BorderLayout;
import java.awt.Button;
import java.awt.GridLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;import javafx.scene.layout.Border;import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;public class Calculator extends JFrame {private boolean start, flag;private String lastCommand;private double result1, result2;private int count=1;JButton display;JPanel panel;public Calculator() {setLayout(new BorderLayout());result1 = 0;result2 = 0;start = true;flag = false;lastCommand = "=";display = new JButton(" ");display.setEnabled(false);add(display, BorderLayout.NORTH);ActionListener insert = new InsertAction();ActionListener command = new CommandListener();panel = new JPanel(new GridLayout(4, 4));addButton("7", insert);addButton("8", insert);addButton("9", insert);addButton("/", command);addButton("4", insert);addButton("5", insert);addButton("6", insert);addButton("*", command);addButton("1", insert);addButton("2", insert);addButton("3", insert);addButton("-", command);addButton("0", insert);addButton(".", insert);addButton("=", command);addButton("+", command);add(panel, BorderLayout.CENTER);pack();setTitle("Calculator");setResizable(false);setSize(300, 200);setLocation(400, 400);setVisible(true);setDefaultCloseOperation(this.EXIT_ON_CLOSE);}private void addButton(String label, ActionListener listener) {Button button = new Button(label);button.addActionListener(listener);panel.add(button);}private class InsertAction implements ActionListener {// 监听数字按钮public void actionPerformed(ActionEvent e) {String input = e.getActionCommand();display.setText(display.getText() + input);}}private class CommandListener implements ActionListener {// 监听命令按钮public void actionPerformed(ActionEvent e) {String command = e.getActionCommand();if (flag) {String[] s;s = display.getText().split("\\" + lastCommand);result2 = Double.parseDouble(s[s.length-1]);System.out.println(result2);calculator();if (command.equals("="))display.setText("" + result1);elsedisplay.setText(display.getText() + command);lastCommand = command;//flag = false;} else {result1 = Double.parseDouble(display.getText());display.setText(display.getText() + command);lastCommand = command;flag = true;}}}public void calculator() {// 进行计算的函数if (lastCommand.equals("+")) {result1 += result2;} else if (lastCommand.equals("-")) {result1 -= result2;} else if (lastCommand.equals("*")) {result1 *= result2;} else if (lastCommand.equals("/")) {result1 /= result2;} else if (lastCommand.equals("=")) {result1 = result2;}}public static void main(String[] args) {new Calculator();}
}

这里写图片描述

4. 拉格朗日乘数法在原材料选择问题上的具体应用

问题需求：
输入待制作的材料：(材料长，材料数量)
分别为(5401，124)、（200，135）、（1350，45），
输入原材料长度最大值6500，最小值3500，浮动间隙10(即步长)，可选种类3
求需要多少原材料，数量分别为多少
备注：原材料可以分割也可以合并，可以想象为黄金

求解：这是一个带有约束条件的拉格朗日乘数法求解最优值的问题，我们直接上代码

from scipy.optimize import minimize
import numpy as np# 由于x[0]*x[1]+(x[0]+10)*x[2]+(x[0]+20)*x[3])是凸函数，所以必定存在全局最优,证明略from scipy.optimize import minimize
import numpy as np
fun = lambda x: (x[0])
# 限制条件 eq等于 ineq大于等于
cons = ({'type': 'eq', 'fun': lambda x: (x[0]*x[1]+(x[0]+10)*x[2]+(x[0]+20)*x[3]) - (5401*124+200*135+1350*45)},{'type': 'ineq', 'fun': lambda x: (x[0] - 3500)},{'type': 'ineq', 'fun': lambda x:  (6500 - (x[0]+20))},{'type': 'ineq', 'fun': lambda x: (x[1] - 1)},{'type': 'ineq', 'fun': lambda x: (x[2] - 1)},{'type': 'ineq','fun': lambda x: (x[3] - 1)})
# 代表四个变量的初始值
x0 = np.array((6500, 1, 1, 1)) # 设置初始值 
# 限制变量范围
bounds = ((3500,6500),(1,None),(1,None),(1,None))
res = minimize(fun, x0, method='SLSQP', constraints=cons, bounds=bounds)
print('最大值：',res.fun)
print('最优解：',res.x)
print('迭代终止是否成功：', res.success)
print('迭代终止原因：', res.message)

最大值： 3500.0
最优解： [3500. 71.82289948 71.93464057 72.04638166]
迭代终止是否成功： True
迭代终止原因： Optimization terminated successfully

total_info = (5401*124+200*135+1350*45)
x = round(res.fun, 0)
now_info = x * int(res.x[1]) + (x+10)*int(res.x[2]) + (x+20) * int(res.x[3])
need_other = total_info - now_info
p_num = int(res.x[1])
q_num = int(res.x[2])
z_num = int(res.x[3])# 由于int取整并且步长远小于原材料长度
# 所以可直接从最小向上依次选
if x >= need_other:p_num += 1
elif x + (x + 10) >= need_other:p_num += 1q_num += 1
elif x + (x + 10) + (x + 20) >= need_other:p_num += 1q_num += 1z_num += 1print(str(int(x)) + ' ' + str(p_num))
print(str(int(x+10)) + ' ' + str(q_num))
print(str(int(x+20)) + ' ' + str(z_num))
print('多买的原材料长度' + " " + str(int((x * p_num + (x+10) * q_num + (x+20) * z_num) - total_info)))

3500 72
3510 72
3520 72
多买的原材料长度 686

5. 最小生成树之安慰奶牛

问题描述
Farmer John变得非常懒，他不想再继续维护供奶牛之间供通行的道路。道路被用来连接N个牧场，牧场被连续地编号为1到N。每一个牧场都是一个奶牛的家。FJ计划除去P条道路中尽可能多的道路，但是还要保持牧场之间的连通性。你首先要决定那些道路是需要保留的N-1条道路。第j条双向道路连接了牧场Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj != Ej)，而且走完它需要Lj的时间。没有两个牧场是被一条以上的道路所连接。奶牛们非常伤心，因为她们的交通系统被削减了。你需要到每一个奶牛的住处去安慰她们。每次你到达第i个牧场的时候(即使你已经到过)，你必须花去Ci的时间和奶牛交谈。你每个晚上都会在同一个牧场(这是供你选择的)过夜，直到奶牛们都从悲伤中缓过神来。在早上起来和晚上回去睡觉的时候，你都需要和在你睡觉的牧场的奶牛交谈一次。这样你才能完成你的交谈任务。假设Farmer John采纳了你的建议，请计算出使所有奶牛都被安慰的最少时间。

输入格式

第1行包含两个整数N和P。
接下来N行，每行包含一个整数Ci。
接下来P行，每行包含三个整数Sj, Ej和Lj。

输出格式

输出一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间)

样例输入

样例输出

数据规模与约定

5 <= N <= 10000，N-1 <= P <= 100000，0 <= Lj <= 1000，1 <= Ci <= 1,000

5.1 代码

import java.util.PriorityQueue;
import java.util.Scanner;public class Main {static int[] s;static int[] a;static int n;static int m;static int ans = 1001;static Scanner in;static Edge edge;public Main() {// 构造函数初始化in = new Scanner(System.in);n=in.nextInt();m=in.nextInt();s = new int[n + 1];a = new int[n + 1];}public static int find(int x) {// 采用路径压缩的find()if (s[x] == -1)return x;elsereturn s[x] = find(s[x]);}public static void union(int root1, int root2) {// 按大小求并if (root1 > root2) {s[root2] = root1;} elses[root1] = root2;}public static void kruskal() {// 克鲁斯卡尔int edgesAccepted = 0;PriorityQueue<Edge> pq = new PriorityQueue<Edge>();for (int i = 1; i <= m; i++) {int u = in.nextInt(), v = in.nextInt(), w = in.nextInt();w = 2 * w + a[u] + a[v];edge = new Edge(u, v, w);pq.add(edge);}while(edgesAccepted<n-1){Edge edgeTemp=pq.poll();int x=find(edgeTemp.u);int y=find(edgeTemp.v);if(x!=y){ans+=edgeTemp.w;		edgesAccepted++;union(x,y);}}}public static void main(String[] args) {new Main();for (int i = 1; i <= n; i++)s[i] = -1;for (int i = 1; i <= n; i++) {a[i] = in.nextInt();if (a[i] < ans)ans = a[i];}kruskal();System.out.println(ans);}public static class Edge implements Comparable<Edge> {// 自定义比较类private int u, v, w;public Edge(int u, int v, int w) {this.u = u;this.v = v;this.w = w;}public int compareTo(Edge o) {if (this.w > o.w)return 1;else if (this.w < o.w)return -1;elsereturn 0;}}
}