剑指offer
剑指offer题目（持续更新）
单例模式
单线程
/**
* 线程不安全
*/
class Singleton1 {
private static Singleton1 instance = null;
// 构造方法私有化，防止外部使用new创建对象
private Singleton1() {
System.out.println("单例模式1");
}
// 获取实例的方法
public static Singleton1 getInstance() {
if (instance == null) {
instance = new Singleton1();
}
return instance;
}
}
多线程
有人提出在getInstance()方法上同步锁，但是锁住一整个方法可能粒度过大，不利于效率。既然锁方法不太好，那么锁代码呢？
class Singleton2 {
private static Singleton2 instance = null;
// 构造方法私有化，防止外部使用new创建对象
private Singleton2() {
System.out.println("单例模式2");
}
// 获取实例的方法
public static Singleton2 getInstance() {
if (instance == null) {
synchronized (Singleton2.class) {
instance = new Singleton2();
}
}
return instance;
}
}
这样做看似解决了线程安全问题，其实不然。设现有线程A和B，在t1时刻线程A和B均已通过判空语句但都未取得锁资源；t2时刻时，A先取得锁资源进入临界区（被锁的代码块），执行new操作创建实例对象，然后退出临界区，释放锁资源。t3时刻，B取得被A释放的锁资源进入临界区，执行new操作创建实例对象，然后退出临界区，释放锁资源。明显地，Singleton被实例化两次。
改进：
/**
* 线程安全，但是如果instance已经存在不能直接返回，也会被锁住，效率很低下，还可以优化
*/
class Singleton3 {
private static Singleton3 instance = null;
private Singleton3() {
System.out.println("单例模式3");
}
public static Singleton3 getInstance() {
synchronized (Singleton3.class) {
if (instance == null) {
instance = new Singleton3();
}
}
return instance;
}
}
双检查锁机制（推荐）
class Singleton4 {
//注意此处加上了volatile关键字
private static Singleton4 instance = null;
private Singleton4() {
System.out.println("单例模式4");
}
public static Singleton4 getInstance() {
if (instance == null) {
synchronized (Singleton4.class) {
if (instance == null) {
instance = new Singleton4();
}
}
}
return instance;
}
}
在JDK1.5以前，DCL（双检查锁机制）是不稳定的，有时也可能创建多个实例，在1.5以后开始提供volatile关键字修饰变量来达到稳定效果。
多线程测试入口
public class Test {
public static void main(String[] args) {
//创建实现了Runnable接口的匿名类
Runnable run = () -> Singleton2.getInstance();
for (int i = 0; i < 50; i++) {
Thread thread = new Thread(run);
thread.start();
}
}
}
总结
单例是为了保证系统中只有一个实例，其关键点有：
- 私有构造函数
- 声明静态单例对象
- 构造单例对象之前要加锁（lock一个静态的object对象）
- 需要两次检测单例实例是否已经被构造，分别在锁之前和锁之后
1.为何要检测两次？
如上面所述，有可能延迟加载或者缓存原因，造成构造多个实例，违反了单例的初衷。
2.构造函数能否公有化？
不行，单例类的构造函数必须私有化，单例类不能被实例化，单例实例只能静态调用
3.lock住的对象为什么要是object对象，可以是int吗？
不行，锁住的必须是个引用类型。如果锁值类型，每个不同的线程在声明的时候值类型变量的地址都不一样，那么上个线程锁住的东西下个线程进来会认为根本没锁，相当于每次都锁了不同的门，没有任何卵用。而引用类型的变量地址是相同的，每个线程进来判断锁多想是否被锁的时候都是判断同一个地址，相当于是锁在通一扇门，起到了锁的作用。
数组
二维有序数组中查找
思路：用target与数组右上角的值进行比较，小于右上角，则跳过该列，大于右上角，则跳过该行
public class Test {
public static void main(String[] args) {
int[][] arr = {
{1, 2, 8, 9},
{2, 4, 9, 12},
{4, 7, 10, 13},
{6, 8, 11, 15},
};
int[][] arr2 = {
{1, 2, 8, 9},
};
System.out.println(find(arr, 11));
}
public static boolean find(int[][] arr, int target) {
if (arr.length < 1) return false;
int i = 0, j = arr[0].length - 1;
// 用target与数组右上角的值进行比较
while (j > 0 && i < arr.length - 1) {
// target小于右上角，则跳过该列
while (target < arr[i][j] && j > 0) {
j--;
}
// target大于右上角，则跳过该行
while (target > arr[i][j] && i < arr.length - 1) {
i++;
}
if (target == arr[i][j]) {
System.out.println("i:" + (i + 1) + ",j:" + (j + 1));
return true;
}
}
return false;
}
}
旋转数组的最小数字
主要考虑三种情况：
- 正常情况：{7,8,1,2,3,4,5,6}
- 有序情况：{1, 2, 3, 4, 5, 6}
- 相等情况：{1, 1, 0, 1, 1, 1, 1, 1}
public class Test {
public static void main(String[] args) {
// int[] a = {5,6,7,8,1,2,3,4};
// int[] a = {1, 1, 0, 1, 1, 1, 1, 1};
int[] a = {1, 2, 3, 4, 5, 6};
System.out.println(findMin(a));
}
/**
* 使用二分法进行查找
*/
public static int findMin(int[] arr) {
if (arr == null || arr.length == 0) {
return -1;
}
int left = 0;
int right = arr.length - 1;
int mid = left;//初始值原因见下方
/**
* 正常情况，左边会大于等于右边，否则就已经是有序的数组，第一个就是最小值，因此mid初始为left
*/
while (arr[left] >= arr[right]) {
if (right - left == 1) {
mid = right;
break;
}
mid = (left + right) / 2;
// 左边=中间=右边，只能遍历,{1, 1, 0, 1, 1, 1, 1, 1};
if (arr[left] == arr[right] && arr[right] == arr[mid]) {
int min = Integer.MAX_VALUE;
for (int i = left; i <= right; i++) {
if (min > arr[i]) {
min = arr[i];
}
}
return min;
}
// 左边<=中间，说明最小值在[mid,right]
if (arr[left] <= arr[mid]) {
left = mid;
}
// 右边>=中间，说明最小值在[left,mid]
else if (arr[right] >= arr[mid]) {
right = mid;
}
}
return arr[mid];
}
调整数组 使奇数在偶数前面
并保证奇数和奇数，偶数和偶数之间的相对位置不变。
基本解法
//基本解法
public static void sort(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return;
}
int left = 0, right = numbers.length - 1;
while (left <= right) {
while ((numbers[left] & 0x1) == 1) left++;
while ((numbers[right] & 0x1) == 0) right--;
if (left <= right) {
int tmp = numbers[left];
numbers[left] = numbers[right];
numbers[right] = tmp;
}
}
}
可扩展的实现，解耦，完成各种条件
// 可扩展的实现
public class Test {
public static void main(String[] args) {
int[] arr = {2, 2, 1, 3, 6, 9, 8, 10, 7, 4, 5};
sort(arr, new Condition() {
@Override
public boolean check(int a) {
if ((a & 0x1) == 1)
return false;
else {
return true;
}
}
});
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void sort(int[] numbers, Condition c) {
if (numbers == null || numbers.length == 0) {
return;
}
int left = 0, right = numbers.length - 1;
while (left <= right) {
while (left <= right && c.check(numbers[left])) left++;
while (left <= right && !c.check(numbers[right])) right--;
if (left <= right) {
int tmp = numbers[left];
numbers[left] = numbers[right];
numbers[right] = tmp;
}
}
}
private interface Condition {
public boolean check(int a);
}
}
保证顺序
import java.util.*;
public class Solution {
//O(n^2)
public void reOrderArray(int [] array) {
if (array == null || array.length == 0) {
return;
}
for (int i = 0; i < array.length; i++) {
for (int j = array.length - 1; j > i; j--) {
if (array[j] % 2 == 1 && array[j - 1] % 2 == 0) {
int temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
}
// O(n),辅助空间
public void reOrderArray2(int [] array) {
if (array == null || array.length == 0) {
return;
}
int left = 0;
int right = array.length - 1;
int[] copy = new int[array.length];
int i = 0;
int j = array.length - 1;
//从前向后扫描奇数
while (left < array.length ) {
if(array[left] % 2 == 1)
copy[i++] = array[left];
left++;
}
//从后向前扫描偶数
while (right >= 0 ) {
if(array[right] % 2 == 0)
copy[j--] = array[right];
right--;
}
for(int k=0;k<array.length;k++){
array[k]=copy[k];
}
}
}
顺时针打印矩阵
public class Test {
public static void main(String[] args) {
int[][] matrix = {
{1, 2, 3, 4},
{12, 13, 14, 5},
{11, 16, 15, 6},
// {10,9,8,7},
};
ArrayList<Integer> list = printMatrix(matrix);
for (int i : list) {
System.out.print(i + " ");
}
}
public static ArrayList<Integer> printMatrix(int [][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return null;
}
int start = 0;// 因为每次打印都是从对角线[0,0]、[1,1]……的开始，因此只需要一个变量来标记
int row = matrix.length;
int col = matrix[0].length;
ArrayList<Integer> printList = new ArrayList<>();
while (start * 2 < row && start * 2 < col) {
ArrayList<Integer> result = print(matrix, row, col, start);
printList.addAll(result);
++start;
}
return printList;
}
public static ArrayList<Integer> print(int[][] matrix, int row, int col, int start) {
int endX = col - start - 1;
int endY = row - start - 1;
ArrayList<Integer> list = new ArrayList<>();
// 打印从左到右的上面一行 :第一行肯定要打印的
for (int i = start; i <= endX; i++) {
list.add(matrix[start][i]);
}
// 打印从上到下的右面的一列：第二行能不能打印的条件在循环中了
for (int i = start + 1; i <= endY; i++) {
list.add(matrix[i][endX]);
}
if (start < endX && start < endY) {
for (int i = endX - 1; i >= start; i--) {
list.add(matrix[endY][i]);
}
}
if (start < endX && start < endY - 1) {
for (int i = endY - 1; i > start; i--) {
list.add(matrix[i][start]);
}
}
return list;
}
}
数组中超过一半的数字（还有一种解法）
解法1：基于partition的函数的O(n)算法，因为数字超过半数，因此将原数组排序后，中位数一定就是那个数值（如果输入是）
解法2：一个数字出现次数超过数组长度的一半，说明他出现的次数比其他所有数字出现的次数还多。因此可以用result，time来分别保存统计的数字，以及出现的次数。遍历时如果相同time+1，不同time-1，当time=0时，result更新为当前数字，time重置为1
public static int MoreThanHalfNum_Solution(int[] array) {
//1.输入合法性验证
if (array == null || array.length == 0) return 0;
//2.统计超过半数的数字
int result = array[0];
int time = 1;
for (int i = 1; i < array.length; i++) {
//当time=0时，result更新为当前数字，time重置为1
if (time == 0) {
result = array[i];
time = 1;
continue;
}
//遍历时如果相同time+1，不同time-1
if (result == array[i])
time++;
else
time--;
}
//3.是否超过半数验证
time = 0;
for (int i = 0; i < array.length; i++) {
if (result == array[i]) {
time++;
}
}
if (time * 2 <= array.length)
result = 0;
return result;
}
最小的k个数（包含海量数据）
解法1，小数据量：快排方法 O(n)
public class Test {
public static void main(String[] args) {
int[] array = {2, 3, 0, 2, 5, 7, 8, 9, 1};
ArrayList<Integer> re = GetLeastNumbers_Solution(array, 10);
System.out.println(re);
}
public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
//输入检验
if (input == null || input.length == 0 || k <= 0 || k > input.length) return result;
int index = parttition(input, 0, input.length - 1);
int start = 0;
int end = input.length - 1;
while (index != k - 1) {
if (index < k - 1) {
start = index + 1;
} else {
end = index - 1;
}
index = parttition(input, start, end);
}
for (int i = 0; i < k; i++) {
result.add(input[i]);
}
return result;
}
public static int parttition(int[] input, int low, int high) {
int i = low;
int j = high;
int mid = (low + high) / 2;
swap(input, mid, low);
int pivot = input[low];
while (i < j) {
while (input[j] >= pivot && i < j) j--;
while (input[i] <= pivot && i < j) i++;
swap(input, i, j);
}
swap(input, i, low);
return i;
}
public static void swap(int[] input, int i, int j) {
int temp = input[i];
input[i] = input[j];
input[j] = temp;
}
}
解法2，海量数据：使用红黑树 O(nlogk)，类似下面介绍的方法5
常见解法思路：
- 最容易想到的方法是将数据全部排序，然后在排序后的集合中进行查找，最快的排序算法的时间复杂度一般为O（nlogn），如快速排序。但是在32位的机器上，每个float类型占4个字节，1亿个浮点数就要占用400MB的存储空间，对于一些可用内存小于400M的计算机而言，很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求，该方法也并不高效，因为题目的目的是寻找出最大的10000个数即可，而排序却是将所有的元素都排序了，做了很多的无用功。
- 第二种方法为局部淘汰法，该方法与排序方法类似，用一个容器保存前10000个数，然后将剩余的所有数字与容器内的最小数字相比，如果某一后续元素比容器内最小数字大，则删掉容器内最小元素，并将该元素插入容器，最后遍历完这1亿个数，得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O（n+m^2），其中m为容器的大小，即10000。
- 第三种方法是分治法，将1亿个数据分成100份，每份100万个数据，找到每份数据中最大的10000个，最后在剩下的100*10000个数据里面找出最大的10000个。如果100万数据选择足够理想，那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下：用快速排序的方法，将数据分为2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大的那堆个数N大于10000个，继续对大堆快速排序一次分成2堆，如果大堆个数N小于10000个，就在小的那堆里面快速排序一次，找第10000-n大的数字；递归以上过程，就可以找到第1w大的数。参考上面的找出第1w大数字，就可以类似的方法找到前10000大数字了。此种方法需要每次的内存空间为10^6*4=4MB，一共需要101次这样的比较。
- 第四种方法是Hash法。如果这1亿个书里面有很多重复的数，先通过Hash法，把这1亿个数字去重复，这样如果重复率很高的话，会减少很大的内存用量，从而缩小运算空间，然后通过分治法或最小堆法查找最大的10000个数。
- 第五种方法采用最小堆。首先读入前10000个数来创建大小为10000的最小堆，建堆的时间复杂度为O（mlogm）（m为数组的大小即为10000），然后遍历后续的数字，并于堆顶（最小）数字进行比较。如果比最小的数小，则继续读取后续数字；如果比堆顶数字大，则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。该算法的时间复杂度为O（n*mlogm），空间复杂度是10000（常数）。
public class Test {
public static void main(String[] args) {
int[] array = {2, 3, 0, 2, 5, 7, 8, 9, 1};
ArrayList<Integer> re = GetLeastNumbers_Solution(array, 10);
System.out.println(re);
}
public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
//输入检验
if (input == null || input.length == 0 || k <= 0 || k > input.length) return result;
TreeSet<Integer> topk=new TreeSet();
for (int val : input) {
if (topk.size() < k) {
topk.add(val);
} else {
if(topk.last()>val){
topk.pollLast();
topk.add(val);
}
}
}
result.addAll(topk);
return result;
}
}
访问次数最多的IP
参考：http://yueyemaitian.iteye.com/blog/1180299
算法思想：分而治之+Hash
1、IP地址最多有2^32=4G种取值情况，所以不能完全加载到内存中处理；
2、可以考虑采用分而治之的思想，按照IP地址的Hash(IP) % 1024值，把海量IP日志分别存储到1024个小文件中，这样，每个小文件最多包含4MB个IP地址；
这里解释一下为什么用Hash(IP) % 1024值，如果不用，而直接分类的话，可能会出现这样一种情况，就是有个IP在每个小文件中都存在，而且这个IP并不一定在那个小文件中是数量最多的，那么最终可能选择的结果会有问题，所以这里用了Hash(IP)%1024值，这样的话，通过计算IP的Hash值，相同IP肯定会放到一个文件中，当然了不同的IP的Hash值也可能相同，就存在一个小文件中。
3、对于每一个小文件，可以构建一个IP为key，出现的次数为value的Hash Map，同时记录当前出现次数最多的那个IP地址；
4、可以得到1024个小文件中的出现次数最多的那个IP，再依据常规的排序算法得出总体上出现次数最多的IP。
连续子数组的最大和
解法1 O(n)，思路如下：
public class Test {
public static void main(String[] args) {
int[] array = {1,-2,3,10,-4,7,2,-5};
System.out.println(FindGreatestSumOfSubArray(array));
}
public static int FindGreatestSumOfSubArray(int[] array) {
if (array == null || array.length == 0) return 0;
int start = 0;
int end = 0;
int max = array[0];
int sum = array[0]; // 初始化为数组中的第一个数
for (int i = 1; i < array.length; i++) {
// 如果之前的和<=0，说明从之前某个位置开始的子数组的和 会小于 从当前位置开始的子数组的和
// 因此可以不考虑之前的子数组，Sum重置为当前位置的值
if (sum <= 0) {
start = i;
end = i;
sum = array[i];
}else{
sum = sum + array[i];
}
// 更新最大和
if (sum > max) {
max = sum;
end = i; //更新子数组最后的下标
}
}
System.out.println("["+start+","+end+"]");
return max;
}
}
解法2：动态规划
public static int FindGreatestSumOfSubArray(int[] array) {
if (array == null || array.length == 0) return 0;
int len = array.length;
int[] f = new int[len];
f[0] = array[0];
for (int i = 1; i < len; i++) {
// 递归公式
// f[i] = array[i] # i=0 或者 f[i-1]<=0
// f(i) = f[i - 1] + array[i] # f[i-1]>0
f[i] = f[i - 1] <= 0 ? array[i] : f[i - 1] + array[i];
}
int max = Integer.MIN_VALUE;
for (int i : f) {
if (max < i) {
max = i;
}
}
return max;
}
解法3：分治（未实现）
把数组排成最小的数
import java.util.*;
public class Solution {
public String PrintMinNumber(int [] numbers) {
// 输入合法性检测
if (numbers == null || numbers.length == 0) {
return "";
}
// 将数字转为字符串类型
ArrayList<String> nums = new ArrayList<>();
for (int i : numbers) {
nums.add(Integer.toString(i));
}
// 使用自定义的规则 进行排序
Collections.sort(nums, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
//为了避免长度问题，将其拼接后再进行字符串比较
return (s1 + s2).compareTo(s2 + s1);
}
});
// 处理最后的结果
return String.join("",nums);
}
}
数组中的逆序对
public static int InversePairs(int[] array) {
if (array == null || array.length <= 0) {
return 0;
}
return countInverse(array, 0, array.length - 1) % 1000000007;
}
public static int countInverse(int[] array, int low, int high) {
if (low >= high) {
return 0;
}
int mid = (low + high) / 2;
int leftCount = countInverse(array, low, mid);
int rightCount = countInverse(array, mid + 1, high);
// 拷贝一份数组的左右部分，用于排序并统计，注意copyOfRange[begin,end)，不包括end位置
int[] leftCopy = Arrays.copyOfRange(array, low, mid + 1);
int[] rightCopy = Arrays.copyOfRange(array, mid + 1, high + 1);
// 排序并统计逆序对
int i = leftCopy.length - 1;
int j = rightCopy.length - 1;
int index = high;
int count = 0;
while (i >= 0 && j >= 0) {
if (leftCopy[i] <= rightCopy[j]) {
array[index--] = rightCopy[j--];
} else {
array[index--] = leftCopy[i--];
count += (j + 1);
// 避免数据溢出，进行取余
if (count > 1000000007) count %= 1000000007;
}
}
// 将剩余的部分拷贝回原数组
for (; i >= 0; i--) {
array[index--] = leftCopy[i];
}
for (; j >= 0; j--) {
array[index--] = rightCopy[j];
}
// 避免数据溢出，进行取余
int result = leftCount + rightCount + count;
if (result > 1000000007) result %= 1000000007;
return result;
}
数字在排序数组中出现的次数
public static int GetNumberOfK(int[] array, int k) {
int count = 0;
if (array != null || array.length > 0) {
// 先找到第一个位置
int start = getFirstK(array, k, 0, array.length - 1);
if (start == -1) return 0;// 查找不到在则直接返回
// 再找最后出现的位置
int end = getLastK(array, k, 0, array.length - 1);
count = end - start + 1;
}
return count;
}
public static int getFirstK(int[] array, int k, int low, int high) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
int midData = array[mid];
if (midData == k) {
// 如果已经是数组第一个 或者 mid前一个位置小于k，则说明已经找到第一个k的位置了
if (mid == 0 || (mid > 0 && array[mid - 1] < k)) {
return mid;
} else {
high = high - 1;
}
} else if (midData < k) {
low = mid + 1;
} else {
high = mid - 1;
}
return getFirstK(array, k, low, high);
}
public static int getLastK(int[] array, int k, int low, int high) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
int midData = array[mid];
if (midData == k) {
// 如果已经是数组最后一个 或者 mid后一个位置大于k，则说明已经找到最后一个k的位置了
if (mid == high || (mid < high && array[mid + 1] > k)) {
return mid;
} else {
low = mid + 1;
}
} else if (midData < k) {
low = mid + 1;
} else {
high = mid - 1;
}
return getLastK(array, k, low, high);
}
数组中只出现一次的数字
public class Test {
public static void main(String[] args) {
int[] array = {2, 4, 3, 6, 3, 2, 5, 5};
int[] num1 = new int[1];
int[] num2 = new int[1];
FindNumsAppearOnce(array, num1, num2);
System.out.println(num1[0]);
System.out.println(num2[0]);
}
public static void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
if (array == null || array.length < 2) return;
// 先遍历一遍求出异或的结果
int xorResult = 0;
for (int i : array) {
xorResult ^= i;
}
int index = findFirstBit(xorResult); //找到第一个bit为1的下标
// 利用第一个bit为1的下标将数组分割为两部分，每部分index位置的bit相同
int n1 = 0;
int n2 = 0;
for (int i : array) {
if (isSameBit(i, index))
n1 ^= i;
else
n2 ^= i;
}
num1[0] = n1;
num2[0] = n2;
}
// 从右往左寻找第一个为1的二进制下标
public static int findFirstBit(int num) {
int i = 1;
int index = 0;
while (index < Integer.SIZE) {
if ((i & num) == i) break;
i = i << 1;
index++;
}
return index;
}
// 判断指定下标的位置的二进制是否为1
public static boolean isSameBit(int num, int leftShift) {
int i = 1 << leftShift;
return (num & i) == i;
}
}
相似题：leetcode：single-number、 single-number-ii
在数组中寻找 和为s的两个数字
思路：分别从最左和最右逼近，如果和小于s，则i++，如果和大于s，则j–
// 如果有多对数字的和等于S，输出两个数的乘积最小的。
public static ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
ArrayList<Integer> result = new ArrayList<Integer>();
if (array == null || array.length < 2) return result;
int i = 0;
int j = array.length - 1;
while (i < j) {
if (array[i] + array[j] == sum) {
result.add(array[i]);
result.add(array[j]);
return result;
} else if (array[i] + array[j] < sum) {
i++;
} else {
j--;
}
}
return result;
}
寻找和为s的连续序列
public static ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (sum <= 0) return result;
// 初始化将sum分为一大一小的2个数字
int small = sum / 2;
int big = sum / 2 + 1;
int curSum = small + big;
while (small >= 1) {
if (curSum == sum) {
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = small; i <= big; i++) {
list.add(i);
}
result.add(list);
// 通过添加更小的small，获得产生新的序列
small--;
curSum += small;
} else if (curSum > sum) {
// 偏大，则剪去big，加上更小的small
small--;
curSum = curSum - big + small;
big--;
} else {
// 偏小则再加一个更小的small
small--;
curSum += small;
}
}
// 序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
result.sort(Comparator.comparingInt(c -> c.get(0)));
return result;
}
数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
思路：
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个，赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
if (numbers == null || numbers.length <= 1) return false;
for (int i = 0; i < length; i++) {
while (numbers[i] != i) {
int m = numbers[i];
// 如果m和第m个数字相等，则说明m该去的位置被人占了，就找到了第一个重复的数字
if (m == numbers[m]) {
duplication[0] = m;
return true;
}
// 否则交换m到对应的第m个位置
numbers[i] = numbers[m];
numbers[m] = m;
}
}
return false;
}
}
构建乘积数组
先算左边部分A0–Ai，再乘以右边部分Ai-1—An-1
package offer;
/**
* 构建乘积数组
*
* @author jizx
* @date 2018/07/24 17:27
*/
public class Multiply {
public int[] multiply(int[] A) {
if (A == null || A.length == 0) return null;
int len = A.length;
int[] B = new int[len];
//自底向上地累乘A[i-1]
B[0] = 1;
for (int i = 1; i < len; i++) {
B[i] = B[i - 1] * A[i - 1];
}
//自上向下地在原来基础上，再累成A[i]
int temp = 1;//这就是右半部分的乘积
for (int i = len - 1; i >= 0; i--) {
B[i] = B[i] * temp;
temp = temp * A[i];
}
return B;
}
}
有序数组的交集
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 有序数组的交集
*
* @author jizx
* @date 2018/08/19 10:18
*/
public class Jiaoji {
public static void main(String[] args) {
int[] a = {1, 3, 8, 10, 11};
int[] b = {1, 3, 9, 10, 12};
ArrayList<Integer> result = new ArrayList<>();
jiaoji(a, b, result);
System.out.println(result);
}
public static void jiaoji(int[] a, int[] b, List<Integer> result) {
if (a == null || b == null || a.length == 0 || b.length == 0) return;
int[] min = a;
int[] max = b;
if (a.length > b.length) {
min = b;
max = a;
}
int index = Arrays.binarySearch(max, min[min.length / 2]);
if (index >= 0) {
result.add(max[index]);
// min中去除min[min.length / 2]，max中去除max[index]因为以及找到了
jiaoji(Arrays.copyOfRange(min, 0, min.length / 2), Arrays.copyOfRange(max, 0, index), result);
jiaoji(Arrays.copyOfRange(min, min.length / 2 + 1, min.length), Arrays.copyOfRange(max, index + 1, max
.length), result);
} else {
index = -index - 1;
jiaoji(Arrays.copyOfRange(min, 0, min.length / 2), Arrays.copyOfRange(max, 0, index), result);
jiaoji(Arrays.copyOfRange(min, min.length / 2 + 1, min.length), Arrays.copyOfRange(max, index, max.length),
result);
}
}
}
字符串
4.字符串替换空格（未实现）
- 先遍历一次字符串，这样就能统计出字符串中空格的总数
- 准备两个指针p1，p2,。p1指向原始字符串的末尾，p2指向替换后的字符串的末尾
- p1、p2同时移动，先前复制，直到p1遇到空格
- p2向前插入‘%20’
- p1、p2继续同时先前移动，直到p1与p2相遇
35.第一个只出现一次的字符
import java.util.*;
public class Solution {
public int FirstNotRepeatingChar(String str) {
// 非法输入检测
if (str == null || "".equals(str)) return -1;
char[] chars = str.toCharArray();
HashMap<Character, Integer> counter = new HashMap<>();
// 第一遍遍历进行统计
for (char c : chars) {
int num = counter.get(c) != null ? counter.get(c) + 1 : 1;
counter.put(c, num);
}
// 第二遍遍历进行搜索
int index = 0;
for (char c : chars) {
if (counter.get(c) == 1) return index;
index++;
}
return -1;
}
}
翻转单词顺序
public class Test {
public static void main(String[] args) {
System.out.println(ReverseSentence("student. a am I"));
}
public static String ReverseSentence(String str) {
if (str == null || str.length() <= 0) return "";
char[] chars = str.toCharArray();
// 先将整个字符串翻转
reverseChars(chars, 0, chars.length);
// 通过空格来定位每个单词的位置，然后进行单词的翻转
int start = 0;//指向单词第一个字符
int end = 0;//指向单词后的第一个空格
for (char c : chars) {
if (c != ' ') {
end++;
if (end == chars.length)
reverseChars(chars, start, end);
} else {
// start与end之间是一个单词的情况
if (start != end) {
reverseChars(chars, start, end);
}
end++;
start = end;// start移动到end位置
}
}
return new String(chars);
}
// start：翻转的开始位置，不包括end位置的字符
public static void reverseChars(char[] str, int start, int end) {
int i = start;
int j = end - 1;
while (i < j) {
char c = str[i];
str[i] = str[j];
str[j] = c;
i++;
j--;
}
}
}
左旋转字符串(循环左移字符串)
题目描述（推荐）：汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。
public class Test {
public static void main(String[] args) {
System.out.println(LeftRotateString("abcXYZdef",3));
}
public String LeftRotateString(String str,int n) {
if (str == null || str.length() <= 0) return "";
char[] chars = str.toCharArray();
// 通过3次翻转即可实现
reverseChars(chars,0,n);
reverseChars(chars,n,chars.length);
reverseChars(chars,0,chars.length);
return new String(chars);
}
// 字符翻转
public static void reverseChars(char[] str, int start, int end) {
int i = start;
int j = end - 1;
while (i < j) {
char c = str[i];
str[i] = str[j];
str[j] = c;
i++;
j--;
}
}
}
将字符串转换为整数
题目描述：
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
// 测试用例有:+123,-123,234k234
public static int StrToInt(String str) {
if (str == null || str.length() <= 0) return 0;
int result = 0;
boolean isMinus = false;
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
// 如果不是数字，则判断是否是在第一位的正负号
if (chars[i] < '0' || chars[i] > '9') {
if ((i != 0) || (chars[i] != '+' && chars[i] != '-')) return 0;
else {
if (chars[i] == '-') isMinus = true;
continue;
}
}
result = result * 10 + chars[i] - '0';// 注意字符要与‘0’进行相减，才是真正对应的数字
}
return isMinus ? -1 * result : result;
}
字符串判断是否为有效数值
package offer;
/**
* 判断字符串是否为有效的数值
*
* @author jizx
* @date 2018/07/24 17:45
*/
public class IsNumeric {
public static void main(String[] args) {
IsNumeric app=new IsNumeric();
System.out.println(app.isNumeric("-1.e0".toCharArray()));
}
public boolean isNumeric(char[] str) {
if (str == null || str.length == 0) return false;
boolean dot = false;
boolean e = false;
boolean sign = false;
for (int i = 0; i < str.length; i++) {
if ((str[i] == '+' || str[i] == '-')) {
if (i == 0) sign = true;// 首位
else if (str[i - 1] == 'e' || str[i - 1] == 'E') {} // 紧跟在e后面
else return false;
} else if (str[i] == 'e' || str[i] == 'E') {
if (e == true) return false;// 已经有e了
else if (i == str.length - 1) return false; // e后面没有数字了
else e = true;
} else if (str[i] == '.') {
// 在e后面，不能有小数点、或者已经有小数点了
if (e == true || dot == true) return false;
else dot = true;
} else {
if (str[i] < '0' || str[i] > '9') return false; // 其他非法字符
}
}
return true;
}
}
字符串的排列
import java.util.ArrayList;
import java.util.*;
public class Solution {
ArrayList<String> result = new ArrayList<String>();
public ArrayList<String> Permutation(String str) {
if (str == null || str.length() == 0) return result;
char[] chars = str.toCharArray();
permutation(0, chars);
//
HashSet<String> set=new HashSet<>(result);
result.clear();
result.addAll(set);
Collections.sort(result);
return result;
}
public void permutation(int prefix, char[] str) {
if (prefix == str.length) {
result.add(new String(str));
return;
}
// [a,b,c]，prefix表示固定的位置，比如a，然后将a与后面的字符依次进行交换
for (int i = prefix; i < str.length; i++) {
// 将固定位置的值与数组中的第i个字符交换
char temp = str[i];
str[i] = str[prefix];
str[prefix] = temp;
// 递归处理[b,c]
permutation(prefix + 1, str);
//还原交换
temp = str[i];
str[i] = str[prefix];
str[prefix] = temp;
}
}
}
链表
java实现链表
/**
* @author jizx
* @date 2018/04/20 15:09
*/
public class Test {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList();
list.add("a");
list.add("c");
list.add("bb");
list.insert(3, "1");
list.printList();
// System.out.println(list.find("2"));
System.out.println(list.search(3));
list.printList();
}
}
class LinkedList<E> {
private class Node<E> {
private E data;
Node next = null;
public Node() {
data = null;
}
public Node(E data) {
this.data = data;
}
}
private Node head;
private Node tail;
private int length;
public LinkedList() {
head = new Node();
tail = head;
length = 0;
}
public void add(E data) {
Node newNode = new Node(data);
tail.next = newNode;
tail = newNode;
length++;
}
public void insert(int position, E data) {
if (position >= 0 && position <= length) {
int i = 0;
Node current = head;
while (i < position) {
current = current.next;
i++;
}
Node temp = current.next;
Node newNode = new Node(data);
newNode.next = temp;
current.next = newNode;
} else {
System.out.println("超出范围");
}
length++;
}
public void remove(E data) {
Node pre = head;
Node current = head.next;
while (current != null) {
if (current.data.equals(data)) {
pre.next = current.next;
break;
} else {
pre = current;
current = current.next;
}
}
}
public void set(int position, E data) {
Node current = head.next;
while (current != null) {
if (current.data.equals(data)) {
break;
} else {
current = current.next;
}
}
}
public int find(E data) {
E result = null;
Node current = head.next;
int position = 0;
while (current != null) {
if (current.data.equals(data)) {
return position;
} else {
current = current.next;
position++;
}
}
return -1;
}
public E search(int position) {
int i = -1;
Node current = head;
if (position >= 0 && position < length) {
while (i < position) {
i++;
current = current.next;
}
return (E) current.data;
} else {
System.out.println("超出范围");
return null;
}
}
public int length() {
return length;
}
public void printList() {
Node current = head.next;
while (current != null) {
System.out.println(current.data);
current = current.next;
}
}
}
从尾到头打印链表
O(1)时间删除链表结点(未实现)
链表中倒数第k个节点
public class Test {
public static void main(String[] args) {
ListNode head = new ListNode(1);
ListNode cur = head;
for (int i = 2; i <= 5; i++) {
ListNode node = new ListNode(i);
cur.next = node;
cur = node;
}
try {
ListNode newHead = findKNode(head, 0);
while (newHead != null) {
System.out.println(newHead.val);
newHead = newHead.next;
}
} catch (Exception e) {
e.printStackTrace();
}
}
public static ListNode findKNode(ListNode head, int k) {
if (head == null|| k <= 0) {
return null;
}
ListNode ahead = head;
ListNode behind = ahead;
// 两者相差k-1个位置，因此ahead先走k-1个位置
for (int i = 0; i < k - 1; i++) {
if (ahead.next != null)
ahead = ahead.next;
else
return null;
}
// 然后两者一起移动
while (ahead.next != null) {
ahead = ahead.next;
behind = behind.next;
}
return behind;
}
}
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
反转链表
public class Test {
public static void main(String[] args) {
ListNode head = new ListNode(0);
ListNode cur=head;
for (int i = 1; i <= 10; i++) {
ListNode node = new ListNode(i);
cur.next = node;
cur = node;
}
try {
ListNode newHead = ReverseList(head);
while (newHead != null) {
System.out.println(newHead.val);
newHead = newHead.next;
}
} catch (Exception e) {
e.printStackTrace();
}
}
public static ListNode ReverseList(ListNode head) {
// 边界处理
if (head == null) return null;
if (head.next == null) return head;
ListNode remainHead = null; // h:剩余未反转的链表头
ListNode handlingNode = head; // i:正在处理的结点，从head开始，它的next指向原方向，因此正要反转
ListNode reversedHead = null; // j:已经反转的链表头
while (handlingNode != null) {
// 原来 reversedHead handlingNode --> remainHead -->k
// 反转 reversedHead <-- handlingNode remainHead -->k
remainHead = handlingNode.next;
handlingNode.next = reversedHead;
// 更新结点为下一次要处理的位置
reversedHead = handlingNode;
handlingNode = remainHead;
}
return reversedHead;
}
}
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
合并两个有序的链表
public class Test {
public static void main(String[] args) {
ListNode list1 = new ListNode(1);
ListNode list2 = new ListNode(2);
ListNode cur1 = list1;
ListNode cur2 = list2;
for (int i = 3; i <= 10; i++) {
ListNode node1 = new ListNode(i);
ListNode node2 = new ListNode(++i);
cur1.next = node1;
cur2.next = node2;
cur1 = node1;
cur2 = node2;
}
ListNode newHead = Merge(list1, list2);
while (newHead != null) {
System.out.print(newHead.val + " ");
newHead = newHead.next;
}
}
public static ListNode Merge(ListNode list1, ListNode list2) {
// 有一个链表为空，直接返回另一个链表
if (list1 == null) return list2;
if (list2 == null) return list1;
// 新链表的头结点初始化为较小的链表的头结点
ListNode head = list1.val < list2.val ? list1 : list2;
ListNode temp;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
temp = list1.next;
list1.next = list2;
list1 = temp;
} else {
temp = list2.next;
list2.next = list1;
list2 = temp;
}
}
return head;
}
}
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
复杂链表的复制
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
if(pHead==null){
return null;
}
copyChain(pHead);
copySibling(pHead);
return splitChain(pHead);
}
/**第一步：复制链表，暂时不考虑random 字段
* A->B->C 变为 A->A'->B->B'->C->C'
* */
public void copyChain(RandomListNode pHead) {
RandomListNode cur = pHead;
while (cur != null) {
RandomListNode n = new RandomListNode(cur.label);
n.next = cur.next;
cur.next = n;
cur = n.next;
}
}
/**第二步：考虑复制sibling字段*/
public void copySibling(RandomListNode pHead) {
RandomListNode cur = pHead;
while (cur != null) {
RandomListNode clone = cur.next;
RandomListNode sibling = cur.random;
if (sibling != null) {
clone.random = sibling.next;
}
cur = clone.next;
}
}
/**第三步：拆分链表，抽取出copy链表*/
public RandomListNode splitChain(RandomListNode pHead) {
RandomListNode copy = pHead.next;
RandomListNode cur1 = pHead;
RandomListNode cur2 = pHead.next;
while (cur1 != null && cur2 != null) {
cur1.next = cur2.next;
cur1 = cur1.next;
if(cur1!=null){
cur2.next=cur1.next;
}
cur2=cur2.next;
}
return copy;
}
}
查找链表的中间节点（未实现）
思路：采用快慢指针的方式查找单链表的中间节点，快指针一次走两步，慢指针一次走一步，当快指针走完时，慢指针刚好到达中间节点
两个链表的第一个公共结点
import java.util.*;
public class Test {
public static void main(String[] args) {
ListNode a1=new ListNode(1);
ListNode a2=new ListNode(2);
ListNode a3=new ListNode(3);
ListNode a4=new ListNode(4);
ListNode a5=new ListNode(5);
ListNode a6=new ListNode(6);
ListNode a7=new ListNode(7);
a1.next=a2;
a2.next=a3;
a3.next=a6;
a4.next=a5;
a5.next=a6;
a6.next=a7;
System.out.println(FindFirstCommonNode(a1,a4));
}
public static ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) return null;
// 先遍历一遍找出两个链表的长度
int len1 = getLength(pHead1);
int len2 = getLength(pHead2);
ListNode longList = pHead1;
ListNode shortList = pHead2;
int diff = len1 - len2;
if (len1 < len2) {
longList = pHead2;
shortList = pHead1;
diff = len2 - len1;
}
// 然后让长的链表先走多的长度
for (int i = 0; i < diff; i++) {
longList = longList.next;
}
// 最后一起走，第一个相同结点就是公共结点
while (longList != null && shortList != null) {
if (longList == shortList){
return longList;
}
longList = longList.next;
shortList = shortList.next;
}
return null;
}
public static int getLength(ListNode list) {
int len = 0;
ListNode current = list;
while (current != null) {
current = current.next;
len++;
}
return len;
}
}
链表中环的入口节点
如果一个链表中包含环，如何找出环的入口节点？
import java.util.*;
/**
* 链表中环的入口
*
* @author jizx
* @date 2018/07/03 18:39
*/
public class EntryNodeOfLoop {
public static void main(String[] args) {
EntryNodeOfLoop app = new EntryNodeOfLoop();
ListNode a1=new ListNode(1);
ListNode a2=new ListNode(2);
ListNode a3=new ListNode(3);
ListNode a4=new ListNode(4);
ListNode a5=new ListNode(5);
ListNode a6=new ListNode(6);
a1.next=a2;
a2.next=a3;
a3.next=a4;
a4.next=a5;
a5.next=a6;
a6.next=a3;
System.out.println(app.EntryNodeOfLoop(null));
}
public ListNode EntryNodeOfLoop(ListNode pHead) {
// 1.判断是否有环,如果有则返回环内的一个节点
ListNode loopNode = meetingNode(pHead);
if (loopNode == null) return null;
// 2.计数环的长度
int count = 1;
ListNode search = loopNode.next;
while (loopNode != search) {
count++;
search = search.next;
}
// 3.找到入口
ListNode behind = pHead;// 慢指针
ListNode prev = pHead;//快指针
// 让快指针先走count个节点，这样才能保证他们相遇的节点是入口节点
while (count-- > 0) {
prev = prev.next;
}
while(prev!=behind){
prev=prev.next;
behind=behind.next;
}
return prev;
}
/**
* 使用快慢指针，当其相遇时有环，快指针==null时无环
*/
private ListNode meetingNode(ListNode head) {
if (head == null) return null;
ListNode slow = head;// 慢指针
ListNode fast = slow.next;//快指针
while (slow != null && fast != null) {
// 如果快慢指针相遇、快指针的下一个是慢指针，则有环
if (slow == fast || fast.next == slow) {
return slow;
}
// 更新快慢指针位置
slow = slow.next;
fast = fast.next;
if (fast != null) fast = fast.next;
}
return null;
}
}
删除链表中重复的结点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
/**
* 删除链表中重复的结点
*
* @author jizx
* @date 2018/07/06 10:41
*/
public class DeleteDuplication {
public static void main(String[] args) {
DeleteDuplication app = new DeleteDuplication();
int[] nums = {1, 1, 2, 3, 3, 4, 5, 5};
ListNode a1 = app.create(nums);
a1 = app.deleteDuplication(a1);
while (a1 != null) {
System.out.print(a1.val + "-->");
a1 = a1.next;
}
}
public ListNode deleteDuplication(ListNode pHead) {
// null或者只有一个结点时 直接返回
if (pHead == null || pHead.next == null) return pHead;
ListNode newHead = new ListNode(0);// 新链表的头结点
newHead.next = pHead;
ListNode pre = newHead;// 记录前一个不重复的结点
ListNode cur = pre.next;// 当前结点
while (cur != null && cur.next != null) {
// 当前结点与下一结点相等
if (cur.val == cur.next.val) {
do{
cur = cur.next;
}
while (cur.next != null && cur.next.val == cur.val);
cur = cur.next; // 更新到这个暂时不重复的点
pre.next = cur; // pre的next连接到这个暂时不重复的点
}
// 当前结点与下一结点不相等
else {
pre = cur;// 则pre更新到这个可以确认是不重复的点上
cur = cur.next; // 移动cur
}
}
return newHead.next;
}
// 保留一个重复结点
public ListNode deleteDuplication2(ListNode pHead) {
ListNode p = pHead;
while (p != null) {
ListNode q = p;
while (q.next != null) {
if (p.val == q.next.val) {
q.next = q.next.next;
} else
q = q.next;
}
p = p.next;
}
return pHead;
}
public ListNode create(int[] nums) {
ListNode cur = new ListNode(0);
ListNode head = cur;
for (int i = 0; i < nums.length; i++) {
cur.next = new ListNode(nums[i]);
cur = cur.next;
}
return head.next;
}
}
树
重建二叉树
public class Solution {
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
if (pre.length == 0 || in.length == 0) {
return null;
}
//先取【先序】的第一个元素，作为根结点
TreeNode root = new TreeNode(pre[0]);
//然后遍历【中序】，找到对应的根结点，进行划分数组
for (int i = 0; i < in.length; i++) {
if (in[i] == pre[0]) {
//注意i对应的是中序的下标，因此是截取pre[1，i+1]
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1,
in.length));
}
}
return root;
}
}
层序遍历
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> result=new ArrayList<>();
if(root==null){
return result;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode node=queue.poll();
result.add(node.val);
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
}
return result;
}
树的子结构
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean isTree = false;
if (root1 != null && root2 != null) {
// 如果当前两个根结点相等，则进行检查
if (root1.val == root2.val) isTree = isSubTree(root1, root2);
// 否则递归对root1的左子树判断
if (!isTree) isTree = HasSubtree(root1.left, root2);
// 左子树也没有，则递归对root1的右子树判断
if (!isTree) isTree = HasSubtree(root1.right, root2);
}
return isTree;
}
public boolean isSubTree(TreeNode root1, TreeNode root2) {
if(root2==null) return true; //root2匹配完了，因此true
if(root1==null) return false; //root2不为null而root1==null，则不相同
if(root1.val!=root2.val) return false;
//当前结点相等，则判断左子树，然后判断右子树
return isSubTree(root1.left, root2.left) && isSubTree(root1.right, root2.right);
}
}
二叉树的镜像
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
// 先序遍历的方法
public static void Mirror(TreeNode root) {
if (root == null) {
return;
}
// 交换子节点
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 递归处理子节点
Mirror(root.left);
Mirror(root.right);
}
}
二叉搜索树的后序遍历序列
public class Test {
public static void main(String[] args) {
int[] a = {5, 7, 6, 9, 11, 10, 8};
int[] b = {6, 8, 7, 5};
int[] c = {4, 8, 6, 12, 16, 14, 10};
int[] d = {};
System.out.println(VerifySquenceOfBST(d));
}
public static boolean VerifySquenceOfBST(int[] sequence) {
// 为空则false
if (sequence == null || sequence.length == 0) {
return false;
}
// 只有一个点，则为true，直接返回不用递归了
if (sequence.length == 1) {
return true;
}
int i = 0;
int high = sequence.length - 1;
int root = sequence[high];
// 以root判断大小，寻找划分点，i最终会落在第一个大于root的位置
while (sequence[i] < root) {
i++;
}
//判断右子树是否都大于root，否则就不可能是后序遍历
for (int j = i; j < high; j++) {
if (root > sequence[j])
return false;
}
// copyOfRange : [begin,end),不包含end
int[] leftTree = Arrays.copyOfRange(sequence, 0, i);
int[] rightTree = Arrays.copyOfRange(sequence, i, high);
boolean leftResult = true;
boolean rightResult = true;
if (leftTree.length > 0) {
leftResult = VerifySquenceOfBST(leftTree);
}
if (rightTree.length > 0) {
rightResult = VerifySquenceOfBST(rightTree);
}
return leftResult && rightResult;
}
}
二叉树中和为某一值的路径
public static ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
ArrayList<ArrayList<Integer>> allRoad = new ArrayList<ArrayList<Integer>>();
if (root != null) {
Stack<Integer> road = new Stack<>();
path(root, target, road, 0, allRoad);
}
return allRoad;
}
public static void path(TreeNode root, int target, Stack<Integer> road, int currentSum, ArrayList<ArrayList<Integer>> allRoad) {
currentSum = root.val + currentSum;
TreeNode left = root.left;
TreeNode right = root.right;
// 超过目标值，不必向下继续
if (currentSum > target) {
return;
}
// 叶结点,但值不等于目标值,返回
if (left == null && right == null && currentSum != target) {
return;
}
road.push(root.val);
// 叶结点，值等于目标值，添加路径
if (left == null && right == null && currentSum == target) {
ArrayList<Integer> result = new ArrayList<Integer>();
for (int i : road) {
result.add(i);
}
allRoad.add(result);
}
if (left != null) {
path(left, target, road, currentSum, allRoad);
}
if (right != null) {
path(right, target, road, currentSum, allRoad);
}
road.pop();
}
二叉搜索树与双向链表转换
public class Test {
public static void main(String[] args) {
TreeNode n1 = new TreeNode(1);
TreeNode n2 = new TreeNode(2);
TreeNode n3 = new TreeNode(3);
TreeNode n4 = new TreeNode(4);
TreeNode n5 = new TreeNode(5);
TreeNode n6 = new TreeNode(6);
TreeNode n7 = new TreeNode(7);
//构建树
n4.left = n2;
n4.right = n6;
n2.left = n1;
n2.right = n3;
n6.left = n5;
n6.right = n7;
Convert(n4);
}
public static TreeNode Convert(TreeNode pRootOfTree) {
TreeNode lastVisitNode = null;
// 注意，不可以将lastVisitNode直接传入，因为就像传入null，不会赋值给lastVisitNode
lastVisitNode = convertNode(pRootOfTree, lastVisitNode);
// 完成转换，从lastVisitNode往前遍历，到头结点
TreeNode first = lastVisitNode;
while (first != null) {
if(first.left==null) break;
first = first.left;
}
return first;
}
/**
* currentNode：当前节点
* lastVisitNode：最后访问的节点，同时也是双向链表的最右节点
*/
public static TreeNode convertNode(TreeNode currentNode, TreeNode lastVisitNode) {
if (currentNode == null) return null;
//先处理左子树，同时获得左子树最右边的点（最大点）
if (currentNode.left != null) {
lastVisitNode = convertNode(currentNode.left, lastVisitNode);
}
//互相连接，当前节点的left连接lastVisitNode,同时lastVisitNode的right连接当前节点
currentNode.left = lastVisitNode;
if (lastVisitNode != null) lastVisitNode.right = currentNode;
lastVisitNode = currentNode; //最后访问的节点更新为当前节点
// 处理右子树
if (currentNode.right != null) {
lastVisitNode = convertNode(currentNode.right, lastVisitNode);
}
return lastVisitNode;
}
}
class TreeNode {
int val = 0;
TreeNode left = null; // 连接小的结点
TreeNode right = null; // 连接大的结点
public TreeNode(int val) {
this.val = val;
}
}
二叉树的深度,以及是否是平衡二叉树
public class Test {
public static void main(String[] args) {
}
public static int TreeDepth(TreeNode root) {
if (root == null) return 0;
int leftDepth = TreeDepth(root.left);
int rightDepth = TreeDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Test {
public static void main(String[] args) {
TreeNode a1 = new TreeNode(1);
TreeNode a2 = new TreeNode(2);
TreeNode a3 = new TreeNode(3);
TreeNode a4 = new TreeNode(4);
TreeNode a5 = new TreeNode(5);
TreeNode a6 = new TreeNode(6);
TreeNode a7 = new TreeNode(7);
TreeNode a8 = new TreeNode(8);
a1.left=a2;
a1.right=a3;
a2.left=a4;
a2.right=a5;
a5.right=a7;
a3.left=a8;
a3.right=a6;
System.out.println(IsBalanced_Solution(a1));
}
public static boolean IsBalanced_Solution(TreeNode root) {
if (root == null) return true;
return isBalanced(root) != -1;
}
// 返回值 -1：非平衡树，0：null结点，正数：树的深度
public static int isBalanced(TreeNode root) {
if (root == null) return 0;
int leftDepth = isBalanced(root.left);
int rightDepth = isBalanced(root.right);
// 如果左右子树都是平衡树，则进行深度比较；如果深度差满足要求，则返回最大深度
if (leftDepth != -1 && rightDepth != -1) {
if (Math.abs(leftDepth - rightDepth) <= 1) {
return Math.max(leftDepth, rightDepth) + 1;
}
}
return -1;
}
}
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
中序遍历二叉树,求某一节点的下一中序节点
public static TreeLinkNode GetNext(TreeLinkNode pNode) {
if (pNode == null) return null;
// 1.有右结点，则找该右结点的最左结点
if (pNode.right != null) {
pNode = pNode.right;
while (pNode.left != null) {
pNode = pNode.left;
}
return pNode;
}
/* 2.没有右节点，则向上找父节点
a a
b b
c c
d d
c是当前节点。确定c是在某个节点(a)的左子树中，还是(a)的右子树中；
如果在左子树中，则找到的第一个包含c的节点就是下一个中序输出的节点；
否则，就没有下一个节点了
* */
TreeLinkNode parent = pNode.next;
while (parent != null) {
if (parent.left == pNode) return parent;
pNode = parent;
parent = parent.next;
}
return null;
}
二叉搜索树的第k个结点
给定一颗二叉搜索树，请找出其中的第k小的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
序列化二叉树
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
// 序列化
String Serialize(TreeNode root) {
if (root == null) return "";
String node = Integer.toString(root.val);
node += ",";//父节点后添加逗号
if (root.left == null)
node += "#";
else
node += Serialize(root.left);
node += ",";//左节点后添加逗号
if (root.right == null)
node += "#";
else
node += Serialize(root.right);
//右节点后 不添加逗号
return node;
}
// 反序列化
TreeNode Deserialize(String str) {
if (str == null || str.length() <= 0) return null;
String[] nodes = str.split(",");
return Deserialize2(nodes);
}
// 正在处理的结点下标
int index=0;
TreeNode Deserialize2(String[] nodes) {
String node = nodes[index++];
if ("#".equals(node)) return null;
TreeNode root = new TreeNode(Integer.parseInt(node));
root.left = Deserialize2(nodes);
root.right = Deserialize2(nodes);
return root;
}
}
队列与栈
两个栈实现队列
import java.util.Stack;
public class Solution {
Stack<Integer> inStack = new Stack<Integer>();// 入队保存的栈
Stack<Integer> outStack = new Stack<Integer>(); // 出队保存的栈
private int size = 0;
public void push(int node) {
inStack.push(node);
size++;
}
public int pop() {
if (size == 0) return -1;
size--;
if (outStack.isEmpty()) {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
return outStack.pop();
}
}
用两个队列实现栈（未实现）
包含min函数的栈
class Solution {
Stack<Integer> stack = new Stack<>();
Stack<Integer> minStack = new Stack<>();
public void push(int node) {
stack.push(node);
if (minStack.empty()) {
minStack.push(node);
return;
}
if (node < minStack.peek()) {
minStack.push(node);
} else {
minStack.push(minStack.peek());
}
}
public void pop() {
if (!stack.empty()) {
stack.pop();
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int min() {
return minStack.peek();
}
}
栈的压入、弹出序列
public class Test {
public static void main(String[] args) {
int [] a={1,2,3,4,5};
int [] b={4,5,3,1,2};
System.out.println(IsPopOrder(a,b));
}
public static boolean IsPopOrder(int[] pushA, int[] popA) {
Stack<Integer> stack = new Stack<>();
int i = 0, j = 0, lena = pushA.length, lenb = popA.length;
boolean isPopOrder = true;
while (i < lena) {
stack.push(pushA[i]);
i++;
// 栈顶与popA[j]相同，则出栈，否则继续进栈
while (stack.peek() == popA[j] && j < lenb) {
stack.pop();
j++;
}
}
// 栈不为空，或者popA没有遍历完，则不是
if (!stack.isEmpty() || j != lenb) {
isPopOrder = false;
}
return isPopOrder;
}
}
排序
员工年龄排序
public class Test {
public static void main(String[] args) {
int[] a = {23,26,27,28,25,30,54,23,23};
sortAge(a);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
public static int[] sortAge(int[] arr) {
if (arr == null || arr.length == 0) {
return null;
}
int oldest = 100;
// 创建0-100的数组来统计每个年龄有多少人
int[] ages = new int[oldest + 1];
// 遍历数组进行统计
for (int i = 0; i < arr.length; i++) {
int age = arr[i];
ages[age]++;
}
int index = 0;
// 遍历统计的数组，将年龄存回原数组
for (int age = 0; age <= oldest; age++) {
for (int i = 0; i < ages[age]; i++) {
arr[index] = age;
index++;
}
}
return arr;
}
}
回溯法
矩阵中的路径
/**
* 判断矩阵中是否有路径
*
* @author jizx
* @date 2018/07/09 20:18
*/
public class HasPath {
public static void main(String[] args) {
HasPath app = new HasPath();
char[] matrix = "ABCESFCSADEE".toCharArray();
char[] str = "ABCB".toCharArray();
System.out.println(app.hasPath(matrix, 3, 4, str));
}
public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
if (matrix == null || rows < 1 || cols < 1 || str == null) return false;
boolean[][] visited = new boolean[rows][cols];
// 遍历矩阵中每个位置，穷举
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (findStr(matrix, rows, cols, i, j, str, visited))
return true;
}
}
return false;
}
private int strIndex = 0;
private boolean findStr(char[] matrix, int rows, int cols, int row, int col, char[] str, boolean[][] visited) {
if (strIndex == str.length) return true;
boolean find = false;
// 矩阵中matrix[row][col] 的字符 与 str[strIndex]的相同，则继续探索该位置的四周与str[strIndex++]是否一样
if (row >= 0 && row < rows && col >= 0 && col < cols && !visited[row][col] && matrix[row * cols + col] == str[strIndex]) {
strIndex++;
visited[row][col] = true;
find = findStr(matrix, rows, cols, row - 1, col, str, visited) ||
findStr(matrix, rows, cols, row + 1, col, str, visited) ||
findStr(matrix, rows, cols, row, col - 1, str, visited) ||
findStr(matrix, rows, cols, row, col + 1, str, visited);
// 如果该点的四周都没有找到符合下一字符的，则退回，重置该位置的状态，以及字符匹配的位置
if (!find) {
visited[row][col] = false;
strIndex--;
}
}
return find;
}
}
机器人的运动范围
/**
* 机器人的运动范围
*
* @author jizx
* @date 2018/07/09 21:45
*/
public class RobotMovingCount {
public static void main(String[] args) {
RobotMovingCount app = new RobotMovingCount();
System.out.println(app.movingCount(18, 3, 4));
}
public int movingCount(int threshold, int rows, int cols) {
if (rows < 0 || cols < 0 || threshold < 0) return 0;
boolean[][] visited = new boolean[rows][cols];
return movingCount(threshold, rows, cols, 0, 0, visited);
}
public int movingCount(int threshold, int rows, int cols, int row, int col, boolean[][] visited) {
int count = 0;
if (canIn(rows, cols, row, col, threshold, visited)) {
visited[row][col] = true;
// 能够到达的位置：当前位置+其他四个方向能够到达的总和
count = 1 + movingCount(threshold, rows, cols, row - 1, col, visited) +
movingCount(threshold, rows, cols, row + 1, col, visited) +
movingCount(threshold, rows, cols, row, col - 1, visited) +
movingCount(threshold, rows, cols, row, col + 1, visited);
}
return count;
}
// 判断是否能进入该位置
public boolean canIn(int rows, int cols, int row, int col, int threshold, boolean[][] visited) {
if (!visited[row][col] && row >= 0 && row < rows && col >= 0 && col < cols) {
int sum = 0;
while (row != 0) {
sum += row % 10;
row /= 10;
}
while (col != 0) {
sum += col % 10;
col /= 10;
}
return sum <= threshold;
}
return false;
}
}
递归
斐波那契数数列
public class Solution {
// 非递归
public int Fibonacci(int n) {
int[] initial = {0, 1}; //初始化第0项、第1项
if (n < 2) return initial[n];
// fn=f(n-1)+f(n-2)
int fn_1 = 1;
int fn_2 = 0;
int fn = 0;
for (int i = 2; i <= n; i++) {
fn = fn_1 + fn_2;
fn_2 = fn_1;
fn_1 = fn;
}
return fn;
}
}
青蛙跳台阶
但是要注意与斐波那契数列的下标起始位置不太一样 ，第0 项是1,即：1 1 2 3 5 。。。
public static int JumpFloor(int target) {
int[] initial = {0, 1};
if (target < 2) return initial[target];
int jumpn_1 = 1; //第1项是1
int jumpn_2 = 1; //第0项是1
int num = 0;
for (int i = 2; i <= target; i++) {
num = jumpn_1 + jumpn_2;
jumpn_2 = jumpn_1;
jumpn_1 = num;
}
return num;
}
矩阵覆盖问题
二进制
10.二进制中1的个数
用1扫描法：
public static int numOf1(int n) {
int count = 0;
int matcher = 1;
while (matcher != 0) {
// n与matcher按位 与运算，如果matcer的1 对应n的1，就不会为0
// n:0000101
// m:0000100
if ((n & matcher) != 0) count++;
//让matcer左移，进行扫描
matcher = matcher << 1;
}
return count;
}
减1法
public static int numOf1(int n) {
int count = 0;
while (n != 0) {
// 把一个整数减去1，再和原整数做 与运算，就会把该整数最右边一个1变成0
n = (n - 1) & n;
count++;
}
return count;
}
数值
精度问题
由于精度原因，不能用等号判断两个double 小数是否相等。
当小数点后位数 大于15位时，jvm就会忽略这个精度，这种情况，我们在开发时如果需要更精确的比较double类型，就要用到 BigDecimal 这个类了。
// jdk1.8
double x1= 4.000000000000002;
double x2= 4.000000000000005;
x1<x2 true
BigDecimal x3=new BigDecimal(4.0000000000000002);
BigDecimal x4=new BigDecimal(4.0000000000000005);
x3<x4 true
000000000000002 // double(15位)
0000000000000002 // BigDecimal（16位）
数值的整数次方pow(x,n)
思路：分治
简洁版
public double pow(double x, int n) {
// 底数为0,不可以直接用等号判断，因为有精度的问题
if (Double.compare(x, 0.0) == 0) return 0.0;
//指数<0的情况，取绝对值，最后进行求倒数即可
if (n < 0) return 1.0 / powWithUnsign(x, -n);
else return powWithUnsign(x, n);
}
public double powWithUnsign(double x, int n) {
if (n == 0) return 1.0;
if (n == 1) return x;
double result = powWithUnsign(x, n/2);
if ((n&1) == 1)
return result * result * x;
else
return result * result;
}
详细版
public static double Power(double basse, int exponent) throws Exception {
// 输入底数为0，指数小于0
if (Double.compare(basse, 0.0) == 0 && exponent < 0) {
throw new Exception("非法");
}
int absExponent = exponent;//指数取绝对值
if (exponent < 0) {
absExponent = exponent * -1;
}
double result = PowerWithUnsignedExponent(basse, absExponent);
if (exponent < 0) {
result = 1.0 / result;
}
return result;
}
public static double PowerWithUnsignedExponent(double base, int exponent) {
// 判断人为输入为0的情况，并不是右移产生的
if (exponent == 0) {
return 1;
}
if (exponent == 1) {
return base;
}
double result = PowerWithUnsignedExponent(base, exponent >> 1);
result *= result;
if ((exponent & 0x1) == 1) {
result *= base;
}
return result;
}
打印1到最大的n位数
public static void printNMax(int n) {
if (n <= 0) {
return;
}
char[] number = new char[n];
for (int i = 0; i < number.length; i++) {
number[i] = '0';
}
int a = number[1];
while (!increase(number, 8)) {
printNum(number);
}
}
public static boolean increase(char[] number, int add) {
int sum = 0;
int takeOver = 0;// 进位
boolean isMax = false;
// 从最后一位开始加一
for (int i = number.length - 1; i >= 0; i--) {
sum = number[i] - '0' + takeOver;
// 个位进行加一
if (i == number.length - 1) {
sum += add;
}
// 和大于10，则有进位，否则就可以结束循环
if (sum >= 10) {
// 如果是最高位，则结束
if (i == 0) isMax = true;
else {
sum -= 10;
takeOver = 1;
number[i] = (char) ('0' + sum);
}
} else {
number[i] = (char) ('0' + sum);
break;
}
}
return isMax;
}
public static void printNum(char[] number) {
int i = 0;
boolean isStart = false;
while (i < number.length) {
if (number[i] == '0' && !isStart) {
} else {
isStart = true;
System.out.print(number[i]);
}
i++;
}
System.out.println();
}
34.丑数
public static int GetUglyNumber_Solution(int index) {
if (index <= 0) {
return 0;
}
// 保存丑数的数组，并初始化第一个丑数
int[] uglyNum = new int[index];
uglyNum[0] = 1;
// 指向对应乘积刚好大于当前找到的丑数的下标
int base2 = 0;// 乘以2后的值，刚好略大于当前丑数的下标
int base3 = 0;// 乘以3后的值，刚好略大于当前丑数的下标
int base5 = 0;// 乘以5后的值，刚好略大于当前丑数的下标
int currentIndex = 1;
while (currentIndex < index) {
int nextNum = Math.min(Math.min(uglyNum[base2] * 2, uglyNum[base3] * 3), uglyNum[base5] * 5);
uglyNum[currentIndex] = nextNum;
// 更新下标，使得下标在刚好略大于当前丑数的下标
while (uglyNum[base2] * 2 <= nextNum) base2++;
while (uglyNum[base3] * 3 <= nextNum) base3++;
while (uglyNum[base5] * 5 <= nextNum) base5++;
currentIndex++;
}
return uglyNum[index - 1];
}
不用加减乘除做加法
思路：
public class Solution {
public int Add(int num1,int num2) {
int sum = 0;
int carry = 0;
do {
sum = num1 ^ num2;
carry = (num1 & num2) << 1;
num1 = sum;
num2 = carry;
} while (carry != 0);
return num1;
}
}
不使用新变量交换两个变量的值
// 基于加减法
a = a + b;
b = a - b;
a = a - b;
// 基于异或
a = a ^ b;
b = a ^ b;
a = a ^ b;
抽象建模
44.扑克牌的顺子
import java.util.*;
public class Solution {
public boolean isContinuous(int [] numbers) {
if (numbers == null || numbers.length != 5) return false;
Arrays.sort(numbers);
// 统计大王的个数
int king = 0;
for (int i : numbers) {
if (i == 0) king++;
else break;
}
// 统计不连续间隔
int gaps = 0;
// i=king的个数+1，从而跳过王
for (int i = king+1; i < numbers.length; i++) {
if (numbers[i] == numbers[i - 1]) return false; // 出现对子，不可能是顺子
gaps += numbers[i] - numbers[i - 1] - 1;
}
return gaps <= king;
}
}
