题目描述：
在一个长度为 \(n\) 的数组里的所有数字都在 \(0\) 到 \(n-1\) 的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为 \(7\) 的数组 \(\{2,3,1,0,2,5,3\}\)，那么对应的输出是第一个重复的数字 \(2\)。
Input: {2, 3, 1, 0, 2, 5} Output: 2思路：
最直接的策略是使用哈希表，时间复杂度为 \(O(n)\)，但是它提高时间效率是以一个大小为 \(O(n)\) 的哈希表为代价的，可以采用更好的方式使空间复杂度降为 \(O(1)\)。
本题数组里的元素都在 \(0\) 到 \(n-1\) 的范围内，我们从头到尾扫描数组的每个元素，将元素 \(j = numbers[i]\) 与下标为 \(j\) 的元素进行位置交换，如果 \(numbers[j]\) 已经等于 \(j\)，则不用进行交换，数字 \(j\) 就是重复数字（\(i \ne j\)）。
public class Solution { /** * numbers: 数组；length: 数组的长度；duplication[0]: 存放任意一个重复的数字 * 返回为 true 代表为数组中存在重复数字，false 代表没有 */ public boolean duplicate(int[] numbers,int length,int[] duplication) { for(int i = 0; i < length; i++) { while(i != numbers[i]) { int j = numbers[i]; if(numbers[j] == j) { //要替换的位置下标 j 上的元素已经为 j，说明已经存在重复元素 duplication[0] = j; return true; } //进行位置上的元素替换 numbers[i] = numbers[j]; numbers[j] = j; } } return false; } }题目描述：
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
Consider the following matrix: [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] Given target = 5, return true. Given target = 20, return false.思路：
该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 \(target\) 和当前元素的大小关系来缩小查找区间，如果当前元素等于 \(target\)，返回 \(true\)；如果当前元素小于 \(target\)，则下个位置左移；如果当前元素大于 \(target\)，则下个位置下移；如果下个位置超出了数组边界范围，返回 \(false\)。
public class Solution { public boolean Find(int target, int [][] array) { if(array == null || array.length == 0 || array[0].length == 0) { return false; } int m = array.length, n = array[0].length; int i = 0, j = n - 1; while(i < m && j >= 0) { if(array[i][j] == target) { return true; }else if(array[i][j] < target) { i++; }else{ j--; } } return false; } }题目描述：
请实现一个函数，将一个字符串中的每个空格替换成 “ ”。例如，当字符串为 We Are Happy，则经过替换之后的字符串为 We Are Happy。
思路：
本题可以直接使用 \(String\) 的 \(replace()\) 或者 \(replaceAll()\) 方法，但是该题的本意是希望在一个字符数组上实现该功能。
public class Solution { public String replaceSpace(StringBuffer str) { return str.toString().replace(" ", " "); } }将字符数组扩充到能容纳替换后的字符串大小，使用指针 \(p1\) 指向原来的字符数组末端，指针 \(p2\) 指向扩充后的字符数组末端。指针 \(p1\) 向前移动，$p1 $ 遇到非空格字符，将该字符拷贝到 \(p2\) 位置，\(p2\) 向前移动一位；\(p1\) 遇到空格字符，\(p2\) 向前移动三位，\(p2\) 后续的三位放置 " "；直达两指针相遇结束。
public class Solution { public String replaceSpace(StringBuffer str) { 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 < p2) { if(str.charAt(p1) != ' ') { str.setCharAt(p2--, str.charAt(p1--)); }else { str.setCharAt(p2--, '0'); str.setCharAt(p2--, '2'); str.setCharAt(p2--, '%'); p1--; } } return str.toString(); } }题目描述：
输入一个链表，按链表从尾到头的顺序返回一个 \(ArrayList\)。
思路：
思路一：
使用递归的方式，逆序打印该链表。
/** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } */ import java.util.ArrayList; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> ret = new ArrayList<>(); if(listNode == null) { return ret; } dfs(listNode, ret); return ret; } public void dfs(ListNode listNode, ArrayList<Integer> ret) { if(listNode.next != null) { dfs(listNode.next, ret); } ret.add(listNode.val); } }思路二：
使用头插法的方式得到一个逆序的链表。
头插法的头结点 \(head\) 是一个额外节点，这个节点不存储值，\(head.next\) 才是链表的第一个节点。当需要插入一个新的节点 \(node\)，该节点的插入位置在 \(head\) 和 \(head.next\) 之间，所以插入时 \(node.next = head.next\)，\(head.next =node\)。
/** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } */ import java.util.ArrayList; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ListNode head = new ListNode(-1); while(listNode != null) { ListNode node = listNode.next; listNode.next = head.next; head.next = listNode; listNode = node; } ArrayList<Integer> ret = new ArrayList<>(); while(head.next != null) { ret.add(head.next.val); head = head.next; } return ret; } }思路三：
使用栈结构。
/** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } */ import java.util.*; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { Stack<Integer> stack = new Stack<>(); while(listNode != null) { stack.push(listNode.val); listNode = listNode.next; } ArrayList<Integer> ret = new ArrayList<>(); while(!stack.isEmpty()) { ret.add(stack.pop()); } return ret; } }题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 \(\{1,2,4,7,3,5,6,8\}\) 和中序遍历序列 \(\{4,7,2,1,5,3,8,6\}\)，则重建下图所示二叉树并返回二叉树的根节点。
思路：
可以从二叉树的前序遍历和中序遍历序列中确定根节点的值、左子树和右子树的范围。
/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode reConstructBinaryTree(int[] pre,int [] in) { return buildSubTree(pre, in, 0, 0, pre.length); } //pStart 是子树在前序遍历数组的起始索引，iStart 是子树在中序遍历数组的起始索引，len 是子树节点数目（大小） public TreeNode buildSubTree(int[] pre, int[] in, int pStart, int iStart, int len) { if(len == 0) { return null; } //子树根节点 int rootVal = pre[pStart]; TreeNode root = new TreeNode(rootVal); //寻找中序遍历数组中子树的根节点 int index = iStart; while(in[index] != rootVal) { index++; } int lLen = index - iStart; //根节点左子树的大小 int rLen = len - lLen - 1; //根节点右子树的大小 //左右孩子节点 TreeNode lNode = buildSubTree(pre, in, pStart + 1, iStart, lLen); TreeNode rNode = buildSubTree(pre, in, pStart + lLen + 1, iStart + lLen + 1, rLen); root.left = lNode; root.right = rNode; return root; } }题目描述：
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。下图中，树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的指针用虚线表示。
思路：
中序遍历顺序的下一个节点可以分两种情况讨论：
如果一个节点的右子树不为空，那么该节点的下一个节点是其右子树的最左节点。例如：上图中的节点 \(b\) 的下一个节点为 \(h\)， 节点 \(a\) 的下一个节点是 \(f\)，节点 \(e\) 的下一个节点是 \(i\) 。如果一个节点的右子树为空，我们沿着父节点的指针往上遍历，如果遍历的某个节点是其父节点的左孩子节点，则该节点的父节点便是我们要寻找的下一个节点。例如：上图中的节点 \(i\) 的下一个节点为 \(a\)，节点 \(d\) 的下一个节点为 \(b\)。 /* public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) { this.val = val; } } */ public class Solution { public TreeLinkNode GetNext(TreeLinkNode pNode){ if(pNode == null) { return null; } //右子树不为空，寻找右子树最左端 if(pNode.right != null) { TreeLinkNode node = pNode.right; while(node.left != null) { node = node.left; } return node; } //右子树为空，往父节点方向向上寻找，直到找到某个节点是其父节点的左孩子 if(pNode.right == null) { while(pNode.next != null) { TreeLinkNode parent = pNode.next; if(parent.left == pNode) { return parent; } pNode = parent; } } return null; } }题目描述：
用两个栈来实现一个队列，完成队列的 \(Push\) 和 \(Pop\) 操作。 队列中的元素为 \(int\) 类型。
思路：
使用两个栈 \(in\) 和 \(out\)，\(in\) 栈负责数据的入栈操作，\(out\) 栈负责数据的出栈操作。需要注意的是，\(in\) 栈的数据倾倒到 \(out\) 栈过程要一次性将 \(in\) 栈全部数据倒入。
import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); //in 栈 Stack<Integer> stack2 = new Stack<Integer>(); //out 栈 public void push(int node) { stack1.push(node); //入栈数据全部进入 in 栈 } public int pop() { if(stack2.isEmpty()) { //out 栈为空，要将 in 栈全部数据一次性倾倒到 out 栈 while(!stack1.isEmpty()) { stack2.push(stack1.pop()); } } return stack2.pop(); } }转载于:https://www.cnblogs.com/zongmin/p/11612478.html
