把自己学习算法的过程以及思考记录下来，与大家一起分享讨论。(牛客网有相应的题目可供大家练习)
1.数组中有重复的数字
题目描述：
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
思路一：
通过两个for循环进行遍历，分别取出第一、第二..个元素，然后依次与后面的元素进行比较找出相同的值。
代码：
public boolean duplicate(int[] nums,int length,int [] duplication) {
if(nums==null || nums.length <= 0 )
return false;
for (int i = 0; i < nums.length; i++) {
int num1 = nums[i];
for (int j =i+1; j < nums.length; j++) {
int num2 = nums[j];
if (num1 == num2) {
duplication[0] = num1;
return true;
}
}
}
return false;
}思路二：
把值等于i的元素放在i的位置上，如果i位置上已经有值为i的元素，则说明值相等。
代码：
public boolean duplicate(int[] nums, int length, int[] duplication) {
if (nums == null || length <= 0)
return false;
for (int i = 0; i < length; i++) {
while (nums[i] != i) {
if (nums[i] == nums[nums[i]]) {
duplication[0] = nums[i];
return true;
}
swap(nums, i, nums[i]);
}
}
return false;
}
private void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}2.二维数组中查找
题目描述:
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路一：
通过两个for循环，array.length 获取行数；array[0].length获取列数。挨个循环得到想要查找的元素，然后返回。
代码：
public class Solution1 {
public boolean Find(int target, int [][] array) {
for(int i=0;i<array.length;i++){
for(int j=0;j<array[0].length;j++){
if (target==array[i][j]){
return true;
}
}
}
return false;
}
}思路二：
从最右上角开始查找，如果得到的数比要查找的元素大，则行数减去1（去查找小的数字）；如果得到的数比目标元素小，则行数加1（去查找大的数字）。以此来查找目标元素。
代码：
public class Solution {
public boolean Find(int target, int [][] array) {
if( array == null || array.length == 0 || array[0].length == 0)
return false;
int r = 0;
int c = array[0].length-1;
while(r <= array.length-1 && c >= 0){
if(target == array[r][c]){
return true;
} else if(target > array[r][c]){
r++;
} else if(target < array[r][c]){
c--;
}
}
return false;
}
}3.空格替换
题目描述:
请实现一个函数，将一个字符串中的每个空格替成“%20”例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
思路:
遍历对象，找出" "所在的索引i，利用StringBuffer的replace(int i,int end, char cha);方法替换为"%20"，打印即可。（《StringBuffer 的一些常用的方法总结》、《StringBuffer与String的相互转换》）
代码:
public static String replaceSpace(StringBuffer str) {
StringBuffer str2 = new StringBuffer();
int n1 = str.capacity();
for (int i = 0; i <= str.length()-1; i++) {
char n2 = str.charAt(i);
if (n2 == ' ') {
str2 = str.replace(i, i+1, "%20");
}
str2=str;
}
String result = str2.toString();
return result;
}4.从尾到头打印链表
题目描述:
输入一个链表，按链表从尾到头的顺序返回一ArrayList。
思路一:
使用递归函数进行操作，每次递归会将函数放进函数栈，也是”后进先出”的思想。
代码：
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<>();
if(listNode != null){
list.addAll(printListFromTailToHead(listNode.next));
list.add(listNode.val);
}
return list;
}思路二:
利用ArrayList的add(int site,int val)方法（如果该位置存在元素，那么原本存在的元素自动往后退一位），每次将链表中的数据放在list的第一个位置，打印list即可得到逆序排列的链表。
代码:
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list=new ArrayList<>();
while(listNode!=null){
list.add(0,listNode.val);
listNode=listNode.next;
}
return list;
}思路三:
利用栈的”先进后出”的特性，将数据存放进栈中，然后再取出打印(做题时用到了 java.util.Stack 包，需要手动导入 )。
代码:
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> sta=new Stack<>();
while(listNode != null){
sta.add(listNode.val);
listNode=listNode.next;
}
ArrayList<Integer> list=new ArrayList<>();
while(!sta.empty()){
list.add(sta.pop());
}
return list;
} 5.重建二叉树
题目描述：
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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) {
TreeNode tre=constructTree(pre,0,pre.length-1,in,0,in.length-1);
return tre;
}
public TreeNode constructTree(int[] pre,int startpre,int endpre,int[] in,int startin,int endin){
if(startpre > endpre || startin > endin){
return null;
}
TreeNode node = new TreeNode(pre[startpre]);
for(int i=startin; i<= endin; i++){
if(in[i] == pre[startpre]){
node.left = constructTree(pre,startpre+1,startpre+i-startin,in,startin,i-1);
node.right = constructTree(pre,startpre+i-startin+1,endpre,in,i+1,endin);
break;
}
}
return node;
}
} 6.二叉树的下一个节点
题目描述：
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路一：
中序遍历：左子树—> 根结点 —> 右子树
简记：左根右
根据中序遍历的特点，若二叉树不为空，则某一个节点的下一个节点大致可以分为以下两种情况：
1. 右孩子不为空，那么它的下一个节点就是右子树的最左的一个节点。
2. 右孩子为空
(1) 该节点是父节点的左孩子，那么父节点就是下一个节点。
(2) 若为右孩子，那么需要找到父节点的父节点一直向上遍历找到根节点，返回。
代码：
/*
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;
}
TreeLinkNode targe = null;
if(pNode.right != null){
targe = pNode.right;
while(targe.left != null){
targe = targe.left;
}
return targe;
} else{
while(pNode.next != null){
TreeLinkNode parent = pNode.next;
if(parent.left == pNode){
return parent;
}
pNode = pNode.next;
}
}
return null;
}
}7.用两个栈实现队列
题目描述：
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路一：
原 始：1–>2–>3
存入栈1：3–>2–>1
存入栈2：1–>2–>3
取 出：1–>2–>3
代码：
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() throws Exception{
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
if(stack2.isEmpty()){
throw new Exception("stack2 is empty...");
}
return stack2.pop();
}
}8.旋转数组的最小数字
题目描述：
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路一：
二分法查找，如果数组为0，则返回0。否则取start、mid、end、三个索引，从中间开始查找，若中间值大于开始的值，因为为非递减，则最小值一定出现在[mid-end]之间，则start=mid，mid再次取中间值。如果中间值小于最后一个值，那么最小值一定在[start-mid]之间，取end=mid，mid取中间值，进行循环。即可得到最小值。
代码：
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int n = array.length;
if(n == 0)
return 0;
int start = 0;
int end = array.length-1;
int mid =0;
while(start+1 != end){
mid = (start+end)/2;
if(array[mid] > array[start]){
start = mid;
}else if(array[mid] < array[end]){
end = mid;
}else {
start++;
}
}
return array[end];
}
}9.斐波那契数列
题目描述：
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39
思路一：
斐波那契数列的一个重要的特点是:
1.当n=1时，f(n)=1; n=0时，f(n)=0
2.前面的两个数相加的和等于后面一个数字，所以第n个数字f(n)等于f(n-1)加上f(n-2),依次类推。
代码：
public class Solution {
public int Fibonacci(int n) {
if(n<2)
return n==0?0:1;
int result = Fibonacci(n-1)+Fibonacci(n-2);
return result;
}
}10.跳台阶
题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
思路一：
参考上一题斐波那契或者说递归的思想，青蛙条第一个台阶的跳法只有1种，跳两个台阶有2种。跳三个台阶，分为跳一个台阶和跳两个台阶的情况。
代码：
public class Solution {
public int JumpFloor(int target) {
if(target < 2)
return target;
int result = JumpFloor(n-1)+JumpFloor(n+1);
return result;11.变态跳台阶
题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路一：
一个台阶有1中跳法、两个台阶2种跳法、三个台阶4种跳法….可以看到是一个等比数列
代码：
public class Solution {
public int JumpFloorII(int target) {
if(target <= 0)
return 0;
int result = (int) Math.pow(2,target-1);
return result;
}
}12.矩阵覆盖
题目描述：
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路一：
当n=1的时候，有1种方法、当n=2的时候，有2种方法、当n=3的时候可以把2*3的矩形分为2*1和2*2的，所以依次类推，可以得到n时的覆盖方法的种类。
代码：
public class Solution {
public int RectCover(int target) {
if(target <= 2)
return target;
int result = RectCover(n-1)+RectCover(n+1);
return result;13.二进制中1的个数
题目描述：
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路一：
Integer.bitCount();
算法思路：先每两位瓯子统计二进制中的1，然后每四位一组统计1，接着是8位、16位和32位，最终在遇0x3f作与运算，输出结果。
代码：
public class Solution {
public int NumberOf1(int n) {
return Integer.bitCount(n);
}
} 思路二：
利用n&(n-1)可以去除n的位级表示中最低的哪一位
示例：
n : 10110100
n-1 : 10110011
n&(n-1) : 10110000 代码：
public class Solution {
public int NumberOf1(int n) {
int c = 0;
while(n!=0){
c++;
n&=(n-1);
}
return c;
}
}14.数值的整数次方
题目描述：
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
思路一：
利用Math.pow()函数进行计算。
代码：
public class Solution {
public double Power(double base, int exponent) {
return Math.pow(base,exponent);
}
}15.调整数组顺序使奇数位于偶数前面
题目描述：
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路一：
使用冒泡的思想，遍历数组每次都把偶数放在当前数组的最右边。
代码：
public class Solution {
public void reOrderArray(int [] array) {
int N = array.length-1;
for(int i=N ; i > 0 ; i--){
for(int j = 0; j < i; j++){
if(judgeO(array[j]) && !judgeO(array[j+1])){
swap(array,j,j+1);
}
}
}
}
public boolean judgeO(int x){
return x%2 == 0;
}
public void swap(int[] num ,int a, int b){
int c=num[a];
num[a] = num[b];
num[b] = c;
}}
16.链表中倒数第k个结点
题目描述：
输入一个链表，输出该链表中倒数第k个结点。
思路一：
双指针，首先先让指针P1移动到第K个节点处，然后指针P2指向头结点，P1和P2同时移动，可知当P1移动到结尾处时候，P2移动到倒数第K个节点处。
代码：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k == 0){
return null;
}
ListNode p1 = head;
while(p1 != null && k-- > 0){
p1 = p1.next;
}
if(k > 0)
return null;
ListNode p2 = head;
while(p1!= null){
p2 = p2.next;
p1 = p1.next;
}
return p2;
}
}17.反转链表
题目描述：
输入一个链表，输出新链表的表头。
思路一：
只需要使得pre–>head–>next，转变为pre<–head<–next即可，在此过程中需要记录下next节点，如不然转变时，单链表会断开。
代码：
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode p = null;
ListNode n = null;
while(head != null){
n = head.next;
head.next = p;
p = head;
head = n;
}
return p;
}
}18.斐波那契数列
题目描述：
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
思路一：
很明显可以看到题目下面提示知识点是递归算法。(斐波那契数列:从第三项开始每一项都等于前面两项的和)。注意：题目说第0项是0。递归会进行大量的重复计算，效率比较低。
代码：
public class Solution {
public int Fibonacci(int n) {
if(n<2)
return n==0?0:1;
int result = Fibonacci(n-1)+Fibonacci(n-2);
return result;
}
} 思路二：
根据斐波那契数列的特性，使用循环进行解答。
代码：（转自：牛客）
/*
整体思路：考虑负数，大数，算法的复杂度，空间的浪费
*/
public class Solution {
public int Fibonacci(int n) {
//方法1：用递归，系统会让一个超大的n来让Stack Overflow，所以
//递归就不考虑了
//使用迭代法，用fn1和fn2保存计算过程中的结果，并复用起来
int fn1 = 1;
int fn2 = 1;
//考虑出错情况
if (n <= 0) {
return 0;
}
//第一和第二个数直接返回
if (n == 1 || n == 2) {
return 1;
}
//当n>=3时，走这里，用迭代法算出结果
//这里也说明了，要用三个数操作的情况，其实也可以简化为两
//个数，从而节省内存空间
while (n-- > 2) {
fn1 += fn2;
fn2 = fn1 - fn2;
}
return fn1;
}
}19.合并两个排序的链表
题目描述：
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路一：
要求合成后的链表满足单调不减的规则，所以在链表合成是需要对当前节点的值的大小进行分情况，运用递归分方法进行解答。
代码：
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null)
return list2;
if(list2 == null)
return list1;
if(list1.val <= list2.val){
list1.next = Merge(list1.next,list2);
return list1;
}else{
list2.next = Merge(list1,list2.next);
return list2;
}
}20. 树的子结构
题目描述：
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路一：
思路很简单，先判断当前根节点是不是相等，不相等的话以A的左子点或者右子点作为起点重新进行判断。
代码：
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null || root2 == null)
return false;
if(root1.val == root2.val){
if(judge(root1,root2))
return true;
}
return HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
}
public boolean judge(TreeNode root1,TreeNode root2){
if(root2 == null)
return true;
if(root1 == null)
return false;
if(root1.val == root2.val)
return judge(root1.left,root2.left) && judge(root1.right, root2.right);
return false;
}21. 二叉树的镜像
题目描述：
操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义：源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5 思路一：
递归，依次交换每个节点即可。
代码：
public void Mirror(TreeNode root) {
if(root == null)
return;
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
Mirror(root.left);
Mirror(root.right);
}