ARTS （第5周）

开篇词

这周做的算法题和看的专栏，使我收获了几个东西：

1、并不是一定更多重循环就比更少重循环的执行效率差，比如，希尔排序是插入排序的优化，插入排序比较标准的写法是双重循环，而希尔排序是三重循环，但是为什么能希尔排序反而是插入排序的优化呢？因为执行次数，希尔排序的执行次数并不会比插入排序多。而交换次数更少。

2、代码长短并不是最重要的，短的代码固然看起来舒服，但是如果写的长而效果更好，那就应该写长点。

本周：

各类经典排序、思路独特的排序

Algorithm 算法

线性排序

桶排序

核心思想就是根据数据大小将数据桶分为几个若干的桶，并且每个桶之间都有大小关系。分完之后，再每个桶进行排序，最后将每个桶的东西全部汇集到一起。

比如我这里的写了3种，分别是用list和数组做的，

我这里是按照位数进行分桶，1位数一个桶，2位数1个桶，以此类推。

计数排序

当数组里有N个数，数组里最大值为M的时候，就将数据分为M个桶。

然后进行counter[i] = counter[i] + counter[i - 1]的操作，这样的话，桶的下标就是对应的数值，而桶里的值就是这个数值，所应该在的位置，但有重复数值的时候需要一些特别的处理，具体可以看代码，注释齐全。

基数排序

与桶排序的思想有些类似，也是将数据分为多个桶，比如10个桶，每个1位数的数字就代表了每一个桶。然后从个位开始排序，排序完了，排第十位数，以次类推。

独特的排序

这些独特的排序，效率可能不是很好，但思路比较独特，所以我也试着写了写。

分别是:猴子排序，睡排序。

PS：睡眠排序的效率，以现在的语言来说，怎么看效果都很差，但我在网络上看到的一个说法，就是这种排序方式如果能用相匹配的硬件支持，效果将会极佳。甚至可以依照这种算法，专门设计出一种硬件来进行排序。但我对硬件的运行机制不是很了解，这里不做评价

排序代码

package jdk8test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * @description
 * 
 * @author lfy
 * @time 2019年4月13日-下午2:24:36
 */
public class Sort {
	//第五周
	public static void main(String[] args) {
		Sort sort = new Sort();
		// 冒泡排序
		int[] arr = { 100, 1, 5, 10, 55, 2, 3, 6, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2 };
		sort.bubbleSort(arr);
		System.out.println("bubbleSort:" + Arrays.toString(arr));
		// 插入排序
		arr = new int[] { 100, 1, 5, 10, 55, 2, 3, 6, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2 };
		sort.insertionSort(arr);
		System.out.println("insertionSort:" + Arrays.toString(arr));
		// 选择排序
		arr = new int[] { 100, 1, 5, 10, 55, 2, 3, 6, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2 };
		sort.selectionSort(arr);
		System.out.println("selectionSort:" + Arrays.toString(arr));
		// 归并排序
		arr = new int[] { 100, 1, 5, 10, 55, 2, 3, 6, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2 };
		sort.mergeSort(arr, 0, arr.length - 1);
		System.out.println("mergeSort:" + Arrays.toString(arr));
		// 归并排序2
		arr = new int[] { 100, 1, 5, 10, 55, 2, 3, 6, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2 };
		sort.mergeSort2(arr, 0, arr.length - 1);
		System.out.println("mergeSort2:" + Arrays.toString(arr));
		// 快速排序
		arr = new int[] { 100, 1, 5, 10, 55, 2, 3, 6, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2 };
		sort.quickSort(arr, 0, arr.length - 1);
		System.out.println("quickSort:" + Arrays.toString(arr));
		// 桶排序 集合版
		arr = new int[] { 100, 1, 5, 10, 55, 2, 3, 6, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2 };
		sort.bucketSort(arr, 3);
		System.out.println("bucketSort :" + Arrays.toString(arr));
		// 桶排序 数组快排版
		arr = new int[] { 100, 1, 5, 10, 55, 2, 3, 6, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2 };
		sort.bucketSort2(arr, 3);
		System.out.println("bucketSort2 :" + Arrays.toString(arr));
		// 桶排序 数组插入版
		arr = new int[] { 100, 1, 5, 10, 55, 2, 3, 6, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2 };
		sort.bucketSort3(arr, 3);
		System.out.println("bucketSort3 :" + Arrays.toString(arr));
		// 桶排序 数组插入版 - 优化版
		arr = new int[] { 100, 1, 5, 10, 55, 2, 3, 6, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2 };
		sort.bucketSort3_1(arr, 3);
		System.out.println("bucketSort3_1:" + Arrays.toString(arr));
		// 计数排序
		arr = new int[] { 100, 1, 5, 10, 55, 2, 3, 6, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2 };
		sort.countingSort(arr, 100);
		System.out.println("countingSort :" + Arrays.toString(arr));
		// 基数排序 Radix 集合版本
		arr = new int[] { 100, 1, 5, 10, 55, 2, 3, 6, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2 };
		sort.radixSort(arr, 4);
		System.out.println("radixSort :" + Arrays.toString(arr));
		// 基数排序 Radix 数组版本
		arr = new int[] { 100, 1, 5, 10, 55, 2, 3, 6, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2 };
		sort.radixSort2(arr, 4);
		System.out.println("radixSort 2:" + Arrays.toString(arr));

		System.out.println("=============奇特的排序算法");
		arr = new int[] { 100, 1, 5, 10, 55, 2, 3, 6, 3, 2 };
		int n = sort.monkeySort(arr);
		System.out.println("monkeySort:" + Arrays.toString(arr) + ",猴子排序次数:" + n);
		System.out.println("睡眠排序启动");
		sort.sleepSort(sellpArr);
		try {
			Thread.sleep(3500);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		System.out.println("sleepSort:" + Arrays.toString(sellpArr));

	}
	//猴子排序
	public int monkeySort(int[] arr) {
		Random random = new Random();
		int t = 0;
		// outer:
		while (true) {
			for (int i = 0; i < arr.length; i++) {
				int p = random.nextInt(i + 1);
				int tmp = arr[i];
				arr[i] = arr[p];
				arr[p] = tmp;
			}
			t++;
			// System.out.println("猴子第"+(t++)+"次排序:"+Arrays.toString(arr));
			for (int i = 0; i < arr.length; i++) {
				if (i == arr.length - 1) {
					return t;// 结束
				}
				if (arr[i] > arr[i + 1]) {
					// continue outer;
					break;
				}
			}
		}

	}

	/**
	 * 睡排序
	 * 
	 * @author lfy
	 */
	public void sleepSort(int[] arr) {

		for (int i = 0; i < arr.length; i++) {
			new Thread(new sleepSort(arr[i])).start();
		}
	}

	private static int SleepIndex = 0;
	private static int[] sellpArr = new int[] { 2048, 512, 1024, 2500, 1500, 3000 };

	private static synchronized void setSleepIndex(int v) {
		sellpArr[SleepIndex] = v;
		System.out.println("第" + SleepIndex + "个睡眠结束，值是" + v);
		SleepIndex++;
	};

	class sleepSort implements Runnable {
		long times;

		public sleepSort(long times) {
			this.times = times;
		}

		@Override
		public void run() {
			try {
				Thread.sleep(times);
				setSleepIndex((int) times);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}

	}

	/**
	 * 基数排序 集合版 入参为数组和最大数字的位数
	 * 
	 * @author lfy
	 */
	public void radixSort(int[] arr, int s) {
		ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
		// 建立10个桶 放10个数字的数据
		for (int i = 0; i < 10; i++) {
			all.add(new ArrayList<Integer>());
		}
		// 每个位数的循环
		for (int i = 1; i <= s; i++) {
			//
			for (int j = 0; j < arr.length; j++) {
				// 第一次取出个位 第二次十位 第三次百位 以此类推
				int num = getNum(arr[j], i);
				all.get(num).add(arr[j]);
			}
			int index = 0;
			for (ArrayList<Integer> arrayList : all) {
				for (Integer integer : arrayList) {
					arr[index++] = integer;
				}
				arrayList.clear();
			}

		}

	}

	/**
	 * 获取数据第N位的值
	 * 
	 * @return
	 */
	public int getNum(int num, int n) {
		int[] a = { 1, 10, 100, 1000, 10000, 100000 };
		return (num / a[n - 1]) % 10;
	}

	/**
	 * 基数排序 数组版 入参为数组和最大数字的位数 为了预防数组不够放东西 所以每个数组都设置的很大
	 * 
	 * @author lfy
	 */
	public void radixSort2(int[] arr, int s) {
		int[][] all = new int[10][];
		int[] size = new int[10];// 桶大小
		for (int i = 0; i < 10; i++) {
			all[i] = new int[arr.length];
		}
		for (int i = 1; i <= s; i++) {
			for (int j = 0; j < arr.length; j++) {
				/*
				 * int num = getNum(arr[j], i); int index = size[num]; int[] bb
				 * = all[num]; bb[index] = arr[j]; size[num]++;
				 */
				// 缩写成下面这样
				int num = getNum(arr[j], i);
				all[num][size[num]++] = arr[j];
			}
			int index = 0;
			for (int x = 0; x < 10; x++) {
				// 循环10个桶
				for (int j : all[x]) {
					if (size[x] == 0) {
						break;
					}
					size[x]--;
					arr[index++] = j;
				}
			}
		}

	}

	/**
	 * 计数排序
	 * 
	 * @author lfy
	 */
	public void countingSort(int[] arr, int max) {
		int[] temp = new int[arr.length];// 备份
		for (int i = 0; i < temp.length; i++) {
			temp[i] = arr[i];
		}

		int[] counter = new int[max + 1];// 加一是因为有0
		// 通过下标统计每个数字有的数量 比如 最后的结果 下标1的值是1 就代表值是1的数据一共有1条
		for (int i = 0; i < arr.length; i++) {
			counter[arr[i]]++;
		}
		// 这里是为了计算每个数 所处的位置，假设下标2的值为2,
		// 就代表着小于等于值2的数字一共有2个
		// 也就是说2应该放在第二个位置，也就是下标1的位置
		// 当然如果有重复的数字就会有问题 这个问题在下一个循环里解决
		for (int i = 1; i < counter.length; i++) {
			counter[i] = counter[i] + counter[i - 1];
		}

		for (int i = 0; i < arr.length; i++) {
			int v = temp[i];// 当前值
			// 去counter找到对应的数据，也就是当前值说应该在的位置
			// 获取的时候就要进行--，是为了得到正确的坐标 还可以预防重复数据，
			// 而如果多次获取相同的数，也就是重复的时候该怎么做呢
			// 假设数据是[2，2，1],那么counter的结果应该会是[0,1,3]
			// 下标2的数值是2 就是说小于等2的数值一共有2个，我们有2个2
			// 然后下标1的数值是1 就是说小于等于1的数值有一个1
			// 因此 1这个数字第一次获取的时候，所在的下标应该是0，而第一次获取2所在的下标应该是2，
			// 但再来获取一次2 就发现数据不对了，应该需要往前一位进行填充，
			// 那么我们可以减一后获取，然后这个做法就得很精巧 也不用需要过多的逻辑
			// 原本counter[2]=3，获取之后减一就变成了counter[2]=2
			// 下次再获取下标2的时候 就变成了1 ，也就是这个数正确的位置
			int index = --counter[v];
			// 赋值
			arr[index] = temp[i];
			// 这个循环里的操作 还可以缩写成这样 但为了写注释 我就拆分开来了
			// arr[--counter[temp[i]]]=temp[i];
		}

	}

	/**
	 * 桶排序 demo 这个分桶策略是简单地根据位数进行的分桶的
	 * 
	 * @author lfy
	 */
	public void bucketSort(int[] arr, int size) {
		// 使用list 而不是数组 是因为list可以帮助我们统计桶的大小
		// 也可以另外建立一个数组存放桶大小
		ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
		// 因为是个demo 桶排序 在不同场景下的分桶方式也可能不一样 桶排序的核心也在于分桶
		// 这里我简单的采用位数进行分桶 比如1位数放第一位桶 二位数放第二位桶
		// max 这里我传入的是最大数字
		// 桶大小
		// 初始化桶
		for (int i = 0; i < size; i++) {
			all.add(new ArrayList<Integer>());
		}

		for (int i = 0; i < arr.length; i++) {
			int bucketNo = getBucketNo(arr[i]);
			// 放到指定的桶

			bucketInsert(all.get(bucketNo), arr[i]);
			// 最初我在这里的做法是放进桶 然后这个循环结束之后
			// 在建立一个循环 对每个桶进行排序 Collections.sort
			// 写完后，在CSDN上看到一个桶排序的写法 ，并不是插入完桶再排序，
			// 是另外写了一个方法 在插入桶的时候 就进行排序 我觉得这种方法更高效 就改成了这种
			// 链接:https://blog.csdn.net/afei__/article/details/82965834
		}
		int i = 0;
		// 赋值
		for (ArrayList<Integer> arrayList : all) {
			for (Integer integer : arrayList) {
				arr[i++] = integer;
			}
		}
	}

	/**
	 * 桶排序 demo 这个分桶策略是简单地根据位数进行的分桶的
	 * 
	 * @author lfy
	 */
	public void bucketSort2(int[] arr, int s) {
		int[][] all = new int[s][];
		for (int i = 0; i < s; i++) {
			all[i] = new int[arr.length];
		}
		int[] size = new int[s];
		for (int i = 0; i < arr.length; i++) {
			int bucketNo = getBucketNo(arr[i]);
			all[bucketNo][size[bucketNo]++] = arr[i];
			// bucketInsert(all[bucketNo],size[bucketNo++],arr[i]);
		}
		for (int i = 0; i < all.length; i++) {
			quickSort(all[i], 0, size[i] - 1);// 快排
		}
		int index = 0;
		for (int i = 0; i < all.length; i++) {
			int[] b = all[i];
			for (int j = 0; j < b.length; j++) {
				if (size[i]-- == 0) {
					break;
				}
				arr[index++] = b[j];

			}
		}

	}

	/**
	 * 桶排序 demo 这个分桶策略是简单地根据位数进行的分桶的
	 * 
	 * @author lfy
	 */
	public void bucketSort3(int[] arr, int s) {
		int[][] all = new int[s][];
		for (int i = 0; i < s; i++) {
			all[i] = new int[arr.length];
		}
		int[] size = new int[s];
		for (int i = 0; i < arr.length; i++) {
			int bucketNo = getBucketNo(arr[i]);
			bucketInsert(all[bucketNo], size[bucketNo]++, arr[i]);
			// i = 0  s = 1
			// i = 0 s = 10 
		}

		int index = 0;
		for (int i = 0; i < all.length; i++) {
			int[] b = all[i];
			for (int j = 0; j < b.length; j++) {
				if (size[i]-- == 0) {
					break;
				}
				arr[index++] = b[j];

			}
		}

	}
	/**
	 * 桶排序 demo 这个分桶策略是简单地根据位数进行的分桶的
	 * 
	 * @author lfy
	 */
	public void bucketSort3_1(int[] arr, int s) {
		int[][] all = new int[s][];
		for (int i = 0; i < s; i++) {
			all[i] = new int[arr.length];
		}
		int[] size = new int[s];
		for (int i = 0; i < arr.length; i++) {
			int bucketNo = getBucketNo(arr[i]);
			bucketInsert1(all[bucketNo], size[bucketNo]++, arr[i]);
			// i = 0  s = 1
			// i = 0 s = 10 
		}

		int index = 0;
		for (int i = 0; i < all.length; i++) {
			int[] b = all[i];
			for (int j = 0; j < b.length; j++) {
				if (size[i]-- == 0) {
					break;
				}
				arr[index++] = b[j];

			}
		}

	}
	/**
	 * 采用类似插入排序的思想 查找后找到新数据应该在的位置
	 * 
	 * @author lfy
	 */
	public void bucketInsert(int[] l, int s, int n) {
		int index = 0;
		for (int i = 0; i < s; i++) {
			if (l[i] < n) {
				index++;
				continue;
			}
			break;
		}
		for (int i = s-1; i >= index; i--) {
			l[i + 1] = l[i];
		}
		/*
		for (int i = index; i <s; i++) {
			l[i + 1] = l[i];
		}*/
		l[index] = n;
	}
	/**
	 * 采用类似插入排序的思想 查找后找到新数据应该在的位置
	 * 
	 * @author lfy
	 */
	public void bucketInsert1(int[] l, int s, int n) {
		int index = 0;
		for (int i = 0; i < s; i++) {
			if (l[i] <= n) {
				index++;
				continue;
			}
			break;
		}
		
		for (int i = s-1; i >= index; i--) {
			l[i + 1] = l[i];
		}
		l[index] = n;
	}

	/**
	 * 采用类似插入排序的思想 查找后找到新数据应该在的位置
	 * 
	 * @author lfy
	 */
	public void bucketInsert(List<Integer> l, int n) {
		int index = 0;
		for (int i = 0; i < l.size(); i++) {
			if (n > l.get(i)) {
				index++;
				continue;
			}
			break;
		}
		l.add(index, n);
	}

	/**
	 * 分桶策略 桶排序的核心内容之一 场景不同 计算方式也不一样 这里是简单的根据位数进行分组
	 * 
	 * @author lfy
	 * @return
	 */
	private int getBucketNo(int v) {
		return ("" + v).length() - 1;
	}

	/**
	 * 快速排序
	 * 
	 * @author lfy
	 */
	public void quickSort(int[] arr, int s, int e) {
		if (e > s) {// 停止条件
			int p = qucik(arr, s, e);
			quickSort(arr, s, p - 1);
			quickSort(arr, p + 1, e);
		}
	}

	public int qucik(int[] arr, int s, int e) {
		int pivot = arr[s];// 基准点
		while (e > s) {
			// 从最右边开始 查找第一个小于基准点的数值
			while (e > s && arr[e] >= pivot) {
				e--;
			}
			// 找到后，首次覆盖基准点，后续则覆盖下个循环里找到的点
			// 如果未找到 则s==e
			arr[s] = arr[e];
			// 从右边查找第一个大于基准点的数值
			while (e > s && arr[s] <= pivot) {
				s++;
			}
			// 找到后，覆盖前一个循环里找到的点
			// 如果未找到 则s==e
			arr[e] = arr[s];
		}
		arr[s] = pivot;
		return e;
	}

	/**
	 * 归并排序
	 * 
	 * @author lfy
	 */
	public void mergeSort2(int[] arr, int s, int e) {
		if (e > s) {
			int m = (s + e) / 2;
			// 拆分成2个
			mergeSort2(arr, s, m);
			mergeSort2(arr, m + 1, e);
			merge2(arr, s, m, e);

		}

	}

	// 合并
	private void merge2(int[] a, int s, int m, int e) {// 0 1 2
		int[] temp = new int[e - s + 1];
		// 备份
		for (int i = s, j = 0; i <= e; i++, j++) {
			temp[j] = a[i];
		}
		int p1 = 0;// 前半段指针
		//难点核心在这里 
		//如果是奇数个数进行匹配的时候 
		//要看先计算前半部分还是后半部分 先计算的必须比后面少
		//如：计算3个数字 然后后面的循环判断是前半部分先判断 那么前半部分必须为1个 后半部分为2个 否则会出错
		int pe1 = m -s ;// 前半段的最终坐标
		//int pe1 = (0 + temp.length - 1) / 2;// 前半段的最终坐标
		int p2 = pe1 + 1;// 后半段指针
		int pe2 = temp.length - 1;// 后半段的最终坐标
		/*
		 * int p1 = 0;// 前半段指针 int pe1 = m-s;// 前半段的最终坐标 int p2 = m-s+1;// 后半段指针
		 * int pe2 = e-s;// 后半段的最终坐标
		 */

		
		
		
		
		
		while (p1 <= pe1 && p2 <= pe2) {
			if (temp[p1] <= temp[p2])
				a[s++] = temp[p1++];
			else
				a[s++] = temp[p2++];
		}
		while (p1 <= pe1) {
			a[s++] = temp[p1++];
		}
		while (p2 <= pe2) {
			a[s++] = temp[p2++];
		}
	}

	/**
	 * 冒泡排序
	 * 
	 * @author lfy
	 */
	public void bubbleSort(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			for (int j = i + 1; j < arr.length; j++) {
				// 当i比j大的时候，2个数字位置对换
				if (arr[i] > arr[j]) {
					// 对换
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}

		}

	}

	/**
	 * 插入排序
	 * 
	 * @author lfy
	 */
	public void insertionSort(int[] arr) {

		for (int i = 0; i < arr.length; i++) {
			int temp = arr[i];// 缓存
			int j = i - 1;// 和之前的数比较
			for (; j >= 0; j--) {
				// 若当前j坐标的数字更小,则往后挪一位
				if (arr[j] > temp) {
					arr[j + 1] = arr[j];
				} else {
					break;
				}

			}
			// 将缓存的数值插入到合适的位置
			arr[j + 1] = temp;
		}
	}

	/**
	 * 选择排序
	 * 
	 * @author lfy
	 */
	public void selectionSort(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			int min = i;// 最小坐标
			for (int j = i + 1; j < arr.length; j++) {
				// 遍历找出最小
				if (arr[min] > arr[j]) {
					min = j;
				}
			}
			// 将最小的和i进行对换
			int temp = arr[i];
			arr[i] = arr[min];
			arr[min] = temp;
		}
	}

	/**
	 * 归并排序
	 * 
	 * @author lfy
	 */
	public void mergeSort(int[] arr, int start, int end) {
		if (end > start) {
			int mid = (end + start) / 2;
			int estart = mid + 1;

			// 以中点进行双路归并
			mergeSort(arr, start, mid);
			mergeSort(arr, estart, end);
			// 归并完成后 进行融合
			merge(arr, start, mid, end);
		}

	}

	/**
	 * 归并
	 * 
	 * @author lfy
	 * @time 2019年4月13日-下午4:13:38
	 * @param a
	 *            数据
	 * @param s
	 *            起始
	 * @param m
	 *            中间
	 * @param e
	 *            结束
	 */
	private void merge(int[] a, int s, int m, int e) {

		int[] temp = new int[a.length];
		for (int ix = s; ix <= e; ix++) {
			temp[ix] = a[ix];
		}
		int i = s;
		int p1 = s;// 前段数组指针
		int p2 = m + 1;// 后段数组指针
		while (p1 <= m && p2 <= e) {
			if (temp[p1] < temp[p2]) {
				a[i++] = temp[p1++];
			} else {
				a[i++] = temp[p2++];
			}
		}
		while (p1 <= m) {
			a[i++] = temp[p1++];
		}
		while (p2 <= e) {
			a[i++] = temp[p2++];
		}

	}
}

LeetoCode

整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

https://leetcode-cn.com/problems/reverse-integer/

这里我做了2种方式，一个是转字符串的，一个是用long计算的方式。

public static int reverse2(int x) {
	long r = 0L;
	while (x != 0) {
		int i = x % 10;
		x /= 10;
		r *= 10;
		r += (i);
	}
	if (r > Integer.MAX_VALUE || r < Integer.MIN_VALUE)
		return 0;
	return (int) r;
}

// 反转
public static int reverse1(int x) {
	boolean minus = false;
	if (x < 0) {
		minus = true;
		x = -x;
	}
	String s = x + "";
	StringBuffer sb = new StringBuffer();
	for (int i = s.length() - 1; i >= 0; i--) {
		sb.append(s.charAt(i));
	}
	try {
		if (minus)
			return -Integer.valueOf(sb.toString());
		return Integer.valueOf(sb.toString());
	} catch (Exception e) {
		return 0;
	}
}

回文数

数字是否回文串

https://leetcode-cn.com/problems/palindrome-number/comments/

如果用转字符串的计算的话，会很简单，取出首尾进行判断就行了，但题目说希望用数字的方式进行。想到之前做的那题数值回转的题，刚好思路可以用到这里来，将数字进行一下反转，就可以得到反转后的数值，匹配一下是否相等，就可以得到结果了。

/**
	 * 是否回文数
	 * 
	 * @author lfy
	 * @time 2019年4月15日-上午10:54:51
	 */
	public static boolean isPalindrome(int x) {
		// 小于0直接false
		if (x < 0)
			return false;

		// 最初想用数字首位和末尾进行判断，判断完后砍掉首位和末位继续判断
		// 后来想了想 砍掉首位之后如果新的数值首位是0 再接下去的判断就会很麻烦
		// 所以放弃了这种想法
		// 改成使用反转
		int temp = x;
		long r = 0L;
		while (x != 0) {
			int i = x % 10;
			x /= 10;
			r *= 10;
			r += (i);
		}
		// 溢出
		if (r > Integer.MAX_VALUE)
			return false;
		if (r == temp)
			return true;
		return false;
	}

罗马数字转整数

https://leetcode-cn.com/problems/roman-to-integer/

这题就是要求将罗马数字转换为整数.

因为我对于罗马数字的了解不足，这是我做的第一个答案，提交后，效率竟然达到了超越99%的人，这个时候我是有点不信的，后来我去看了各种提交的答案，看到很多答案里，用了很多字符串处理的api 等，这些字符串的处理里，循环是少不了的。也应该是因此，我这个答案的循环次数极少，所以才会有比较高的排名。

对此，在结合之前看过的希尔排序，我感觉到了1个结论

2、代码长短并不是最重要的，短的代码固然看起来舒服，但是如果写的长而效果更好，那就应该写长点。

public static int romanToInt1(String s) {
		int r = 0;
		int l = s.length();
		for (int i = 0; i < l; i++) {
			char c = s.charAt(i);
			if (c == 'M') {
				r += 1000;
				continue;
			}
			if (c == 'D') {
				r += 500;
				continue;
			}
			if (c == 'L') {
				r += 50;
				continue;
			}
			if (c == 'V') {
				r += 5;
				continue;
			}
			if (c == 'C') {
				if (i == l - 1) {
					r += 100;
					break;
				}
				char n = s.charAt(i + 1);
				if (n == 'D') {
					i++;
					r += 400;
				} else if (n == 'M') {
					i++;
					r += 900;
				} else {
					r += 100;
				}

				continue;
			}

			if (c == 'X') {
				if (i == l - 1) {
					r += 10;
					break;
				}
				char n = s.charAt(i + 1);
				if (n == 'L') {
					i++;
					r += 40;
				} else if (n == 'C') {
					i++;
					r += 90;
				} else {
					r += 10;
				}

				continue;
			}
			if (c == 'I') {
				if (i == l - 1) {
					r += 1;
					break;
				}
				char n = s.charAt(i + 1);
				if (n == 'V') {
					i++;
					r += 4;
				} else if (n == 'X') {
					i++;
					r += 9;
				} else {
					r += 1;
				}
				continue;
			}
		}

		return r;
	}

然后我看到了第一名的做法，很精巧的一个答案

利用下标进行取数判断，最后得出值。

private final int[] symbols = new int[]{
	            0, 0, 100, 500, 0, 0, 0, 0, 1, 0, 0, 50, 1000, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 10
	    };

	    public int romanToInt(String a) {
	        int prev = 0, sum = 0, cur = 0;
	        for (int i = a.length() - 1; i >= 0; i--) {
	            cur = symbols[a.charAt(i) - 'A'];
	            sum += cur >= prev ? cur : -cur;
	            prev = cur;
	        }
	        return sum;
	    }

Review 英文文章

https://hbase.apache.org/

这篇文章简单的介绍了hbase的使用。

Tip 技巧

极客时间的专栏《数据结构与算法之美》

本周学习了该专栏中的13-14篇

学习了排序优化和线性排序算法。

出处：《数据结构与算法之美》（作者：王争）

https://time.geekbang.org/column/intro/126

本周的分享也是我的开篇词

2、代码长短并不是最重要的，短的代码固然看起来舒服，但是如果写的长而效果更好，那就应该写长点。

ARTS （第5周）

Algorithm 算法

线性排序

桶排序

计数排序

基数排序

独特的排序

排序代码

LeetoCode

整数反转

回文数

罗马数字转整数

Review 英文文章

Tip 技巧

极客时间的专栏《数据结构与算法之美》

Share 分享