算法汇总代表性学习记录

1.斐波那契数列　(推荐使用动态规划的，当输入n=40的时候就能明显的感觉出递归的不足了)　　　 

这个递归思想是最简单的了
static int feiboArr(int n)
        {
            if (n == 0) { return 0; }
            else if (n==1) { return 1; }
            else if (n==2) { return 1; }
            else
            {
                return feiboArr(n-1) + feiboArr(n-2);
            }
        }

 //使用动态规划来做，这个方法我觉得更好，因为比递归占用空间更小了。
        //这个思路非常简单，就是一个个记录前一个是啥就好了，f记录本次的那一个，g记录本次的下一个
        public static int JumpFloor2(int n)
        {
            int f = 0, g = 1;
            while (n-- > -1)
            {
                g += f;
                f = g - f;//上面g=g+f这里f其实就是加之前的那个g，也就是本次的那一个
            }
            return f;
        }

对于：下面的题，得出结论，见题需要按照逻辑去分析，不要莽写，下面的题我莽写想了那么多，写了一百行的代码最后发现还少考虑了每个划分后不同划分之间可能重复的情况，如果能够按照下面的思路分析，可能感觉好像不是特别的直观，但是代码按照这样逻辑去写就是可以实现出来的哦。

=============↓题干↓=============

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

=============↓分析↓=============

//对于本题, 前提只有 一次 1阶或者2阶的跳法。

//a.如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);

// b.假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)

//c.由a假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)

//d.然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2

//e.可以发现最终得出的是一个斐波那契数列：

以上分析后，解题思路竟然是斐波那契数列，对于斐波那契数列我们使用动态规划来做是最香的！

 ==============================

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

自己写的3种写法，第一种为迭代，第二种和第三种其实是一样的，只不过一个使用List<int>一个使用int[]

给自己也给所有看博客的人提醒，能使用动态规划的最好不要使用迭代，因为迭代非常耗性能，占用了大量的栈，当设置的数字较大时，使用动态规划可以瞬间求解，但是使用迭代则需要很久很久...

=============↓分析↓=============

这题的分析和【1】类似，就是如果有n个阶梯的话，则我可以先走1个，求后n-1个的组合；先走2个，求后n-2个的组合；...；先走n个，则后0个的组合就是1了；它的全部和为f(n-1)+f(n-2)+...+f(0)

其中f(0)根据分析，它需要=1；f(1)因为只有一个嘛，它只能有一个

对于f(2)如果分析的话：走1，则f(1)；走2，则f(0) ；f(1)+f(2)=2已经有答案了，因此我只需设置f(0)与f(1)即可，其余的自己计算就ok了。

 //第一种  迭代
        public static int jumpFloorII(int number)
        {
            // write code here
            if (number < 0) { return 0; }
            else if (number == 0) { return 1; }
            else if (number==1) { return 1; }
            else
            {
                int count = 0;
                for (int i = 0; i < number; i++)
                {
                    count+= jumpFloorII(i);
                }
                return count;
            }
        }

 //第二种 动态规划
        //按照动态规划写一下
        public static int jumpFloorII2(int number)
        {
            // write code here
            List<int> list = new List<int>() { 1, 1 };
            if (number < 0) { return 0; }
            else if (number == 0) { return 1; }
            else if (number == 1) { return 1; }
            else
            {
                int num;
                for (int i = 2; i <= number; i++)
                {
                    num = 0;
                    for (int j = 0; j < i; j++)
                    {
                        num += list[j];
                    }
                    list.Add(num);
                }
                return list[list.Count - 1];
            }
        }

 //第三种 仍然动态规划
        public static int jumpFloorII3(int number)
        {
            // write code here
            int[] list = new int[number+1];
            list[0] = 1; list[1] = 1;
            if (number < 0) { return 0; }
            else if (number == 0) { return 1; }
            else if (number == 1) { return 1; }
            else
            {
                int num;
                for (int i = 2; i <= number; i++)
                {
                    num = 0;
                    for (int j = 0; j < i; j++)
                    {
                        num += list[j];
                    }
                    list[i] = num;
                    //list.Add(num);
                }
                return list[number];
            }
        }

  static void Main(string[] args)
        {
            int c = 20;//不能太大，否则会超出int的范围
            int count3 = jumpFloorII3(c); Console.WriteLine(count3);
            int count = jumpFloorII(c); Console.WriteLine(count);
            int count2 = jumpFloorII2(c); Console.WriteLine(count2);
            Console.ReadKey();
        }

 ============================== 

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

 =============↓分析↓=============

详情网址：https://www.nowcoder.com/questionTerminal/72a5a919508a4251859fb2cfb987a0e6?f=discussion

个人理解分析：

n=1则只有1个

n=2有2个

n=3时，取一个2*1，则剩余2*2的组合有2个；取一个2*2，因为如果||这样排列的话会和刚刚的重复，因此这里只能取=这种形状，剩余一个2*1只有一个组合，所以n=3的组合有2+1=3

对于n时，和上方一样，取一个2*1，则剩余组合为f(n-1)；取一个2*2只能按照=形式排列，剩余组合为f(n-2)，则f(n)=f(n-1)+f(n-2)

本体对应的高度是2，对于高度为m，我们也可以推导，取一个m*1，剩余组合为f(m-1)，取一个m*m,剩余组合为f(n-m)，则f(n)=f(n-1)+f(n-m)；

　　当m>2时，之所以只取m*1和m*m的原因解释如下：对于如果我们取m*2，因为横着无法覆盖，那么它只能竖着放两个，这样的话，这种组合会在取m*1中后续出现，因此取m*1和m*m已经足够

对于本题的实现其实正好就是斐波那契数列

    public int rectCover(int number)
        {
            // write code here
            if (number <= 0) { return 0; }
            else if (number==1) { return 1; }
            else if (number==2) { return 2; }
            else
            {
                return rectCover(number - 1) + rectCover(number - 2);
            }
        }

  ==============================

3.输入一个链表，反转链表后，输出新链表的表头。

　　做个记录，就是可以这样处理链表，而不使用迭代，使用链表的list集合即可处理哈，切记，切记！！！

using System.Collections.Generic;
 
/*
public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode (int x)
    {
        val = x;
    }
}*/
class Solution
{
    public ListNode ReverseList(ListNode pHead)
    {
        if(pHead==null)
            {
                return null;
            }
            List<ListNode> temp = new List<ListNode>();
            ListNode node = pHead;
            while(node!=null)
            {
                temp.Add(node);
                node = node.next;
            }
            for(int i=temp.Count-1;i>0;i--)
            {
                temp[i].next = temp[i - 1];
            }
        temp[0].next=null;
            return temp[temp.Count - 1];
    }
}

 或者我每次只存储当前值的节点。

  static ListNode insertIntoNode(ListNode listnpode,int i, ListNode newNode)
        {
            if (listnpode==null) { return null; }
            List<ListNode> list = new List<ListNode>();
            ListNode temp = listnpode;
            while (temp!=null)
            {
                list.Add(new ListNode(temp.val));//一个个的存储val值
                temp = temp.next; 
            }
            if (i > list.Count) { Console.WriteLine("索引位置超出数组太大");  }
            else if(i == list.Count) { ListNode res= listnpode; res.next = newNode; return res; }
            else
            {
                for (int j = 0; j < i-1; j++)
                {
                    list[j].next = list[j + 1];
                }
                list[i - 1].next = newNode;
                newNode.next = list[i];
                for (int j = i; j < list.Count-1; j++)
                {
                    list[j].next= list[j + 1]; 
                }
            }
            return list[0];
        }

  ==============================

4.约瑟斯问题求解（例子，每过2个删除一个，求最后剩余的是哪两个，或者哪一个也可以）

　　其实这就是循环列表的问题，以下为我按照循环列表来写的，感觉写的还可以贴出来，防止以后遗忘

   //生成ListNode
        static ListNode getListNode()
        {
            List<ListNode> list_listNode = new List<ListNode>();
            for (int i =1 ; i <= 41; i++)
            {
                list_listNode.Add(new ListNode(i));
            }
            for (int i = 0; i < list_listNode.Count-1; i++)
            {
                list_listNode[i].next = list_listNode[i + 1];
            }
            list_listNode[list_listNode.Count - 1].next = list_listNode[0];
            return list_listNode[0];
        }

  //思路就是，因为是循环列表，我读取两个后，删除一个，指向下下个，  我将下下个作为开始，再重复上述读取两个，删除一个....如此往复
        //直到只剩两个的时候，结束
        static ListNode getDeleteNode(ListNode listnode)
        {
            ListNode listnode1 = listnode;
            while(listnode1.next.next!= listnode1)
            {
                listnode1.next.next = listnode1.next.next.next;
                listnode1 = listnode1.next.next;
            }
            return listnode1;
        }

  static void Main(string[] args)
        {
            ListNode listnode = getListNode();
            ListNode ln=getDeleteNode(listnode);
            Console.ReadKey();
        }
class ListNode
    {
        public int val { get; set; }
        public ListNode next { get; set; }
        public ListNode(int _val)
        {
            val = _val;
        }
    }

  ==============================

5.对于约瑟斯问题提升难度

　　编号1~N顺时针坐，每个人都有一个正整数握在手里，初始的时候给定一个m，从第一个人开始喊号，喊道m的那个人出列，使用他手里的那个正整数作为下一个出列的号，然后从后一个人重新从1开始喊号，一直喊下去，求整个出列的顺序。

 =============↓分析↓=============　

完全个人的思路：我使用循环链表，对于每个人手里的那个正整数，我也使用循环链表来存，这样操作是时候统一嘛

删除一个之后，我让目前的链表从下一个开始，因为这样根据m来找最方便，而且因为是循环链表，所有的节点都在哈。感觉讲的不是很清楚呢，自己看代码应该能看懂哈。

   　　  /// <param name="listnode"></param>
        /// <param name="m">初始化的正整数</param>
        /// <param name="mList">每个人手中的正整数</param>
        static void getDeleteNode(ListNode listnode,int m, ListNode mList)
        {
            List<int> delVal = new List<int>();
            ListNode listnode1 = listnode;
            while(listnode1.next!= listnode1)
            {
                //m==1的时去掉第一个
                if (m == 1)
                {
                    ListNode listnode3 = listnode1.next;
                    ListNode listnode2= listnode1;
                    while (listnode2.next!=listnode1)
                    {
                        listnode2 = listnode2.next;
                    }
                    listnode2.next = listnode3;
                    listnode1 = listnode2.next;
                }

                for (int i = 2; i < m; i++)
                {
                    listnode1 = listnode1.next;
                    mList = mList.next;
                }
                delVal.Add(listnode1.next.val);
                listnode1.next = listnode1.next.next;
                listnode1 = listnode1.next;

                m = mList.next.val;
                mList.next = mList.next.next; 
                mList = mList.next;
            }
            delVal.Add(listnode1.val);
            for (int i = 0; i < delVal.Count-1; i++)
            {
                Console.Write(delVal[i]+"->");
            }
            Console.Write(delVal[delVal.Count-1] );
        }
        #endregion
    }

  ==============================

6.从上往下打印出二叉树的每个节点，同层节点从左至右打印。

二分树，（广度优先搜索） 一种很好的方法

方法一：不用迭代

循环实现了找本节点可达到的节点

  public List<int> PrintFromTopToBottomBOZHU(TreeNode root)
        {
            List<int> resultList = new List<int>();
            List<TreeNode> allNodes = new List<TreeNode>();
            if (root != null)
                allNodes.Add(root);
            int i = 0;
            while (i < allNodes.Count)
            {
                TreeNode curNode = allNodes[i];
                resultList.Add(curNode.val);
                if (curNode.left != null)
                    allNodes.Add(curNode.left);
                if (curNode.right != null)
                    allNodes.Add(curNode.right);
                i++;
            }
            return resultList;
        }

方法二：迭代

  　　　public static List<int> PrintFromTopToBottom(TreeNode root)
        {
            // write code here
            List<int> list = new List<int>();
            if (root != null)
            {
                list.Add(root.val);
                List<TreeNode> treenodes = getNextNode(root);
                while (treenodes.Count > 0)
                {
                    List<TreeNode> temp = new List<TreeNode>();
                    foreach (var item in treenodes)
                    {
                        list.Add(item.val);
                        temp.AddRange(getNextNode(item));
                    }
                    treenodes = temp;
                }
            }
            return list;
        }
        //===============找本节点相邻的子节点
        public static List<TreeNode> getNextNode(TreeNode root)
        {
            List<TreeNode> list = new List<TreeNode>();
            if(root!=null)
            {
                if (root.left != null) { list.Add(root.left); }
                if (root.right != null) { list.Add(root.right); }
            }
            return list;
        }

  ==============================

7.求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

//下面我写了快一个小时的递归，发现审题审错了，我的结果是包含1的数字的个数，比如11这个就算一个，但是题干算2个，还是做个记录吧，下方的递归在数字偏大的时候，效率极其的高

  //数字越大，执行效率越高
        public static int NumberOf1Between1AndN_Solution(int n)
        {
            // write code here
            int res = 0;
            if (n.ToString().Length == 1) { if (n >= 1) { return 1; } else { return 0; } }
            else if (n.ToString().Length == 2)
            {
                int tenBit = n % 100 / 10;
                int zeroBit = n % 10;
                if (tenBit == 1) { res = 1 + zeroBit + 1; return res; }//res= NumberOf1Between1AndN_Solution(9)+除去最高位的1的数字+1;
                else
                {
                    res += 11;//NumberOf1Between1AndN_Solution(19);
                    res += tenBit - 2;
                    if (zeroBit >= 1) { res += 1; }
                }
                return res;
            }
            else//length>=3
            {
                int valueLength = n.ToString().Length;
                int maxBit = (n % (int)Math.Pow(10, valueLength)) / (int)Math.Pow(10, valueLength - 1);
                int exceptMaxBit = n % (int)Math.Pow(10, valueLength - 1);
                if (maxBit == 1)
                {
                    res = NumberOf1Between1AndN_Solution((int)Math.Pow(10, valueLength - 1) - 1);//121 则先加99 ； 1223 则加999
                    res += exceptMaxBit + 1;
                    return res;
                }
                else
                {
                    res += NumberOf1Between1AndN_Solution((2 * (int)Math.Pow(10, valueLength - 1)) - 1);//234 则先处理199
                    //现在处理200~234  相当于处理0~34 也就是1~34
                    res += NumberOf1Between1AndN_Solution(exceptMaxBit);
                    return res;
                }
            }
        }

//满足题干的答案是

  public static int NumberOf1Between1AndN_Solution2(int n)
        {
            //int res = 0;
            //for (int i = 1; i <= n; i++)
            //{
            //    foreach (char item in i.ToString())
            //    {
            //        if (item == '1') { res += 1; }
            //    }
            //}
            //return res;

            int result = 0, temp;
            for (int i = 1; i <= n; i++)
            {
                temp = i;
                while (temp > 0)
                {
                    if (temp % 10 == 1)
                    {
                        result++;
                    }
                    temp = temp / 10;
                }
            }
            return result;
        }

  ==============================

8.

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）

 

链接：https://www.nowcoder.com/questionTerminal/94a4d381a68b47b7a8bed86f2975db46?f=discussion
来源：牛客网

B[i]的值可以看作下图的矩阵中每行的乘积。

下三角用连乘可以很容求得，上三角，从下向上也是连乘。

因此我们的思路就很清晰了，先算下三角中的连乘，即我们先算出B[i]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。

 public int[] multiply(int[] A) {
        int[] B=new int[A.length];
        //先搞下三角，然后搞上三角 B[i]=B[i]的下三角这行*B[i]的上三角这行
        //搞下三角
        B[0]=1;
        for (int i = 1; i < B.length; i++) {
            B[i]=B[i-1]*A[i-1];
        }
        //搞上三角
        int temp=1;
        for (int i =B.length-2 ; i >=0 ; i--) {
            temp*=A[i+1];
            B[i]*=temp;
        }
        return B;
    }