二分查找算法
public class BinarySearch {
public static void main(String[] args) {
int arr[] = {
1, 2, 3, 4, 5};
System.out.println(binarySearch2(arr, 0, arr.length - 1, 4));
}
//使用递归
static int binarySearch(int[] arr, int left, int right, int findVal) {
if (left > right) return -1;
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal > midVal) {
return binarySearch(arr, mid + 1, right, findVal);
} else if (findVal < midVal) {
return binarySearch(arr, left, mid - 1, findVal);
} else {
return mid;
}
}
//使用非递归
static int binarySearch2(int[] arr, int left, int right, int findVal) {
while (left <= right) {
int mid = (left + right) / 2;
int midVal = arr[mid];
if (findVal < midVal) {
right = mid - 1;
} else if (findVal > midVal) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
}
汉诺塔问题
public class Hanoitower {
public static void main(String[] args) {
hanoiTower(3, "A", "B", "C");
}
//汉诺塔的移动的方法
//使用分治算法
public static void hanoiTower(int num, String a, String b, String c) {
//如果只有一个盘
if(num == 1) {
System.out.println("第1个盘从 " + a + "->" + c);
} else {
//如果我们有 n >= 2 情况，我们总是可以看做是两个盘 1.最下边的一个盘 2. 上面的所有盘
//1. 先把 最上面的所有盘 A->B， 移动过程会使用到 c
hanoiTower(num - 1, a, c, b);
//2. 把最下边的盘 A->C
System.out.println("第" + num + "个盘从 " + a + "->" + c);
//3. 把B塔的所有盘 从 B->C , 移动过程使用到 a塔
hanoiTower(num - 1, b, a, c);
}
}
}
全排列
public class FullSort {
public static void main(String[] args) {
int[] arr = {
1, 2, 3};
fullSort(arr, 0, arr.length - 1);
}
private static void fullSort(int[] arr, int start, int end) {
// 递归终止条件
if (start == end) {
for (int i : arr) {
System.out.print(i);//一次递归结束。将整个数组打印出来
}
System.out.println();
return;
}
for (int i = start; i <= end; i++) {
swap(arr, i, start);
fullSort(arr, start + 1, end);// 把剩下的元素都做全排列。
swap(arr, i, start); // 然后再交换回去，数组还原，保证下一次不会有重复交换。
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
背包问题-动态规划
public class KnapsackProblem {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] w = {
1, 4, 3};//物品的重量
int[] val = {
1500, 3000, 2000}; //物品的价值 这里val[i] 就是前面讲的v[i]
int m = 4; //背包的容量
int n = val.length; //物品的个数
//创建二维数组，
//v[i][j] 表示在前i个物品中能够装入容量为j的背包中的最大价值
int[][] v = new int[n+1][m+1];
//为了记录放入商品的情况，我们定一个二维数组
int[][] path = new int[n+1][m+1];
//初始化第一行和第一列, 这里在本程序中，可以不去处理，因为默认就是0
for(int i = 0; i < v.length; i++) {
v[i][0] = 0; //将第一列设置为0
}
for(int i=0; i < v[0].length; i++) {
v[0][i] = 0; //将第一行设置0
}
//根据前面得到公式来动态规划处理
for(int i = 1; i < v.length; i++) {
//不处理第一行 i是从1开始的
for(int j=1; j < v[0].length; j++) {
//不处理第一列, j是从1开始的
//公式
if(w[i-1]> j) {
// 因为我们程序i 是从1开始的，因此原来公式中的 w[i] 修改成 w[i-1]
v[i][j]=v[i-1][j];
} else {
//说明:
//因为我们的i 从1开始的， 因此公式需要调整成
//v[i][j]=Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]);
//v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
//为了记录商品存放到背包的情况，我们不能直接的使用上面的公式，需要使用if-else来体现公式
if(v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
//把当前的情况记录到path
path[i][j] = 1;
} else {
v[i][j] = v[i - 1][j];
}
}
}
}
//输出一下v 看看目前的情况
for(int i =0; i < v.length;i++) {
for(int j = 0; j < v[i].length;j++) {
System.out.print(v[i][j] + " ");
}
System.out.println();
}
System.out.println("============================");
//输出最后我们是放入的哪些商品
//遍历path, 这样输出会把所有的放入情况都得到, 其实我们只需要最后的放入
// for(int i = 0; i < path.length; i++) {
// for(int j=0; j < path[i].length; j++) {
// if(path[i][j] == 1) {
// System.out.printf("第%d个商品放入到背包\n", i);
// }
// }
// }
//动脑筋
int i = path.length - 1; //行的最大下标
int j = path[0].length - 1; //列的最大下标
while(i > 0 && j > 0 ) {
//从path的最后开始找
if(path[i][j] == 1) {
System.out.printf("第%d个商品放入到背包\n", i);
j -= w[i-1]; //w[i-1]
}
i--;
}
}
}
KMP算法（匹配字符串）
public class KMPAlgorithm {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
//String str2 = "BBC";
int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0]
System.out.println("next=" + Arrays.toString(next));
int index = kmpSearch(str1, str2, next);
System.out.println("index=" + index); // 15了
}
//写出我们的kmp搜索算法
/**
* @param str1 源字符串
* @param str2 子串
* @param next 部分匹配表, 是子串对应的部分匹配表
* @return 如果是-1就是没有匹配到，否则返回第一个匹配的位置
*/
private static int kmpSearch(String str1, String str2, int[] next) {
//遍历
for (int i = 0, j = 0; i < str1.length(); i++) {
//需要处理 str1.charAt(i) ！= str2.charAt(j), 去调整j的大小
//KMP算法核心点, 可以验证...
while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
j = next[j - 1];
}
if (str1.charAt(i) == str2.charAt(j)) {
j++;
}
if (j == str2.length()) {
//找到了 // j = 3 i
return i - j + 1;
}
}
return -1;
}
//获取到一个字符串(子串) 的部分匹配值表
private static int[] kmpNext(String dest) {
//创建一个next 数组保存部分匹配值
int[] next = new int[dest.length()];
next[0] = 0; //如果字符串是长度为1 部分匹配值就是0
for (int i = 1, j = 0; i < dest.length(); i++) {
//当dest.charAt(i) != dest.charAt(j) ，我们需要从next[j-1]获取新的j
//直到我们发现 有 dest.charAt(i) == dest.charAt(j)成立才退出
//这时kmp算法的核心点
while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
j = next[j - 1];
}
//当dest.charAt(i) == dest.charAt(j) 满足时，部分匹配值就是+1
if (dest.charAt(i) == dest.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}
}
青蛙跳台阶
链接：https://www.nowcoder.com/questionTerminal/8c82a5b80378478f9484d87d1c5f12a4?f=discussion
来源：牛客网
//递归方法
int jumpFloor(int number)
{
if(number<=2)
return number;
else
return jumpFloor(number-1)+jumpFloor(number-2);
}
//使用迭代
public static int JumpFloor(int target) {
if (target == 0)
return 1;
if (target == 1)
return 1;
int si_1 = 1;
int si_2 = 1;
int result = 0;
for (int i = 2; i <= target; i++) {
result = si_1 + si_2;
si_2 = si_1;
si_1 = result;
}
return result;
}
旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
//二分法主键缩短距离
public int minNumberInRotateArray(int[] nums) {
if (nums.length == 0)
return 0;
int l = 0, h = nums.length - 1;
while (l < h) {
int m = (l + h) / 2;
if (nums[m] <= nums[h])
h = m;
else
l = m + 1;
}
return nums[l];
}
//暴力匹配法
public int minNumberInRotateArray(int[] array) {
if (array.length == 0)
return 0;
for (int i = 0; i < array.length - 1; i++) {
if (array[i] > array[i + 1])
return array[i + 1];
}
return array[0];
}
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: