剑指offer总结（一）
1. 二维数组中的查找
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路
暴力法，直接两层循环，时间复杂度为O（row * col），牛客网能通过，但是不推荐
优化的方法：利用有序性避免不必要的查找。对于该数组的任意一个元素来说，大于它的元素在其右下方，小于它的元素在其左上方，所以我们可以从右上角开始搜索，当目标值大于当前元素时向下走，当目标值小于当前元素时，向左走。最好情况时间复杂度为O（1），最坏情况时间复杂度为O（row + col），平均时间复杂度为 O（row + col），空间复杂度为O（1）。
public class Solution { public boolean Find(int target, int [][] array) { if(array == null) return false; int rows = array.length; int cols = array[0].length; int row = 0, col = cols - 1; while(col >= 0 && row <= rows - 1){ if(target > array[row][col]) row++; else if(target < array[row][col]) col--; else return true; } return false; } }
2. 替换空格
题目描述
请实现一个函数，将一个字符串中的每个空格替换成 “%20”。例如，当字符串为 We Are Happy. 则经过替换之后的字符串为 We%20Are%20Happy。
解题思路
- 先确定给定字符串中有几个空格，每出现一个空格，则在字符串末尾添加两个空格，因为一个空格要替换成三个字符（%20）。
- 令 p1 指向原字符串的末尾，p2 指向当前字符串的末尾，为了不影响 p1 遍历原字符串，我们从后往前开始遍历字符串，当遇到 p1 为空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。
public class Solution { public String replaceSpace(StringBuffer str) { if(str == null) return str.toString(); int p1 = str.length() - 1; for(int i = 0; i <= p1; i++){ if(str.charAt(i) == ' ') str.append(" "); } int p2 = str.length() - 1; while(p1 >= 0 && p2 > p1) { char c = str.charAt(p1--); if(c == ' '){ str.setCharAt(p2--, '0'); str.setCharAt(p2--, '2'); str.setCharAt(p2--, '%'); } else { str.setCharAt(p2--, c); } } return str.toString(); } }
3. 从尾到头打印链表
题目描述
输入一个链表，按链表值从尾到头的顺序返回一个 ArrayList。
解题思路
- 最容易想到的就是遍历链表，每次都往 ArrayList 头部添加值，但每次添加，ArrayList的所有元素都要往后移动一位，故时间复杂度为 O（n ^2^)。由于题目限制了结果存放在 ArrayList ，所以不能直接使用 LinkendList 返回结果，但可以先降结果存放在 LinkedList （可以认为是一个栈）中（每次往头部添加元素时间复杂度为O（1）），然后再遍历 LinkedList 转存在 ArrayList 中，这样时间复杂度就降为O（n）了。但额外多使用了 一个 LinkedList，空间消耗大了。
//O（n ^2^) public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> res = new ArrayList<>(); while(listNode != null){ res.add(0, listNode.val); listNode = listNode.next; } return res; } } //O(n) public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> res = new ArrayList<>(); LinkedList<Integer> list = new LinkedList<>(); while(listNode != null){ list.addFirst(listNode.val); listNode = listNode.next; } for(int l : list){ res.add(l); } return res; } }
- 与上面思想类似的是使用一个头节点（不存放数据）先逆转链表，然后顺序遍历链表，依次存在放 ArrayList 中。
public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> res = new ArrayList<>(); ListNode head = new ListNode(-1); while(listNode != null) { ListNode next = listNode.next; listNode.next = head.next; head.next = listNode; listNode = next; } head = head.next; while(head != null) { res.add(head.val); head = head.next; } return res; } }
可以使用递归思想来实现头插，感觉效率比较低
public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> res = new ArrayList<>(); if(listNode != null) { res.addAll(printListFromTailToHead(listNode.next)); res.add(listNode.val); } return res; } }
4. 重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列 {4,7,2,1,5,3,8,6}，则重建二叉树并返回。
解题思路
前序序列第一个为根节点的值，根节点把中序遍历分为两部分，左边为左子树，右边为右子树。因为每次都要在中序序列中寻找根节点，所以用一个 HashMap 来存储中序序列的索引，查找的时候比较快
public class Solution { private Map<Integer, Integer> map = new HashMap<>(); public TreeNode reConstructBinaryTree(int [] pre,int [] in) { for(int i = 0; i < in.length; i++) map.put(in[i], i); return help(pre, 0, pre.length - 1, 0); } private TreeNode help(int[] pre, int low, int high, int inL){ if(low > high) return null; TreeNode head = new TreeNode(pre[low]); int index = map.get(pre[low]); int leftSize = index - inL; head.left = help(pre, low + 1, low + leftSize, inL); head.right = help(pre, low + leftSize + 1, high, index + 1); return head; } }
5. 两个栈实现队列
题目描述
用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。 队列中的元素为 int 类型。
解题思路
入队：直接往栈 s1 push
出队：如果两个栈都为空，则一个抛出异常。先判断栈 s2 是否为空，不为空直接在 s2 pop，否则将 s1 中所有元素转移到 s2 中，然后 s2 再 pop，一个优化的思路是当 s1 剩下一个元素的时候直接返回 s1 的最后一个元素
public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { stack1.push(node); } public int pop() { if(stack1.isEmpty() && stack2.isEmpty()) return -1; if(!stack2.isEmpty()) return stack2.pop(); while(!stack1.isEmpty() && stack1.size() != 1){ stack2.push(stack1.pop()); } return stack1.pop(); } }
6.旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转，该数组的最小值为 1。 NOTE：给出的所有元素都大于 0，若数组大小为 0，请返回 0。
解题思路
思路是每次将旋转数组对分之后会得到两个子数组，其中一个是递增数组，一个是新的旋转数组，这样就把问题规模减半了，时间复杂度为O(logn)。这里的问题是如何区分递增数组和新的旋转数组，根据规律可以发现旋转数组的第一个元素一定大于等于最后一个元素，而递增数组则是小于，所以可以用此来区分。
public class Solution { public int minNumberInRotateArray(int [] array) { if(array.length == 0) return 0; if(array.length == 1) return array[0]; int low = 0, high = array.length - 1; while(low < high ){ int mid = (low + high) / 2; if(array[mid] > array[high]) low = mid + 1; else high = mid; } return array[low]; } }
7. 斐波那契数列
题目描述
大家都知道斐波那契数列，现在要求输入一个整数 n，请你输出斐波那契数列的第 n 项（从 0 开始，第 0 项为 0）。n<=39
解题思路
如果使用递归求解，会重复计算一些子问题。例如，计算 f (4) 需要计算 f (3) 和 f (2)，计算 f (3) 需要计算 f (2) 和 f (1)，可以看到 f (2) 被重复计算了。递归是将一个问题划分成多个子问题求解，动态规划也是如此，但是动态规划会把子问题的解缓存起来，从而避免重复求解子问题。
public class Solution { public int Fibonacci(int n) { if(n == 1 || n == 0) return n; int res = 1, ppre = 0, pre = 1; for(int i = 2; i <= n; i++){ res = ppre + pre; ppre = pre; pre = res; } return res; } }
8. 跳台阶
题目描述
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
解题思路
当 n = 1时，有 1 种跳法；当 n = 2 时，有两种跳法 ；跳 n 阶台阶，可以先跳 1 阶台阶，再跳 n - 1 阶台阶，也可以先跳 2 阶台阶，再跳 n - 2 阶台阶；跳 n - 1 和 n -2 阶台阶可以看做跳 n 阶台阶的子问题，所以这是一个斐波那契数列问题，可用动态规划来求解。
public class Solution { public int JumpFloor(int target) { if(target == 1 || target == 2) return target; int res = 1,ppre = 1, pre = 2; for(int i = 3; i <= target; i++){ res = ppre + pre; ppre = pre; pre = res; } return res ; } }
9. 变态跳台阶
题目描述
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级…… 它也可以跳上 n 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
解题思路
跳 n 阶台阶可以从 n - 1 阶跳上去，也可以从 n - 2 阶台阶跳上去……甚至可以从 1 阶台阶跳上去，所以 f(n-1) = f(n-2) + f(n-3) + ... + f(0)；即 f (n) = 2^n-1^ ; 可以转换为位运算。
public class Solution { public int JumpFloorII(int target) { int res = 1; for(int i = 1; i < target; i++){ res <<= 1; } return res; } }
10 矩形覆盖
题目描述
我们可以用 21 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 21 的小矩形无重叠地覆盖一个 2*n 的大矩形，总共有多少种方法？
解题思路
当 n 为 1 时，只有一种覆盖方法，当 n 为 2 时，有两种覆盖方法：要覆盖 2n 的大矩形，可以先覆盖 2*1 的矩形，再覆盖 2(n-1) 的矩形；或者先覆盖 22 的矩形，再覆盖 2(n-2) 的矩形。而覆盖 2(n-1) 和 2(n-2) 的矩形可以看成子问题。所以这是一个斐波那契数列问题，可用动态规划来求解。
public class Solution { public int RectCover(int target) { if(target <= 2) return target; int res = 0, ppre = 1, pre = 2; for(int i = 2; i < target; i++){ res = ppre + pre; ppre = pre; pre = res; } return res; } }
11. 二进制中1的个数
题目描述
输入一个整数，输出该数二进制表示中 1 的个数。其中负数用补码表示。
解题思路
n & n - 1 每次都能消除一个最低位的
public class Solution { public int NumberOf1(int n) { /** n & n - 1 每次都能消除一个 1 **/ int count = 0; while(n != 0){ n = n & (n - 1); count++; } return count; } }
Integer 中有个 bitCount（） 方法可以统计 二级制 1 的个数
public class Solution { public int NumberOf1(int n) { return Integer.bitCount(n); } }
CVTE公司福利 266人发布