二叉树镜像
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);//将根节点入队
while(!queue.isEmpty())
{
current = queue.poll();//出队队头元素并访问
System.out.print(current.val +"-->");
if(current.left != null)//如果当前节点的左节点不为空入队
{
queue.offer(current.left);
}
if(current.right != null)//如果当前节点的右节点不为空，把右节点入队
{
queue.offer(current.right);
}
}
}
}
整数反转
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); // 偶数层 -> 队列头部
else tmp.addFirst(node.val); // 奇数层 -> 队列尾部
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
}
连续子数组的最大和
动态规划
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修饰（非静态）方法和synchronized（this）都是锁住自己本身的对象；synchronized修饰静态方法和synchronized（类名.class）都是锁住加载类对象；synchronized（object）是锁住object对象
双向量表修改
使用临时变量保存 前面
归并
public class MergeSort implements IArraySort {
2
3 @Override
4 public int[] sort(int[] sourceArray) throws Exception {
5 // 对 arr 进行拷贝，不改变参数内容
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) {
// 找寻基准数据的正确索引
int index = getIndex(arr, low, high);
// 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
//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) {
// 基准数据
int tmp = arr[low];
while (low < high) {
// 当队尾的元素大于等于基准数据时,向前挪动high指针
while (low < high && arr[high] >= tmp) {
high--;
}
// 如果队尾元素小于tmp了,需要将其赋值给low
arr[low] = arr[high];
// 当队首元素小于等于tmp时,向前挪动low指针
while (low < high && arr[low] <= tmp) {
low++;
}
// 当队首元素大于tmp时,需要将其赋值给high
arr[high] = arr[low];
}
// 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
// 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
arr[low] = tmp;
return low; // 返回tmp的正确位置
}
链表反转
迭代
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;
}
}
