二叉樹鏡像
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode leftRoot = mirrorTree(root.right);
TreeNode rightRoot = mirrorTree(root.left);
root.left = leftRoot;
root.right = rightRoot;
return root;
}
最長回文子串
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) {
return "";
}
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
public int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
--left;
++right;
}
return right - left - 1;
}
}
二叉樹層級遍歷
public class LevelOrder
{
public void levelIterator(BiTree root)
{
if(root == null)
{
return ;
}
LinkedList<BiTree> queue = new LinkedList<BiTree>();
BiTree current = null;
queue.offer(root);//將根節(jié)點(diǎn)入隊(duì)
while(!queue.isEmpty())
{
current = queue.poll();//出隊(duì)隊(duì)頭元素并訪問
System.out.print(current.val +"-->");
if(current.left != null)//如果當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)不為空入隊(duì)
{
queue.offer(current.left);
}
if(current.right != null)//如果當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)不為空，把右節(jié)點(diǎn)入隊(duì)
{
queue.offer(current.right);
}
}
}
}
整數(shù)反轉(zhuǎn)
class Solution {
public int reverse(int x) {
int rev = 0;
while (x != 0) {
int pop = x % 10;
x /= 10;
if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
rev = rev * 10 + pop;
}
return rev;
}
}
二叉樹先序遍歷
public static void iterativePreOrder_2(TreeNode p) {
if (p == null) return;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(p);
while (!stack.empty()) {
p = stack.pop();
visit(p);
if (p.right != null) stack.push(p.right);
if (p.left != null) stack.push(p.left);
}
}
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()) {
LinkedList<Integer> tmp = new LinkedList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
if(res.size() % 2 == 0) tmp.addLast(node.val); // 偶數(shù)層 -> 隊(duì)列頭部
else tmp.addFirst(node.val); // 奇數(shù)層 -> 隊(duì)列尾部
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}
二分法
public static int myBinarySearch(int[] arr,int value) {
int low=0;
int high=arr.length-1;
while(low<=high) {
int mid=(low+high)/2;
if(value==arr[mid]) {
return mid;
}
if(value>arr[mid]) {
low=mid+1;
}
if(value<arr[mid]) {
high=mid-1;
}
}
return -1;//沒有找到返回-1
}
連續(xù)子數(shù)組的最大和
動(dòng)態(tài)規(guī)劃
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
for(int i = 1; i < nums.length; i++) {
nums[i] += Math.max(nums[i - 1], 0);
res = Math.max(res, nums[i]);
}
return res;
}
}
synchronized修飾（非靜態(tài)）方法和synchronized（this）都是鎖住自己本身的對象；synchronized修飾靜態(tài)方法和synchronized（類名.class）都是鎖住加載類對象；synchronized（object）是鎖住object對象
雙向量表修改
使用臨時(shí)變量保存 前面
歸并
public class MergeSort implements IArraySort {
2
3 @Override
4 public int[] sort(int[] sourceArray) throws Exception {
5 // 對 arr 進(jìn)行拷貝，不改變參數(shù)內(nèi)容
6 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
7
8 if (arr.length < 2) {
9 return arr;
10 }
11 int middle = (int) Math.floor(arr.length / 2);
12
13 int[] left = Arrays.copyOfRange(arr, 0, middle);
14 int[] right = Arrays.copyOfRange(arr, middle, arr.length);
15
16 return merge(sort(left), sort(right));
17 }
18
19 protected int[] merge(int[] left, int[] right) {
20 int[] result = new int[left.length + right.length];
21 int i = 0;
22 while (left.length > 0 && right.length > 0) {
23 if (left[0] <= right[0]) {
24 result[i++] = left[0];
25 left = Arrays.copyOfRange(left, 1, left.length);
26 } else {
27 result[i++] = right[0];
28 right = Arrays.copyOfRange(right, 1, right.length);
29 }
30 }
31
32 while (left.length > 0) {
33 result[i++] = left[0];
34 left = Arrays.copyOfRange(left, 1, left.length);
35 }
36
37 while (right.length > 0) {
38 result[i++] = right[0];
39 right = Arrays.copyOfRange(right, 1, right.length);
40 }
41
42 return result;
43 }
44
45}
快速排序
private static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 找尋基準(zhǔn)數(shù)據(jù)的正確索引
int index = getIndex(arr, low, high);
// 進(jìn)行迭代對index之前和之后的數(shù)組進(jìn)行相同的操作使整個(gè)數(shù)組變成有序
//quickSort(arr, 0, index - 1); 之前的版本，這種姿勢有很大的性能問題，謝謝大家的建議
quickSort(arr, low, index - 1);
quickSort(arr, index + 1, high);
}
}
private static int getIndex(int[] arr, int low, int high) {
// 基準(zhǔn)數(shù)據(jù)
int tmp = arr[low];
while (low < high) {
// 當(dāng)隊(duì)尾的元素大于等于基準(zhǔn)數(shù)據(jù)時(shí),向前挪動(dòng)high指針
while (low < high && arr[high] >= tmp) {
high--;
}
// 如果隊(duì)尾元素小于tmp了,需要將其賦值給low
arr[low] = arr[high];
// 當(dāng)隊(duì)首元素小于等于tmp時(shí),向前挪動(dòng)low指針
while (low < high && arr[low] <= tmp) {
low++;
}
// 當(dāng)隊(duì)首元素大于tmp時(shí),需要將其賦值給high
arr[high] = arr[low];
}
// 跳出循環(huán)時(shí)low和high相等,此時(shí)的low或high就是tmp的正確索引位置
// 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要將tmp賦值給arr[low]
arr[low] = tmp;
return low; // 返回tmp的正確位置
}
鏈表反轉(zhuǎn)
迭代
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
遞歸
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
合并有序列表
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dum = new ListNode(0), cur = dum;
while(l1 != null && l2 != null) {
if(l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
}
else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 != null ? l1 : l2;
return dum.next;
}
}
