1.二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
考点：数组
- 1.直接使用两次嵌套遍历。时间复杂度O(n^2)
public class Solution {
public boolean Find(int [][] array,int target) {
for(int i=0;i<array.length;i++){
for(int j=0;j<array[i].length;j++){
if(array[i][j]==target){
return true;
}
}
}
return false;
}
}
- 2.改进：根据题目，每行每列都是递增，则找到矩阵右上角数字，判断它和target大小，它小则行减1，它大则列减一。时间复杂度O(n)
public class Problem_1 {
public static boolean Find(int[][] array, int target) {
boolean found = false;
int rows = array.length;
int columns = array[0].length;
if (array != null && rows > 0 && columns > 0 ) {
int row = 0;
int column = columns - 1;
while (row < rows && column >= 0) {
if (array[row][column] == target) {
found = true;
break;
}
else if (array[row][column] > target) {
--column;
}
else
++row;
}
}
return found;
}
}
2.替换空格
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
考点：字符串
public class Solution {
public String replaceSpace(StringBuffer str) {
String str1 = str.toString();
String str2 = str1.replace(" ", "%20");
return str2;
}
}
3.从尾到头打印链表
输入一个链表，从尾到头打印链表每个节点的值。
考点：链表
解题点：先进后出，使用栈。递归的本质就是栈。
使用栈
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> sk = new Stack<Integer>();
while(listNode!=null)
{
sk.push(listNode.val);
listNode=listNode.next;
}
ArrayList<Integer> al = new ArrayList<Integer>();
while(!sk.isEmpty())
{
al.add(sk.pop());
}
return al;
}
}
使用递归
/**
* 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> list = new ArrayList<Integer>();
if (list == null){
return list;
}
ListNode pnode = listNode;
if(pnode != null){
if(pnode.next != null){
list = printListFromTailToHead(pnode.next);
}
list.add(pnode.val);
}
return list;
}
}
当链表很长时，则函数调用层级很深，导致函数调用栈溢出。
4.重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
考点：二叉树
先序中序后序遍历的实现方法都有递归和循环实现方法。
求最大（最小值）时可以使用最大（最小）堆来解决。
- 1.根据先序和中序的特点，根据先序第一个值找到根节点;
- 2.在中序中找到根节点，则根节点前面就是左子树，后面就是右子树；
- 3.通过递归，构建新二叉树的左子树和右子树。
/**
* 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) {
TreeNode root = inputTree(pre, 0, pre.length-1, in, 0, in.length-1);
return root;
}
public TreeNode inputTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn){
if(startPre > endPre || startIn > endIn){
return null;
}
TreeNode root = new TreeNode(pre[startPre]);
for(int i=startIn;i<=endIn;i++){
if(in[i]==pre[startPre]){
root.left=inputTree(pre,startPre+1,startPre+i-startIn,in,startIn,i-1);
root.right=inputTree(pre,startPre+i-startIn+1,endPre,in,i+1,endIn);
}
}
return root;
}
}
5.用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
考点：栈和队列
栈：先去后出；队列：先进先出
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(new Integer(node));
}
public int pop() {
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
if(stack2.empty()){
System.out.println("null");
}
return stack2.pop().intValue();
}
}
