1、二维数组中的查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
python版本:
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
row = len(array) - 1
col = len(array[0]) - 1
i = row
j = 0
while (j<=col and i>=0):
if target < array[i][j]:
i -= 1
elif target > array[i][j]:
j += 1
else:
return True
return False
java版本：
public class Solution {
public boolean Find(int target, int [][] array) {
int row = 0;
int col = array[0].length - 1;
while(row<=array.length-1 & col>=0){
if(target<array[row][col]){
col -= 1;
}
else if(target>array[row][col]){
row += 1;
}
else{
return true;
}
}
return false;
}
}
2、空格替换
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
java版本：
public class Solution {
public String replaceSpace(StringBuffer str) {
int spacenum = 0;
for(int i=0; i<str.length(); i++){
if(str.charAt(i) == ' '){
spacenum++;
}
}
int indexold = str.length() - 1;
int newlength = str.length() + spacenum*2;
int indexnew = newlength - 1;
str.setLength(newlength);
for(;indexold>=0&&indexold<newlength; --indexold){
if(str.charAt(indexold) == ' '){
str.setCharAt(indexnew--, '0');
str.setCharAt(indexnew--, '2');
str.setCharAt(indexnew--, '%');
}
else{
// 从indexnew的后边往前插入，先要计算好替换后的长度
// 这样每次在替换时，后边的不用动
str.setCharAt(indexnew--, str.charAt(indexold));
}
}
return str.toString();
}
}
3、从尾到头打印链表
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
java版本：
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
// 堆栈思想
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack=new Stack<Integer>();
while(listNode!=null){
stack.push(listNode.val);
listNode=listNode.next;
}
ArrayList<Integer> res_list=new ArrayList<Integer>();
while(!stack.isEmpty()){
res_list.add(stack.pop());
}
return res_list;
}
}
4、重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
import java.util.Arrays;
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre.length == 0 || in.length == 0){
return null;
}
// 确定跟节点为前序遍历的第一个元素
TreeNode root = new TreeNode(pre[0]);
// 在中序遍历中找到跟节点
for(int i = 0; i < in.length; i++){
if(in[i] == pre[0]){
// 左子树，copyOfRange函数，复制原始数组，下标左闭右开
root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
// 右子树
root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
break;
}
}
return root;
}
}
5、栈和队列的转换(两个栈实现队列 && 两个栈实现队列)
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
import java.util.Stack;
// 思路：当入栈时都入stack1，出栈时若stack2不为空则从stack2弹出
// 若为空则将stack1中的全部导入stack2中
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();
}
}
用两个队列来实现一个栈，完成队列的Push和Pop操作。 队列中的元素为int类型。
public static class Queue2Stack{
private Queue<Integer> data;
private Queue<Integer> help;
public Queue2Stack(){
data = new LinkedList<Integer>();
help = new LinkedList<Integer>();
}
public void push(int obj){
data.add(obj);
}
public int pop(){
if(data.isEmpty()){
throw new RuntimeException("Stack is empty!");
}
while(data.size() > 1){
help.add(data.poll());
}
// 关键的一步，交换引用
swap();
return data.poll();
}
public int peek(){
if(data.isEmpty()){
throw new RuntimeException("Stack is empty!");
}
while(data.size() != 1){
help.add(data.poll());
}
// 将data中最后一个元素即为栈顶元素，先取出
//再放回help栈交换，保证数据不发生变化
int res = data.poll();
help.add(res);
swap();
return res;
}
}
6、旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
// 二分查找的思路
public class Solution {
public int minNumberInRotateArray(int [] array) {
int low = 0;
int high = array.length - 1;
while(low < high){
int mid = low + (high-low)/2;
if(array[mid] > array[high]){
low = mid + 1;
}
else if(array[mid] == array[high]){
high = high - 1;
}
else{
high = mid;
}
}
return array[low];
}
}
7、斐波那契数列
现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）n<=39
66、剪绳子
一根长度为n（2<=n<=60）的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
// 贪心算法：要想乘积最大，分割的长度最好都是2或者3，因此就相当于取3和2的个数，因为3*3=9>2*2*2，所以先计算3的个数，再计算2的个数
public class Solution {
public int cutRope(int target) {
if(target<2){
return 0;
}
if(target == 2){
return 1;
}
if(target == 3){
return 2;
}
int timeOf3 = target / 3;
// 当减去的值为1时，表示剩下的长度为4，则切分为2和2，则timeOf3的数量减1
if(target - timeOf3 * 3 == 1){
timeOf3--;
}
int timeOf2 = (target - timeOf3*3) / 2;
return (int)Math.pow(3, timeOf3) * (int)Math.pow(2, timeOf2);
}
}
