categories

二维数组中的查找

本题知识点：查找

题目描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

public class Solution {
    public boolean Find(int target, int [][] array) {
        if (array.length == 0) return false;
        else if (array[0].length == 0) return false;
        int row = array.length-1;
        int column = array[0].length-1;
        int begin = 0;
        while(begin <= column && row >= 0){
            if (target < array[row][begin]) {
                row --;
            }
            else if (target > array[row][begin]) {
                begin ++;
            }
            else return true;                
        }
        return false;
    }
}

注意事项

二维数组为空，要检查三个部分:

数组首地址是否为空，
是否为“[]”（此处用大括号hexo会报错），也就是array.length==0的情况，
是否为“[[]]”（此处用大括号hexo会报错），这时array.length=1，但是array[0].length==0。满足任意一个条件就可以返回false了。

1 2	if(array==null\|\|array.length==0\|\|(array.length==1&&array[0].length==0)) return false;

替换空格

本题知识点：字符串

题目描述

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

public class Solution {
    public String replaceSpace(StringBuffer str) {
    	int length = str.length();
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < length; i++) {
            if (str.charAt(i)==' ') {
                sb.append("%20");
            }
            else {
                sb.append(str.charAt(i));
            }
        }
        return sb.toString();
    }
}

注意事项

StringBufffer的append()的参数类型要求是String，但是char实测也可以。
输出的时候要求String类型，要是用StringBuffer的toString()函数进行转换。
本题没有改变原有的StringBuffer的值，即使将初始变量的类型改为String，代码也同样适用。
使用Java的时候也不用考虑数组溢出的情况。

从尾到头打印链表

本题知识点：链表

题目描述

输入一个链表，从尾到头打印链表每个节点的值。

/**
*    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>();
        _printListFromTailToHead(listNode,list);
        return list;
    }   
    public void _printListFromTailToHead(ListNode listNode, ArrayList<Integer> list) {
        if (listNode != null){
            if (listNode.next != null) {
                _printListFromTailToHead(listNode.next,list);
            }
            list.add(listNode.val);
        }
    }    
}

注意事项

ArrayList的声明方式如下：

1	ArrayList<Integer> list = new ArrayList<Integer>();

可以用一个静态变量

1	static ArrayList<Integer> list = new ArrayList<Integer>();

来进行递归时的数据保存，但是在测试多个测试用例的时候会出现之前的输入无法清零错误，比如连续测试两个长度为4的链表，第二次测试会输出一个长度为8的数组。于是采用双函数的方式。
基于栈的代码以后再补充，就是顺序输入一个ArrayList之后再倒序输入另一个ArrayList即可。使用get()和add()方法即可。

/**
 * 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 tree = new TreeNode();
        int length = pre.length;
        _reConstructBinaryTree(pre,in, tree, 0, 0, length);
        return tree;
    }
    public TreeNode _reConstructBinaryTree(int [] pre,int [] in, TreeNode tree,int preindex, int inindex, int length) {
        for(int i = inindex; i < inindex + length; i++) {
            if(in[i]==pre[preindex]){
                tree.val = pre[preindex];
                int leftlength = i - inindex;
                int rightlength = length - i;
                int leftpreindex = preindex + 1;
                int rightpreindex = leftpreindex + leftlength;
                int leftinindex = inindex;
                int rightinindex = i+1;
            }
        }
        tree.left = _reConstructBinaryTree(pre,in, tree.left, leftpreindex, leftinindex, leftlength);
        tree.right = _reConstructBinaryTree(pre,in, tree.right, rightpreindex, rightinindex, rightlength);
        return tree;
}

重建二叉树

本题知识点：链表

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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) {
          if (pre.length <= 0 || in.length <= 0 || pre.length != in.length) {
            return null;
          }
	        int len = pre.length;
	        return _reConstructBinaryTree(pre, in, 0, len - 1, 0, len - 1);
	    }
	    public TreeNode _reConstructBinaryTree(int [] pre,int [] in, int preStart, int preEnd, int inStart,  int inEnd) {
	        TreeNode tree = new TreeNode(pre[preStart]);
            int i;
	    	for(i = inStart; i <= inEnd; i++) {
	            if(in[i] == pre[preStart]) {
	                break;
	            }
	        }
            int leftLen = i - inStart;
            if (leftLen > 0) {
	        tree.left = _reConstructBinaryTree(pre, in, preStart + 1, preStart + leftLen, inStart, i - 1);
            }
            if (inEnd - i > 0) {
	        tree.right = _reConstructBinaryTree(pre, in, preStart + 1 + leftLen, preEnd, i + 1, inEnd);
            }
	        return tree;
	    }
}

注意事项

递归寻找左右子树的时候要先判断是否存在左右子树。

传递参数越多，逻辑梳理越清晰。

创建树对象的时候如果不传入参数会报错。（不懂）

用两个栈实现队列

本题知识点：队列栈

题目描述

用两个栈来实现一个队列，完成队列的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(node);
    }
    
    public int pop() {
        if (stack2.size() == 0) {
            while (stack1.size() > 0) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

注意事项

java中Stack对象的方法：.size() .empty() .pop() .push()。

旋转数组的最小数字

本题知识点：查找二分

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if (array.length == 0) {
            return 0;
        }
        int left = 0;
        int right = array.length - 1;
        int mid;
        while (array[left] >= array[right]) {
            if (right - left == 1) {
                mid = right;
                break;
            }
            mid = (left + right) / 2;
            if (array[left] == array[right] && array[left] == array[mid]) {
                mid = minNumber(array, left, right);
                break;
            }
            if (array[mid] >= array[left]) {
                    left = mid;
                }
            else 
            if (array[mid] <= array[right]) {
                    right = mid;
                }
        }
        return array[mid];
    }
    public int minNumber (int [] array, int left, int right) {
        int min = array[left];
        for (int i = left; i <= right; i++) {
            if (array[i] <= min) {
                min = i;
            }
        }
        return min;
    }
}

注意事项

循环第一步判断是否是所求，是则跳出循环；

第二步生成新的mid值，进行判断，并且更新left和right。

while循环就是一个不断更新left和right的过程，知道满足题意。

斐波那契数列

本题知识点：循环递归

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39

public class Solution {
    public int Fibonacci(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 0) {
            return 0;
        }
        //return Fibonacci(n-1) + Fibonacci(n-2);\
        int F1 = 1;
        int F2 = 0;
        int temp;
        for (int i = 2; i <= n; i++) {
            temp = F1 + F2;
            F2 = F1;
            F1 = temp;
        }
        return F1;
    }
}

注意事项

循环的时候只需要保存两个变量即前面两项的值。

跳台阶

本题知识点：循环递归

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

public class Solution {
    public int JumpFloor(int target) {
        if (target == 0) {
            return 0;
        }
        else if (target == 1) {
            return 1;
        }
        else if (target == 2) {
            return 2;
        }
        else {
        return JumpFloor(target - 2) + JumpFloor(target - 1);
        }
    }
}

注意事项

递归好写，用递归。

变态跳台阶

本题知识点：循环递归

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

public class Solution {
    public int JumpFloorII(int target) {
        int [] jump = new int [target+1];
        if (target == 0) {
            return 0;
        }
        else if (target == 1) {
            return 1;
        }
        else if (target == 2) {
            return 2;
        }
        else {
            jump[0] = 0;
            jump[1] = 1;
            jump[2] = 2;
            int temp = 0;
            int a = 2;
            for (int i = 3; i <= target; i++) {
                for (int j = 0; j < i; j++) {
                    temp += jump[j];
                }
                jump[i] = temp + 1;
                temp = 0;
                a *= 2;
            }
            return jump[target];
        }
    }
}

注意事项

算前n项的和最后加一固然是一种方法，但是也可以用2的n次方来做。结果是一样的。上面的返回值也可以是a，也可以AC。

注意temp每次要清0。

矩形覆盖

本题知识点：循环递归

题目描述

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

public class Solution {
    public int RectCover(int target) {
        if (target == 0) {
            return 0;
        }
        if (target == 1) {
            return 1;
        }
        if (target == 2) {
            return 2;
        }
        return  RectCover(target - 2) + RectCover(target - 1);
    }
}

注意事项

无