1.二维数组查找
题目描述：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：本题中，由于二维数组在行和列都保持有序，将起始点设置在左下角和右上角可以利用数组的有序性快速查找。
代码：
public class Solution { public boolean Find(int target, int [][] array) { int row = array.length, col = array[0].length; if (array == null || row == 0 || col == 0) { return false; } int i = 0, j = col - 1; while (i < row && j >= 0) { if (array[i][j] == target){ return true; } else if (array[i][j] > target) { j--; } else { i++; } } return false; } }
2.替换空格
题目描述：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路：先将字符串转换成字符数组，用StringBuffer进行拼接，如果为空格，拼接%20；否则，拼接原位置字符。
代码：
public class Solution { public String replaceSpace (String s) { // write code here StringBuffer sb = new StringBuffer(); char[] ch = s.toCharArray(); for (int i = 0; i < ch.length; ++i) { if (ch[i] == ' ') { sb.append("%20"); } else { sb.append(ch[i]); } } return sb.toString(); } }
3.从尾到头打印链表
题目描述：输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
思路：
法1：遍历链表，add(int index, E element)方法： 将当前处于该位置的元素和所有后续元素向右移动（在其索引中加 1）。
法2：先顺序加入集合，然后使用工具类Colleactions反转集合。
法2：反转链表后顺序加入集合，考察反转链表。
代码：
public class Solution { // 法1.指定位置加入元素 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> ans = new ArrayList<>(); ListNode t = listNode; while (t != null) { ans.add(0, t.val); t = t.next; } return ans; } // 法2.Colleactions工具类 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> ans = new ArrayList<>(); ListNode t = listNode; while (t != null) { ans.add(t.val); t = t.next; } Collections.reverse(ans); return ans; } // 法3：链表反转 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> ans = new ArrayList<>(); // ListNode newHead = reverseList(listNode); ListNode pre = null, next; while (listNode != null) { next = listNode.next; listNode.next = pre; pre = listNode; listNode = next; } while (pre != null) { ans.add(pre.val); pre = pre.next; } return ans; } } // 反转链表递归版本 public ListNode reverseList (ListNode listNode) { if (listNode == null || listNode.next == null) { return listNode; } ListNode newHead = reverseList(listNode.next); listNode.next.next = listNode; //改变指针 listNode.next = null; return newHead; }
4.重建二叉树
题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：根据题意和二叉树遍历知识，我们可以得到以下逻辑：
- 前序遍历的首个元素即为根节点
root的值； - 在中序遍历中搜索根节点
root的索引 ，可将中序遍历划分为[ 左子树 | 根节点 | 右子树 ] - 根据中序遍历中的左（右）子树的节点数量(理解pre_root的更新)，可将前序遍历划分为
[ 根节点 | 左子树 | 右子树 ]
子树以同样的方法进行划分，每轮可确认三个节点的关系 ，即树的根节点和左右子树的根节点（前序遍历中左右子树的首个元素），这样递推我们可以使用递归实现，三部曲：
- 递归函数：通过前序遍历中根节点的索引
pre_root、中序遍历左边界in_left、中序遍历右边界in_right三者关系构建树。 - 终止条件：子树中序遍历为空，
in_left > in_right，返回null - 递归逻辑：构建头结点-->找到当前根节点在中序遍历数组中的索引 --> 递归左右子树。
代码：
public class Solution { HashMap<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 rebuildTree(pre, 0, 0, in.length - 1); } public TreeNode rebuildTree(int[] pre, int pre_root, int in_left, int in_right) { if (in_left > in_right) return null; TreeNode root = new TreeNode(pre[pre_root]); // 获取当前头结点在中序遍历数组的索引 int i = map.get(pre[pre_root]); root.left = rebuildTree(pre, pre_root + 1, in_left, i - 1); // i - in_left + 1:当前节点的偏移 root.right = rebuildTree(pre, pre_root + i - in_left + 1, i + 1, in_right); return root; } }
5.用两个栈实现队列操作
题目描述：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路：压栈（stack1），出栈进辅助栈（stack2），辅助栈实现队列pop()操作。注：由于出栈时要检查是否为空！
代码：
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 (stack2.isEmpty()) { while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } } return stack2.pop(); } }
