排序
/**
* 插入排序
*
* @param arr
*/
public static void insertSort(int arr[]) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i;
while (j > 0 && temp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp;
}
}
/**
* 冒泡排序
*
* @param array
*/
public static void bubbleSort(int array[]) {
if (array == null || array.length == 0) {
return;
}
for (int i = 0; i < array.length - 1; i++) {// 執(zhí)行n-1趟
boolean flag = false;// 標(biāo)志位降瞳，判斷這一趟排序是否有交換位置
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j] > array[j + 1]) {
// 利用異或的自反性交換值
array[j] = array[j] ^ array[j + 1];
array[j + 1] = array[j] ^ array[j + 1];
array[j] = array[j] ^ array[j + 1];
flag = true;
}
}
if (!flag) {
break;
}
}
}
/**
* 簡單選擇排序
*
* @param array
*/
public static void selectSort(int array[]) {
int len = array.length;
for (int i = 0; i < len - 1; i++) {
int min = i;
for (int j = i + 1; j < len; j++) {
if (array[j] < array[min]) {
min = j;
}
}
// 交換
if (min != i) {
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
}
/**
* 堆排序
*
* @param array
*/
public static void heapSort(int array[]) {
createHeap(array);
for (int i = array.length - 1; i > 0; i--) {
// 交換
int temp = array[0];
array[0] = array[i];
array[i] = temp;
adjustHeap(array, 0, i);// 調(diào)整前面剩下的i個元素缕粹，后面的元素不要動
}
}
// 建初堆
public static void createHeap(int array[]) {
for (int i = array.length / 2; i >= 0; i--) {// 從最后一個非終端結(jié)點開始
adjustHeap(array, i, array.length);
}
}
// 調(diào)整堆
public static void adjustHeap(int array[], int parentNode, int maxSize) {
int leftChildNode = (parentNode << 1) + 1;// 位運(yùn)算效率更高
int rightChildNode = (parentNode << 1) + 2;
int maxNode = parentNode;
// 選出三個之中最大值的下標(biāo)
if (leftChildNode < maxSize && array[parentNode] < array[leftChildNode]) {// 有左孩子結(jié)點(且此孩子結(jié)點在未排序的范圍內(nèi))
maxNode = leftChildNode;
}
if (rightChildNode < maxSize && array[maxNode] < array[rightChildNode]) {// 有右孩子結(jié)點
maxNode = rightChildNode;
}
if (maxNode != parentNode) {
// 交換
array[maxNode] = array[maxNode] ^ array[parentNode];
array[parentNode] = array[maxNode] ^ array[parentNode];
array[maxNode] = array[maxNode] ^ array[parentNode];
adjustHeap(array, maxNode, maxSize);// 重新調(diào)整孩子結(jié)點所在樹為大根堆
}
}
/**
* 快速排序
*
* @param array
* @param low
* @param high
*/
public static void quickSort(int array[], int low, int high) {
if (low < high) {// 長度大于1
int p = partition(array, low, high);
quickSort(array, low, p - 1);
quickSort(array, p + 1, high);
}
}
// 每一趟排序確定此數(shù)組第一個數(shù)的最終位置沈矿，并返回下標(biāo)
public static int partition(int array[], int low, int high) {
int key = array[low];// 取次數(shù)組第一個數(shù)為樞軸
while (low < high) {
while (low < high && array[high] >= key) {
high--;
}
array[low] = array[high];
while (low < high && array[low] <= key) {
low++;
}
array[high] = array[low];
}
array[low] = key;
return low;
}
}
查找
/**
* 二分查找 非遞歸
*
* @param array
* @param tar
* @return
*/
public static int binSearch(int array[], int tar) {
int len = array.length;
int low = 0;
int high = len - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (array[mid] == tar) {
return mid;
} else if (array[mid] > tar) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
/**
* 二分查找 遞歸
*
* @param array
* @param tar
* @param low
* @param high
* @return
*/
public static int binSearch(int array[], int tar, int low, int high) {
if (low > high) {
return -1;
}
int mid = (low + high) / 2;
if (array[mid] == tar) {
return mid;
} else if (array[mid] > tar) {
return binSearch(array, tar, low, mid - 1);
} else {
return binSearch(array, tar, mid + 1, high);
}
}
動態(tài)規(guī)劃
/**
* 01背包
*
* @param v
* @param w
* @param W
* @return
*/
public static int knapsack(int v[], int w[], int W) {
int row = v.length;
int c[][] = new int[row + 1][W + 1];// c[i][j]選擇前i個物品放入質(zhì)量為j的背包的最大價值
for (int i = 0; i <= row; i++) {
c[i][0] = 0;
}
for (int i = 0; i <= W; i++) {
c[0][i] = 0;
}
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= W; j++) {
if (w[i] > j) {
c[i][j] = c[i - 1][j];
} else {
c[i][j] = c[i - 1][j] > v[i] + c[i - 1][j - w[i]] ? c[i - 1][j]
: v[i] + c[i - 1][j - w[i]];
}
}
}
return c[row][W];
}
/**
* 格子取數(shù)/走棋盤問題
* 問題描述：給定一個m*n的矩陣，每個位置是一個非負(fù)整數(shù)魁瞪，從左上角開始放一個機(jī)器人，它每次只能朝右和下走栋艳，走到右下角恢准，求機(jī)器人的所有路徑中
* 蔗包，總和最小的那條路徑
*
* @param array
* 原始棋盤數(shù)組
* @return 最小總和
*/
public static int minPath(int[][] array) {
if (array == null || array.length == 0) {
return 0;
}
int row = array.length;
int col = array[0].length;
int[][] dp = new int[row][col];
dp[0][0] = array[0][0];
for (int i = 1; i < row; i++) {
dp[i][0] = dp[i - 1][0] + array[i][0];
}
for (int i = 1; i < col; i++) {
dp[0][i] = dp[0][i - 1] + array[0][i];
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
dp[i][j] = (dp[i - 1][j] < dp[i][j - 1] ? dp[i - 1][j]
: dp[i][j - 1]) + array[i][j];
}
}
return dp[row - 1][col - 1];
}
/**
* 最長單調(diào)遞增子序列
* 問題描述：給定長度為N的數(shù)組A秉扑，計算A的最長單調(diào)遞增的子序列（不一定連續(xù)）。如給定數(shù)組A{5调限，6舟陆，7误澳，1，2吨娜，8}脓匿，則A的LIS為
* {5，6宦赠，7陪毡，8}，長度為4.
*
* @param array
* 原始序列
* @return 最大長度
*/
public static int LIS(int array[]) {
if (array == null || array.length == 0) {
return 0;
}
int len = array.length;
int b[] = new int[len];// b[i]表示以下標(biāo)i元素結(jié)束的 最長單調(diào)遞增子序列的長度
Stack<Integer> stack = new Stack<Integer>();
int pre[] = new int[len]; // 前驅(qū)元素數(shù)組勾扭，記錄當(dāng)前以該元素作為最大元素的遞增序列中該元素的前驅(qū)節(jié)點毡琉，用于打印序列用
for (int i = 0; i < len; i++) {
pre[i] = i;
}
int maxLen = 1;
int index = 0;
b[0] = 1;
for (int i = 1; i < len; i++) {
int max = 0;
for (int j = 0; j < i; j++) {
if (array[j] < array[i] && max < b[j]) {
max = b[j];
pre[i] = j;
}
}
b[i] = max + 1;
// 得到當(dāng)前最長遞增子序列的長度，以及該子序列的最末元素的位置
if (maxLen < b[i]) {
maxLen = b[i];
index = i;
}
}
// 輸出序列
while (pre[index] != index) {
stack.add(array[index]);
index = pre[index];
}
stack.add(array[index]);
while (!stack.empty()) {
System.out.println("s=" + stack.pop());
}
return maxLen;
}
}
回溯
/**
* @author Allen Lin
* @date 2016-8-17
* @desc 回溯法求01背包妙色，復(fù)雜度O(n*n^2)桅滋。用動態(tài)規(guī)劃更好，O(n*C)身辨，C為背包容量
*/
public class HuiShuo {
static int n;// 物品數(shù)量
static int w[], v[];// 物品的重量丐谋，價值
static int s;// 包的容量
static int x[];// 暫時選中情況
static int bestx[];// 最好的選中情況
static int maxv;// 最大的價值
public static void main(String[] arg) {
n = 4;
w = new int[] { 0, 7, 3, 4, 5 };
v = new int[] { 0, 42, 12, 40, 25 };
s = 10;
x = new int[n + 1];
bestx = new int[n + 1];
backTrack(1, 0, 0);
for (int j = 1; j <= n; j++) {
if (bestx[j] == 1) {
System.out.println(v[j] + " ");
}
}
System.out.println("maxv" + maxv);
}
private static void backTrack(int i, int cv, int cw) {
if (i > n) {
if (cv > maxv) {
maxv = cv;
for (int j = 1; j <= n; j++) {
bestx[j] = x[j];
}
}
} else {
// 左子樹
if (cw + w[i] <= s) {
x[i] = 1;
cw += w[i];
cv += v[i];
backTrack(i + 1, cv, cw);
cw -= w[i];
cv -= v[i];
}
// 右子樹
if (bound(i + 1, cv, cw) > maxv) {
x[i] = 0;
backTrack(i + 1, cv, cw);
}
}
}
// 上界函數(shù)
private static int bound(int i, int cv, int cw) {
int b = cv;
int left_w = s - cw;
while (i <= n && left_w >= w[i]) {
left_w -= w[i];
b += v[i];
i++;
}
// 裝滿背包
if (i <= n) {
b += v[i] / w[i] * left_w;
}
return b;
}
}
數(shù)據(jù)結(jié)構(gòu)相關(guān)
/**
* 題目描述 :輸入一個鏈表，從尾到頭打印鏈表每個節(jié)點的值煌珊。
*
* 輸入描述: 輸入為鏈表的表頭
*
* 輸出描述: 輸出為需要打印的“新鏈表”的表頭
*
*/
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
// 遞歸實現(xiàn)
ArrayList<Integer> arrayList = new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if (listNode != null) {
printListFromTailToHead(listNode.next);
arrayList.add(listNode.val);
}
return arrayList;
}
/*
* 重建二叉樹
*
* 題目描述
*
* 輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果号俐，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字定庵。例如輸入前序遍歷序列{1,2,4,7
* ,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}吏饿，則重建二叉樹并返回。
*/
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in, 0,
in.length - 1);
return root;
}
private TreeNode reConstructBinaryTree(int[] pre, int startPre, int endPre,
int[] in, int startIn, int endIn) {
if (startPre > endPre || startIn > endIn)
return null;
TreeNode root = new TreeNode(pre[startPre]);
for (int i = startIn; i <= endIn; i++)
if (in[i] == pre[startPre]) {
root.left = reConstructBinaryTree(pre, startPre + 1, startPre
+ i - startIn, in, startIn, i - 1);
root.right = reConstructBinaryTree(pre, i - startIn + startPre
+ 1, endPre, in, i + 1, endIn);
}
return root;
}
/**
*
* 二叉樹的鏡像
*
* 操作給定的二叉樹蔬浙，將其變換為源二叉樹的鏡像猪落。
*/
public class TreeNode2 {
int val = 0;
TreeNode2 left = null;
TreeNode2 right = null;
public TreeNode2(int val) {
this.val = val;
}
}
public void Mirror(TreeNode2 root) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
return;
}
TreeNode2 tn = root.left;
root.left = root.right;
root.right = tn;
if (root.left != null) {
Mirror(root.left);
}
if (root.right != null) {
Mirror(root.right);
}
}
/**
* 包含min函數(shù)的棧
*
* 定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧最小元素的min函數(shù)
*/
Stack<Integer> data = new Stack<Integer>();
Stack<Integer> min = new Stack<Integer>();
public void push(int node) {
data.push(node);
if (min.size() == 0) {
min.push(node);
} else {
if (node < min.peek()) {
min.push(node);
} else {
min.push(min.peek());
}
}
}
public void pop() {
data.pop();
min.pop();
}
public int top() {
return data.peek();
}
public int min() {
return min.peek();
}
/**
*
* 從上往下打印二叉樹( 廣度優(yōu)先遍歷二叉樹)
*
* 思路是用arraylist模擬一個隊列來存儲相應(yīng)的TreeNode
*/
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayList<Integer> list = new ArrayList<>();
ArrayList<TreeNode> queue = new ArrayList<>();
if (root == null) {
return list;
}
queue.add(root);
while (queue.size() != 0) {
TreeNode temp = queue.remove(0);
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
list.add(temp.val);
}
return list;
}
/**
*
* 棧的壓入畴博、彈出序列
*
* 題目描述:
* 輸入兩個整數(shù)序列笨忌，第一個序列表示棧的壓入順序，請判斷第二個序列是否為該棧的彈出順序俱病。假設(shè)壓入棧的所有數(shù)字均不相等蜜唾。例如序列1,2,3,4,5
* 是某棧的壓入順序
* ，序列4庶艾，5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列擎勘。（注意：這兩個序列的長度是相等的）
*/
public boolean IsPopOrder(int[] pushA, int[] popA) {
if (pushA.length == 0 || popA.length == 0)
return false;
Stack<Integer> s = new Stack<Integer>();
// 用于標(biāo)識彈出序列的位置
int popIndex = 0;
for (int i = 0; i < pushA.length; i++) {
s.push(pushA[i]);
// 如果棧不為空咱揍，且棧頂元素等于彈出序列
while (!s.empty() && s.peek() == popA[popIndex]) {
// 出棧
s.pop();
// 彈出序列向后一位
popIndex++;
}
}
return s.empty();
}
/**
* 二叉搜索樹的后序遍歷序列
*
* 輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結(jié)果棚饵。如果是則輸出Yes,否則輸出No煤裙。假設(shè)輸入的數(shù)組的任意兩個數(shù)字都互不相同掩完。
*/
// 左子樹一定比右子樹小，因此去掉根后硼砰，數(shù)字分為left且蓬，right兩部分，right部分的
// 最后一個數(shù)字是右子樹的根他也比左子樹所有值大
public boolean VerifySquenceOfBST(int[] sequence) {
int size = sequence.length;
if (0 == size)
return false;
int i = 0;
while (size != 0) {
while (sequence[i] < sequence[size - 1]) {
i++;
}
while (sequence[i] > sequence[size - 1]) {
i++;
}
if (i != size - 1)
return false;
i = 0;
size--;
}
return true;
}
/**
* 二叉樹中和為某一值的路徑
*
* 輸入一顆二叉樹和一個整數(shù)题翰，打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑恶阴。路徑定義為從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑。
*/
private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
private ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
if (root != null) {
list.add(root.val);
target -= root.val;
if (target == 0 && root.left == null && root.right == null)
listAll.add(new ArrayList<Integer>(list));
FindPath(root.left, target);
FindPath(root.right, target);
target += root.val;
list.remove(list.size() - 1);
}
return listAll;
}
/**
* 字符串的排列
*
* 輸入一個字符串,按字典序打印出該字符串中字符的所有排列豹障。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,
* bac,bca,cab和cba冯事。 結(jié)果請按字母順序輸出
*/
public static ArrayList<String> Permutation(String str) {
ArrayList<String> al = new ArrayList<String>();
if (str == null || str.length() == 0) {
return al;
}
Set<String> set = new HashSet<String>();
permutation(set, str.toCharArray(), 0);
al.addAll(set);
Collections.sort(al);
return al;
}
public static void permutation(Set<String> set, char[] buf, int k) {
if (k == buf.length - 1) {// 當(dāng)只要求對數(shù)組中一個字母進(jìn)行全排列時，只要就按該數(shù)組輸出即可
set.add(new String(buf));
return;
} else {// 多個字母全排列
for (int i = k; i < buf.length; i++) {
char temp = buf[k];// 交換數(shù)組第一個元素與后續(xù)的元素
buf[k] = buf[i];
buf[i] = temp;
permutation(set, buf, k + 1);// 后續(xù)元素遞歸全排列
temp = buf[k];// 將交換后的數(shù)組還原
buf[k] = buf[i];
buf[i] = temp;
}
}
}
}
其他
/**
* 大整數(shù)乘法(復(fù)雜度：O(m*n))
*
* @param str1
* @param str2
*/
public static void multiply(String str1, String str2) {
char[] c1 = str1.toCharArray();
char[] c2 = str2.toCharArray();
int m = str1.length();
int n = str2.length();
int array[] = new int[m + n];// 兩數(shù)乘積位數(shù)不會超過兩數(shù)的位數(shù)之和
// 高低位對調(diào),為了低位對齊
covert(c1);
covert(c2);
// 對齊逐位相乘
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
array[i + j] = array[i + j] + Integer.parseInt(c1[i] + "")
* Integer.parseInt(String.valueOf(c2[j]));
}
// 進(jìn)位
for (int i = 0; i < m + n; i++) {
int temp = array[i] / 10;
if (temp > 0) {
array[i] = array[i] % 10;
array[i + 1] += temp;
}
}
String res = "";
for (int i = m + n - 1; i >= 0; i--) {
res = res + array[i];
}
// 刪除結(jié)果前面的0
int i = 0;
while (res.charAt(i) == '0') {
i++;
}
System.out.print(res.substring(i));
}
public static void covert(char[] c) {
for (int i = 0; i < c.length / 2; i++) {
char temp = c[i];
c[i] = c[c.length - 1 - i];
c[c.length - 1 - i] = temp;
}
}
}
/**
* 反轉(zhuǎn)鏈表
*
* @param head
* @return
*/
public ListNode ReverseList(ListNode head) {
ListNode next = null;
ListNode pre = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
已放到github https://github.com/ALLENnan/Allen-Study
