剑指Offer系列
[TOC]
数组和字符串
剑指offer 04.二维数组中的查找
-
从左下角开始查找，二分思想。
public boolean findNumberIn2DArray(int[][] matrix, int target) { int row = matrix.length - 1; int col = 0; while (row >=0 && col < matrix[0].length) { if (matrix[row][col] > target) { row--; } else if (matrix[row][col] < target) { col++; } else { return true; } } return false; }
剑指offer 05. 替换空格
-
借助
StringBuilder逐一替换。public String replaceSpace(String s) { StringBuilder sb = new StringBuilder(); for (char c : s.toCharArray()) { if (c == ' ') { sb.append("%20"); } else { sb.append(c); } } return sb.toString(); }
剑指offer11. 旋转数组的最小数字
-
排序后的数组做旋转是存在规律，可通过二分查找降低时间复杂度。
public int minArray(int[] numbers) { int low = 0; int high = numbers.length - 1; while (low < high) { int mid = low + (high - low) / 2; if (numbers[mid] > numbers[high]) { low = mid + 1; } else if (numbers[mid] < numbers[low]) { high = mid; } else { high--; } } return numbers[low]; }
剑指offer 17. 打印从1到最大的n位数
-
先求最大值maxSum，打印1...maxSum。
def printNumbers(self, n: int) -> List[int]: res = [] for i in range(1, 10 ** n): res.append(i) return res
剑指offer21. 调整数组顺序使奇数位于偶数前面
-
快速排序寻找中间点思想，双指针一遍遍历。
public int[] exchange(int[] nums) { int l = 0, h = nums.length - 1; while (l < h) { while (l < h && ((nums[l] & 0x1) == 1)) { l++; } while (l < h && ((nums[h] & 0x1) == 0)) { h--; } swap(nums, l, h); } return nums; } void swap(int[] nums, int l, int h) { int tmp = nums[l]; nums[l] = nums[h]; nums[h] = tmp; }
剑指offer 29.顺时针打印矩阵
上下左右四个阈值，不停往中间缩进，直到相等。
-
注意在第三步判断
top、第四步判断right是否超范围。public int[] spiralOrder(int[][] matrix) { if (matrix.length == 0) { return new int[0]; } int left = 0, right = matrix[0].length - 1; int top = 0, down = matrix.length - 1; int[] res = new int[(right + 1) * (down + 1)]; int index = 0; while (left <= right && top <= down) { for (int i = left; i <= right; i++) { res[index++] = matrix[top][i]; } top++; for (int i = top; i <= down; i++) { res[index++] = matrix[i][right]; } right--; for (int i = right; i >= left && top <= down; i--) {//同时判断top res[index++] = matrix[down][i]; } down--; for (int i = down; i >= top && left <= right; i--) { // 同时判断right res[index++] = matrix[i][left]; } left++; } return res; }
剑指offer 39.数组中出现次数超过一半的数字
-
遍历
nums数组，使用count进行计数，记录当前出现的数字为cur，如果遍历到的num与cur相等，则count自增，否则自减，当其减为 0 时则将cur修改为当前遍历的num，通过增减抵消的方式，最终达到剩下的数字是结果的效果，时间复杂度为O(n)public int majorityElement(int[] nums) { int curr = nums[0]; int count = 0; for (int num : nums) { if (count == 0) { curr = num; } if (curr == num) { count++; } else { count--; } } return curr; }
剑指offer 45.把数组排成最小的数
-
自定义排序，关键在于按拼接后的字符串进行排序。
public String minNumber(int[] nums) { String[] strs = Arrays.stream(nums).mapToObj(item -> String.valueOf(item)). collect(Collectors.toList()).toArray(new String[0]); Arrays.sort(strs, ((o1, o2) -> { return (o1 + o2).compareTo(o2 + o1); })); return String.join("", strs); }
剑指 Offer 53 - I. 在排序数组中查找数字 I
排序数组 -> 二分查找，左右边界差。
-
可通过技巧复用左边界方法或右边界方法。
public int search(int[] nums, int target) { return rightBound(nums, target) - rightBound(nums, target - 1); } int rightBound(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] <= target) { l = mid + 1; } else { r = mid - 1; } } return r; }
剑指 Offer 53 - II. 0～n-1 中缺失的数字
排序后的数组 ->二分查找。
-
注意缺失的是最后一个数字的边界情况处理。
public int missingNumber(int[] nums) { int l = 0; int r = nums.length - 1; while (l < r) { int m = l + (r - l) / 2; if (m == nums[m]) { l = m + 1; } else { r = m; } } return l == nums[l] ? l + 1 : l; }
剑指 Offer 57. 和为 s 的两个数字
-
与两数之后的区别在于排序后的数组，使用前后指针加速。
public int[] twoSum(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l < r) { if (nums[l] + nums[r] < target) { l++; } else if (nums[l] + nums[r] > target) { r--; } else { return new int[]{nums[l], nums[r]}; } } return new int[0]; }
剑指 Offer 57 - II. 和为 s 的连续正数序列
-
滑动窗口解法清晰明了，当然暴力求解也是可以的。
public int[][] findContinuousSequence(int target) { int window = 0; int left = 0, right = 0; List<List<Integer>> res = new ArrayList<>(); while (right < target / 2 + 1) { right++; window += right; if (window == target) { res.add(IntStream.rangeClosed(left + 1, right).boxed().collect(Collectors.toList())); } while (window > target) { left++; window -= left; if (window == target) { res.add(IntStream.rangeClosed(left + 1, right).boxed().collect(Collectors.toList())); } } } int[][] result = new int[res.size()][]; for (int i = 0; i < result.length; i++) { result[i] = res.get(i).stream().mapToInt(Integer::intValue).toArray(); } return result; }
剑指 Offer 58 - I. 翻转单词顺序
-
反向按顺序遍历。
public String reverseWords(String s) { List<String> str = new ArrayList<>(); s = s.trim(); int l = s.length() - 1, r = s.length() - 1; while (l >= 0) { while (l >= 0 && s.charAt(l) != ' ') { l--; } str.add(s.substring(l + 1, r + 1)); while (l >= 0 && s.charAt(l) == ' ') { l--; } r = l; } return String.join(" ", str); }
剑指 Offer 58 - II. 左旋转字符串
-
子串拼接。
public String reverseLeftWords(String s, int n) { return s.substring(n) + s.substring(0, n); }
剑指 Offer 61. 扑克牌中的顺子
-
排序之后计算最大值和最小值的差值 < 5 && 不能有重复元素。
public boolean isStraight(int[] nums) { if (nums.length > 5) { return false; } int zeroCount = 0; Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { if (nums[i] == 0) { zeroCount++; } else if (i != nums.length - 1 && nums[i] == nums[i + 1]) { return false; } } return (nums[nums.length - 1] - nums[zeroCount]) < 5; }
剑指 Offer 66. 构建乘积数组
-
分别计算
nums[i]左右两边的乘机，然后相乘。public int[] constructArr(int[] a) { int left = 1; int res[] = new int[a.length]; for (int i = 0; i < a.length; i++) { res[i] = left; left *= a[i]; } int right = 1; for (int i = a.length - 1; i >= 0; i--) { res[i] *= right; right *= a[i]; } return res; }
剑指 Offer 67. 把字符串转换成整数
-
按下标遍历，主要是判断越界的方法。
public int strToInt(String str) { str = str.trim(); if (str.length() == 0) { return 0; } int index = 0; char first = str.charAt(0); if (!(first == '+' || first == '-' || (first >= '0' && first <= '9'))) { return 0; } int sign = 1; if (first == '+' || first == '-') { sign = first == '+' ? 1 : -1; index++; } int count = 0; int boundary = Integer.MAX_VALUE / 10; while (index < str.length()) { if (str.charAt(index) < '0' || str.charAt(index) > '9') { break; } if (count > boundary || (count == boundary && str.charAt(index) > '7')) { return sign == -1 ? Integer.MIN_VALUE : Integer.MAX_VALUE; } count = count * 10 + (str.charAt(index) - '0'); index++; } return sign == -1 ? -count : count; }
栈和队列
剑指 Offer 06. 从尾到头打印链表
遍历一次，计算链表节点个数，再遍历一次从后往前填充数组。
-
或者是借助一个辅助栈。
public int[] reversePrint(ListNode head) { int count = 0; ListNode headDump = head; while (head != null) { count++; head = head.next; } int[] result = new int[count]; while(headDump != null) { result[--count] = headDump.val; headDump = headDump.next; } return result; }
剑指 Offer 09. 用两个栈实现队列
-
一个栈存进栈的元素，另一个栈缓存出栈的元素。
class CQueue { Stack<Integer> s1; Stack<Integer> s2; public CQueue() { s1 = new Stack<>(); s2 = new Stack<>(); } public void appendTail(int value) { s1.push(value); } public int deleteHead() { if (s2.isEmpty()) { while (!s1.isEmpty()) { s2.push(s1.pop()); } } if (s2.isEmpty()) { return -1; } return s2.pop(); } }
剑指 Offer 30. 包含min函数的栈
-
用一个栈存当前最小元素。
class MinStack { Stack<Integer> data; Stack<Integer> minData; /** initialize your data structure here. */ public MinStack() { data = new Stack<>(); minData = new Stack<>(); } public void push(int x) { data.push(x); if (minData.isEmpty() || x <= minData.peek()) { minData.push(x); } } public void pop() { if (data.isEmpty()) { return; } if (data.pop().equals(minData.peek())) { minData.pop(); } } public int top() { if (data.isEmpty()) { return -1; } return data.peek(); } public int min() { if (minData.isEmpty()) { return -1; } return minData.peek(); } }
剑指 Offer 31. 栈的压入、弹出序列
-
按照题意模拟栈的操作，直到所有元素都与弹出序列匹配，返回
true。public boolean validateStackSequences(int[] pushed, int[] popped) { Stack<Integer> stack = new Stack<>(); int index = 0; for (int num: pushed) { stack.push(num); while (!stack.isEmpty() && popped[index] == stack.peek()) { stack.pop(); index++; } } return index == popped.length; }
剑指 Offer 59 - I. 滑动窗口的最大值
-
滑动窗口算法的应用，可以辅助一个最小值下标队列降低时间复杂度。
public int[] maxSlidingWindow(int[] nums, int k) { if (nums.length == 0 || k == 0) { return new int[0]; } int[] res = new int[nums.length - k + 1]; int l = 0, r = 0; LinkedList<Integer> maxNums = new LinkedList<>(); while (l < res.length) { r++; while (!maxNums.isEmpty() && nums[maxNums.peekLast()] <= nums[r - 1]) { maxNums.removeLast(); } maxNums.addLast(r - 1); if (r - l == k) { res[l] = nums[maxNums.peekFirst()]; } if (r - l == k) { if (maxNums.peekFirst() == l) { maxNums.removeFirst(); } l++; } } return res; }
剑指 Offer 59 - II. 队列的最大值
-
两个队列实现，一个队列负责队列的基本操作，另一个队列维护一个单调最大值集合。
class MaxQueue { LinkedList<Integer> queue; LinkedList<Integer> maxValues; public MaxQueue() { queue = new LinkedList<>(); maxValues = new LinkedList<>(); } public int max_value() { if (maxValues.isEmpty()) { return -1; } return maxValues.getFirst(); } public void push_back(int value) { while (!maxValues.isEmpty() && maxValues.getLast() < value) { maxValues.removeLast(); } maxValues.addLast(value); queue.addLast(value); } public int pop_front() { if (queue.isEmpty()) { return -1; } int res = queue.removeFirst(); if (res == maxValues.getFirst()) { maxValues.removeFirst(); } return res; } }
哈希表
剑指 Offer 03. 数组中重复的数字
-
数组中元素范围固定，hash 桶统计元素个数。
public int findRepeatNumber(int[] nums) { int[] count = new int[nums.length]; for (int num : nums) { if (count[num] == 0) { count[num] = 1; } else { return num; } } return -1; }
剑指 Offer 48. 最长不含重复字符的子字符串
-
滑动窗口的应用，可借助 hash 桶记录窗口内元素出现的位置，当窗口内出现重复元素时，即可快速向左收缩窗口大小。
public int lengthOfLongestSubstring(String s) { int[] window = new int[256]; Arrays.fill(window, -1); int l = 0, r = 0; int res = 0; while (r < s.length()) { char curr = s.charAt(r); r++; if (window[curr] != -1) { l = Math.max(l, window[curr]); } window[curr] = r; res = Math.max(res, r - l); } return res; }
剑指 Offer 50. 第一个只出现一次的字符
-
暴力求解，两边遍历。
public char firstUniqChar(String s) { int[] count = new int[26]; for(char c : s.toCharArray()) { count[c - 'a']++; } for (char c : s.toCharArray()) { if (count[c - 'a'] == 1) { return c; } } return ' '; }
链表
剑指 Offer 18. 删除链表的节点
-
遍历找到要删除的链表节点，在遍历的过程中保存 pre 节点，找到之后改节点 next 指针，直接删除。
public ListNode deleteNode(ListNode head, int val) { if (head.val == val) { return head.next; } ListNode curr= head; ListNode pre = curr; while (curr != null && curr.val != val) { pre = curr; curr = curr.next; } if (curr != null) { pre.next = curr.next; } return head; }
剑指 Offer 22. 链表中倒数第k个节点
-
链表类题目中快慢指针最基本实践，快指针先走 K 步，然后快慢指针一起走。
public ListNode getKthFromEnd(ListNode head, int k) { ListNode slow = head; ListNode fast = head; int step = k; while (k > 0 && fast != null) { fast = fast.next; k--; } while (fast != null) { fast = fast.next; slow = slow.next; } return slow; }
剑指 Offer 24. 反转链表
-
修改每个节点的 next 指针，需要三个指针 pre、 curr、 tail。
public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode curr = head; ListNode tail = null; while (curr != null) { tail = curr.next; curr.next = pre; pre = curr; curr = tail; } return pre; }
剑指 Offer 25. 合并两个排序的链表
-
依次合并节点，注意最后较长链表剩余部分拼接。
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: res = ListNode(0) curr = res while l1 and l2: if l1.val < l2.val: curr.next = l1 l1 = l1.next else: curr.next = l2 l2 = l2.next curr = curr.next if l1: curr.next = l1 if l2: curr.next = l2 return res.next
剑指 Offer 52. 两个链表的第一个公共节点
如果A != B，分别循环遍历 A + B
-
如果A == B，则同时遍历A、B
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode currA = headA; ListNode currB = headB; while (currA != currB) { currA = currA == null ? headB : currA.next; currB = currB == null ? headA : currB.next; } return currA; }
搜索
剑指 Offer 12. 矩阵中的路径
-
深度优先搜索，循环以矩阵中的每一个节点作为起始节点进行搜索。
public boolean exist(char[][] board, String word) { for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (dfs(board, i, j, 0, word)) { return true; } } } return false; } public boolean dfs(char[][] board, int row, int col, int index, String word) { if (index == word.length()) { return true; } if (row < 0 || col < 0 || row >= board.length || col >= board[0].length || board[row][col] != word.charAt(index)) { return false; } board[row][col] = '\0'; boolean res = dfs(board, row + 1, col, index + 1, word) || dfs(board, row - 1, col, index + 1, word) || dfs(board, row, col + 1, index + 1, word) || dfs(board, row, col - 1, index + 1, word); board[row][col] = word.charAt(index); return res; }
剑指 Offer 13. 机器人的运动范围
DFS 和 BFS 均可以做，典型的水满岛屿问题。
-
注意此处递归结束，状态不用重置，因为同一个节点无需被统计两次。
public int movingCount(int m, int n, int k) { return dfs(new boolean[m][n], 0, 0, k); } public int dfs(boolean[][] visited, int row, int col, int k) { if (row < 0 || col < 0 || row >= visited.length || col >= visited[0].length || visited[row][col]) { return 0; } if (sumDigit(row) + sumDigit(col) > k) { return 0; } visited[row][col] = true; return 1+ dfs(visited, row + 1, col, k)+ dfs(visited, row - 1, col, k)+ dfs(visited, row, col + 1, k)+ dfs(visited, row, col - 1, k); } int sumDigit(int num) { int res = 0; while (num != 0) { res += num % 10; num /= 10; } return res; }
树
剑指offer 37 序列化二叉树
解题要点：通过层次遍历序列化二叉树。因为序列化后的字符串是带完整信息的二叉树序列，所以可通过层次遍历的结果反向构造二叉树。
-
注意 null 和 "[]" 的边界处理。
// Encodes a tree to a single string. public String serialize(TreeNode root) { if (root == null) { return "[]"; } Deque<TreeNode> visited = new LinkedList<>(); visited.add(root); StringBuilder sb = new StringBuilder("["); while (!visited.isEmpty()) { TreeNode curr = visited.pollFirst(); if (curr != null) { sb.append(curr.val).append(","); visited.addLast(curr.left); visited.addLast(curr.right); } else { sb.append("null").append(","); } } sb.deleteCharAt(sb.length() - 1); sb.append("]"); return sb.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { Deque<TreeNode> levelNodes = new LinkedList<>(); String[] nodeStrs = data.substring(1, data.length() - 1).split(","); if (nodeStrs.equals("")) { return null; } TreeNode root = new TreeNode(Integer.parseInt(nodeStrs[0])); int index = 0; try { levelNodes.add(root); while (index < nodeStrs.length - 1) { int levelCount = levelNodes.size(); for (int i = 0; i < levelCount; i++) { TreeNode curr = levelNodes.pollFirst(); String leftStr = nodeStrs[++index]; if (!leftStr.equals("null")) { curr.left = new TreeNode(Integer.parseInt(leftStr)); levelNodes.addLast(curr.left); } String rightStr = nodeStrs[++index]; if (!rightStr.equals("null")) { curr.right = new TreeNode(Integer.parseInt(rightStr)); levelNodes.addLast(curr.right); } } } } catch (NumberFormatException e) { System.out.println("Number format exception."); } return root; }
剑指 Offer 27. 二叉树的镜像
-
分别对所有的左右子树进行对调。
public TreeNode mirrorTree(TreeNode root) { if (root == null) { return null; } TreeNode tmp = mirrorTree(root.left); root.left = mirrorTree(root.right); root.right = tmp; return root; }
剑指 Offer 28. 对称的二叉树
-
分别判断左子树的 left 、右子树的 right是否相同 和左子树的 right、右子树的 left 是否相同。
public boolean isSymmetric(TreeNode root) { return root == null || isSymmetric(root.left, root.right); } boolean isSymmetric(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p == null || q == null || p.val != q.val) { return false; } return isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left); }
剑指 Offer 54. 二叉搜索树的第k大节点
-
二叉搜索树的中序遍历是个升序数组，反向遍历（右->根->左）即是一个降序数组，遍历到第K个元素返回。
class Solution { int res = 0; int count; public int kthLargest(TreeNode root, int k) { count = k; dfs(root); return res; } public void dfs(TreeNode root) { if (root != null && count > 0) { dfs(root.right); if (--count == 0) { res = root.val; return; } dfs(root.left); } } }
剑指 Offer 55 - I. 二叉树的深度
-
左右子树的深度求最大值。
public int maxDepth(TreeNode root) { if (root == null) { return 0; } return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; }
剑指 Offer 32 - I. 从上到下打印二叉树
-
二叉树的层序遍历。
public int[] levelOrder(TreeNode root) { if (root == null) { return new int[0]; } Deque<TreeNode> queue = new LinkedList<>(); TreeNode curr; queue.push(root); List<Integer> res = new ArrayList<>(); while (!queue.isEmpty()) { curr = queue.pollFirst(); res.add(curr.val); if (curr.left != null) { queue.addLast(curr.left); } if (curr.right != null) { queue.addLast(curr.right); } } return res.stream().mapToInt(Integer::intValue).toArray(); }
剑指 Offer 32 - II. 从上到下打印二叉树 II
-
二叉树的层序遍历，按行保存。
public List<List<Integer>> levelOrder(TreeNode root) { if (root == null) { return new ArrayList<>(); } List<List<Integer>> result = new ArrayList<>(); LinkedList<TreeNode> visited = new LinkedList<>(); visited.add(root); while (!visited.isEmpty()) { int count = visited.size(); List<Integer> level = new ArrayList<>(); for (int i = 0; i < count; i++) { TreeNode curr = visited.pollFirst(); level.add(curr.val); if (curr.left != null) { visited.addLast(curr.left); } if (curr.right != null) { visited.addLast(curr.right); } } result.add(level); } return result; }
剑指 Offer 32 - III. 从上到下打印二叉树 III
-
二叉树的层序遍历，隔行按反序保存。
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } LinkedList<TreeNode> visited = new LinkedList<>(); visited.add(root); boolean isReverse = false; while (!visited.isEmpty()) { List<Integer> level = new LinkedList<>(); int levelCount = visited.size(); for (int i = 0; i < levelCount; i++) { TreeNode curr = visited.removeFirst(); level.add(curr.val); if (curr.left != null) { visited.add(curr.left); } if (curr.right != null) { visited.add(curr.right); } } if (isReverse) { Collections.reverse(level); } isReverse = !isReverse; res.add(level); } return res; }
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
二分思想，直到两个节点分别位于 root 两侧。
-
注意等号怎么处理。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while (root != null && (root.val - p.val) * (root.val - q.val) > 0) { if (root.val - p.val < 0) { root = root.right; } else { root = root.left; } } return root; }
剑指 Offer 68 - II. 二叉树的最近公共祖先
-
递归处理，遇到 p、q 节点直接返回。
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) { return root; } TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left == null) { return right; } if (right == null) { return left; } return root; }
剑指 Offer 07. 重建二叉树
-
递归求解，不断缩小规模
Map<Integer, Integer> inorderIndex = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { for (int i = 0; i < inorder.length; i++) { inorderIndex.put(inorder[i], i); } return buildTree(preorder, 0, inorder, 0, inorder.length - 1); } public TreeNode buildTree(int[] preorder, int preLeft, int[] inorder, int inLeft, int inRight) { if (preLeft < 0 || inLeft < 0 || inRight >= inorder.length || inLeft > inRight) { return null; } int rootVal = preorder[preLeft]; TreeNode root = new TreeNode(rootVal); int rootIndex = inorderIndex.get(rootVal); root.left = buildTree(preorder, preLeft + 1, inorder, inLeft, rootIndex - 1); root.right = buildTree(preorder, preLeft + rootIndex - inLeft + 1, inorder, rootIndex + 1, inRight); return root; }
剑指 Offer 26. 树的子结构
-
先找到根节点，然后验证左子树和右子树
public boolean isSubStructure(TreeNode A, TreeNode B) { return (A != null && B != null) && (dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)); } public boolean dfs(TreeNode A, TreeNode B) { if (B == null) { return true; } if (A == null || A.val != B.val) { return false; } return dfs(A.left, B.left) && dfs(A.right, B.right); }
动态规划
剑指 Offer 10- I. 斐波那契数列
f(n) = f(n - 1) + f(n - 2)-
同类问题，青蛙跳台阶
public int fib(int n) { int a = 0; int b = 1; int sum; for(int i = 0; i < n; i++) { sum = (a + b) % 1000000007; a = b; b = sum; } return a; }
剑指 Offer 42. 连续子数组的最大和
dp[n] = max(0, dp[n - 1]) + nums[n]-
借助原有数组可降低空间复杂度至
O(1)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; }
剑指 Offer 46. 把数字翻译成字符串
dp[n] 表示已 num.charAt(n) 结尾的数字有多少种翻译方法。
-
递归也可以解，但是规模超过一定限制后会超时。
public int translateNum(int num) { String str = String.valueOf(num); int[] count = new int[str.length()]; for (int i = 0; i < str.length(); i++) { if (i == 0) { count[i] = 1; } else { String subStr = str.substring(i - 1, i + 1); if (subStr.compareTo("10") >= 0 && subStr.compareTo("26") < 0) { count[i] = i == 1 ? count[0] + 1 : count[i - 2] + count[i - 1]; } else { count[i] = count[i - 1]; } } } return count[str.length() - 1]; }
剑指 Offer 47. 礼物的最大价值
以当前格子为终点的礼物最大值依赖于以左边和上边格子为终点格子的礼物最大值。
-
状态压缩，降低空间复杂度。
public int maxValue(int[][] grid) { if (grid == null || grid.length == 0) { return 0; } int[] maxValues = new int[grid[0].length]; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < maxValues.length; j++) { maxValues[j] = Math.max(maxValues[j], j == 0 ? 0 : maxValues[j - 1]) + grid[i][j]; } } return maxValues[maxValues.length - 1]; }
剑指 Offer 49. 丑数
-
记录2，3，5因子的倍数下标，每次去三者之最小值，并将对应因子倍数下标 + 1。
public int nthUglyNumber(int n) { int[] index = new int[]{0, 0, 0}; int[] multi = new int[]{2, 3, 5}; int[] num = new int[]{1, 1, 1}; int[] dp = new int[n]; dp[0] = 1; for (int i = 1; i < dp.length; i++){ for (int j = 0; j < index.length; j++) { num[j] = dp[index[j]] * multi[j]; } dp[i] = Math.min(Math.min(num[0], num[1]), num[2]); for (int j = 0; j < index.length; j++) { if (dp[i] == num[j]) { index[j]++; } } } return dp[n - 1]; }
剑指 Offer 62. 圆圈中最后剩下的数字
假设第 i 次计算之后需要删除的数字下标是x，递推出 i+1 次的结果。
-
约瑟尔环问题
public int lastRemaining(int n, int m) { int[] remaining = new int[n]; for (int i = 2; i <= n; i++) { remaining[i - 1] = (remaining[i - 2] + m) % i; } return remaining[n - 1]; }
剑指 Offer 63. 股票的最大利润
-
dp[i][1] : 第 i 天持有股票的最大收益，dp[i][0]：第 i 天未持有股票的最大收益。
public int maxProfit(int[] prices) { if (prices.length == 0) { return 0; } int[][] maxProfits = new int[prices.length][2]; maxProfits[0][1] = - prices[0]; for (int i = 1; i < prices.length; i++) { maxProfits[i][0] = Math.max(maxProfits[i - 1][0], maxProfits[i - 1][1] + prices[i]); maxProfits[i][1] = Math.max(-prices[i], maxProfits[i - 1][1]); } return maxProfits[prices.length - 1][0]; }
位运算
剑指 Offer 15. 二进制中1的个数
n & (n - 1) 可以将 n 二进制最右边的 1 置为0。
-
循环上述计算直到 n == 0。
public int hammingWeight(int n) { int count = 0; while (n != 0) { count += (n & 0x1); n = n >>> 1; } return count; }
剑指 Offer 16. 数值的整数次方
-
二分递归
class Solution { public double myPow(double x, int n) { if (n < 0) { n = -n; x = 1 / x; } return fastPow(x, n); } public double fastPow(double x, int n) { if (n == 0) { return 1.0; } double res = fastPow(x, n / 2); return n % 2 == 0 ? res * res : res * res * x; } }
剑指 Offer 56 - I. 数组中数字出现的次数
-
通过异或求出 p^q，再找到这个结果中最右边的 1，通过这个 bit 位将数组分为两个子数组，p 和 q 因为在这个 bit 位上异或结果是1，所以 p 和 q 分别分到了不同的子数组中，最后分别异或这两个子数组求出 p 和 q。
public int[] singleNumbers(int[] nums) { int n = 0; for (int num : nums) { n ^= num; } int bit = 1; while ((bit & n) == 0) { bit <<= 1; } int num1 = 0, num2 = 0; for (int num : nums) { if ((num & bit) == 0) { num1 ^= num; } else { num2 ^= num; } } return new int[]{num1, num2}; }
剑指 Offer 65. 不用加减乘除做加法
位运算，a & b << 1 得出进位结果 ， a ^ b 得到相加不含进位结果。
-
不停循环直到进位为 0
public int add(int a, int b) { while (b != 0) { int carry = (a & b) << 1; a ^= b; b = carry; } return a; }
技巧类
剑指 Offer 64. 求1+2+…+n
-
通过 && 运算代替 if
public int sumNums(int n) { boolean flag = n > 0 && (n += sumNums(n - 1)) > 0; return n; }
剑指 Offer 44. 数字序列中某一位的数字
当前进制数字多少个bit，占用多少个位，循环计算
-
count = 9 * digit * start
public int findNthDigit(int n) { long start = 1; long digit = 1; long count = 9; while (count < n) { n -= count; digit += 1; start *= 10; count = 9 * digit * start; } long num = start + (n - 1) / digit; return String.valueOf(num).charAt((int)((n - 1) % digit)) - '0'; }
