二分查找
public static int binSearch(int[] a, int e) { int low = 0; int high = a.length - 1; while (low <= high) { int mid = (low + high) / 2; if (a[mid] == e) { return mid; } else if (a[mid] < e) { low = mid + 1; } else { high = mid - 1; } } return -1; }
快排
public static void main(String[] args) { int[] x = {3, 5, 1, 0, 2, 7, 6, 7, 9}; quicSort(x, 0, x.length - 1); System.out.printf(Arrays.toString(x)); } public static void quicSort(int[] a, int start, int end) { if (start >= end) { //如果只有一个元素，就不用再排下去了 return; } else { //如果不止一个元素，继续划分两边递归排序下去 int partition = divide(a, start, end); quicSort(a, start, partition - 1); quicSort(a, partition + 1, end); } } public static int divide(int[] a, int start, int end) { //每次都以最右边的元素作为基准值 int base = a[end]; //start一旦等于end，就说明左右两个指针合并到了同一位置，可以结束此轮循环。 while (start < end) { while (start < end && a[start] <= base) //从左边开始遍历，如果比基准值小，就继续向右走 start++; //上面的while循环结束时，就说明当前的a[start]的值比基准值大，应与基准值进行交换 if (start < end) { //交换 int temp = a[start]; a[start] = a[end]; a[end] = temp; //交换后，此时的那个被调换的值也同时调到了正确的位置(基准值右边)，因此右边也要同时向前移动一位 end--; } while (start < end && a[end] >= base) //从右边开始遍历，如果比基准值大，就继续向左走 end--; //上面的while循环结束时，就说明当前的a[end]的值比基准值小，应与基准值进行交换 if (start < end) { //交换 int temp = a[start]; a[start] = a[end]; a[end] = temp; //交换后，此时的那个被调换的值也同时调到了正确的位置(基准值左边)，因此左边也要同时向后移动一位 start++; } } //这里返回start或者end皆可，此时的start和end都为基准值所在的位置 return end; }
单链表反转
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; } }
两个链表合并
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { ListNode head = new ListNode(0); ListNode tmp = head; while(list1!=null&&list2!=null){ if(list1.val<list2.val){//谁小先挂谁 tmp.next = list1; list1 = list1.next; }else{ tmp.next = list2; list2 = list2.next; } tmp = tmp.next; }//代码走到这，一个为空一个不为空 if(list1!=null){ tmp.next = list1; } if(list2!=null){ tmp.next = list2; } return head.next; } }
链表环的入口
public class Solution { //判断有没有环，返回相遇的地方 public ListNode hasCycle(ListNode head) { //先判断链表为空的情况 if(head == null) return null; //快慢双指针 ListNode fast = head; ListNode slow = head; //如果没环快指针会先到链表尾 while(fast != null && fast.next != null){ //快指针移动两步 fast = fast.next.next; //慢指针移动一步 slow = slow.next; //相遇则有环，返回相遇的位置 if(fast == slow) return slow; } //到末尾说明没有环，返回null return null; } public ListNode EntryNodeOfLoop(ListNode pHead) { ListNode slow = hasCycle(pHead); //没有环 if(slow == null) return null; //快指针回到表头 ListNode fast = pHead; //再次相遇即是环入口 while(fast != slow){ fast = fast.next; slow = slow.next; } return slow; } }
有效的括号
import java.util.*; public class Solution { /** * * @param s string字符串 * @return bool布尔型 */ public boolean isValid (String s) { // write code here Stack<Character> stack = new Stack<>(); Map<Character,Character> map = new HashMap<>(); map.put('(',')'); map.put('[',']'); map.put('{','}'); for(Character c : s.toCharArray()) { if (!stack.isEmpty() && c == map.get(stack.peek())){ stack.pop(); } else { stack.add(c); } } return stack.isEmpty(); } }
滑动窗口最大值
import java.util.*; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size) { if (num == null || size == 0 || size > num.length) { return new ArrayList<>(); } LinkedList<Integer> qmax = new LinkedList<>(); ArrayList<Integer> result = new ArrayList<>(); for(int i = 0;i<num.length;i++) { //保证在窗口范围内队头元素存放的是最大值，第二个元素次大 while(!qmax.isEmpty() && num[qmax.peekLast()] <= num[i]){ qmax.pollLast(); } qmax.addLast(i); //如果队头值已经过期了，则移除 if (i - size == qmax.peekFirst()) { qmax.pollFirst(); } if (i-size+1 >= 0) { result.add(num[qmax.peekFirst()]); } } return result; } }
二叉树公共祖先
public int lowestCommonAncestor(TreeNode root, int o1, int o2) { return helper(root, o1, o2).val; } public TreeNode helper(TreeNode root, int o1, int o2) { if (root == null || root.val == o1 || root.val == o2) return root; TreeNode left = helper(root.left, o1, o2); TreeNode right = helper(root.right, o1, o2); //如果left为空，说明这两个节点在root结点的右子树上，我们只需要返回右子树查找的结果即可 if (left == null) return right; //同上 if (right == null) return left; //如果left和right都不为空，说明这两个节点一个在root的左子树上一个在root的右子树上， //我们只需要返回cur结点即可。 return root; }
之字打印二叉树
public class questionthree { public static void main(String[] args) { TreeNode root = new TreeNode(8); root.left = new TreeNode(6); root.right = new TreeNode(10); root.left.left = new TreeNode(5); root.left.right = new TreeNode(7); root.right.left = new TreeNode(9); root.right.right = new TreeNode(11); List<List<Integer>> res = new ArrayList<>(); res = levelOrder(root); for(int i = 0; i<res.size();i++){ System.out.println(res.get(i)); } } public static List<List<Integer>> levelOrder(TreeNode root){ List<List<Integer>> ans = new ArrayList<>(); if(root == null) return ans; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root);//把根节点放进队列，开始程序 boolean flag = true; //控制列表是顺序还是逆序的标志 while(!queue.isEmpty()){ //如果队列不是空的，说明二叉树不会遍历完，如果有下一层，会在当前这层往队列里加入下一层的节点 int size = queue.size(); //首先得到当前要这一层要处理的节点数 List<Integer> curlevel = new ArrayList<>(); //初始化用来放当前这层节点的值的容器 while(--size >= 0){ //按照要处理节点的个数来处理 TreeNode cur = queue.remove(); //每处理一个节点，就把一个节点移出队列 curlevel.add(cur.val); //同时把要处理节点的值放进当前层的容器中 if(cur.left != null) queue.add(cur.left); //如果当前节点有左右子节点，就加入到队列中 if(cur.right != null) queue.add(cur.right); } if(flag == false) { //如果标志位false，将列表逆序 Collections.reverse(curlevel); } ans.add(curlevel); flag = !flag; //下一层，flag取反 } return ans; } }
买卖股票最佳时机
dp[i]=max(dp[i-1],prices[i]-min(prices[0:i]))
class Solution { public int maxProfit(int[] prices) { int maxProfit = 0, minPrice = prices[0]; for (int i = 1; i < prices.length; i++) { maxProfit = Math.max(maxProfit, prices[i] - minPrice); minPrice = Math.min(minPrice, prices[i]); } return maxProfit; } }
class Solution { public int maxProfit(int[] prices) { int[] dp = new int[prices.length]; int minPrice = prices[0]; // base case: dp_0 = 0 dp[0] = 0; // state transition: dp[i]=max(dp[i-1],prices[i]-minPrice) for (int i = 1; i < prices.length; i++) { dp[i] = Math.max(dp[i - 1], prices[i] - minPrice); minPrice = Math.min(minPrice, prices[i]); } return dp[prices.length - 1]; } }
打家劫舍
dp[i] = max( dp[i-2] + nums[i] , dp [i-1])
dp[i]=max(dp[i−2]+nums[i],dp[i−1]) class Solution { public int rob(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int length = nums.length; if (length == 1) { return nums[0]; } int[] dp = new int[length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < length; i++) { dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); } return dp[length - 1]; } }
回文子串
这里需要二维的 dp[][] 数组，dp[i][j] 表示子串 [i..j] 是否为回文子串
当我们判断 [i..j] 是否为回文子串时，只需要判断 s[i] == s[j]，同时判断 [i-1..j-1] 是否为回文子串即可
需要注意有两种特殊情况：[i, i] or [i, i + 1]，即：子串长度为 1 或者 2。所以加了一个条件限定 j - i < 2
状态转移方程如下：
dp[i][j] = (s[i] == s[j]) && (j - i < 2 || dp[i + 1][j - 1])
public int countSubstrings(String s) { int ans = 0; int n = s.length(); boolean[][] dp = new boolean[n][n]; for (int j = 0; j < n; j++) { for (int i = 0; i <= j; i++) { if (s.charAt(j) == s.charAt(i) && (j - i < 2 || dp[i + 1][j - 1])) { dp[i][j] = true; ans++; } } } return ans; }
接雨水
public int trap(int[] height) { int sum = 0; Stack<Integer> stack = new Stack<>(); int current = 0; while (current < height.length) { //如果栈不空并且当前指向的高度大于栈顶高度就一直循环 while (!stack.empty() && height[current] > height[stack.peek()]) { int h = height[stack.peek()]; //取出要出栈的元素 stack.pop(); //出栈 if (stack.empty()) { // 栈空就出去 break; } int distance = current - stack.peek() - 1; //两堵墙之前的距离。 int min = Math.min(height[stack.peek()], height[current]); sum = sum + distance * (min - h); } stack.push(current); //当前指向的墙入栈 current++; //指针后移 } return sum; }
岛屿问题
class Solution { public int numIslands(char[][] grid) { int count = 0; for(int i = 0; i < grid.length; i++) { for(int j = 0; j < grid[0].length; j++) { if(grid[i][j] == '1'){ dfs(grid, i, j); count++; } } } return count; } private void dfs(char[][] grid, int i, int j){ if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') return; grid[i][j] = '0'; dfs(grid, i + 1, j); dfs(grid, i, j + 1); dfs(grid, i - 1, j); dfs(grid, i, j - 1); } }
