算法学习class3

于 2021-12-14 20:32:27 发布
阅读量100 收藏
点赞数
分类专栏： 算法 文章标签： 算法 数据结构 蓝桥杯
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/cxy_jzli/article/details/121939324
版权 
package class02;

public class Code01_PreSum {

	public static class RangeSum1 {

		private int[] arr;

		public RangeSum1(int[] array) {
			arr = array;
		}

		public int rangeSum(int L, int R) {
			int sum = 0;
			for (int i = L; i <= R; i++) {
				sum += arr[i];
			}
			return sum;
		}

	}

	public static class RangeSum2 {

		private int[] preSum;

		public RangeSum2(int[] array) {
			int N = array.length;
			preSum = new int[N];
			preSum[0] = array[0];
			for (int i = 1; i < N; i++) {
				preSum[i] = preSum[i - 1] + array[i];
			}
		}

		public int rangeSum(int L, int R) {
			return L == 0 ? preSum[R] : preSum[R] - preSum[L - 1];
		}

	}

}

package class02;

public class Code02_RandToRand {

	// 此函数只能用，不能修改
	// 等概率返回1~5
	public static int f() {
		return (int) (Math.random() * 5) + 1;
	}

	// 等概率得到0和1
	public static int a() {
		int ans = 0;
		do {
			ans = f();
		} while (ans == 3);
		return ans < 3 ? 0 : 1;
	}

	// 等概率返回0~6
	public static int b() {
		int ans = 0;
		do {
			ans = (a() << 2) + (a() << 1) + a();
		} while (ans == 7);
		return ans;
	}

	// 等概率返回1~7
	public static int c() {
		return b() + 1;
	}

	// 这个结构是唯一的随机机制
	// 你只能初始化并使用，不可修改
	public static class RandomBox {
		private final int min;
		private final int max;

		// 初始化时请一定不要让mi==ma
		public RandomBox(int mi, int ma) {
			min = mi;
			max = ma;
		}

		// 13 ~ 17
		// 13 + [0,4]
		public int random() {
			return min + (int) (Math.random() * (max - min + 1));
		}

		public int min() {
			return min;
		}

		public int max() {
			return max;
		}
	}

	// 利用条件RandomBox，如何等概率返回0和1
	public static int rand01(RandomBox randomBox) {
		int min = randomBox.min();
		int max = randomBox.max();
		// min ~ max
		int size = max - min + 1;
		// size是不是奇数，odd 奇数
		boolean odd = (size & 1) != 0;
		int mid = size / 2;
		int ans = 0;
		do {
			ans = randomBox.random() - min;
		} while (odd && ans == mid);
		return ans < mid ? 0 : 1;
	}

	// 给你一个RandomBox，这是唯一能借助的随机机制
	// 等概率返回from~to范围上任何一个数
	// 要求from<=to
	public static int random(RandomBox randomBox, int from, int to) {
		if (from == to) {
			return from;
		}
		// 3 ~ 9
		// 0 ~ 6
		// 0 ~ range
		int range = to - from;
		int num = 1;
		// 求0～range需要几个2进制位
		while ((1 << num) - 1 < range) {
			num++;
		}

		// 我们一共需要num位
		// 最终的累加和，首先+0位上是1还是0，1位上是1还是0，2位上是1还是0...
		int ans = 0;
		do {
			ans = 0;
			for (int i = 0; i < num; i++) {
				ans |= (rand01(randomBox) << i);
			}
		} while (ans > range);
		return ans + from;
	}

	public static void main(String[] args) {
		System.out.println("测试开始");
		// Math.random() -> double -> [0,1)
		//

		int testTimes = 10000000;
		int count = 0;
		for (int i = 0; i < testTimes; i++) {
			if (Math.random() < 0.75) {
				count++;
			}
		}
		System.out.println((double) count / (double) testTimes);

		System.out.println("=========");

		// [0,1) -> [0,8)
		count = 0;
		for (int i = 0; i < testTimes; i++) {
			if (Math.random() * 8 < 5) {
				count++;
			}
		}
		System.out.println((double) count / (double) testTimes);
		System.out.println((double) 5 / (double) 8);

		int K = 9;
		// [0,K) -> [0,8]

		int[] counts = new int[9];
		for (int i = 0; i < testTimes; i++) {
			int ans = (int) (Math.random() * K); // [0,K-1]
			counts[ans]++;
		}
		for (int i = 0; i < K; i++) {
			System.out.println(i + "这个数，出现了 " + counts[i] + " 次");
		}

		System.out.println("=========");

		count = 0;
		double x = 0.17;
		for (int i = 0; i < testTimes; i++) {
			if (xToXPower2() < x) {
				count++;
			}
		}
		System.out.println((double) count / (double) testTimes);
		System.out.println((double) 1 - Math.pow((double) 1 - x, 2));

		System.out.println("==========");
		count = 0;
		for (int i = 0; i < testTimes; i++) {
			if (f2() == 0) {
				count++;
			}
		}
		System.out.println((double) count / (double) testTimes);

		System.out.println("==========");

		counts = new int[8];
		for (int i = 0; i < testTimes; i++) {
			int num = g();
			counts[num]++;
		}
		for (int i = 0; i < 8; i++) {
			System.out.println(i + "这个数，出现了 " + counts[i] + " 次");
		}

	}

	// 返回[0,1)的一个小数
	// 任意的x，x属于[0,1)，[0,x)范围上的数出现概率由原来的x调整成x平方
	public static double xToXPower2() {
		return Math.min(Math.random(), Math.random());
	}

	// lib里的，不能改！
	public static int f1() {
		return (int) (Math.random() * 5) + 1;
	}

	// 随机机制，只能用f1，
	// 等概率返回0和1
	public static int f2() {
		int ans = 0;
		do {
			ans = f1();
		} while (ans == 3);
		return ans < 3 ? 0 : 1;
	}

	// 得到000 ~ 111 做到等概率 0 ~ 7等概率返回一个
	public static int f3() {
		return (f2() << 2) + (f2() << 1) + f2();
	}

	// 0 ~ 6等概率返回一个
	public static int f4() {
		int ans = 0;
		do {
			ans = f3();
		} while (ans == 7);
		return ans;
	}

	public static int g() {
		return f4() + 1;
	}

	// 你只能知道，x会以固定概率返回0和1，但是x的内容，你看不到！
	public static int x() {
		return Math.random() < 0.84 ? 0 : 1;
	}

	// 等概率返回0和1
	public static int y() {
		int ans = 0;
		do {
			ans = x();
		} while (ans == x());
		return ans;
	}

}

package class02;

public class Code03_Comp {

	public static void selectionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 0; i < arr.length - 1; i++) {
			int minIndex = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < arr[minIndex]) {
					minIndex = j;
				}
			}
			swap(arr, i, minIndex);
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	public static void insertionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序
			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
				swap(arr, j, j + 1);
			}
		}
	}

	// 返回一个数组arr，arr长度[0,maxLen-1],arr中的每个值[0,maxValue-1]
	public static int[] lenRandomValueRandom(int maxLen, int maxValue) {
		int len = (int) (Math.random() * maxLen);
		int[] ans = new int[len];
		for (int i = 0; i < len; i++) {
			ans[i] = (int) (Math.random() * maxValue);
		}
		return ans;
	}

	public static int[] copyArray(int[] arr) {
		int[] ans = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			ans[i] = arr[i];
		}
		return ans;
	}

	// arr1和arr2一定等长
	public static boolean isSorted(int[] arr) {
		if (arr.length < 2) {
			return true;
		}
		int max = arr[0];
		for (int i = 1; i < arr.length; i++) {
			if (max > arr[i]) {
				return false;
			}
			max = Math.max(max, arr[i]);
		}
		return true;
	}

	public static void main(String[] args) {
		int maxLen = 5;
		int maxValue = 1000;
		int testTime = 10000;
		for (int i = 0; i < testTime; i++) {
			int[] arr1 = lenRandomValueRandom(maxLen, maxValue);
			int[] tmp = copyArray(arr1);
			selectionSort(arr1);
			if (!isSorted(arr1)) {
				for (int j = 0; j < tmp.length; j++) {
					System.out.print(tmp[j] + " ");
				}
				System.out.println();
				System.out.println("选择排序错了！");
				break;
			}
		}

	}

}

package class02;

public class Code03_EqualProbabilityRandom {

	// 内部内容不可见
	public static int f() {
		return Math.random() < 0.8 ? 0 : 1;
	}

	// 等概率返回0和1
	public static int g() {
		int first = 0;
		do {
			first = f(); // 0 1
		} while (first == f());
		return first;
	}

	// 这个结构是唯一的随机机制
	// 你只能初始化并使用，不可修改
	public static class RandomBox {
		private final double p;

		// 初始化时请一定满足：0 < zeroP < 1
		public RandomBox(double zeroP) {
			p = zeroP;
		}

		public int random() {
			return Math.random() < p ? 0 : 1;
		}

	}

	// 底层依赖一个以p概率返回0，以1-p概率返回1的随机函数rand01p
	// 如何加工出等概率返回0和1的函数
	public static int rand01(RandomBox randomBox) {
		int num;
		do {
			num = randomBox.random();
		} while (num == randomBox.random());
		return num;
	}

	public static void main(String[] args) {
		int[] count = new int[2];// 0 1
		for (int i = 0; i < 1000000; i++) {
			int ans = g();
			count[ans]++;
		}
		System.out.println(count[0] + " , " + count[1]);

//		double zeroP = 0.88;
//		RandomBox randomBox = new RandomBox(zeroP);
//
//		int testTime = 10000000;
//		int count = 0;
//		for (int i = 0; i < testTime; i++) {
//			if (rand01(randomBox) == 0) {
//				count++;
//			}
//		}
//		System.out.println((double) count / (double) testTime);

	}

}

package class03;

public class Code04_BSAwesome {

	// arr 整体无序
	// arr 相邻的数不相等！
	public static int oneMinIndex(int[] arr) {
		if (arr == null || arr.length == 0) {
			return -1;
		}
		int N = arr.length;
		if (N == 1) {
			return 0;
		}
		if (arr[0] < arr[1]) {
			return 0;
		}
		if (arr[N - 1] < arr[N - 2]) {
			return N - 1;
		}
		int L = 0;
		int R = N - 1;
		// L...R 肯定有局部最小
		while (L < R - 1) {
			int mid = (L + R) / 2;
			if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
				return mid;
			} else {
				if (arr[mid] > arr[mid - 1]) {
					R = mid - 1;
				} else {
					L = mid + 1;
				}
			}
		}
		return arr[L] < arr[R] ? L : R;
	}

	// 生成随机数组，且相邻数不相等
	public static int[] randomArray(int maxLen, int maxValue) {
		int len = (int) (Math.random() * maxLen);
		int[] arr = new int[len];
		if (len > 0) {
			arr[0] = (int) (Math.random() * maxValue);
			for (int i = 1; i < len; i++) {
				do {
					arr[i] = (int) (Math.random() * maxValue);
				} while (arr[i] == arr[i - 1]);
			}
		}
		return arr;
	}

	// 也用于测试
	public static boolean check(int[] arr, int minIndex) {
		if (arr.length == 0) {
			return minIndex == -1;
		}
		int left = minIndex - 1;
		int right = minIndex + 1;
		boolean leftBigger = left >= 0 ? arr[left] > arr[minIndex] : true;
		boolean rightBigger = right < arr.length ? arr[right] > arr[minIndex] : true;
		return leftBigger && rightBigger;
	}

	public static void printArray(int[] arr) {
		for (int num : arr) {
			System.out.print(num + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int maxLen = 100;
		int maxValue = 200;
		int testTime = 1000000;
		System.out.println("测试开始");
		for (int i = 0; i < testTime; i++) {
			int[] arr = randomArray(maxLen, maxValue);
			int ans = oneMinIndex(arr);
			if (!check(arr, ans)) {
				printArray(arr);
				System.out.println(ans);
				break;
			}
		}
		System.out.println("测试结束");

	}

}

package class03;

import java.util.HashMap;
import java.util.TreeMap;

public class Code05_HashMapTreeMap {

	public static class Node {
		public int value;

		public Node(int v) {
			value = v;
		}
	}

	// (K V)表
	public static void main(String[] args) {
		HashMap<String, String> map = new HashMap<>();
		map.put("zuochengyun", "我是左程云");
		System.out.println(map.containsKey("zuochengyun"));
		System.out.println(map.containsKey("zuo"));
		System.out.println(map.get("zuochengyun"));

		map.put("zuochengyun", "他是左程云");
		System.out.println(map.get("zuochengyun"));

//		map.remove("zuochengyun");
//		System.out.println(map.containsKey("zuochengyun"));
//		System.out.println(map.get("zuochengyun"));

		String test1 = "zuochengyun";
		String test2 = "zuochengyun";
		System.out.println(map.containsKey(test1));
		System.out.println(map.containsKey(test2));

		HashMap<Integer, String> map2 = new HashMap<>();
		map2.put(1234567, "我是1234567");

		Integer a = 1234567;
		Integer b = 1234567;

		System.out.println(a == b);
		System.out.println(map2.containsKey(a));
		System.out.println(map2.containsKey(b));

		Node node1 = new Node(1);
		Node node2 = new Node(1);
		HashMap<Node, String> map3 = new HashMap<>();
		map3.put(node1, "我进来了！");
		System.out.println(map3.containsKey(node1));
		System.out.println(map3.containsKey(node2));

		System.out.println("===================");

		TreeMap<Integer, String> treeMap1 = new TreeMap<>();

		treeMap1.put(3, "我是3");
		treeMap1.put(0, "我是3");
		treeMap1.put(7, "我是3");
		treeMap1.put(2, "我是3");
		treeMap1.put(5, "我是3");
		treeMap1.put(9, "我是3");

		System.out.println(treeMap1.containsKey(7));
		System.out.println(treeMap1.containsKey(6));
		System.out.println(treeMap1.get(3));

		treeMap1.put(3, "他是3");
		System.out.println(treeMap1.get(3));

		treeMap1.remove(3);
		System.out.println(treeMap1.get(3));

		System.out.println(treeMap1.firstKey());
		System.out.println(treeMap1.lastKey());
		// <=5 离5最近的key告诉我
		System.out.println(treeMap1.floorKey(5));
		// <=6 离6最近的key告诉我
		System.out.println(treeMap1.floorKey(6));
		// >=5 离5最近的key告诉我
		System.out.println(treeMap1.ceilingKey(5));
		// >=6 离6最近的key告诉我
		System.out.println(treeMap1.ceilingKey(6));

//		Node node3 = new Node(3);
//		Node node4 = new Node(4);
//		TreeMap<Node, String> treeMap2 = new TreeMap<>();
//		treeMap2.put(node3, "我是node3");
//		treeMap2.put(node4, "我是node4");

	}

}

评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值