算法，就是计算机处理信息的一个步骤。是独立存在的一种处理问题的方法和思想，并不局限于具体的实现过程。
排序
冒泡
1public static int[] BubbleSort (int[] arr) { 2 for (int i = 0; i < arr.length; i++) { 3 for (int j = 0; j < arr.length - i - 1; j++) { 4 if (arr[j] > arr[j+1]) { 5 int temp = arr[j]; 6 arr[j] = arr[j+1]; 7 arr[j+1] = temp; 8 } 9 } 10 } 11 return arr; 12}
选择
1public static int[] SelectSort (int[] arr) { 2 for (int i = 0; i < arr.length-1; i++) { 3 for (int j = i + 1; j < arr.length; j++) { 4 int temp = arr[i]; 5 if (arr[i] > arr[j]) { 6 arr[i] = arr[j]; 7 arr[j] = temp; 8 } 9 } 10 } 11 return arr; 12}
快排
1public int[] MySort (int[] arr) { 2 quicksort(arr, 0, arr.length - 1); 3 return arr; 4 } 5 6 public void quicksort(int[] list, int left, int right) { 7 if (left < right) { 8 int pivot = randompivot(list, left, right); 9 quicksort(list,left, pivot-1); 10 quicksort(list, pivot+1, right); 11 } 12 } 13 14 public int randompivot(int[] list, int left, int right) { 15 int first = list[left]; 16 while (left < right) { 17 while (left < right && list[right] >= first) { 18 right--; 19 } 20 swap(list, left, right); 21 22 while(left<right && list[left] <= first) { 23 left++; 24 } 25 swap(list, left, right); 26 } 27 return left; 28 } 29 public void swap(int[] list, int left, int right) { 30 int temp = list[left]; 31 list[left] = list[right]; 32 list[right] = temp; 33 34 }
堆排序
二分查找
复杂度 O(log2n)
1 public static int search(int[] nums, int target) { 2 if (nums == null || nums.length == 0) return -1; 3 int left = 0; 4 int right = nums.length - 1; 5 while (left < right) { 6 int mid = left + (right - left) / 2; 7 if (nums[mid] < target) { 8 left = mid + 1; 9 } else { 10 right = mid; 11 } 12 } 13 return nums[left] == target ? left : -1; 14 }
栈与队列
用栈实现队列
1public class Solution { 2 Stack<Integer> stack1 = new Stack<Integer>(); 3 Stack<Integer> stack2 = new Stack<Integer>(); 4 5 public void push(int node) { 6 stack1.push(node); 7 } 8 9 public int pop() { 10 if (stack2.isEmpty()) { 11 //如果 outstack 是空的，就把instack 全部 push 到 outstack 里 12 while (!stack1.isEmpty()) { 13 stack2.push(stack1.pop()); 14 } 15 } 16 // 否则直接弹出 17 return stack2.pop(); 18 } 19}
字符串
最长无重复子串
1 public int maxLength(int[] arr) { 2 //用链表实现队列，队列是先进先出的 3 Queue<Integer> queue = new LinkedList<>(); 4 int res = 0; 5 for (int c : arr) { 6 while (queue.contains(c)) { 7 //如果有重复的，队头出队 8 queue.poll(); 9 } 10 //添加到队尾 11 queue.add(c); 12 res = Math.max(res, queue.size()); 13 } 14 return res; 15 }
数组
斐波那契数列
递归
1public int Fibonacci(int n) { 2 if (n <= 1) return n; 3 return Fibonacci(n-1) + Fibonacci(n-2); 4}
非归递
1public int Fibonacci(int n) { 2 if (n <= 1) return n; 3 int first = 0; 4 int second = 1; 5 int temp; 6 for (int i = 2; i <= n; i++){ 7 temp = second; 8 second = first + second; 9 first = temp; 10 } 11 return second; 12 }
有序数组合并
1public void merge(int A[], int m, int B[], int n) { 2 3 int aPtr = m - 1, bPtr = n - 1; 4// 两数组元素从右至左比较，大的去 A 尾部，直至有一方指针到头为止 5 for (int ptr = m + n - 1; aPtr >= 0 && bPtr >= 0; ptr--){ 6 A[ptr] = A[aPtr] > B[bPtr] ? A[aPtr--] : B[bPtr--]; 7 } 8// A 指针先走完的情况，B 中剩余元素直接copy至 A 对应位置即可； 9 while (bPtr >= 0){ 10 A[bPtr] = B[bPtr--]; 11 } 12 13}
两数之和
1public int[] twoSum (int[] numbers, int target) { 2 Map<Integer, Integer> map = new HashMap<>(); 3 for (int index = 0; index < numbers.length; index++) { 4 int cur = numbers[index]; 5 if (map.containsKey(target-cur)) { 6 return new int[]{map.get(target-cur)+1, index+1}; 7 } 8 map.put(cur, index); 9 } 10 throw new RuntimeException("results not exits"); 11}
移除有序数组中的重复元素
链表
链表翻转
1public ListNode ReverseList(ListNode head) { 2 ListNode pre = null; 3 ListNode cur = head; 4 ListNode next = null; 5 while (cur != null) { 6 next = cur.next;//先找 next 指针 7 cur.next = pre;//往前指 8 pre = cur;//往后平移 9 cur = next;//往后平移 10 } 11 return pre; 12 }
判断是否有环
1public class Solution { 2 public boolean hasCycle(ListNode head) { 3 if (head == null) return false; 4 ListNode fast = head; 5 ListNode slow = head; 6 while (fast != null && fast.next !=null) { 7 slow = slow.next; 8 fast = fast.next.next; 9 if (fast == slow) { 10 return true; 11 } 12 } 13 return false; 14 } 15}
链表中环的入口节点
- 那么我们可以知道fast指针走过a+b+c+b
- slow指针走过a+b
- 那么 2*(a+b) = a+b+c+b
- 所以a = c
- 那么此时让 fast 回到起点，slow 依然停在z，两个同时开始走，一次走一步
- 那么它们最终会相遇在y点，正是环的起始点
1public class Solution { 2 public ListNode detectCycle(ListNode head) { 3 if (head == null || head.next == null) return null; 4 ListNode fast = head; 5 ListNode slow = head; 6 while (fast != null && fast.next !=null) { 7 slow = slow.next; 8 fast = fast.next.next; 9 if (fast == slow) { 10 fast = head;// fast回到起点 11 while (fast != slow) { 12 slow = slow.next; 13 fast = fast.next; 14 } 15 return slow; 16 } 17 } 18 return null; 19 } 20}
链表中倒数第K个节点
1.先让first指针先走 K 步 2.再让first和second指针同时走，first指针走到尾，则second相当于走到倒数第k个节点
1public ListNode FindKthToTail (ListNode pHead, int k) { 2 if (pHead == null) return pHead; 3 ListNode first = pHead; 4 while (k-- > 0) { 5 if (first == null) return null; 6 first = first.next; 7 } 8 ListNode second = pHead; 9 while (first != null) { 10 first = first.next; 11 second = second.next; 12 } 13 return second; 14 }
合并有序链表
归递
1public ListNode mergeTwoLists (ListNode l1, ListNode l2) { 2 3 if (l1 == null || l2 == null) { 4 return l1 == null ? l2 : l1; 5 } 6 ListNode first = l1.val < l2.val ? l1 : l2; 7 first.next = mergeTwoLists(first.next, first == l1 ? l2 : l1); 8 return first; 9}
非递归
1public ListNode mergeTwoLists (ListNode l1, ListNode l2) { 2 if (l1 == null) return l2; 3 if (l2 == null) return l1; 4 ListNode dummy = new ListNode(0); 5 ListNode cur = dummy; 6 while (l1 != null && l2 != null) { 7 if (l1.val > l2.val) { 8 cur.next = l2; 9 l2 = l2.next; 10 } else { 11 cur.next = l1; 12 l1 = l1.next; 13 } 14 cur = cur.next; 15 } 16 cur.next = l1 == null ? l2 : l1; 17 return dummy.next; 18 }
两个链表的第一个公共结点
1、假设 链表A 长度为 a，链表B长度为 b， 2、A 走完 a 再将指针指向B 和 B走完b 再将指针指向A，那肯定会相遇； 3、即 a+c+b = b+c+a; (公共点后长度为 c)
此题和链表入口环的节点 题目题解一样的思路。
1public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { 2 3 if (pHead1 == null || pHead2 == null) return null; 4 ListNode p1 = pHead1; 5 ListNode p2 = pHead2; 6 7 while (p1 != p2) { 8 p1 = p1 != null ? p1.next : pHead2;//到头了就指向 B 9 p2 = p2 != null ? p2.next : pHead1;//到头了就指向 A 10 } 11 return p1; 12 }
二叉树
判断是否是完全二叉树
1 public boolean isFull(TreeNode root) { 2 if (root == null) return false; 3 Queue<TreeNode> queue = new LinkedList(); 4 boolean isLeaf = false; 5 while(!queue.isEmpty()) { 6 7 TreeNode node = queue.poll(); 8 if (isLeaf && !isLeaf(node)) { 9 return false; 10 } 11 if (node.left != null) { 12 queue.offer(node); 13 } else if (node.right != null) { 14 return false; 15 } 16 17 if (node.right != null) { 18 queue.offer(node); 19 } else { 20 isLeaf = true; 21 } 22 } 23 return true; 24 } 25 private boolean isLeaf(TreeNode node) { 26 return (node.left == null) && (node.right == null); 27 }
二叉树高度
归递
1public int maxDepth (TreeNode root) { 2 if(root == null) return 0; 3 return 1+ Math.max(maxDepth(root.left), maxDepth(root.right)); 4 }
层序遍历
1 public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) { 2 if (root == null) return new ArrayList(); 3 ArrayList list = new ArrayList(); 4 Queue<TreeNode> queue = new LinkedList<>(); 5 queue.offer(root); 6 while (!queue.isEmpty()) { 7 int size = queue.size(); 8 ArrayList subList = new ArrayList(); 9 for (int i = 0; i < size;i++) { 10 TreeNode node = queue.poll(); 11 subList.add(node.val); 12 if (node.left != null) { 13 queue.offer(node.left); 14 } 15 if (node.right != null) { 16 queue.offer(node.right); 17 } 18 } 19 list.add(subList); 20 } 21 return list; 22 }
之字形层序遍历
1public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) { 2 if (root == null) return new ArrayList(); 3 ArrayList list = new ArrayList(); 4 Queue<TreeNode> queue = new LinkedList(); 5 queue.offer(root); 6 while (!queue.isEmpty()) { 7 ArrayList sublist = new ArrayList();//存储每一层节点 8 for (int i = queue.size(); i >0;i--) { 9 TreeNode node = queue.poll();//弹出队列中的节点 10 if ((list.size()+1) %2 !=0) {//奇数层，尾部插入 11 sublist.add(node.val); 12 } else {//偶数层 头插 13 sublist.add(0, node.val); 14 } 15 if (node.left != null) { 16 queue.offer(node.left); 17 } 18 if (node.right != null) { 19 queue.offer(node.right); 20 } 21 } 22 list.add(sublist); 23 } 24 return list; 25 }
二叉树翻转
1 public TreeNode invertTree(TreeNode node) { 2 if (node == null) { 3 return null; 4 } 5 TreeNode temp = node.left; 6 node.left = node.right; 7 node.right = temp; 8 invertTree(node.left); 9 invertTree(node.right); 10 return node; 11 }
