算法刷题总结

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> {

    @Override
    public 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^2
        list.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> {

    @Override
    public 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> {

    @Override
    public 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> {

    @Override
    public 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> {

    @Override
    public 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));
    }
}

1.6 直接插入排序

public class InsertSort{
     
    public static void insertSort(int[] array){//直接插入排序
        
    	for(int i=1;i<array.length;i++){
    		if(array[i]<array[i-1]){
    			int temp=array[i];
    			int k=i-1;
    			for(int j=k;temp<array[j] && j>=0;j--){
    				array[j+1]=array[j];
    				k--;
    			}
    			array[k+1]=temp;
    		}
    	}
    }
     
    public static void printArray(int[] array) {//打印
         for(int i=0;i<array.length;i++){
        	 System.out.print(array[i]);
        	 if(i!=array.length-1){
        		 System.out.print(" ");
        	 }
         }
     }
 
    public static void main(String[] args) {
		//{05, 56, 13, 88，19, 37, 64,75,80, 21,92}（用数组存放）
    	int[] a={05, 56, 13, 88,19, 37, 64,75,80, 21,92};
    	System.out.println("排序前的序列:");
    	printArray(a);
    	insertSort(a);
    	System.out.println("\n排序后的序列:");
    	printArray(a);
    	
	}
}

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);
				else
					display.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 += 1
    q_num += 1
elif x + (x + 10) + (x + 20) >= need_other:
    p_num += 1
    q_num += 1
    z_num += 1

print(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;
		else
			return s[x] = find(s[x]);
	}

	public static void union(int root1, int root2) {// 按大小求并
		if (root1 > root2) {
			s[root2] = root1;
		} else
			s[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;
			else
				return 0;
		}
	}
}

6. A除以B

题目描述
本题要求计算A/B，其中A是不超过1000位的正整数，B是1位正整数。你需要输出商数Q和余数R，使得A = B * Q + R成立。
输入描述:
输入在1行中依次给出A和B，中间以1空格分隔。
输出描述:
在1行中依次输出Q和R，中间以1空格分隔。
输入例子:
123456789050987654321 7
输出例子:
17636684150141093474 3

public class Main{
     
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        BigInteger bi=new BigInteger(in.next());
        BigInteger a=new BigInteger(in.next());
        System.out.print(bi.divide(a)+" ");
        System.out.println(bi.mod(a));
    }
}

7. 部分A+B

题目描述
正整数A的“DA（为1位整数）部分”定义为由A中所有DA组成的新整数PA。例如：给定A = 3862767，DA = 6，则A的“6部分”PA是66，因为A中有2个6。
现给定A、DA、B、DB，请编写程序计算PA + PB。
输入描述:
输入在一行中依次给出A、DA、B、DB，中间以空格分隔，其中0 < A, B < 1010。
输出描述:
在一行中输出PA + PB的值。
输入例子:
3862767 6 13530293 3
输出例子:
399

public class Main {
  
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        char[] a=in.next().toCharArray();
        int sum=cal(a,in.nextInt());
         
        char[] b=in.next().toCharArray();
        sum+=cal(b,in.nextInt());
         
        System.out.println(sum);
    }
 
    private static int cal(char[] c,int aim) {
        int sum=0;
        for(int i=0;i<c.length;i++){
            if(c[i]-'0' == aim){
                sum=sum*10+aim;
            }
        }
        return sum;
    }
}

8. A+B和C

给定区间[-2^31, 2^31]内的3个整数A、B和C，请判断A+B是否大于C。
输入描述:
输入第1行给出正整数T(<=10)，是测试用例的个数。随后给出T组测试用例，每组占一行，顺序给出A、B和C。整数间以空格分隔。
输出描述:
对每组测试用例，在一行中输出“Case #X: true”如果A+B>C，否则输出“Case #X: false”，其中X是测试用例的编号（从1开始）。
输入例子:
4
1 2 3
2 3 4
2147483647 0 2147483646
0 -2147483648 -2147483647
输出例子:
Case #1: false
Case #2: true
Case #3: true
Case #4: false

public class Main{
        public static void main(String[] args) {
          Scanner in=new Scanner(System.in);
          int n=in.nextInt();
          for(int i=1;i<=n;i++){
               BigInteger a,b,c;
               a=in.nextBigInteger();
               b=in.nextBigInteger();
               c=in.nextBigInteger();
               if(a.add(b).compareTo(c)>0){
                   System.out.println("Case #"+i+": true");
               }else{
                   System.out.println("Case #"+i+": false");
               }
        }
    }
}
```

欢迎关注公众号算法小生与我沟通交流