精华内容
下载资源
问答
  • 百度指数的是以使用百度搜索引擎的用户为数据基础的数据分享平台,是当前互联网乃至整个数据时代最重要的统计分析平台之一。 百度指数能够反映出用户搜索的某个关键词在百度的搜索规模有多大,一段时间内的涨跌

    百度指数是什么意思ne ?其中的数值又代表什么?简单说百度指数是站长们开始做网站优化之前最先用到的工具,可以说如果没有百度指数,站长们就无法确定要优化哪些关键词。既然百度指数对我们做SEO优化如此重要,那我们又应该如何利用好百度指数呢?下面,北京SEO培训崔鹏瀚SEO就为大家讲一下这个问题。


    一、什么是百度指数


    百度指数指的是以使用百度搜索引擎的用户为数据基础的数据分享平台,是当前互联网乃至整个数据时代最重要的统计分析平台之一。


    百度指数能够反映出用户搜索的某个关键词在百度的搜索规模有多大,一段时间内的涨跌态势以及相关的新闻舆论变化,关注这些词的网民是什么样的,分布在哪里,同时还搜了哪些相关的词等等,利用好百度指数将有助于我们做好网站关键词排名,下面,北京SEO培训崔鹏瀚SEO将以【SEO】这个关键词作为案例来分析。


    百度指数登陆网址:index.baidu.com


    二、百度指数使用方法


    1. 关键词搜索指数





    关键词搜索指数是以网民在百度的搜索量为数据基础,以关键词为统计对象,科学分析并计算出各个关键词在百度网页搜索中搜索频次的加权和。根据使用百度搜索来源的不同,搜索指数分为PC搜索指数和移动搜索指数。


    当然,这些指数只能作为我们预选关键词的参考,并不能作为唯一标准,因为百度指数中有些关键词指数是人为

    展开全文
  • offer(1-10题)详解

    千次阅读 2020-01-19 21:37:34
    选定一个维度(行或列)先找到需要查找的元素所在的 行 (列),再从该 行 (列)找到该元素的该元素具体的列(行)位置。复杂度O(n)。 优化:因为数列是递增有序的, 可以进行二分查找进行优化 ,但是 本题可以不进行二分...

    欢迎关注个人数据结构专栏
    剑指offer系列
    剑指offer(1-10题)详解
    剑指offer(11-25题)详解
    剑指offer(26-33题)详解
    剑指offer(34-40题)详解
    剑指offer(41-50题)详解
    剑指offer(51-59题)详解
    剑指offer(60-67题)详解
    微信公众号:bigsai
    声明:大部分题基本未参考题解,基本为个人想法,如果由效率太低的或者错误还请指正!,如果有误导,还请指正!
    在这里插入图片描述

    01二维数组的查找

    题目描述

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

    思路
    选定一个维度(行或列)先找到需要查找的元素所在的(列),再从该(列)找到该元素的该元素具体的列(行)位置。复杂度O(n)。

    优化:因为数列是递增有序的,可以进行二分查找进行优化,但是本题可以不进行二分也可以过。因为大家有兴趣可以去查一查编程语言数组可以开多大。然后单个查找在这个范围内即使不优化也不会超时。有兴趣的可以自己写一写二分!复杂度O(logn)

    在这里插入图片描述
    代码:

    public class Solution {
       public boolean Find(int target, int [][] array) {
    		 if(array.length==0||array[0].length==0)return false;
    		 for(int i=array.length-1;i>=0;i--)
    		 {
    			 if(array[i][0]>target) {continue;}
    			 for(int j=0;j<array[0].length;j++)
    			 {
    				 if(array[i][j]==target)
    				 {return true;}
    			 }
    		 }
    		 return false;	        
    	    }
    }
    

    02替换空格

    题目描述

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

    思路
    水题,字符串遍历重构即可。遇到为 的字符直接在新的字符添加一个%20即可。当然,在java中直接使用replaceAll即可。复杂度O(n);

    ps: replaceall效率较低,建议使用StringBuider之类完成

    参考讨论区
    在讨论区看到了一些不一样的声音,大致就是 有讨论是在原字符串上进行移动还是新建字符串的问题。当然新建字符串会更简单些,但是如果遇到要求在原字符串基础上进行移动的,因为String的底层实现是数组,那就要首先遍历一次知道有多少空格,然后扩充空间。至于遍历完空格的移动方式:从后往前移动的方式更好,因为最终移动的位置是相同的,但是从前往后每次遇到空格都会拖家带口后面一串都要跟着移动。(好比国旗下讲话排队往后挫,要挫很多次整体慢慢腾腾移动),而从后往前插就相当于很明确一个个明确移动到哪。

    虽然两者最终已经总距离一样的,但是从前往后每个单词要经过(1-n)次才能移动到最后,而从后往前每个单词只1次就移动到目标位置!

    代码:

    public class Solution {
    	public static String replaceSpace(StringBuffer str) {
    		String team=str.toString();
    		return team.replaceAll(" ", "%20");
    	}
    	public static String replaceSpace(StringBuffer str) {//方法二
    
    		StringBuffer str2 = new StringBuffer();
    		char demo = ' ';
    		for (int i = 0; i < str.length(); i++) {
    			
    			demo = str.charAt(i);
    			if (demo == ' ') {
    				str2.append("%20");
    			} else {
    				str2.append(demo);
    			}
    		}
    		return str2.toString();
    
    	}
    }
    

    03从尾到头打印链表

    题目描述

    输入一个链表,按链表从尾到头的顺序返回一个ArrayList。

    思路:
    题目给我们一个链表让我们返回一个序列数字。而这个序列要求我们将链表从后向前的顺序返回。当然,这样的话处理方法就比较多了。比如先从前往后存到一个数组中,然后数组再从后往前往List中塞。

    当然Arraylist本身也是一个线性表(顺序表),可以进行头插。将链表每次向后遍历的数插在首位,最后返回即可

    /**
    *    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>();
    		while (listNode!=null) {
    			list.add(0, listNode.val);
    			listNode=listNode.next;
    		}
    		return list;
    	        
    	    }
    }
    

    参考讨论区
    这题参考了讨论区,发现了一些其他比较优秀的解法,比如可以用递归函数进行插入,当next为null的时候停止,当然还有就是利用栈的结构储存然后抛出啦。这些思想都可实现!

    04重建二叉树★

    题目描述

    输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

    思路:
    说实话这题还是有难度的,以前手动模拟的时候也没掌握方法只是瞎画。以前再力扣也曾经遇到这题当时不会停滞下来。不过这次凭借思考还是克服了

    我们都知道一个中序序列带着一个前序或者后序序列都能确定一棵完整的二叉树。首先分析这种问题。二叉树的问题大部分有可重复性,经常会使用递归。所以大部分人应该能够想到使用递归,但是可能不清楚该怎么递归。其实递归的使用不需要你考虑全篇,需要你谨慎完整的考虑其中一个过程。现在我们看看前序遍历序列{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 node=new TreeNode(in[0]);//根节点
    	       int preleft=0,preright=pre.length-1;
    	       int inleft=0,inright=pre.length-1;
    	       return creat(pre, in, preleft, preright,inleft,inright);   
    	    }
    	private TreeNode creat(int[] pre, int[] in, int preleft, int preright, int inleft, int inright) {
    		if(preleft>preright||inleft>inright)return null;
    		TreeNode node=new TreeNode(pre[preleft]);
    		int mid=0;
    		for(int i=inleft;i<=inright;i++)
    		{
    			if(pre[preleft]==in[i])
    			{
    				mid=i;
    			}
    		}
    		node.left=creat(pre, in, preleft+1, preleft+(mid-inleft), inleft, mid-1);
    		node.right=creat(pre, in, preleft+(mid-inleft)+1, preright, mid+1, inright);
    	    return node;
    	}
    }
    

    05 用两个栈实现队列

    题目描述

    用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型

    思路:
    首先要了解队列,队列是一种先进先出(排队)的结构,而栈是一种后进先出的结构。如果基本概念不清可以看我以前写的哈。要求完成push和pop两种操作。push就是加入队尾(tail)类似enqueue,而pop是返回并抛出队头(front)类似dequeue。我们假设stack1是用作返回,而stack2用作中转。可以先看看下面的图。假设7、3、5、6在队列中,待加入8(push8).

    1. stack1用作返回,那么栈顶肯定是队头(才能返回),在不发生变化的状态甚至是pop返回的状态是这样的:在这里插入图片描述
    2. 对于push加入的操作,两个栈,处理思路就是先用栈2倒置栈1,然后加入要加入的元素到栈2,再用栈1倒置栈2

    在这里插入图片描述

    实现代码为:

    import java.util.Stack;
    
    public class Solution {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        public void push(int node) {     
            while (!stack1.isEmpty()) {
    			stack2.push(stack1.pop());
    		}
            stack2.push(node);
            while (!stack2.isEmpty()) {
    			stack1.push(stack2.pop());
    		}
            stack2.clear();
        }
        
        public int pop() {
    		
        	return stack1.pop();
        
        }
    }
    

    06旋转数组的最小数字

    题目描述

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

    思路:
    就是要求我们在这么一组序列中找到最小的一个数字,非递减的旋转,也就是这么一串有两段非递减的连续串串。找到第二个非递减的串串头就是结果。

    然而,我们只需第一次查找到最小即可结束。不会超时还是因为数组大小有限制。无法提供更大量输入数据。复杂度为O(n);

    public int minNumberInRotateArray(int [] array) {
    		if(array.length==0)return 0;
    		int min=array[0];
            for(int i=0;i<array.length;i++)
            {
            	if(array[i]<min)
            	{
            		min=array[i];
                    break;
            	}
            }
            return min;
        }
    

    参考题解
    之前提过二分,但是这题很多讨论区的方案并非完善,漏了非递减比如101111这种情况。而二分也只是压缩搜索空间,如归一个非递减串被分成左侧非递减和右侧非递减,右侧的最大要小于等于左侧最小的。就跟就行分类讨论,下面分享一个讲的不错的题解(原文链接):
    在这里插入图片描述
    在这里插入图片描述

    07 斐波那契数列

    题目描述

    大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
    n<=39

    思路:斐波那契的公式为:

    F(0)=0;F(1)=1;
    F(n)=F(n-1)+F(n-2); (n>=2)

    你可以使用递归,但是递归效率极低!因为递归的一项会产生新的两项递归函数。它的复杂度是O(2n)指数级别的。具体原因可以参考以前的一篇文章的动态图递归详解。这里不做累述。因为递归浪费太多资源,进行很多没必要的运算。所以我们采用数组从前往后计算。两种方法都附上代码。

    代码为(推荐法2):

    public int Fibonacci(int n) {
    
    		if (n == 1 || n == 0) {
    			return n;
    		} else {
    			return Fibonacci(n - 1) + Fibonacci(n - 2);
    		}
    	}
    	/*
    	 * 法二,打表法
    	 */
    	public int Fibonacci2(int n) {
    
    		int Fibo[]=new int [40];
    		Fibo[0]=0;
    		Fibo[1]=1;
    		for(int i=2;i<=n;i++)
    		{
    			Fibo[i]=Fibo[i-1]+Fibo[i-2];
    		}
    		return Fibo[n];
    		
    	}
    

    参考讨论区:
    其他的其实没有多少区别的,主要是动态规划从前往后计算不需要整个数组。只需要两个变量就够了,这样空间能够节省一些。
    在这里插入图片描述

    08 跳台阶

    题目描述

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

    思路
    可以递归或者dp吧,因为当前台阶F(n)可能是1步跳来的,也可能是2步跳来的。所以F(n)=F(n-1)+F(n-2).(初始情况单独考虑)。这题递归和正向dp时间复杂度差不多,区别不大。

    代码为:

     public int JumpFloor(int target) {
    
    		 int dp[]=new int[target+1];
    		 dp[0]=1;
    		 dp[1]=1;
    		 for(int i=2;i<=target;i++)
    		 {
    			 dp[i]=dp[i-1]+dp[i-2];
    		 }
    		 return dp[target];
    		 
    	    }
    

    参考评论区:
    本题评论区的有些递归方案感觉感觉不太好,只有优化和斐波那契差不多,可以用两个数进行计算就可以了,节省部分空间。

    09 变态跳台阶★

    题目描述

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

    思路
    这种复杂的就别想着用递归了,从正面考虑吧。对于n位置的跳法,可能从n-1跳,可能从n-2跳-------可能从1跳,也可能直接从开始跳。所以F(n)=1(直接跳)+sum(F(k)) (k属于1到n-1)。我们肯定需要一个数组储存F[n];但是我们不能每次都要相加。所以用一个sum[]数组储存前n个跳法的合即可!

    在这里插入图片描述

    代码:

    public class Solution {
        public int JumpFloorII(int target) {	
            int a[]=new int[target+1];//存储结果
            int sum[]=new int[target+1];//储存和
            a[1]=1;
            sum[1]=1;
            for(int i=2;i<=target;i++)
            {
            	a[i]=1+sum[i-1];
            	sum[i]=a[i]+sum[i-1];
            }
            return a[target];        
        }
    }
    

    参考评论区:
    这题,个人分析方法是基于常规算法的,看了讨论区有个非常非常牛的用数学推理方法,类似等差等比数列的推理,做题的时候没想到直接这么推哈哈,大家可以学习一波!
    在这里插入图片描述
    在这里插入图片描述

    10 矩阵覆盖

    题目描述

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

    思路:
    递归或dp。每个矩形的大小都是2*1;同样第F(n)=F(n-1)+F(n-2).(第n-1个横铺一块,第n-2竖直两块)考虑下初始即可

    在这里插入图片描述

    代码为:

    	/*
    	 * dp
    	 */
    	public int RectCover(int target) {
    		if(target==0)return 0;
    		int dp[]=new int[target+1];
    		dp[0]=1;
    		dp[1]=1;
    		for(int i=2;i<=target;i++)
    		{
    			dp[i]=dp[i-1]+dp[i-2];
    		}
    		return dp[target];
        }
    	/*
    	 * 递归
    	 */
    //	public int RectCover(int target) {
    //		if(target==0)return 0;
    //		if(target==1)return 1;
    //		if(target==2)return 2;
    //		else {
    //			return RectCover(target-1)+RectCover(target-2);
    //		}
    //    }
    

    欢迎关注、交流,微信公众号:bigsai

    展开全文
  • 什么是边缘计算?

    万次阅读 多人点赞 2018-07-07 16:59:44
    什么是边缘计算 为什么需要边缘计算 什么是边缘计算 边缘计算的优点 案例研究 云卸载 视频分析 智能家居 智慧城市 边缘协作 机遇和挑战 编程可行性 命名 数据抽象 服务管理 私密性 最优化方法 小结 ...

    注:本篇翻译自施巍松教授的论文《Edge Computing : Vision and Challenges》

    目录

    摘要

    物联网技术的快速发展和云服务的推动使得云计算模型已经不能很好的解决现在的问题,于是,这里给出一种新型的计算模型,边缘计算。边缘计算指的是在网络的边缘来处理数据,这样能够减少请求响应时间、提升电池续航能力、减少网络带宽同时保证数据的安全性和私密性。这篇文章会通过一些案例来介绍边缘计算的相关概念,内容包括云卸载、智能家居、智慧城市和协同边缘节点实现边缘计算。希望这篇文章能够给你一些启发并让更多的人投入边缘计算的研究中来。

    简介

    云计算自从它与2005年提出之后,就开始逐步的改变我们生活、学习、工作的方式。生活中经常用到的google、facebook等软件提供的服务就是典型的代表。并且,可伸缩的基础设施和能够支持云服务的处理引擎也对我们运营商业的模式产生了一定的影响,比如,hadoop、spark等等。
    物联网的快速发展让我们进入了后云时代,在我们的日常生活中会产生大量的数据。思科估计到2019年会有将近500亿的事物连接到互联网。物联网应用可能会要求极快的响应时间,数据的私密性等等。如果把物联网产生的数据传输给云计算中心,将会加大网络负载,网路可能造成拥堵,并且会有一定的数据处理延时。
    随着物联网和云服务的推动,我们假设了一种新的处理问题的模型,边缘计算。在网络的边缘产生、处理、分析数据。接下来的文章会介绍为什么需要边缘计算,相关定义。有关云卸载和智慧城市的一些研究,有关边缘计算下的编程、命名、数据抽象、服务管理、数据私密和安全性的问题也会在下文讨论。

    什么是边缘计算

    在网络边缘产生的数据正在逐步增加,如果我们能够在网络的边缘结点去处理、分析数据,那么这种计算模型会更高效。许多新的计算模型正在不断的提出,因为我们发现随着物联网的发展,云计算并不总是那么高效的。接下来文章中将会列出一些原因来证明为什么边缘计算能够比云计算更高效,更优秀。
    ##为什么需要边缘计算

    • 云服务的推动:云中心具有强大的处理性能,能够处理海量的数据。但是,将海量的数据传送到云中心成了一个难题。云计算模型的系统性能瓶颈在于网络带宽的有限性,传送海量数据需要一定的时间,云中心处理数据也需要一定的时间,这就会加大请求响应时间,用户体验极差。

    • 物联网的推动:现在几乎所有的电子设备都可以连接到互联网,这些电子设备会后产生海量的数据。传统的云计算模型并不能及时有效的处理这些数据,在边缘结点处理这些数据将会带来极小的响应时间、减轻网络负载、保证用户数据的私密性。

    • 终端设备的角色转变:终端设备大部分时间都在扮演数据消费者的角色,比如使用智能手机观看爱奇艺、刷抖音等。然而,现在智能手机让终端设备也有了生产数据的能力,比如在淘宝购买东西,在百度里搜索内容这些都是终端节点产生的数据。

    下面两幅图,图1是传统云计算模型下的范式,最左侧是服务提供者来提供数据,上传到云中心,终端客户发送请求到云中心,云中心响应相关请求并发送数据给终端客户。终端客户始终是消费者的角色。
    图2是现在物联网快速发展下的边缘计算范式。边缘结点(包括智能家电、手机、平板等)产生数据,上传到云中心,服务提供商也产生数据上传到云中心。边缘结点发送请求到云中心,云中心返还相关数据给边缘结点。
    这里写图片描述
    图1 云计算范式
    这里写图片描述
    图2 边缘计算范式

    什么是边缘计算

    边缘计算指的是在网络边缘结点来处理、分析数据。这里,我们给出边缘结点的定义,边缘结点指的就是在数据产生源头和云中心之间任一具有计算资源和网络资源的结点。比如,手机就是人与云中心之间的边缘结点,网关是智能家居和云中心之间的边缘结点。在理想环境中,边缘计算指的就是在数据产生源附近分析、处理数据,没有数据的流转,进而减少网络流量和响应时间。

    边缘计算的优点

    • 在人脸识别领域,响应时间由900ms减少为169ms
    • 把部分计算任务从云端卸载到边缘之后,整个系统对能源的消耗减少了30%-40%。
    • 数据在整合、迁移等方面可以减少20倍的时间。

    案例研究

    云卸载

    在传统的内容分发网络中,数据都会缓存到边缘结点,随着物联网的发展,数据的生产和消费都是在边缘结点,也就是说边缘结点也需要承担一定的计算任务。把云中心的计算任务卸载到边缘结点这个过程叫做云卸载。
    举个例子,移动互联网的发展,让我们得以在移动端流畅的购物,我们的购物车以及相关操作(商品的增删改查)都是依靠将数据上传到云中心才能得以实现的。如果将购物车的相关数据和操作都下放到边缘结点进行,那么将会极大提高响应速度,增强用户体验。通过减少延迟来提高人与系统的交互质量。

    视频分析

    随着移动设备的增加,以及城市中摄像头布控的增加,利用视频来达成某种目的成为一种合适的手段,但是云计算这种模型已经不适合用于这种视频处理,因为大量数据在网络中的传输可能会导致网络拥塞,并且视频数据的私密性难以得到保证。
    因此,提出边缘计算,让云中心下放相关请求,各个边缘结点对请求结合本地视频数据进行处理,然后只返回相关结果给云中心,这样既降低了网络流量, 也在一定程度上保证了用户的隐私。
    举例而言,有个小孩儿在城市中丢失,那么云中心可以下放找小孩儿这个请求到各个边缘结点,边缘结点结合本地的数据进行处理,然后返回是否找到小孩儿这个结果。相比把所有视频上传到云中心,并让云中心去解决,这种方式能够更快的解决问题。

    智能家居

    物联网的发展让普通人家里的电子器件都变得活泼了起来,仅仅让这些电子器件连上网络是不够的,我们需要更好的利用这些电子元件产生的数据,并利用这些数据更好的为当前家庭服务。考虑到网络带宽和数据私密保护,我们需要这些数据最好仅能在本地流通,并直接在本地处理即可。我们需要网关作为边缘结点,让它自己消费家庭里所产生的数据。同时由于数据的来源有很多(可以是来自电脑、手机、传感器等任何智能设备),我们需要定制一个特殊的OS,以至于它能把这些抽象的数据揉和在一起并能有机的统一起来。

    智慧城市

    边缘计算的设计初衷是为了让数据能够更接近数据源,因此边缘计算在智慧城市中有以下几方面优势:

    • 海量数据处理:在一个人口众多的大城市中,无时无刻不在产生着大量的数据,而这些数据如果通通交由云中心来处理,那么将会导致巨大的网络负担,资源浪费严重。如果这些数据能够就近进行处理,在数据源所在的局域网内进行处理,那么网络负载就会大幅度降低,数据的处理能力也会有进一步的提升。
    • 低延迟:在大城市中,有很多服务是要求具有实时特性的,这就要求响应速度能够尽可能的进一步提升。比如医疗和公共安全方面,通过边缘计算,将减少数据在网络中传输的时间,简化网络结构,对于数据的分析、诊断和决策都可以交由边缘结点来进行处理,从而提高用户体验。
    • 位置感知:对基于位置的一些应用来说,边缘计算的性能要由于云计算。比如导航,终端设备可以根据自己的实时位置把相关位置信息和数据交给边缘结点来进行处理、边缘结点基于现有的数据进行判断和决策。整个过程中的网络开销都是最小的。用户请求得以极快的得到响应。
      ##边缘协作
      由于数据隐私性问题和数据在网络中传输的成本问题,有一些数据是不能由云中心去处理的,但是这些数据有时候又需要多个部门协同合作才能发挥它最大的作用。于是,我们提出了边缘协同合作的概念,利用多个边缘结点协同合作,创建一个虚拟的共享数据的视图,利用一个预定义的公共服务接口来将这些数据进行整合,同时,通过这个数据接口,我们可以编写应用程序为用户提供更复杂的服务。
      举个多个边缘结点协同合作共赢的例子。比如流感爆发的时候,医院作为一个边缘结点与药房、医药公司、政府、保险行业等多个节点进行数据共享,把当前流感的受感染人数、流感的症状、治疗流感的成本等共享给以上边缘结点。药房通过这些信息有针对性的调整自己的采购计划,平衡仓库的库存;医药公司则能通过共享的数据得知哪些为要紧的药品,提升该类药品生产的优先级;政府向相关地区的人们提高流感警戒级别,此外,还可以采取进一步的行动来控制流感爆发的蔓延;保险公司根据这次流感程度的严峻性来调整明年该类保险的售价。总之,边缘结点中的任何一个节点都在这次数据共享中得到了一定的利益。

    机遇和挑战

    以上是边缘计算在解决相关问题的潜力和展望,接下来会分析在实现边缘计算的过程中将要面临的机遇和挑战。

    编程可行性

    在云计算平台编程是非常便捷的,因为云有特定的编译平台,大部分程序都可以在云上跑。但是边缘计算下的编程就会面临一个问题,平台异构问题,每一个网络的边缘都是不一样的,有可能是ios系统,也有可能是安卓或者linux等等,不同平台下的编程又是不同的。因此我们提出了计算流的概念,计算流是数据传播路径上的函数序列/计算序列,可以通过应用程序指定计算发生在数据传播路径中的哪个节点。计算流可以帮助用户确定应该完成哪些功能/计算,以及在计算发生在边缘之后如何传播数据。通过部署计算流,可以让计算尽可能的接近数据源。

    命名

    命名方案对于编程、寻址、事物识别和数据通信非常重要,但是在边缘计算中还没有行之有效的数据处理方式。边缘计算中事物的通信是多样的,可以依靠wifi、蓝牙、2.4g等通信技术,因此,仅仅依靠tcp/ip协议栈并不能满足这些异构的事物之间进行通信。边缘计算的命名方案需要处理事物的移动性,动态的网络拓扑结构,隐私和安全保护,以事物的可伸缩性。传统的命名机制如DNS(域名解析服务)、URI(统一资源标志符)都不能很好的解决动态的边缘网络的命名问题。目前正在提出的NDN(命名分发网络)解决此类问题也有一定的局限性。在一个相对较小的网络环境中,我们提出一种解决方案,如图3所示,我们描述一个事物的时间、地点以及正在做的事情,这种统一的命名机制使得管理变得非常容易。当然,当环境上升到城市的高度的时候,这种命名机制可能就不是很合适了,还可以进行进一步的讨论。
    这里写图片描述
    图3 命名机制

    数据抽象

    在物联网环境中会有大量的数据生成,并且由于物联网网络的异构环境,生成的数据是各种格式的,把各种各样的数据格式化对边缘计算来说是一个挑战。同时,网络边缘的大部分事物只是周期性的收集数据,定期把收集到的数据发送给网关,而网关中的存储是有限的,他只能存储最新的数据,因此边缘结点的数据会被经常刷新。利用集成的数据表来存储感兴趣的数据,表内部的结构可以如图4所示,用id、时间、名称、数据等来表示数据。
    这里写图片描述
    图4 相应表结构
    如果筛选掉过多的原始数据,将导致边缘结点数据报告的不可靠,如果保留大量的原始数据,那么边缘结点的存储又将是新的问题;同时这些数据应该是可以被引用程序读写和操作的,由于物联网中事物的异构性,导致数据库的读写和操作会存在一定的问题。

    服务管理

    边缘结点的服务管理我们认为应该有以下四个特征,,包括差异化、可扩展性、隔离性和可靠性,进而保证一个高效可靠的系统。

    • 差异化:随着物联网的发展,会有这种各样的服务,不同的服务应该有差异化的优先级。比如,有关事物判断和故障警报这样的关键服务就应该高于其它一般服务,有关人类身体健康比如心跳检测相关的服务就要比娱乐相关服务的优先级要高一些。
    • 可扩展性:物联网中的物品都是动态的,向物联网中添加或删除一件物品都不是那么容易的,服务缺少或者增加一个新的结点能否适应都是待解决的问题,这些问题可以通过对边缘os的高扩展和灵活的设计来解决。
    • 隔离性:所谓隔离性是指,不同的操作之间互不干扰。举例而言,有多个应用程序可以控制家庭里面的灯光,有关控制灯光的数据是共享的,当有某个应用程序不能响应时,使用其他的应用程序依然能够控制灯光。也就是说这些应用程序之间是相互独立的,互相并没有影响;隔离性还要求用户数据和第三方应用是隔离的,也就是说应用不应该能够跟踪用户的数据并记录下来,为了解决该问题,应当添加一种全新的应用访问用户数据的方式。
    • 可靠性:可靠性可以从服务、系统和数据三方面来谈论
      • 从服务方面来说,网络拓扑中任意节点的丢失都有可能导致服务的不可用,如果边缘系统能够提前检测到具有高风险的节点那么就可以避免这种风险。较好的一种实现方式是使用无线传感器网络来实时监测服务器集群。
      • 从系统角度来看,边缘操作系统是维护整个网络拓扑的重要一部分内容。节点之间能够互通状态和诊断信息。这种特征使得在系统层面部署故障检测、节点替换、数据检测等十分的方便。
      • 从数据角度来看,可靠性指的是数据在传感和通信方面是可靠地。边缘网络中的节点有可能会在不可靠的时候报告信息,比如当传感器处于电量不足的时候就极有可能导致传输的数据不可靠。为解决此类问题可能要提出新的协议来保证物联网在传输数据时的可靠性。

    私密性

    现存的提供服务的方法是手机终端用户的数据并上传到云端,然后利用云端强大的处理能力去处理任务,在数据上传的过程中,数据很容易被别有用心的人收集到。为了保证数据的私密性,我们可以从以下这些方面入手。
    1,在网络的边缘处理用户数据,这样数据就只会在本地被存储、分析和处理。
    2,对于不同的应用设置权限,对私密数据的访问加以限制。
    3,边缘的网络是高度动态化的网络,需要有效的工具保护数据在网络中的传输。

    最优化指标

    在边缘计算当中,由于节点众多并且不同节点的处理能力是不同的,因此,在不同的节点当中选择合适的调度策略是非常重要的。接下来从延迟、带宽、能耗和花费这四个方面来讨论最优化的指标。

    • 延迟: 很明显云中心具有强大的处理能力,但是网络延迟并不单单是处理能力决定的,也会结合数据在网路中传输的时间。拿智慧城市距离来说,如果要寻找丢失的小孩儿信息,在本地的手机处理,然后把处理结果返回给云明显能加快响应速度。当然,这种事情也是相对而言的,我们需要放一个逻辑判断层,来判断把任务交给哪一个节点处理合适,如果此时手机正在打游戏或者处理其他非常重要的事情,那么手机就不是很适合处理这种任务,把这种任务交给其他层次来处理会更好些。
    • 带宽:高带宽传输数据意味着低延迟,但是高带宽也意味着大量的资源浪费。数据在边缘处理有两种可能,一种是数据在边缘完全处理结束,然后边缘结点上传处理结果到云端;另外一种结果是数据处理了一部分,然后剩下的一部分内容将会交给云来处理。以上两种方式的任意一种,都能极大的改善网路带宽的现状,减少数据在网络中的传输,进而增强用户体验。
    • 能耗:对于给定的任务,需要判定放在本地运算节省资源还是传输给其他节点计算节省资源。如果本地空闲,那么当然在本地计算是最省资源的,如果本地正在忙碌状态,那么把计算任务分给其他节点会更合适一些。权衡好计算消耗的能源和网络传输消耗的能源是一件非常重要的事情。一般当网络传输消耗的资源远小于在本地计算消耗的能源时,我们会考虑使用边缘计算把计算任务卸载到其他空闲的节点上,帮助实现负载均衡,保证每一个结点的高性能。
    • 花费:目前在边缘计算上的花费包括但不限于边缘结点的构建和维护、新型模型的开发等。利用边缘计算的模型,大型的服务提供商在处理相同工作的情况下能够获取到更大的利润。

    小结

    物联网的发展和云计算的推动使得边缘计算的模型出现在社区之中。在边缘结点处理数据能够提高响应速度,减少带宽,保证用户数据的私密性。这篇文章当中,我们提出了边缘计算可能在以后的生活中一些相关场景的运用,也提到了边缘计算以后发展的展望和挑战。希望以后有更多的同僚能够关注到这么一个领域。

    展开全文
  • offer所有的题目总结

    万次阅读 多人点赞 2018-09-17 10:13:28
    看看什么时候n为0. public class erjinzhi { public int NumberOf1(int n) { /*int count = 0; //自己的思路,主要就是n与2 4 8 16分别与,来判断 long temp = 1; for(int i = 1; i ;i++){ if((n&temp) > 0) ...

    自己找工作过程中进行的整理总结。

    参考别的博客和书本的代码进行的总结,作为自己笔记用!!

    零、小结:

    一、位运算

    1、二进制中1的个数

    2、判断二进制中0的个数

    3.二进制高位连续0的个数

    二、二叉树

    1、二叉搜索树第k个结点

    2.0 从上往下打印二叉树

    2.1二叉树打印成多行

    2.2按之字形顺序打印二叉树

    题目描述

    3.数据流中位数

    4.二叉树中和为某一值的路径

    5.重建二叉树

    6.树的子结构

    7.二叉树的镜像

    8、二叉搜素树的后序遍历序列 

    9、二叉搜索树与双向链表

    10、二叉树的深度

    11、平衡二叉树

    12、二叉树的下一个节点

     13、对称的二叉树

    14、序列化二叉树

    三、字符串

    1.正则表达式的匹配

    2.表示数值的字符串

    3.0第一个只出现一次的字符

    3.1字符流中第一个不重复的字符

    4.翻转字符串

    5.左旋转字符串

    5.把字符串转换为整数

    6、字符串的排列 

    四、数组

    1.数组中重复的数字

    2.构建乘积数组

    3.二维数组的查找

    4.数组中只出现一次的数字

    5、和为S的两个数

    6.和为S的连续正数序列

    7、调整数组顺序使奇数位于偶数前面 

    8、数组中出现次数超过一半的数字

    9、连续子数组的最大和

    10、把数组排成最小的数 

    11、数组中的逆序对

    12、数字在排序数组中出现的次数

    五、其他

    1.求1+2+3+...+n

    2.不用加减乘除做加法

    3、旋转数组的最小数字

    六、其他

    1.整数中1出现的次数(从1到n中的整数中1出现的次数)

    2.扑克牌顺子

    3.孩子们的游戏(圆圈中剩下的数)

    4、替换空格

    5、斐波那契数列 

    6、跳台阶

     7、变态跳台阶

    8、矩形覆盖

     9、数值的整数次方

    10、顺时针打印矩阵

    11、最小的k个数

    12、丑数

    七、栈和队列

    1、滑动窗口的最大值

    2、用 两个栈实现队列

     3、包含min函数的栈

    4、栈的压入、弹出序列

    八、回溯法

    1、矩阵中的路径

    2、机器人运动范围

    九、链表

    1、从尾到头打印链表

    2、链表中倒数第k个结点

     3、反转链表

    4、合并两个排序的链表

    5、复杂链表的复制

    6、两个链表的第一个公共结点

    7、链表中环的入口节点

    8、删除链表中重复的节点

    9、链表回文结构

    十、非剑指offer

    1、 左神的


    基本是参考别的博客和书本的代码进行的总结整理,作为自己笔记用!!

    零、小结:

    1、<<      :     左移运算符,num << 1,相当于num乘以2

         >>      :     右移运算符,num >> 1,相当于num除以2

        >>>    :     无符号右移,忽略符号位,空位都以0补齐

    2、//与1位与得1就是奇数,1只有最后一位是1

    一、位运算

    1、二进制中1的个数

    输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

    思路:最简单的思路,整数n每次进行无符号右移一位,同1做&运算,可以判断最后以为是否为1。

    通常的剑指offer的思路,n&(n-1) 操作相当于把二进制表示中最右边的1变成0。所以只需要看看进行了多少次这样的操作即可。看看什么时候n为0.

    public class erjinzhi {
        public int NumberOf1(int n) {
            /*int count = 0;  //自己的思路,主要就是n与2 4 8 16分别与,来判断
        	long temp = 1;
        	for(int i = 1; i <= 32;i++){
        		if((n&temp) > 0)
        			count++;
        		temp = temp * 2;
        		
        		
        	}
            return count;*/
    /*    	//简单的思路
        	int res = 0;
        	while (n!=0) {
    	    res = res + n&1;
    	    n>>>=1;
    		}
        	return res;*/
            int count = 0;
            while(n!=0)
            {
                n = n&(n-1);
                count++;
            }
            return count;
    
        }
    }
    • 2、判断二进制中0的个数

    思路:每次右移一位,判断是否是0即可。暂时没有找到别的好思路。

        public static int findZero(int n) {
    		int count = 0;
    		
    		
    		while(n != 0) {
    			if((n&1)!=1)
    				count++;
    			n>>>=1;
    		}
    	    return count;
        }
    • 3.二进制高位连续0的个数

    思路:每次与最高位为1的二进制进行&操作。0x80000000的二进制是1000 0000 0000 0000 ...共32位,最高位为1.

    参考https://blog.csdn.net/u013190513/article/details/70216730

    https://www.cnblogs.com/hongten/p/hongten_java_integer_toBinaryString.html

    https://blog.csdn.net/lpjishu/article/details/51323722

        public static int numberOfLeadingZeros0(int i){
                if(i == 0)
                    return 32;
                int n = 0;
                int mask = 0x80000000;
                int j = i & mask;
                while(j == 0){
                    n++;
                    i <<= 1;
                    j = i & mask;
                }
                return n;
            }

    JDK中源码解决思路.

       public static int numberOfLeadingZeros(int i) {
            // HD, Figure 5-6
            if (i == 0)
                return 32;
            int n = 1;
            if (i >>> 16 == 0) { n += 16; i <<= 16; }
            if (i >>> 24 == 0) { n +=  8; i <<=  8; }
            if (i >>> 28 == 0) { n +=  4; i <<=  4; }
            if (i >>> 30 == 0) { n +=  2; i <<=  2; }
            n -= i >>> 31;
            return n;
        }

    二、二叉树

    • 1、二叉搜索树第k个结点

    给定一颗二叉搜索树,请找出其中的第k小的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。

    思路:递归的方式:二叉搜索树的中序遍历就是排序的,所以用中序遍历,每一次中间的时候判断是否等于k即可。

             非递归的方式:运用栈进行操作。相当于用栈实现了中序遍历,在中间进行了个数的判断

    	int count = 0;
        TreeNode KthNode(TreeNode pRoot, int k)
        {
            if(pRoot != null) {
            	TreeNode leftNode = KthNode(pRoot.left, k);
            	if(leftNode != null)
            		return leftNode;
            	count++;
            	if(count == k)
            		return pRoot;
            	TreeNode rightNode = KthNode(pRoot.right, k);
            	if(rightNode != null)
            		return rightNode;
            }
            return null;
        }

    //栈的方式

        TreeNode KthNode(TreeNode pRoot, int k)
        {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            if(pRoot==null||k==0) return null;
            int t=0;
            while(pRoot!=null ||stack.size()>0){
                while(pRoot!=null){
                    stack.push(pRoot);
                    pRoot = pRoot.left;
                }
                if(stack.size()>0){
                    pRoot= stack.pop();
                    t++;
                    if(t==k) return pRoot;
                    pRoot= pRoot.right;
                }
            }
           return null;   
        }
    • 2.0 从上往下打印二叉树

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

    思路:

    import java.util.ArrayList;
    import java.util.LinkedList;
    /**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
       /**
    	 * 算法思路,(剑指offer图片)
    	 * 1.根节点放到队列里面,队列不空,就打印队列头,打印这个节点,马上把这个节点的左右子节点放到队列中。
    	 * 2.再要访问一个节点,把这个节点的左右放入,此时队头是同层的,对位是打印出来的左右。依次先入先出就可以得到结果。
    	 * @param root
    	 * @return
    	 */
    	public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    		ArrayList<Integer> layerList = new ArrayList<Integer>();
    		if (root == null)
    			return layerList;
    		LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
    		queue.add(root);
    		while (!queue.isEmpty()) {
    			TreeNode node = queue.poll();
    			layerList.add(node.val);
    			if (node.left != null)
    				queue.addLast(node.left);
    			if (node.right != null)
    				queue.addLast(node.right);
    		}
    		return layerList;
    	}
    
    }
    • 2.1二叉树打印成多行

    从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。(注意是一行一行输出)

    思路:主要采用左程云的思路,

       static ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        	ArrayList<ArrayList<Integer>> res = new ArrayList<>();
            if(pRoot == null)
            	return res;
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            TreeNode last = pRoot;
            TreeNode nlast =null;
            queue.offer(pRoot);
            ArrayList<Integer> tmp = new ArrayList<>();
            while (!queue.isEmpty()) {
    			pRoot = queue.poll();
    			tmp.add(pRoot.val);//出队列,就把他左右孩子入队列,
    			                    //此时,下一层的最右要跟着更新
    			if (pRoot.left!=null) {
    				queue.offer(pRoot.left);
    				nlast = pRoot.left;
    			} 
    			if (pRoot.right!=null) {
    				queue.offer(pRoot.right);
    				nlast = pRoot.right;
    			}
    			//如果到了本层的最右,就把这一层结果放入。注意最后一层时,isempty不成立,
    			//最后一层的结果要单独放入。
    			if (pRoot == last && !queue.isEmpty()) {
    				res.add(new ArrayList<>(tmp));
    				last = nlast;
    				tmp.clear();
    			}
    		}
            res.add(new ArrayList<>(tmp));
            return res;
        }

    2.2按之字形顺序打印二叉树

    题目描述

    请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

    利用两个栈的辅助空间分别存储奇数偶数层的节点,然后打印输出。或使用链表的辅助空间来实现,利用链表的反向迭实现逆序输出。

    import java.util.ArrayList;
    import java.util.Stack;
    /*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        //利用两个栈的辅助空间分别存储奇数偶数层的节点,然后打印输出。或使用链表的辅助空间来实现,利用链表的反向迭实现逆序输出。
        public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
            ArrayList<ArrayList<Integer>> res = new ArrayList<>();
            if(pRoot == null)
            	return res;
            Stack<TreeNode> s1 = new Stack<>();
            Stack<TreeNode> s2 = new Stack<>();
            s1.push(pRoot);
            int level = 1;
            while (!s1.empty()||!s2.empty()) {
    			if (level %2 != 0) {
    				ArrayList<Integer> list = new ArrayList<>();
    				while (!s1.empty()) {
    					TreeNode node = s1.pop();
    					if (node!= null) {
    						list.add(node.val);
    						s2.push(node.left);//因为偶数层,先右后左,所以要先放左子树,栈
    						s2.push(node.right);
    						
    					}
    				}
    				  if (!list.isEmpty()) {
    		                res.add(list);
    		                level++;
    		            }
    			}
    			else {
    				ArrayList<Integer> list = new ArrayList<>();
    				while (!s2.empty()) {
    					TreeNode node = s2.pop();
    					if (node!= null) {
    						list.add(node.val);
    						s1.push(node.right);
    						s1.push(node.left);
    						
    					}
    				}
    				  if (!list.isEmpty()) {
    		                res.add(list);
    		                level++;
    		            }
    			}
    		}
            return res;
        }
    
    }

    • 3.数据流中位数

    如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

    思路:主要是博客的代码,参考了左的部分分析。

    创建优先级队列维护大顶堆和小顶堆两个堆,并且小顶堆的值都大于大顶堆的值。比如6,1,3,0,9,8,7,2则较小的部分大根堆是0,1,2,3 较大的部分小根堆是6,7,8,9.

    具体思路:

    1.本代码为了保证两个堆的尺寸差距最大为1,采用奇数个时候插到大根堆,偶数个插到小根堆。

    2.当数据总数为偶数时,新加入的元素,应当进入小根堆(注意不是直接进入小根堆,而是经大根堆筛选后取大根堆中最大元素进入小根堆),要保证小根堆里面所有数都比大根堆的大。

    3.当数据为奇数个时,按照相应的调整进入大根堆。

    4.如果个数位奇数个,则大根堆堆顶为中位数,否则就是两个堆顶除以2.比如新加入三个,那么第一个在大,第二个在小,第三个可能在大。所以就是大根堆的堆顶。

    * 插入有两种思路: 左采用第一种,本代码采用第二种

    * 1:直接插入大堆中,之后若两堆尺寸之差大于1(也就是2),则从大堆中弹出堆顶元素并插入到小堆中

    * 若两队之差不大于1,则直接插入大堆中即可。

    * 2:奇数个数插入到大堆中,偶数个数插入到小堆中,

    * 但是 可能会出现当前待插入的数比小堆堆顶元素大,此时需要将元素先插入到小堆,然后将小堆堆顶元素弹出并插入到大堆中

    * 对于偶数时插入小堆的情况,一样的道理。why?

    * 因为要保证最大堆的元素要比最小堆的元素都要小。

    import java.util.Comparator;
    import java.util.PriorityQueue;
    
    public class Shujuliumedian {
    	int count = 0;
    	PriorityQueue<Integer> minheap = new PriorityQueue<>();
    	PriorityQueue<Integer> maxheap = new PriorityQueue<>(11, new Comparator<Integer>() {
    
    		@Override
    		public int compare(Integer o1, Integer o2) {
    			// TODO Auto-generated method stub
    			
    			return o2.compareTo(o1);//o2大于o1返回1 ,否则返回-1
    		}
    	});
        public void Insert(Integer num) {
            count++;
            if (count % 2 ==0) {//偶数进入小根堆,这个其实无所谓,定了一个平均分配的规则
            	//保证进入小根堆的元素要比大根堆最大的大,所以如果小调整
            	if (!maxheap.isEmpty() && num < maxheap.peek()) {
    				maxheap.offer(num);
    				num = maxheap.poll();
    			}
    			minheap.offer(num);
    		}
            else {//奇数进入大根堆
            	if (!minheap.isEmpty() && num > minheap.peek()) {
    				minheap.offer(num);
    				num = minheap.poll();
    			}
            	maxheap.offer(num);
            }
        }
    
        public Double GetMedian() {
            double median = 0;
            if (count % 2 ==1) {
    			median = maxheap.peek();
    		}
            else
            	median = (minheap.peek()+maxheap.peek())/2.0;
            return median;
        }
    }
    
    • 4.二叉树中和为某一值的路径

    输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前)

    思路:     * 剑指offer思路 博客代码
         * 代码步骤:一个链表记录路径,一个存放这个链表的链表记录最终的结果。
         * 1.首先将根节点放入链表,target减去这个根节点
         * 2.判断是否target同时是叶子节点,如果是就将当前的链表放在结果连表里
         * 3.如果不是,就递归去访问左右子节点。

         * 4.无论是找到没有,都要回退一步、

    import java.util.ArrayList;
    /**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
    private ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();  
    
        private ArrayList<Integer> list =new ArrayList<Integer>();
        private ArrayList<ArrayList<Integer>> resultList = new ArrayList<ArrayList<Integer>>();
        /**
         * 剑指offer思路
         * 代码步骤:一个链表记录路径,一个存放这个链表的链表记录最终的结果。前序遍历去访问。先访问根,在递归在左右子树找。注意回退
         * 1.首先将根节点放入链表,target减去这个根节点
         * 2.判断是否target同时是叶子节点,如果是就将当前的链表放在结果连表里
         * 3.如果不是,就递归去访问左右子节点。
         * 4.无论是找到没有,都要回退一步、
         * @param root
         * @param target
         * @return
         */
        public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
            if(root == null)
            	return resultList;
            list.add(root.val);
            target = target - root.val;
            if(target == 0 && root.left == null && root.right == null){
            	resultList.add(new ArrayList<Integer>(list));
            }
            else {
    			FindPath(root.left, target);
    			FindPath(root.right, target);
    			
    		}
            // 在返回父节点之前,在路径上删除该结点
            list.remove(list.size()-1);
            return resultList;
        }
        
    }
    • 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; }
     * }
     */
    import java.util.Arrays;
    
    public class Solution {
    	public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
    		if (pre == null || in == null) {
    			return null;
    		}
    		if (pre.length == 0 || in.length == 0) {
    			return null;
    		}
    		if (pre.length != in.length) {
    			return null;
    		}
    		TreeNode root = new TreeNode(pre[0]);//第一个
    		for (int i = 0; i < in.length; i++) {
    			if (pre[0] == in[i]) {
    				//pre的0往后数i个是左子树的,copyofrange包含前面的下标,不包含后面的下标
    				//in的i往前数i个是左子树的。
    				root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
    				//注意in是从i+1开始,因为i是现在的根,i+1开始才是右子树
    				root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length),
    						Arrays.copyOfRange(in, i + 1, in.length));
    			}
    		}
    		return root;
    	}
    }
    • 6.树的子结构

    输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

    思路:   //先从根开始再把左作为根,再把右作为根由本函数决定。把一个为根的时候的具体比对过程是第二个函数决定。
        //从根可以认为是一颗树,从左子树开始又可以认为是另外一颗树,从右子树开始又是另外一棵树。
        //本函数就是判断这一整颗树包不包含树2,如果从根开始的不包含,就从左子树作为根节点开始判断,
        //再不包含从右子树作为根节点开始判断。
        //是整体算法递归流程控制。


    /**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
       //先从根开始再把左作为根,再把右作为根由本函数决定。把一个为根的时候的具体比对过程是第二个函数决定。
        //从根可以认为是一颗树,从左子树开始又可以认为是另外一颗树,从右子树开始又是另外一棵树。
        //本函数就是判断这一整颗树包不包含树2,如果从根开始的不包含,就从左子树作为根节点开始判断,
        //再不包含从右子树作为根节点开始判断。
        //是整体算法递归流程控制。
        public boolean HasSubtree(TreeNode root1,TreeNode root2) {
            boolean res = false;
            if (root1 != null && root2 != null) {
    			if(root1.val == root2.val){
    				res = doesTree1haveTree2(root1,root2);
    			}
    			if(!res)
    			{
    				res = HasSubtree(root1.left, root2);
    			}
    			if(!res)
    			{
    				res = HasSubtree(root1.right, root2);
    			}
    		}
            return res;
        }
    	//本函数,判断从当前的节点 ,开始两个树能不能对应上,是具体的比对过程
        public boolean doesTree1haveTree2(TreeNode root1,TreeNode root2) {
    		if(root2 == null)
    			return true;
    		if(root1 == null)
    			return false;
    		if(root1.val != root2.val){
    			return false;
    		}
    		//如果根节点可以对应上,那么就去分别比对左子树和右子树是否对应上
    		return doesTree1haveTree2(root1.left, root2.left) && doesTree1haveTree2(root1.right, root2.right);
    	}
    }
    • 7.二叉树的镜像

    操作给定的二叉树,将其变换为源二叉树的镜像。

    二叉树的镜像定义:源二叉树 
        	    8
        	   /  \
        	  6   10
        	 / \  / \
        	5  7 9 11
        	镜像二叉树
        	    8
        	   /  \
        	  10   6
        	 / \  / \
        	11 9 7  5
    /**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    import java.util.Stack;
    public class Solution {
    /**
         * 算法步骤
         * 1.节点为空直接返回
         * 2.如果这个节点的左右子树不为空,就交换。
         * 3.递归对这个节点的左子树进行求镜像。对这个节点的右子树求镜像。
         * @param root
         */
        public void Mirror(TreeNode root){
            if (root == null) {
    			return;
    		}
        	if(root.left != null || root.right != null) {
    			TreeNode temp = root.left;
    			root.left = root.right;
    			root.right = temp;
    			Mirror(root.left);
    			Mirror(root.right);
    		}
        	
        }
            /*public void Mirror(TreeNode root) {
            if (root == null) {
    			return;
    		}
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(root);
            while (!stack.isEmpty()) {
            	TreeNode node = stack.pop();
            	if (node.left != null || node.right != null) {
    				TreeNode temp = node.left;
    				node.left = node.right;
    				node.right = temp;
    			}
            	if(node.left != null)
            		stack.push(node.left);
            	if(node.right != null)
            		stack.push(node.right);
    			
    		}
        }*/
    }

    8、二叉搜素树的后序遍历序列 

    输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

    public class Solution {
       /**二叉搜索树的性质:
         * 所有左子树的节点小于根节点,所有右子树的节点值大于根节点的值。
         * 算法步骤:
         * 1.后序遍历的最后一个值为root,在前面的数组中找到第一个大于root值的位置。
         * 2.这个位置的前面是root的左子树,右边是右子树。然后左右子树分别进行这个递归操作。
         * 3.其中,如果右边子树中有比root值小的直接返回false
         * @param sequence
         * @return
         */
        public boolean VerifySquenceOfBST(int [] sequence) {
        	if (sequence == null || sequence.length == 0) 
    			return false;
        	return IsBST(sequence, 0, sequence.length -1);
        	
        }
        
        public boolean IsBST(int [] sequence, int start, int end) {
        	if(start >= end) //注意这个条件的添加// 如果对应要处理的数据只有一个或者已经没
                //有数据要处理(start>end)就返回true
        		return true;
        	int index = start;
        	for (; index < end; index++) {//寻找大于root的第一个节点,然后再分左右两部分
    			if(sequence[index] > sequence[end])
    				break;
    		}
            for (int i = index; i < end; i++) {//若右子树有小于根节点的值,直接返回false
    			if (sequence[i] < sequence[end]) {
    				return false;
    			}
    		}
            return IsBST(sequence, start, index-1) && IsBST(sequence, index, end-1);
    	}
        
    }/*当案例为{4,6,7,5}的时候就可以看到: 
    (此时start为0,end为3) 
    一开始index处的值为1,左边4的是start为0,index-1为0,下一次递归的start和end是一样的,true! 
    右边,start为1,end-1为2,是{6,7}元素,下一轮递归是: 
    ————7为root,index的值指向7, 
    ————所以左边为6,start和index-1都指向6,返回true。 
    ————右边index指向7,end-1指向6,这时候end > start!如果这部分还不返回true,下面的数组肯定超了    */
    

    9、二叉搜索树与双向链表

    题目描述

    输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

    /**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
     /**二叉搜索树的中序遍历就是递增的排序,所以就运用中序遍历方法来做。
         * 算法思想:
         * 中序遍历的步骤,只不过在递归的中间部分不是输出节点值,而是调整指针指向。
         *     10
         *     /\
         *    5 12
         *   /\
         *  4 7
         *  步骤记住就行,第一次执行,到4的时候,head和resulthead都指向这个
         *  指针调整的其中一步:4是head 5是pRootOfTree 然后调整head右指向5,5左指向4,然后5变成head就行了。
         * @param pRootOfTree
         * @return
         */
        TreeNode head = null;
        TreeNode resultHead = null; //保存生成链表的头结点,便于程序返回
        public TreeNode Convert(TreeNode pRootOfTree) {
            ConvertSub(pRootOfTree);
            return resultHead;
        }
        public void ConvertSub(TreeNode pRootOfTree) {
        	if(pRootOfTree == null)
        		return;
        	ConvertSub(pRootOfTree.left);
    		if(head == null){
    			head = pRootOfTree;
    			resultHead = pRootOfTree;
    		}
    		else {
    			head.right = pRootOfTree;
    			pRootOfTree.left = head;
    			head = pRootOfTree;
    		}
    		ConvertSub(pRootOfTree.right);		
    	}
    }

    10、二叉树的深度

    题目描述

    输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

    /**
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
    	// 注意最后加1,因为左右子树的深度大的+根节点的深度1 
        public int TreeDepth(TreeNode root) {
            if(root == null)
            	return 0;
            int left = TreeDepth(root.left);
            int right = TreeDepth(root.right);
            return left > right? left +1:right+1;
        }
    }

    11、平衡二叉树

    输入一棵二叉树,判断该二叉树是否是平衡二叉树

    描述:如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

    public class Solution {
        // 注意使用全局变量  
        boolean isBalance = true;  
        public boolean IsBalanced_Solution(TreeNode root) {  
            lengthOfTree(root);  
            return isBalance;  
        }  
      
        private int lengthOfTree(TreeNode root) {  
            if (root == null)  
                return 0;  
            int left = lengthOfTree(root.left);  
            int right = lengthOfTree(root.right);  
            if (Math.abs(left - right) > 1)  
                isBalance = false;  
            return Math.max(left, right) + 1;  
      
        } 
    }

    第二种Better思路:从底向上判断,这样可以记录下一层的深度

    public class Solution {
      public boolean IsBalanced(TreeNode root) {
            int depth = 0;
            return IsBalanced(root, depth);
        }
    
        public boolean IsBalanced(TreeNode root, int depth) {
            if (root == null) {
                depth = 0;
                return true;
            }
    
            int left = 0, right = 0;
            if (IsBalanced(root.left, left) && IsBalanced(root.right, right)) {
                int diff = left - right;
                if (diff <= 1 && diff >= -1) {
                    depth = 1 + (left > right ? left : right);
                    return true;
                }
            }
    
            return false;
        }
    }

    12、二叉树的下一个节点

    题目描述

    给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

    /*
    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;
    
        TreeLinkNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
        /**参考左程云和有详解博客的思路,
         * 主要分三种:
         * 1.如果有右孩子,后继节点就是最左边的
         * 2.如果没有右孩子,判断是否是父节点的左孩子,是的话,返回,不是继续网上找
         * 3.找不到就是null
         * @param pNode
         * @return
         */
        public TreeLinkNode GetNext(TreeLinkNode pNode)
        {
            if(pNode == null)
            	return null;
         // 如果有右子树,则找右子树的最左节点  
            if (pNode.right != null) {
            	pNode = pNode.right;
            	// 如果此时pNode没有左子树,那么它就是下一个结点 ,就是最左边的了
            	//如果有左子树,那就在左子树找最左边的
            	while(pNode.left != null)
            		pNode = pNode.left;
            	return pNode;
    			
    		}
             非跟结点,并且没有右子树
            while(pNode.next != null) {
            	// 找到一个结点是该其父亲的左孩子  ,找到就是返回父节点作为后记
            	if (pNode.next.left == pNode) 
    				return pNode.next;
            	//找不到这个左孩子的,就继续往上,next其实是parent
    			pNode = pNode.next;
            }
            return null;	
        }
    }

     13、对称的二叉树

    请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。

    /*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        //利用递归进行判断,
        //若左子树的左孩子等于右子树的右孩子且左子树的右孩子等于右子树的左孩子,
        //并且左右子树节点的值相等,则是对称的。
        boolean isSymmetrical(TreeNode pRoot)
        {
            if (pRoot == null) 
    			return true;
    		return isCommon(pRoot.left,pRoot.right);
        }
        public boolean isCommon(TreeNode leftNode, TreeNode rightNode) {
    		if (leftNode == null && rightNode == null)
    			return true;
    		if (leftNode != null && rightNode != null) {
    			return leftNode.val == rightNode.val && 
    					isCommon(leftNode.left, rightNode.right) &&
    					isCommon(leftNode.right, rightNode.left);
    		}
    		return false;
    	}
    }

    14、序列化二叉树

    请实现两个函数,分别用来序列化和反序列化二叉树 

     

    这段代码是按照先序遍历的方法来做的: 

    /*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    import java.util.LinkedList;
    import java.util.Queue;
    public class Solution {
        //主要运用左程云的编程思想的方式来实现
        String Serialize(TreeNode root) {
            if(root == null)
            	return "#!";
            String res = root.val+"!";
            res = res + Serialize(root.left);
            res = res + Serialize(root.right);
            return res;
       }
    
        TreeNode Deserialize(String str) {
           String [] values = str.split("!");
           Queue<String> queue = new LinkedList<String>();
           for (int i = 0; i < values.length; i++) {
    		queue.offer(values[i]);
    	}
           return reconPre(queue);
      }
        TreeNode reconPre(Queue<String> queue) {
        	String value = queue.poll();
        	if(value.equals("#"))
        		return null;
        	TreeNode head = new TreeNode(Integer.valueOf(value));
        	head.left = reconPre(queue);
        	head.right = reconPre(queue);
        	return head;
        }
    }

    三、字符串

    • 1.正则表达式的匹配

    请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a"和"ab*ac*a"匹配,但是与"aa.a"和"ab*a"均不匹配。

    思路:参考网上的思路,主要就是分程序中的两种情况来讨论。第二位是不是*

    /*
    当模式中的第二个字符不是“*”时:
      1、如果字符串第一个字符和模式中的第一个字符相匹配,
      那么字符串和模式都后移一个字符,然后匹配剩余的。 
      2、如果字符串第一个字符和模式中的第一个字符相不匹配,直接返回false。
      而当模式中的第二个字符是“*”时:
      如果字符串第一个字符跟模式第一个字符不匹配,则模式后移2个字符,继续匹配。
      如果字符串第一个字符跟模式第一个字符匹配,可以有3种匹配方式: 
      1、模式后移2字符,相当于x*被忽略; 
      2、字符串后移1字符,模式后移2字符; 相当于x*算一次
      3、字符串后移1字符,模式不变,即继续匹配字符下一位,因为*可以匹配多位,相当于算多次
      这里需要注意的是:Java里,要时刻检验数组是否越界。*/
    public class Zhengze {
    	public boolean match(char[] str, char[] pattern) {
    		if (str == null || pattern == null) {
    			return false;
    		}
    		int strIndex = 0;
    		int patternIndex = 0;
    		return matchCore(str, strIndex, pattern, patternIndex);
    	}
     
    	public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
    		// 有效性检验:str到尾,pattern到尾,匹配成功
    		if (strIndex == str.length && patternIndex == pattern.length)
    			return true;
    		// pattern先到尾,匹配失败
    		if (strIndex != str.length && patternIndex == pattern.length)
    			return false;
    		// 模式第2个是*,且字符串第1个跟模式第1个匹配,分3种匹配模式;如不匹配,模式后移2位
    		if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
    			if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
    					|| (pattern[patternIndex] == '.' && strIndex != str.length)) {
    				return // 模式后移2,视为x*匹配0个字符
    				matchCore(str, strIndex, pattern, patternIndex + 2)
    						// 视为模式匹配1个字符
    						|| matchCore(str, strIndex + 1, pattern, patternIndex + 2)
    						// *匹配1个,再匹配str中的下一个
    						|| matchCore(str, strIndex + 1, pattern, patternIndex);
     
    			} else {
    				return matchCore(str, strIndex, pattern, patternIndex + 2);
    			}
    		} // 模式第2个不是*,且字符串第1个跟模式第1个匹配,则都后移1位,否则直接返回false
    		if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
    				|| (pattern[patternIndex] == '.' && strIndex != str.length)) {
    			return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
    		}
    		return false;
    	}
    }
    
    • 2.表示数值的字符串

    请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

    思路:按照一定的规则,如果第一位是+或-,就后移一位。

    如果是数字,索引后移,数字表示1.

    如果是点,要判断至此点的数量和e的数量是否已经有了,因为java 中e要求后面为整数,如果有了肯定false。索引后移,dotnum增加。

    如果是e,判断是否重复e,或者前面没有数字返回false。enum++, 索引++,此时还要判断最后一位是不是e或者+或者-,如果是false。

    public class StrexpressNum {
    	/*例子:
    	 * 110   1a1   1.1.1  2.2  12e 
    	 * 
    	 * */
    	public  static boolean isNumeric(char[] str) {
    		if(str == null)
    			return false;
    		int length = str.length;
    		int dotNum = 0;//记录点的数量
    		int index = 0;//索引
    		int eNum = 0;//记录e的数量
    		int num = 0;//记录数字的数量
    		if (str[0] == '+' || str[0] == '-') {
    			index++;
    		}
    		while (index < length) {
    			if(str[index]>='0' && str[index]<='9') {
    				index++;
    	            num = 1;
    	         // .前面可以没有数字,所以不需要判断num是否为0
    			}else if(str[index]=='.') {
    				// e后面不能有.,e的个数不能大于1.java科学计数要求aeb,b为整数
    				if(dotNum >0 || eNum >0)
    					return false;
    				dotNum++;
    				index++;
    			}else if(str[index] == 'e' || str[index] == 'E') {
    				// 重复e或者e前面没有数字
    				if(eNum > 0 || num ==0)
    					return false;
    				eNum++;
    				index++;
    				// 符号不能在最后一位
    				if(index < length &&(str[index]=='+'||str[index]=='-'))
    					index++;
    				// 表示e或者符号在最后一位
    				if(index == length)
    					return false;
    			}else {
    				return false;
    			}
    			
    		}
    		return true;
    	}
    public static void main(String[] args) {
    	char [] str = {'1','2','e'};
    	System.out.println(isNumeric(str));
    
    }
    }

    或者用正则表达式来匹配:

    [+-]? 表示+或者-出现0次或1次。[0-9]{0,}表示0到9出现0次或者更多次。()表示这个分组作为一个整体。 \\.?表示.出现0次或1次。[0-9]{1,}表示0到9出现1次或者多次。()表示一个分组。如果把两个分组去掉进行判断是不准确的。100匹配到[0-9]{1,}出错。

        public boolean isNumeric(char[] str) {
            String res = String.valueOf(str);
    		return res.matches("[+-]?[0-9]{0,}(\\.?[0-9]{1,})?([Ee][+-]?[0-9]{1,})?");
        }
    • 3.0第一个只出现一次的字符

    题目描述

    在一个字符串(0<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).

    import java.util.LinkedHashMap;
    public class Solution {
    public int FirstNotRepeatingChar(String str) {
        	//这个hashmap有序,所以用这个
            LinkedHashMap<Character, Integer> map= new LinkedHashMap<>();
            //遍历字符串,第一次设为1 否则就加
            for (int i = 0; i < str.length(); i++) {
    			if (!map.containsKey(str.charAt(i))) {
    				map.put(str.charAt(i), 1);
    			}
    			else
    				map.put(str.charAt(i),map.get(str.charAt(i))+1);
    		}
            //找出现次数为1的
            for (int i = 0; i < str.length(); i++) {
    			if (map.get(str.charAt(i)) == 1) {
    				return i;
    			}
    		}
            return -1;
        }
    }

    • 3.1字符流中第一个不重复的字符

    请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时,第一个只出现一次的字符是"l"。如果当前字符流没有存在出现一次的字符,返回#字符

    思路:参考两个博客一种用hashmap来做,一种用字符数组来做。

    hashmap方法:

        HashMap<Character, Integer> map = new HashMap<>();//记录字符出现次数
        ArrayList<Character> list = new ArrayList<>();//记录当前的所有的字符
        //Insert one char from stringstream
        public void Insert(char ch)
        {
            if(map.containsKey(ch))
            	map.put(ch, map.get(ch)+1);
            else
            	map.put(ch,1);
            list.add(ch);
        }
      //return the first appearence once char in current stringstream
        public char FirstAppearingOnce()
        {
            for(char c:list) {
            	if(map.get(c)==1)
            		return c;
            }
            return '#';
        }

    字符数组的方法:

    char类型和int类型数值在 0-255之内的可以通用

    默认初始值是ASCII的0(int);char类型会自动转换成(int型)ASCII进行算术运算

       char [] chars = new char[256];//ascii字符共128,其他字符非中文认为256个,
                                    //为每个字符预留空间。默认每个存的ascii值为0 
       StringBuffer sb = new StringBuffer();//记录当前的所有字符
        //Insert one char from stringstream
        public void Insert(char ch)
        {
            sb.append(ch);
            chars[ch]++;//如果字符是1,那么就是在字符1对应的下标的地方
                        //也就是49的下标处,ascii加1.此时如果输出chars[ch],里面存ascii值
                        //为1,所以是一个不可显示的字符。
        }
      //return the first appearence once char in current stringstream
        public char FirstAppearingOnce()
        {
             char [] str = sb.toString().toCharArray();
             for(char c:str) {
            	 if(chars[c] == 1)//判断这个字符数组中在这个字符下标处值是否为1.
            		 return c;
             }
             return '#';
        }
    • 4.翻转字符串

    牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?

    思路:两个思路,一个比较简单的就是用空格切分出来,student.  a am I。然后从后往前添加到stringbuffer里面。

    另一个思路就是基本思路剑指offer,先将整个字符串翻转,然后将每个单词翻转。i love you  反转就是  uoy evol i,然后再每个单词进行反转。

    public class Fanzhuan {
    	//第一种方法,用空格将字符串切分,
    	//倒着往stringbuffer里面插入。
    	public String ReverseSentence1(String str) {
    		if (str == null || str.trim().length() == 0) {
    			return str;
    		}
    		String[] strs =str.split(" ");//str = "i love you"则strs[0]=i strs[1]=love
    		StringBuffer sb = new StringBuffer();
    		for (int i = strs.length -1; i >= 0; i--) {
    			sb.append(strs[i]);
    			if (i>0) {//最后一个不添加空格
    				sb.append(" ");
    			}
    		}
    		return sb.toString();
    	}
    	//第二种思路,先将整个字符串反转,再逐个单词反转
    	public String ReverseSentence(String str) {
    	    if (str == null || str.length() == 0)
    	        return str;
    	    if (str.trim().length() == 0)
    	        return str;
    	    StringBuilder sb = new StringBuilder();
    	    String re = reverse(str);
    	    String[] s = re.split(" ");
    	    for (int i = 0; i < s.length - 1; i++) {
    	        sb.append(reverse(s[i]) + " ");
    	    }
    	    sb.append(reverse(s[s.length-1]));
    	    return String.valueOf(sb);
    	}
    
    	public String reverse(String str) {
    	    StringBuilder sb = new StringBuilder();
    	    for (int i = str.length() - 1; i >= 0 ; i--) {
    	        sb.append(str.charAt(i));
    	    }
    	    return String.valueOf(sb);
    	}
    }
    
    • 5.左旋转字符串

    汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S,请你把其循环左移K位后的序列输出。例如,字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!

    思路:前n位反转,后几位反转,最后总的反转

    先反转前n位,再反转后几位,变为了cbafedZYX,再整体反转变为XYZdefabc

     public String LeftRotateString(String str,int n) {
            if (str == null || str.trim().length() == 0) {
    			return str;
    		}
            int len = str.length();
            n = n % len;// 当len=3,n=4,其实相当于左旋转1位,所以需要取余
            char[] charstr = str.toCharArray();
            //先旋转前面的
            reverse(charstr, 0, n-1);
            //再旋转后面的字符串
            reverse(charstr, n, len -1);
            //最后整体反转
            reverse(charstr, 0, len-1);
            return String.valueOf(charstr);
        }
        //实现的是charstrs从i到j的反转,也可以使用上题中stringbuffer的反转方式
    	private void reverse(char[] charStrs, int i, int j) { 
    		while(i<j) {
    			char temp = charStrs[i];
    			charStrs[i] =charStrs[j];
    			charStrs[j] = temp;
    			i++;
    			j--;
    		}
    	}
    
    • 5.把字符串转换为整数

    将一个字符串转换成一个整数,要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0

    思路:若为负数,则输出负数,字符0对应48,9对应57,不在范围内则返回false。

    public class Strtoint {
    	public int StrToInt(String str) {
    		if (str == null || str.length() == 0)
    			return 0;
    		int mark = 0;
    		int number = 0;
    		char[] chars = str.toCharArray();
    		if (chars[0] == '-')
    			mark = 1;//第一位如果是-号,则从第二位开始循环
    		for (int i = mark; i < chars.length; i++) {
                 if(chars[i] == '+')
                	 continue;
                 if(chars[i]<48 || chars[i]>57)
                	 return 0;
                 number = number * 10+chars[i] - 48;
    		}
    		return mark==0?number:-number;//最后根据mark标记的正负号来决定数字正负
    	}
    
    }
    

    6、字符串的排列 

    题目描述

    输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

    输入描述:

    输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    
    public class Solution {
    //解法来源:牛客网评论。基于回溯的递归实现。
        /**剑指offer的思路解析。
    	 * 步骤:
    	 * 
    	 * @param str
    	 * @return
    	 */
    	public ArrayList<String> Permutation(String str) {
    		List <String> res = new ArrayList<String>();
    	    if(str != null && str.length() >0){
    	    	PermutationHelp(str.toCharArray(),0,res);
    	    	Collections.sort(res); //按字典序 输出字符串数组。
    	    }
    	    	
    		return (ArrayList)res;
    	}
    	public void PermutationHelp(char[] chars, int index, List<String> list) {
    		if(index == chars.length -1){ //当递归交换到最后一个位置的时候,就看看list有么有这个字符串,没有的话就放进去。
    			String val = String.valueOf(chars);
    			if (!list.contains(val)) {//如果最后list没有这个string,因为可能交换后有重复的
    				list.add(val);
    			}
    		}
    		else {
    		    for (int i = index; i < chars.length; i++) { //循环来执行交换操作,先交换,然后固定这个,下一个交换。最后要交换回来不要影响执行
    				swap(chars, index, i);
    				PermutationHelp(chars, index+1, list);//依次固定一个
    				swap(chars, index, i);
    			}
    		}
    	}
    	public void swap(char[] chars,int i, int j) {//交换数组中的两个位置中的值
    		char temp =chars[i];
    		chars[i] = chars[j];
    		chars[j] = temp;
    			
    	}
    	
    }

    四、数组

    • 1.数组中重复的数字

    在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2

    思路:比较好的思路的分析为,数组中的数字为0到n-1的范围内。如果这个数组中没有重复的数字,则对应的i位置的数据也为i。可以重排此数组,

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashSet;
    import java.util.Set;
    
    public class chongfushuzi {
        // 使用排序的方式
        public boolean duplicate(int numbers[],int length,int [] duplication) {
            if(numbers == null || numbers.length ==0) {
            	duplication[0] = -1;
            	return false;
            }
            Arrays.sort(numbers);
            for (int i = 0; i < length -1; i++) {//注意这个i的范围可能越界
    			if(numbers[i] == numbers[i+1]) {
    				duplication[0] = numbers[i];
    				return true;
    			}
    		}
            return false;
            
        }
        //使用额外空间的方法。
        public boolean duplicate2(int numbers[],int length,int [] duplication) {
            if(numbers == null || numbers.length ==0) {
            	duplication[0] = -1;
            	return false;
            }
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < length; i++) {
    			if(list.contains(numbers[i])) {
    				duplication[0] = numbers[i];
    				return true;
    			}
    			list.add(numbers[i]);
    		}
            return false;
        }
        //使用额外空间的方法。
        public boolean duplicate4(int numbers[],int length,int [] duplication) {
        	 if(length < 2||numbers==null){
                 return false;
             }
    
             Set<Integer> ss = new HashSet<Integer>();
             for (int i = 0; i < numbers.length; i++) {
                 if (ss.contains(numbers[i])) {
                     duplication[0] = numbers[i];
                     return true;
                 } else {
                     ss.add(numbers[i]);
                 }
             }
             return false;
         }
        
        //比较好的解决方式,时间复杂度O(n),空间复杂度O(1)
        //数组中的数字为0到n-1的范围内。
        //如果这个数组中没有重复的数字,则对应的i位置的数据也为i。可以重排此数组
        public boolean duplicate3(int numbers[],int length,int [] duplication) {
        	  if(numbers == null || numbers.length ==0) {
              	duplication[0] = -1;
              	return false;
              }
        	  for (int i = 0; i < length; i++) {
      			if (numbers[i] < 0 || numbers[i] > length - 1) {
      				duplication[0] = -1;
      				return false;
      			}
             }
        	  for (int i = 0; i < length; i++) {
    			while(numbers[i] != i) {
    				if(numbers[i] == numbers[numbers[i]]) {
    					duplication[0] = numbers[i];
    					return true;
    				}
    				else {
    					int tmp = numbers[i];
    					numbers[i] = numbers[tmp];
    					numbers[tmp] = tmp;
    				}
    				
    			}
    		}
        	 return false; 
        }
    }
    
    • 2.构建乘积数组

    给定一个数组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]。不能使用除法。

    思路:用矩阵的方式,先计算左下三角,再计算右上三角。根据图来分析即可。

    public class MultiArray {
    	// 新建一个新数组B, 对A数组i项左侧自上往下累乘,
    	// 对A数组i项右侧自下往上累乘 时间复杂度O(n)
        public int[] multiply(int[] A) {
        	// 将B拆分为A[0] *...* A[i-1]和A[n-1]*...*A[i+1] 两部分
        	if(A == null || A.length ==0)
            	return A;
            int length = A.length;
            int [] B = new int[length];
            B[0] = 1;
         // 先计算左下三角形,此时B[0]只有一个元素,舍为1,
         		// B[0]不包括A[0]
            for (int i = 1; i < length; i++) {
    			B[i] = B[i-1]*A[i-1];
    		}
            int tmp =1;
            //计算右上三角形
            for (int i = length -1; i >=0; i--) {
    			//最终的B[i]是之前乘好的再乘以右边的
            	B[i] *=tmp;
    		tmp *= A[i];
    		}
            
            return B;
        }
    }

    复杂度为O(n^2)的解法如下:(有个对比就行)

    public int[] multiplyWithFor(int[] A) {
    		int len = A.length;
    		// 定义一个结果对象
    		int[] result = new int[len];
    		// 定义一个基本的量
    		int rst = 1;
    		for (int i = 0; i < len; i++) {
    			// 如果相同,就路过继续
    			for (int j = 0; j < len; j++) {
    				if (i == j) {
    					continue;
    				}
    				// 如果不同,就相乘
    				rst *= A[j];
    			}
    			result[i] = rst;
    			rst = 1; // 还原基本的量
    		}
    		return result;
    	}
    	// 
    • 3.二维数组的查找

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

    思路:

     从右上角开始,若小,向下走,删除一行,若大,向左走,删除一列

    /*
    利用二维数组由上到下,由左到右递增的规律,
    那么选取右上角的元素a[row] [col]与target进行比较,
    当target小于元素a[row] [col]时,那么target必定在元素a所在行的左边,
    即col--;
    当target大于元素a[row][col]时,那么target必定在元素a所在列的下边,
    即row++;
    *
        public boolean Find(int target, int [][] array) {
            int row = 0;
            int col = array[0].length -1;
            while(row<array.length && col>= 0) {
            	if (array[row][col]==target) {
    				return true;
    			}
            	else if (array[row][col]<target) {
    				row++;
    			}
            	else {
    				col--;
    			}
            }
            return false;
        }
    • 4.数组中只出现一次的数字

    一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

    思路:主要参考左神的思路,辅之以剑指offer思路。主要如下:

    参考的部分思路:当只有一个数出现一次时,我们把数组中所有的数,依次异或运算,最后剩下的就是落单的数,因为成对儿出现的都抵消了。 

     依照这个思路,我们来看两个数(我们假设是AB)出现一次的数组。我们首先还是先异或,剩下的数字肯定是A、B异或的结果,这个结果的二进制中的1,表现的是A和B的不同的位。我们就取第一个1所在的位数,假设是第3位,接着把原数组分成两组,分组标准是第3位是否为1。如此,相同的数肯定在一个组,因为相同数字所有位都相同,而不同的数,肯定不在一组。然后把这两个组按照最开始的思路,依次异或,剩余的两个结果就是这两个只出现一次的数字。

    所以,只于k位上是1的异或,就把其中一组的落单的那个异或出来了。此外a^b=d  则a^d=b满足结果的互换。知道异或的结果和其中一个,可以求得另一个。

        public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
            int eO = 0,eOne = 0;
            for(int num:array)
            	eO ^=num;
            int firstOne = eO &(~eO +1);//求得二进制中第一位1,比如101和011得到010
            for(int cur:array)
            	if ((cur&firstOne) !=0) {//把第k位是1的一组找出来进行异或
    				eOne ^=cur; 
    			}//最终结果就是第k位是1且落单的那个
           num1[0] = eOne;
           num2[0] = eOne^eO;//异或结果的运算规则。
        }
    • 5、和为S的两个数

    输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

    思路:

    1. // 数列满足递增,设两个头尾两个指针i和j,

    2. // 若ai + aj == sum,就是答案(和一定,两个数字相差越远乘积越小)

    3. // 若ai + aj > sum,aj肯定不是答案之一,j -= 1

    4. // 若ai + aj < sum,ai肯定不是答案之一,i += 1

    5. // O(n)

    6. // 已经排好序,运用数学上的夹

        public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
            ArrayList<Integer> list = new ArrayList<>();
            if(array == null || array.length <2)
            	return list;
            int low = 0;
            int high = array.length -1;
            while(low < high) {
            	int small = array[low];
            	int big = array[high];
            	if(small + big == sum) {
            		list.add(small);
            		list.add(big);
            		break;
            	}
            	else if (small+big < sum) 
    				low++;
            	else 
    				high--;
    			
            	
            }
            return list;
        }

    • 6.和为S的连续正数序列

    小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

    思路:剑指offer

    	/*
    	*初始化small=1,big=2;
    	*small到big序列和小于sum,big++;大于sum,small++;
    	*当small增加到(1+sum)/2是停止
    	*/
        public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
            ArrayList<ArrayList<Integer>> res = new ArrayList<>();
            ArrayList<Integer> list = new ArrayList<>();
            if(sum < 3) //不重复,最少有两个数字
            	return res;
            int small = 1;
            int big = 2;
          //因为是两个数,假设small是这个
            //,big假设也是这个,和为sum+1,所以到此就可以停了,后面肯定更大
            while(small !=(sum+1)/2) { 
            	int cursum = SumOfList(small, big);
            	if(cursum == sum) {
            		for (int i = small; i <= big; i++) {
    					list.add(i);
    				}
            		res.add(new ArrayList<>(list));
            		list.clear();//清理掉
            		big++;//找到一组,继续big++,找下一组满足要求的。
            	}
            	else if (cursum > sum) {
    				small++;
    			}
            	else {
    				big++;
    			}
            }
            return res;
        }
        //计算list内的数据的和
        public int SumOfList(int small, int big) {
    		int sum = 0;
    		for (int i = small; i <= big; i++) {
    			sum +=i;
    		}
    		return sum;
    	}

    7、调整数组顺序使奇数位于偶数前面 

    输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。

    import java.util.ArrayList;
    //import java.util.Arrays;
    public class Solution {
        public void reOrderArray(int [] array) {
            ArrayList<Integer> jlist = new ArrayList<Integer>();
            ArrayList<Integer> olist = new ArrayList<Integer>();
            for (int i = 0; i < array.length; i++) {
    			if (array[i]%2 == 0) 
    				olist.add(Integer.valueOf(array[i]));
    			else
    				jlist.add(Integer.valueOf(array[i]));//valueOf 是将int转换为Integer
                                                         //intValue是反过来
    			
    		}
            jlist.addAll(olist);
            int temp = 0;
            for (int i = 0; i < jlist.size(); i++) {  
                //System.out.println(jlist.get(i));  
            	array[temp] = jlist.get(i).intValue();
            	temp++;
            } 
        }
        //前一种方法的执行时间低,但是需要额外的空间,后一种方法执行时间高一点,但是不需要额外的空间
        /*public void reOrderArray(int[] array) {  
            int temp = 0;
            for (int i = 0; i < array.length - 1; i++) {  
                for (int j = 0; j < array.length - 1 - i; j++) {  
                    // 前偶后奇数就交换  
                    if ((array[j] & 1) == 0 && (array[j + 1] & 1) == 1) {  //与1位与得1就是奇数,1只有最后一位是1
                        temp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = temp;
                    }  
                }  
            }  
        } */
    }

    8、数组中出现次数超过一半的数字

    数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

    public class Solution {
        /**自己的空间复杂度的思路,哈希表记录。
         * 此外:博客,基于快排、基于阵地。此处采用基于防守阵地的方式来进行。
         * 左的思路。
         * 一次再数组中删除两个不同的数,最后剩下的数   有可能    是超过一半的。所以要检验一下。 一个数出现次数大于一半,他肯定会被剩下来,但是剩下来的缺不一定满足。
         * 算法步骤:
         * 如果times为0,就把候选设为当前值。
         * 如果下个数和候选一样,times就++。
         * 如果下个数和候选不一样,times就--。相当于对子,同归于尽。因为超过一半的数肯定超过剩下的所有数。所以和这个数对,这个数肯定会剩下来。
         * 但是剩下的数不一定是,比如 1 2 3 剩下3 比如 1 2 1 3 3 3 2 2 也是剩下3.所以要余外的判断,看是否这个数真的超过。
         * @param array
         * @return
         */
        public int MoreThanHalfNum_Solution(int [] array) {
            int cand = 0;
            int times = 0;
            for (int i = 0; i < array.length; i++) {
    			if(times == 0){
    				cand = array[i];
    				times = 1;
    			}
    			else if (array[i] == cand) {
    				times++;
    			}
    			else {
    				times--;
    			}
    		}
            times = 0;
            for (int i = 0; i < array.length; i++) {
    			if(array[i] == cand)
    				times++;
    		}
            if (times*2 > array.length) {
    			return cand;
    		}
            else
               return 0;
        }
    }

    9、连续子数组的最大和

    题目描述

    HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组,返回它的最大连续子序列的和,你会不会被他忽悠住?(子向量的长度至少是1)

    /* 算法时间复杂度O(n) 用total记录累计值,maxSum记录和最大 基于思想:对于一个数A,若是A的左边累计数非负,那么加上A能使得值不小于A,认为累计值对 整体和是有贡献的。如果前几项累计值负数,则认为有害于总和,total记录当前值。 此时 若和大于maxSum 则用maxSum记录下来 */

    public class Solution {
    /**
    	 * 不是看当前的值,而是看当前的累计值,如果当前累计为负数,那么加上现在这个数,
    	 * 肯定和就小了,所以继续从当前开始累计,如果为正,那就继续加,
    	 * 但是要时刻保存下最大值来,因为后面的累计有可能小。
    	 * @param array
    	 * @return
    	 */
    	public int FindGreatestSumOfSubArray(int[] array) {  
    		if(array.length == 0)
    			return 0;
    		int total = array[0];//当前的前面的和累计
    		int maxsum = array[0];//记录可能的最大值
    		for (int i = 1; i < array.length; i++) {
    			if(total >= 0)//
    				total = total + array[i];
    			else
    				total = array[i];
    			if(total>maxsum)
    				maxsum = total;
    		}
    		return maxsum;
    	}
    }

    10、把数组排成最小的数 

    题目描述

    输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。

    /* 解题思路: * 考虑到大数问题,先将整型数组转换成String数组,然后将String数组排序,最后将排好序的字符串数组拼接出来。关键就是制定排序规则。 * 排序规则如下: * 若ab > ba 则 a > b, * 若ab < ba 则 a < b, * 若ab = ba 则 a = b; * 解释说明: * 比如 "3" < "31"但是 "331" > "313",所以要将二者拼接起来进行比较 */

    import java.util.Arrays;
    import java.util.Comparator;
    
    public class Solution {
    
    	    /**
    	     * 主要就是规则的制定,将两个数字转换为字符串,防止溢出
    	     * 假设两个数字m和n,拼接有mn和nm
    	     * 如果mn>nm, 我们打印nm,此时定义n小于m。(此处小于是我们定义的)
    	     * 不是m和n的大小关系,
    	     * 而是看拼了之后的大小,来决定m和n的大小。
    	     * 如果mn<nm 那么就是m小于n。
    	     * 
    	     * @param numbers
    	     * @return
    	     */
    	    public String PrintMinNumber(int [] numbers) {
                 if(numbers == null || numbers.length == 0)
                	 return "";
                 int len = numbers.length;
                 String[] str = new String[len];
                 StringBuffer sb = new StringBuffer();
                 //将数字型的放在字符串数组中。
                 for (int i = 0; i < len; i++) {
    				str[i] = String.valueOf(numbers[i]);
    			}
                 //根据定义的规则重新堆str进行升序排序
                Arrays.sort(str, new Comparator<String>() {
    
    				@Override
    				public int compare(String s1, String s2) {
    					// TODO Auto-generated method stub
    					String c1 = s1 + s2;
    					String c2 = s2 + s1;
    					
    					return c1.compareTo(c2);
    				}
    
    			});
                //根据规则排好序,将结果依次放入stringbuffer中就行了
                for (int i = 0; i < len; i++) {
    				sb.append(str[i]);
    			}
                
                return sb.toString();
    	    }
    }

    11、数组中的逆序对

    题目描述

    在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

    输入描述:

    题目保证输入的数组中没有的相同的数字

    数据范围:

    对于%50的数据,size<=10^4

    对于%75的数据,size<=10^5

    对于%100的数据,size<=2*10^5

    示例1

    输入1,2,3,4,5,6,7,0

    输出7

    public class Solution {
     
        /**主要是剑指offer的思想,用了归并排序,用count来记录数量
         * 所不同的是用的--而不是++
         * 每一次归并之前,记录当前有的个数,
         * @param array
         * @return
         */
    	int count = 0;
        public int InversePairs(int [] array) {
        	if(array == null || array.length ==0)
        		return 0;
        	mergeSort(array, 0, array.length -1);
        	return count;
        	
        }
        public void mergeSort(int []array, int start, int end) {
    		if(start < end) {
    			int mid = (start + end)/2;
    			mergeSort(array, start, mid);
    			mergeSort(array, mid + 1, end);
    			merge(array, start, mid, mid+ 1, end);
    		}
    	}
        public void merge(int []array,int start1,int end1, int start2, int end2) {
    		int i = end1;
    		int j = end2;
    		int k = end2 - start1 ;
    		int [] temp = new int[end2- start1 +1];
    		while(i >= start1 && j >=start2) {
    			if(array[i] > array[j]) { 
    				//假设此时两个归并的是17 19 22 || 16 18 21
    				//那么22大于21,所以可以看出对应22
    			    //有三个,22 16 22 18 22 21
    				temp[k--] = array[i--];
    				count = count + j - start2 +1;
    				count %= 1000000007;
    			}
    			else
    				temp[k--] = array[j--];
    		}
    		while(i >= start1)
    			temp[k--] = array[i--];
    		while(j >= start2)
    			temp[k--] = array[j--];
    
            int m = start1;
            for(int element:temp)
            	array[m++] = element;
    		
    	}
    }

    12、数字在排序数组中出现的次数

    统计一个数字在排序数组中出现的次数。

    思路:

    public class Solution {
        /**
         * 博客上的解题思路,也就是剑指offer的思路
         * 首先用递归二分法找到第一个k和最后一个k,然后得到个数
         * @param array
         * @param k
         * @return
         */
        public int GetNumberOfK(int [] array , int k) {
            int num = 0;
            if (array != null && array.length >0) {
    			int firstk = getFirstK(array, k,0, array.length-1);
    			int lastk = getLastK(array, k,0, array.length-1);
    			if (firstk > -1 && lastk > -1) 
    				num = lastk -firstk +1;
    			
    			
    		}
            return num;
        }
        /*
         * 找到第一个出现的数字的下标
         */
        public int getFirstK(int [] array, int k,int start, int end) {
        	if(start > end)
        		return -1;
    		int midindex = (start + end)/2;
    		int middata = array[midindex];
    		if (middata == k) {
    			//判断是不是第一个K,前一个不等于K,就是第一个K
    			if(midindex > 0 && array[midindex - 1]!=k||midindex == 0)
    				return midindex;
    			else
    				end = midindex -1;//如果不是第一个k,那么肯定是在前面找,所以end要往前放
    				
    		}
    		else if (middata > k) {
    			end = midindex -1; //二分,如果这个大于k,所以要在前面找
    		}
    		else
    			start = midindex + 1;// 如果小于k,说明要往后找
    		return getFirstK(array,k, start, end);
    	}
    
        /*
       * 找到最后一个出现的数字的下标
       */
        public int getLastK(int [] array, int k,int start, int end) {
    		if(start > end)
    			return -1;
    		int midindex = (start + end)/2;
    		int middata = array[midindex];
    		if(middata == k) {
    			 //判断是不是最后一个K,后一个不等于K,就是最后一个K
    			if(midindex < array.length-1 && array[midindex + 1]!= k||midindex ==array.length -1)
    		            return midindex;
    			else
    				start = midindex + 1;
    		}
    		else if (middata > k) {
    			end = midindex - 1;
    		}
    		else 
    			start = midindex +1;
    		return getLastK(array, k,start, end);
    	}
    }

    五、发散思维能力

    • 1.求1+2+3+...+n

    求1+2+3+...+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

    思路:巧用递归,用了短路,使递归结束。

    1. // &&两侧的表达式结果必须为boolean型,

    2. // 所有&&右侧要用一个无关变量a判断是否与result相等,

    3. // 让右侧的表达式返回boolean型。不管返回的是true还是false,

    4. // 我们的目的仅仅是让&&右侧的表达式执行。

    5. // &&连接的表达式,必须要将最终的boolean结果赋给变量,否则编译报错!

    6. 一直执行递归,当n=0时,短路,不执行,开始执行result+n,一直回溯就把n给加上来。

        public int Sum_Solution(int n) {
            int result =0;
            int temp = 0;
            boolean flag = (n>0) && temp == (result = Sum_Solution(n-1));
            result += n;
            return result;
        }
    • 2.不用加减乘除做加法

    写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。

    思路:

    首先看十进制是如何做的: 5+7=12,三步走

    第一步:相加各位的值,不算进位,得到2。

    第二步:计算进位值,得到10. 如果这一步的进位值为0,那么第一步得到的值就是最终结果。

    第三步:重复上述两步,只是相加的值变成上述两步的得到的结果2和10,得到12。

    同样我们可以用三步走的方式计算二进制值相加: 5-101,7-111 第一步:相加各位的值,不算进位,得到010,二进制每位相加就相当于各位做异或操作,101^111。

    第二步:计算进位值,得到1010,相当于各位做与操作得到101,再向左移一位得到1010,(101&111)<<1。

    第三步重复上述两步, 各位相加 010^1010=1000,进位值为100=(010&1010)<<1。 
    继续重复上述两步:1000^100 = 1100,进位值为0,跳出循环,1100为最终结果。

        public int Add(int num1,int num2) {
    		int sum = num1;//保证当num2为0时候返回num1
    		int carry = 0;
    		while(num2 != 0) {
    			sum = num1 ^ num2;
    			carry = (num1 & num2) << 1;
    			num1 = sum;
    			num2 = carry;
    			
    		} 
    		return sum;
        }

    使用递归的方式实现:

    	public int Add(int num1, int num2) {
    		if (num2 == 0)
    			return num1;
    		return Add(num1 ^ num2, (num1 & num2) << 1);
    	}

    3、旋转数组的最小数字

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

    思路:思路:利用二分法,找到中间的数,然后和最左边的值进行比较,若大于最左边的数,则最左边从mid开始,若小于最右边值,则最右边从mid开始。若左中右三值相等,则取mid前后值中较小的数。

    import java.util.ArrayList;
    public class Solution {
        public int minNumberInRotateArray(int [] array) {
            int front = 0;
            int rear = array.length-1;
            int mid = (front + rear)/2;
            while(front < rear){
                if(rear - front == 1){
                    break;
                }
                mid = (front + rear)/2;
                if(array[mid] >= array[front]){
                    front = mid;
                }
                else{
                    rear = mid;
                }
            }
            return array[rear];
        }
    }

    六、其他

    • 1.整数中1出现的次数(从1到n中的整数中1出现的次数)

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

    思路:主要是根据编程之美博客的思路,左程云的思路类似,但是感觉代码稍微麻烦一点。

    编程之美上给出的规律: 
    1、 如果第i位(自右至左,从1开始标号)上的数字为0
    (小于x),则第i位可能出现1的次数由更高位决定(若没有高位,视高位为0),等于更高位数字 * 当前位数的权重10^(i-1)。

    2、如果第i位上的数字为1(等于x),则第i位上可能出现1的次数不仅受更高位影响,还受低位影响(若没有低位,视低位为0),等于更高位数字 * 当前位数的权重10^(i-1)+(低位数字+1)。

    3、如果第i位上的数字大于1(大于x),则第i位上可能出现1的次数仅由更高位决定(若没有高位,视高位为0),等于(更高位数字+1) * 当前位数的权重10^(i-1)。

    这个思路中,如果不是求1出现的次数,而是求其他1-9任意一个次数,就是比较大于、等于、小于这个数就行了,分别对应上边的三条规则。0的出现次数需要余外计算。

    X的数目 
    这里的 X∈[1,9] ,因为 X=0 不符合下列规律,需要单独计算。

    首先要知道以下的规律: 
    从 1 至 10,在它们的个位数中,任意的 X 都出现了 1 次。 
    从 1 至 100,在它们的十位数中,任意的 X 都出现了 10 次。 
    从 1 至 1000,在它们的百位数中,任意的 X 都出现了 100 次。

    依此类推,从 1 至 10^ i ,在它们的左数第二位(右数第 i 位)中,任意的 X 都出现了 10^(i-1) 次。

    这个规律很容易验证,这里不再多做说明。 
    接下来以 n=2593,X=5 为例来解释如何得到数学公式。从 1 至 2593 中,数字 5 总计出现了 813 次,其中有 259 次出现在个位,260 次出现在十位,294 次出现在百位,0 次出现在千位。

    现在依次分析这些数据, 
    首先是个位。从 1 至 2590 中,包含了 259 个 10,因此任意的 X 都出现了 259 次。最后剩余的三个数 2591, 2592 和 2593,因为它们最大的个位数字 3 < X,因此不会包含任何 5。(也可以这么看,3 < X,则个位上可能出现的X的次数仅由更高位决定,等于更高位数字(259)*10^(1-1)=259)。

    然后是十位。从 1 至 2500 中,包含了 25 个 100,因此任意的 X 都出现了 25×10=250 次。剩下的数字是从 2501 至 2593,它们最大的十位数字 9 > X,因此会包含全部 10 个 5。最后总计 250 + 10 = 260。(也可以这么看,9>X,则十位上可能出现的X的次数仅由更高位决定,等于更高位数字(25+1)*10^(2-1)=260)。

    接下来是百位。从 1 至 2000 中,包含了 2 个 1000,因此任意的 X 都出现了 2×100=200 次。剩下的数字是从 2001 至 2593,它们最大的百位数字 5 == X,这时情况就略微复杂,它们的百位肯定是包含 5 的,但不会包含全部 100 个。如果把百位是 5 的数字列出来,是从 2500 至 2593,数字的个数与百位和十位数字相关,是 93+1 = 94。最后总计 200 + 94 = 294。(也可以这么看,5==X,则百位上可能出现X的次数不仅受更高位影响,还受低位影响,等于更高位数字(2)*10^(3-1)+(93+1)=294)。

    最后是千位。现在已经没有更高位,因此直接看最大的千位数字2< X,所以不会包含任何 5。(也可以这么看,2< X,则千位上可能出现的X的次数仅由更高位决定,等于更高位数字(0)*10^(4-1)=0)。 
    到此为止,已经计算出全部数字 5 的出现次数。

    总结一下就是:

    求x出现的次数,分别拆分,然后根据编程之美判断这一位与x的大小关系,分情况写出出现的次数。

      public int NumberOf1Between1AndN_Solution(int n) {
            int low,cur,temp,i=1;
            int high = n;//记录高位数
            int total = 0; //总的1的数量
            if(n < 1)
            	return 0;
            while(high!=0) {
            	//记忆2593 此时i=2,依次拆分25 9 3
            	high = n/powerBaseof10(i); 获取第i位的高位
            	temp = n%powerBaseof10(i);
            	cur = temp/powerBaseof10(i-1);// 获取第i位
            	low = temp%powerBaseof10(i-1);// 获取第i位的低位
            	if(cur ==1) {
            		total += high * powerBaseof10(i-1) + low +1;
            	}
            	else if (cur > 1) {
    				total += (high + 1) * powerBaseof10(i -1);
    			}
            	else {
    				total += high * powerBaseof10(i-1);
    			}
            	i++;
            }
            return total;
        }
        //就是求10^base次方
        public int powerBaseof10(int base) {
        	return (int)Math.pow(10, base);
        }
    • 2.扑克牌顺子

    LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿!!“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何。为了方便起见,你可以认为大小王是0。

    思路:剑指和博客

    思路:用数组记录五张扑克牌,将数组调整为有序的,若0出现的次数>=顺子的差值,即为顺子。

        public boolean isContinuous(int [] numbers) {
            if(numbers == null || numbers.length ==0)
            	return false;
            int zero = 0;//记录0的个数
            int diff = 0;//记录空缺的数
            Arrays.sort(numbers);
            
            for (int i = 0; i < numbers.length -1; i++) {
    			if(numbers[i] == 0) {
    				zero++; //找不到非0的就继续下一次循环
    				continue;
    			}
    			if (numbers[i] != numbers[i+1]) {
    				diff += numbers[i+1] - numbers[i] -1 ;//4 和 8,中间空缺3
    			}
    			else
    				return false;//说明有对子,肯定不是顺子
    				
    		}
            if(diff<= zero)
            	return true;//如果diff小于zero,那么zero放在最后就行,因为任意值
            return false;
        }
    • 3.孩子们的游戏(圆圈中剩下的数)

    每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢?(注:小朋友的编号是从0到n-1)

    思路:使用递推或者是循环链表的方式。

    循环链表的方式:

    bt = (bt + m -1)%list.size();解析:

    假设有9个人,m=5,那么第一次是去掉4,然后从5开始数,下次刚好是0.

       public int LastRemaining_Solution(int n, int m) {
            LinkedList<Integer> list = new LinkedList<>();
            for (int i = 0; i < n; i++) {
    			list.add(i);
    		}
            int bt = 0;
            while(list.size() >1) {
            	 删除报数为m-1的人(从0开始)
            	//解析看前面
            	bt = (bt + m -1)%list.size();
            	list.remove(bt);
            }
            return list.size()==1?list.get(0):-1;
        }

    递推公式的:主要剑指offer上有,没有细看。

    // 第一种方法使用递推公式
    	public int LastRemaining_Solution(int n, int m) {
    		if (m < 1 || n < 1)
    			return -1;
    		int last = 0;
    		// i代表有目前有个人
    		for (int i = 2; i <= n; i++)
    			last = (last + m) % i;
    		return last;
    	}
    • 4、替换空格

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

    思路:新定义一个往后追加。

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

    5、斐波那契数列 

    大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。

    n<=39

    递归简洁,但是效率不高。循环O(N)

    public class Solution {
        public int Fibonacci(int n) {
    	    	/*int pretwo = 0;
    	    	int preone = 1;
    	    	int res = 0;
    	    	if(n==0)
    	    		return 0;
    	    	if(n==1)
    	    		return 1;
    	    	for(int i = 2;i <= n;i++)
    	    	{
    	    		res = preone + pretwo;
    	    		pretwo = preone;
    	    		preone = res;
    	    		
    	    	}
    	    	return res;*/
            int res = 0;
    	    	
    	        if(n==1 || n==2)
    	        	return 1;
    	        else if(n == 0)
    	        	return 0;
    	        else {
    		       res = Fibonacci(n-1) + Fibonacci(n-2);		
    			}
    	        return res;
        }
    }

    6、跳台阶

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

    思路:斐波拉契数序列,初始条件n=1:只能一种方法,n=2:两种 
    对于第n个台阶来说,只能从n-1或者n-2的台阶跳上来,所以 
    F(n) = F(n-1) + F(n-2)

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

     7、变态跳台阶

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

    思路:

    public class Solution {
        public int JumpFloorII(int target) {
            int res = 1;
            for(int i =1;i <=target-1;i++){
                
                res = res * 2;
                
            }
            return res;
        }
    }

    8、矩形覆盖

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

    public class Solution {
        public int RectCover(int target) {
    	        int res = 0;
                if(target == 0)
                    return 0;
    	        else if(target == 2)
    	            return 2;
                else if(target ==1)
                    return 1;
    	      	else
    	            res = RectCover(target - 1) + RectCover(target-2);
    	        return res;
             /*int result = 0;  
                if (target > 0) {  
                    if (target <= 2)  
                        return target;  
                    else  
                        return result = RectCover(target - 1) + RectCover(target - 2);  
                }  
                return result;  */
        }
    }

     9、数值的整数次方

    给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方

    public class Solution {
        public double Power(double base, int exponent) {
    		//本题注意的是exponent小于0 或者 等于 0 的情况 还有base为0的情况
            double result = 1;
    	    if(exponent < 0){
    	    	base = 1/base;
    	    	exponent = (-1) * exponent;
    	    	for (int i = 1; i <= exponent; i++) {
    				result = result *base;
    			}
    	    }
    	    else{
    		    for (int i = 1; i <= exponent; i++) {
    				result = result *base;
    			}
    	    }
    		return result;
      }
    }
            
        /*{
                double res = 0;
    
        if (exponent == 0) {
            return 1.0;
        }
        if (exponent > 0) {
            res = mutiply(base,exponent);
        }else {
            res = mutiply(1/base,-exponent);
        }
        return res;
    }
    
    public double mutiply(double base, int e) {
        double sum = 1;
        for (int i = 0; i < e; i++) {
            sum = sum * base;
        }
        return sum;
    }
    }*/
    /*博客
    public class Solution {
    	//时间复杂度O(n)
    	public double Power(double base, int exponent) {
    		int n = Math.abs(exponent);
    		if (n == 0)
    			return 1;
    		if (n == 1)
    			return base;
    		//以上两个if判断可省。for循环中判断
    		double result = 
    1.0
    ;
    		for (int i = 0; i < n; i++) {
    			result *= base;
    		}
    		if (exponent < 0) {
    			result = 1 / result;
    		}
    		return result;
    	}
    }
    
    */
    
    

    10、顺时针打印矩阵

     输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

    思路:左神的

    import java.util.ArrayList;
    public class Solution {
    	/**
    	 * 基本思路:
    	 * 1.左上角的坐标和右下角的坐标固定了一圈矩阵,先打印这一圈矩阵。其中,对矩阵只有一行或者一列分别打印。
    	 * 2.打印完了这一圈,左上角坐标都+1 ,右下角的都减一,到更内一圈。
          *比如:4*4的矩阵,(0,0)--(3,3)然后,(1,1)--(2,2)
    	 * 3.当左上角跑到右下角下面就结束了。
         * —---------|
           |         |
           |         |
           |----------
    	 * @param matrix
    	 * @return
    	 */
    	public  ArrayList<Integer> printMatrix(int [][] matrix){
    		ArrayList<Integer> list = new ArrayList<Integer>();
    		int topRow = 0;
    		int topCol = 0;
    		int downRow = matrix.length - 1;
    		int downCol = matrix[0].length - 1;
    		while (topRow <= downRow && topCol <= downCol) { //当满足左上角的小于等于右下角就可以循环
    			printCircle(list, matrix, topRow++, topCol++, downRow--, downCol--);
    		}
    		return list;
    	}
    	
    	public  void printCircle(ArrayList<Integer> list, int [][] matrix, int topRow, int topCol, int downRow, int downCol) {
    		if (topRow == downRow) { //子矩阵只有一行的时候
    			for (int i = topCol; i <= downCol; i++) {//注意循环开始的条件,是从这一列开始,不是从零
    				list.add(matrix[topRow][i]);
    			}
    		}
    		else if (topCol == downCol) {//子矩阵只有一列的时候
    			for (int i = topRow; i <= downRow; i++) {//
    				list.add(matrix[i][topCol]);
    			}
    		}
    		else { //其他的情况下
    			int currentRow = topRow;
    			int currentCol = topCol;
    			while (currentCol != downCol) {//左到右 本行最后一个不访问,在下个循环里面。如图
    				list.add(matrix[topRow][currentCol]);
    			    currentCol++;
    			}
    			while (currentRow != downRow) {//上到下0
    				list.add(matrix[currentRow][downCol]);
    				currentRow++;
    			}
    			while (currentCol != topCol) {//右到左
    				list.add(matrix[downRow][currentCol]);
    				currentCol--;
    			}
    			while (currentRow != topRow) {//下到上
    				list.add(matrix[currentRow][topCol]);
    				currentRow--;
    			}
    		}
    	}
    }

    11、最小的k个数

    题目描述

    输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    import java.util.Arrays;
    public class Solution {
    public  ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
    		ArrayList<Integer> list = new ArrayList<>();
    		if (input == null || k <= 0 || k > input.length) {
    			return list;
    		}
    		int[] kArray = Arrays.copyOfRange(input, 0, k);
            //1.构建大顶堆
            for(int i=kArray.length / 2 - 1;i>=0;i--){
                //从第一个非叶子节点开始,下次第二个,依次调整构建大根堆
                adjustHeap(kArray,i,kArray.length);
            }
            //2.依次来判断,有小于堆顶的那就替换掉继续调整一个堆
    		for (int i = k; i < input.length; i++) {
    			if (input[i] < kArray[0]) {
    				kArray[0] = input[i];
    				adjustHeap(kArray, 0, kArray.length);
    			}
    		}
            //最后把堆里的元素读出来
    		for (int i = kArray.length - 1; i >= 0; i--) {
    			list.add(kArray[i]);
    		}
    
    		return list;
    	}
        public static void adjustHeap(int []arr,int i,int length){ //从i节点开始调整,
            int temp = arr[i];//先取出当前元素i
            for(int k = i*2+1;k<length;k = k*2+1){//从i结点的左子结点开始,也就是2i+1处开始
                if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点,k指向右子结点
                    k++;
                }
                if(arr[k] >temp){//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
                    arr[i] = arr[k];
                    i = k;
                }else{
                    break;
                }
            }
            arr[i] = temp;//将temp值放到最终的位置
        }
        
        
        
        
            /**自己的思路:先鲁棒性判断是否k超了长度或者k为0
         * 基本步骤就是:
         * 1.先把k个数放到list里面,
         * 2.把list排序,从k后面一个开始遍历,如果比list里面最大的值小,就替换掉。重新排序一次。循环执行
         * @param input
         * @param k
         * @return
         */
        /*public  ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        	List<Integer> list = new ArrayList<Integer>();
        	if (k>input.length || k==0) {
        		return (ArrayList)list; 
    		}
            
        	for (int i = 0; i < k; i++) {
    			list.add(input[i]);
    		}
        	for (int i = k; i < input.length; i++) {
        		
        		Collections.sort(list);
    			if(input[i] < list.get(k-1)){
    				list.set(k-1, input[i]);
    			}
    		}
        	return (ArrayList)list;
        }
        //public static void main(String[] args) {
    	//	int [] input = {4,5,1,6,2,7,3,8};
    	//	System.out.println(GetLeastNumbers_Solution(input,4).toString());
    	//}
        //}
        */
    }

    12、丑数

    题目描述

    把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

    public class Solution {
      /**
         * 剑指offer的思路:
         * 取一个数组来放丑数,下一个丑数必定是这个数组里面的数乘以2或者3
         * 或者5,这三种中最小的那一个。依次,判断下去
         * @param index
         * @return
         */
        public int GetUglyNumber_Solution(int index) {
        	if(index <= 0)
        		return 0;
        	int [] res = new int[index];
        	res[0] = 1;//先把1放入
        	int m2 = 0;//控制乘以2的位置,假设得到一个丑数是乘以2得到的,
        	            //那么下一次就是数组中的下一个丑数可能达到。
        	int m3 = 0;
        	int m5 = 0;
        	for (int i = 1; i < index; i++) {
    			int min = Math.min(res[m2]*2, Math.min(res[m3]*3, res[m5]*5));
    			res[i] = min;//最小的那个作为当前的丑数
    			//判断是由谁乘以得到的
    			if(res[m2] *2 == min)//假设res[1]是乘以2得到的丑数,那么下一次就要判断
    				              //是否是res[2]乘以2可能得到丑数,所以就要++
    				m2++;
    			if(res[m3]*3 == min)
    				m3++;
    			if(res[m5]*5 == min)
    				m5++;
    		}
            return res[index - 1];
        }
    }

    七、栈和队列

    • 1、滑动窗口的最大值

    给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。

    思路:左程云的代码和思路,博客的代码其实可以用左的思路来说明。

    	public static ArrayList<Integer> maxInWindows(int[] num, int size) {
    		ArrayList<Integer> maxWindows = new ArrayList<>();
    		if (num == null || size == 0 || num.length == 0 || num.length < size)
    			return maxWindows;
    		Deque<Integer> dq = new LinkedList<>();
    		for (int i = 0; i < size; i++) {
       // 如果已有数字小于待存入的数据,      
    // 如果已有数字小于待存入的数据,      
              // 这些数字已经不可能是滑动窗口的最大值        
    // 这些数字已经不可能是滑动窗口的最大值        
            // 因此它们将会依次地从队尾删除
    			while (!dq.isEmpty() && num[i] > num[dq.getLast()])
    				dq.removeLast();
    			dq.addLast(i);
    		}
    		//System.out.println(dq);
    		for (int i = size; i < num.length; i++) {
    			maxWindows.add(num[dq.getFirst()]);
    			while (!dq.isEmpty() && num[i] >= num[dq.getLast()])
    				dq.removeLast();
     
    			if (!dq.isEmpty() && dq.getFirst() <= i - size)
    				dq.removeFirst();
    			dq.addLast(i);
    			System.out.println(i + "--" + dq);
    		}
    		maxWindows.add(num[dq.getFirst()]);
    		return maxWindows;
    	}
    // 因此它们将会依次地从队尾删除
    			while (!dq.isEmpty() && num[i] > num[dq.getLast()])
    				dq.removeLast();
    			dq.addLast(i);
    		}
    		//System.out.println(dq);
    		for (int i = size; i < num.length; i++) {
    			maxWindows.add(num[dq.getFirst()]);
    			while (!dq.isEmpty() && num[i] >= num[dq.getLast()])
    				dq.removeLast();
     
    			if (!dq.isEmpty() && dq.getFirst() <= i - size)
    				dq.removeFirst();
    			dq.addLast(i);
    			System.out.println(i + "--" + dq);
    		}
    		maxWindows.add(num[dq.getFirst()]);
    		return maxWindows;
    	}

    左程云的代码:

    思路:其实当有新的数来的时候,无论这个数是大于队尾还是小于队尾都要保存。只不过如果新来的大于队尾,说明队尾的数永远不会是大的数了,因为来了更大的,所以直接弹出就好了。如果新来的数小于队尾,说明队中的仍是大值,但是这个大的数值可能会过期,所以新来的小数仍然要保存。如下两个例子

    a. 5 4 3 2 窗口是3,所以[5 4 3] 2第一个是5,如果新数4 和 3 不保存,当第二个窗口的时候,[4 3 2]就把4没有了

    b.5 6 7 2窗口是3,要依次队尾中添加,最后剩7,前面的小,去掉就好了。

    import java.util.ArrayList;
    import java.util.LinkedList;
    
    public class HuadongWindows {
    	public static void main(String[] args) {
    		int num[] = { 2, 3, 4, 2, 6, 2, 5, 1 };
    		System.out.println(maxInWindows(num, 3));
    
    	}
    	//因为函数形式是这样的,其实因为返回的窗口最大值的数组一共就是n-w+1,不需要arraylist
    	public static  ArrayList<Integer> maxInWindows(int [] num, int size){
    		ArrayList<Integer> res = new ArrayList<>();
    		if(num == null || size <=0 || size > num.length)
    			return res;
    		LinkedList<Integer> qmax = new LinkedList<>();//记录窗口
    		for (int i = 0; i < num.length; i++) {
    			//如果新值大于队尾的,之前的那个队尾永远不是最大了,就直接弹出来就好了
    			while(!qmax.isEmpty() && num[qmax.peekLast()]<=num[i])
    				qmax.pollLast();
    			qmax.addLast(i);
    			if(qmax.peekFirst() == i -size)//此时,下标已经过期,说明此时的窗口其实
    				                           //没有包含这个下标了
    				qmax.pollFirst(); 
    			if(i >= size-1)//保证一开始的不存入,假设3 2 1,
    				                        //只有下标大于窗口时候才判断加入此时的对头
    				res.add(num[qmax.peekFirst()]);
    		}
    		return res;
    	}
    }
    • 2、用 两个栈实现队列

    题目描述:用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

    思路:入栈给stack1,出栈时,若stack2不为空,则出栈,若为空,把stack1的内容全都放入stack2,然后再出栈

    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.isEmpty()){
                while(!stack1.isEmpty()){
                    stack2.push(stack1.pop());
                }
             
            }
            return stack2.pop();
        }
    }

     3、包含min函数的栈

    定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。

    思路:

    import java.util.Stack;
    
    public class Solution {
    
        
     /* 
    * 思路:用一个栈stack保存数据,用另外一个栈min保存依次入栈最小的数  
    * 比如,stack中依次入栈,5, 4, 3, 8, 10,11,12,1  
    * 则min依次入栈,5, 4, 3, 3, 3, 3, 3, 1 
    * 每次入栈的时候,如果入栈的元素比min中的栈顶元素小或等于则入栈,否则入stack的栈顶元素。  
    * 保持stack中和min中保持相同个数的元素 ,同时保持min的栈顶是此时原栈的最小值。
    */
        Stack<Integer> stackData = new Stack<>(); //声明时候的异同
    	Stack<Integer> stackMin = new Stack<Integer>();
        public void push(int node) {
            stackData.push(node);
         // 如果min为空或者node比min栈中的元素小,则入min栈  
            if(stackMin.size() == 0 || stackMin.peek() > node)
            	stackMin.push(node);
            else // 否则把min栈中的顶部元素重复入栈
    			stackMin.push(stackMin.peek());
        }
        
        public void pop() {//因为时刻保持两个栈的高度相同,所以两个都pop,时刻保持min的栈顶是原栈的最小值。
            //如果返回应该是返回原栈的。
            if(!stackData.isEmpty()){
            	stackData.pop();
            	stackMin.pop();
            }
        }
        
        public int top() {
            return stackData.peek();
        }
        
        public int min() {
            return stackMin.peek();
        }
    }

    4、栈的压入、弹出序列

    输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

    import java.util.ArrayList;
    import java.util.Stack;
    
    public class Solution {
    	/**借用一个辅助的栈,遍历压栈顺序,先讲第一个放入栈中,这里是1,
        然后判断栈顶元素是不是出栈顺序的第一个元素,这里是4,很显然1≠4,所以我们继续压栈,
        直到相等以后开始出栈,出栈一个元素,则将出栈顺序向后移动一位,直到不相等,
        这样循环等压栈顺序遍历完成,如果辅助栈还不为空,说明弹出序列不是该栈的弹出顺序。
        举例: 
        入栈1,2,3,4,5 
       出栈4,5,3,2,1 
       首先1入辅助栈,此时栈顶1≠4,继续入栈2 
       此时栈顶2≠4,继续入栈3 
       此时栈顶3≠4,继续入栈4 
       此时栈顶4=4,出栈4,弹出序列向后一位,此时为5,,辅助栈里面是1,2,3 
       此时栈顶3≠5,继续入栈5 
       此时栈顶5=5,出栈5,弹出序列向后一位,此时为3,,辅助栈里面是1,2,3 
      …. 
      依次执行,最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。
    	 * @param pushA
    	 * @param popA
    	 * @return
    	 */
    	public boolean IsPopOrder(int[] pushA, int[] popA) {
    		if (pushA == null || popA == null || pushA.length == 0
    				|| popA.length == 0)
    			return false;
    		int index = 0; //作为弹出序列的一个索引
    		Stack<Integer> stack = new Stack<Integer>();
            for (int i = 0; i < pushA.length; i++) {
            	stack.push(pushA[i]); 
                while (!stack.isEmpty() && stack.peek() == popA[index]) {// 当栈不为空且栈顶元
                    //素等于弹出序列元素时候,就弹出一个,同时让弹出序列后移一个
                    stack.pop();
                    index++;
                }
    		}
    		return stack.isEmpty();//如果最后,栈不为空,相当于没有按照给定的弹出popA弹出完毕,
            //就说明不能按照popA,返回false
    	}
    
    }

    八、回溯法

    • 1、矩阵中的路径

    请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始,每一步可以在矩阵中向左,向右,向上,向下移动一个格子。如果一条路径经过了矩阵中的某一个格子,则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径,但是矩阵中不包含"abcb"路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入该格子。

    思路:回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。首先,在矩阵中任选一个格子作为路径的二七店。假设矩阵中某个格子的字符为ch并且这个格子将对应于路径上的第i个字符。如果路径上的第i个字符不是ch,那么这个格子不可能处在路径上的第i个位置。如果路径上的第i个字符正好是ch,那么朝相邻的格子寻找路径上的第i+1个字符。除在边界上的格子之外,其他格子都有4个相邻的格子。重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。

    由于回溯法的递归特性,路径可以看成一个栈。当矩阵中定位了路径中的前n个字符的位置之后,在与第n个字符对应的格子的周围都没有找到第n+1个字,需要在路径上会退到第n-1个字符,重新定位第n个字符。由于路径不能重复进入矩阵的格子,还需要定义和矩阵大小一样的布尔值矩阵,用来标识路径是否已经进入了每个格子。

    public class Solution {
        /**
         * 判断字符矩阵是否包含某一个字符序列
         * @param matrix    
         * @param rows  矩阵行数
         * @param cols  矩阵列数
         * @param str   目标字符序列
         * @return
         */
        public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
            boolean visitFlags[] = new boolean[matrix.length];
            for (int row = 0; row < rows; row++) {
                for (int col = 0; col < cols; col++) {
                    if (hasPathCore(matrix, rows, cols, row, col, str, 0, visitFlags))
                        return true;
                }
            }
    
            return false;
        }
    
        /**
         * 回溯法递归实现判断
         * @param matrix    字符矩阵
         * @param rows  矩阵行数
         * @param cols  矩阵列数
         * @param row   当前行索引
         * @param col   当前列索引
         * @param str   目标字符序列
         * @param k 目标字符序列中当前字符索引
         * @param visitFlags    字符矩阵是否被访问过标记
         * @return
         */
        boolean hasPathCore(char[] matrix, int rows, int cols, int row, int col, char[] str,  int k, boolean[] visitFlags) {
            int index = row * cols + col;
            // 行列索引超限、当前字符已经被访问过、当前字符不等于目标字符序列的当前字符,直接返回false
            if (row < 0 || col < 0 || row >= rows || col >= cols || 
                    visitFlags[index] || matrix[index] != str[k])
                return false;
    
            visitFlags[index] = true;   // 设置访问标记
            if (k == str.length - 1)    // 递归结束条件,k已经到达目标字符序列的最后一个字符
                return true;
    
            k++;    // 匹配目标字符序列的下一个字符
    
            // 在当前字符的上、下、左、右的元素搜索下一个目标字符,递归
            if (hasPathCore(matrix, rows, cols, row + 1, col, str, k, visitFlags) || 
                    hasPathCore(matrix, rows, cols, row - 1, col, str, k, visitFlags) || 
                    hasPathCore(matrix, rows, cols, row, col + 1, str, k, visitFlags) || 
                    hasPathCore(matrix, rows, cols, row, col - 1, str, k, visitFlags))
                return true;
    
            // // 在当前字符的上、下、左、右的元素没有搜索到下一个目标字符,将访问标记重置为false,返回false;
            visitFlags[index] = false;
            return false;
        }
    }
    • 2、机器人运动范围

    地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?

    思路:利用递归实现,每次只能走上下左右四个点,进行判断点的位置是否越界,点数之和是否大于K,是否已经走过了。

    public int movingCount(int threshold, int rows, int cols) {
        int flag[][] = new int[rows][cols]; //记录是否已经走过
        return helper(0, 0, rows, cols, flag, threshold);
    }
    
    private int helper(int i, int j, int rows, int cols, int[][] flag, int threshold) {
        if (i < 0 || i >= rows || j < 0 || j >= cols ||
                numSum(i) + numSum(j) > threshold || flag[i][j] == 1)
            return 0;
        flag[i][j] = 1;
        return helper(i - 1, j, rows, cols, flag, threshold)
                + helper(i + 1, j, rows, cols, flag, threshold)
                + helper(i, j - 1, rows, cols, flag, threshold)
                + helper(i, j + 1, rows, cols, flag, threshold) + 1;
    }
    
    private int numSum(int i) {
        int sum = 0;
        while (i > 0) {
            sum += i % 10;
            i = i / 10;
        }
        return sum;
    }

    九、链表

    • 1、从尾到头打印链表

    输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。

    也可以用栈:

    public class Solution {
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            if(listNode == null){
                ArrayList list = new ArrayList();
                return list;
            }
            Stack<Integer> stk = new Stack<Integer>();
            while(listNode != null){
                stk.push(listNode.val);
                listNode = listNode.next;
            }
            ArrayList<Integer> arr = new ArrayList<Integer>();
            while(!stk.isEmpty()){
                arr.add(stk.pop());
            }
            return arr;
        }
    }
    /**
    *    public class ListNode {
    *        int val;
    *        ListNode next = null;
    *
    *        ListNode(int val) {
    *            this.val = val;
    *        }
    *    }
    *
    */
    import java.util.ArrayList;
    import java.util.Collections;
    public class Solution {
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> addressArrayList = new ArrayList<Integer>();
            if(listNode == null){
            ArrayList first = new ArrayList();
                return first;
            }
            while (listNode != null) {
                addressArrayList.add(listNode.val);
              listNode = listNode.next;
     
           }
    
            Collections.reverse(addressArrayList); 
             return addressArrayList;
          }
        }
    

    2、链表中倒数第k个结点

    输入一个链表,输出该链表中倒数第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) {
        	//一种思路是先遍历一遍求长度,然后输出倒数k个
        	//正常的思路是,设置两个游标,让快的领先k个
        	ListNode slow = head;
        	ListNode fast = head;
            if (head == null || k <= 0) {
                return null;
            }
        	for (int i = 1; i < k; i++) { //快的先走k-1步,倒数第三个,其实应该快的指到第三个,只需要走两步即可。
    			if(fast.next == null) //这个是k与链表长度的关系,如果,链表长度小于k,肯定在走到k之前就出现
                    //null,直接返回null即可
    				return null;
    			else 
    			   fast = fast.next;
    		}
        	while(fast.next != null){ //快的从第k个,慢的从第1个,同时开始走。
        		slow = slow.next;
        		fast = fast.next;
        	}
        	return slow;
        }
    }

     3、反转链表

    输入一个链表,反转链表后,输出新链表的表头。

    /*
    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) 
    			return null;
    		ListNode pre = null;
    		ListNode next = null;
    		while(head != null){ //注意这个地方的写法,如果写head.next将会丢失最后一个节点
    			next = head.next;
    			head.next = pre;
    			pre = head;
    			head = next;
    		}
    		return pre;
    
        }
    }
    /*
     //反转链表
    	public ListNode ReverseList1(ListNode head) {
    		if (head == null) 
    			return null; // head为当前节点,如果当前节点为空的话,那就什么也不做,直接返回null; 
    		ListNode pre = null;
    		ListNode next = null;
    		// 当前节点是head,pre为当前节点的前一节点,next为当前节点的下一节点  
            // 需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2  
            // 即pre让节点可以反转所指方向,但反转之后如果不用next节点保存next1节点的话,此单链表就此断开了  
            // 所以需要用到pre和next两个节点  
            // 1->2->3->4->5  
            // 1<-2<-3->4->5  
    		while(head != null){ //注意这个地方的写法,如果写head.next将会丢失最后一个节点
    			// 做循环,如果当前节点不为空的话,始终执行此循环,此循环的目的就是让当前节点从指向next到指向pre   
                // 如此就可以做到反转链表的效果  
                // 先用next保存head的下一个节点的信息,保证单链表不会因为失去head节点的原next节点而就此断裂
    			next = head.next; //先让head.next指向的节点,即第二个节点叫next
    			head.next = pre; //将head.next指向pre,也就是说断开head节点与后面的连接
    			pre = head;//pre,head依次向后移动一个节点,进行下一次反转
    			head = next;
    		}
    		// 如果head为null的时候,pre就为最后一个节点了,但是链表已经反转完毕,pre就是反转后链表的第一个节点 
    		return pre;
    	}
    	//合并两个递增的链表并且保证最终的链表也是单调不减的。
    */

    4、合并两个排序的链表

    题目描述

    输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

     思路:输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
        比较两个链表的首结点,哪个小的的结点则合并到第三个链表尾结点,并向前移动一个结点。
        步骤一结果会有一个链表先遍历结束,或者没有
        第三个链表尾结点指向剩余未遍历结束的链表
        返回第三个链表首结点 

    /*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        public ListNode Merge(ListNode list1,ListNode list2) {
            	    if (list1 == null) {
    			return list2;
    		}
    	    if (list2 == null) {
    			return list1;
    		}
    	    //新建一个用于存放融合之后的链表
    	    //因为,融合的过程中链表是一直移动的,所以要把链表的头保存下来,才能返回正确的一条链
    	    ListNode res = new ListNode(0);  //此处或者res = null,这样就不是res.next 而是res
    	    ListNode merlistNode = res;
    	    while (list1 != null && list2 != null) { //依次比较,将较小的节点连到融合节点上
    			if(list1.val < list2.val){   
    				merlistNode.next = list1;      //连上小的list1
    			    list1 = list1.next;         //list1 可以往后移动一个,下次用移动后的和list2比较
    			    merlistNode = merlistNode.next;// merlistNode也往后移动一个
    			}
    			
    			else {
    				merlistNode.next = list2;
    			    list2 = list2.next;
    			    merlistNode = merlistNode.next;
    			}
    			
    		}
    	    //把未结束的链表连接到合并后的链表尾部 
    	    if(list1 != null)
    	    	merlistNode.next = list1;
    	    if(list2 != null)
    	    	merlistNode.next = list2;
    	    return res.next;
        }
        //递归的方式
         /*public ListNode Merge(ListNode list1,ListNode list2) {  
                if (list1 == null) {  
                    return list2;  
                }  
                if (list2 == null) {  
                    return list1;  
                }  
                ListNode newHead = null;  
                if (list1.val <= list2.val) {  
                    newHead = list1;  
                    newHead.next = Merge(list1.next,list2);  
                }else {  
                    newHead = list2;  
                    newHead.next = Merge(list1,list2.next);  
                }  
      
                return newHead;  
            }  */
    }

    5、复杂链表的复制

    题目描述

    输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

    /*
    public class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;
    
        RandomListNode(int label) {
            this.label = label;
        }
    }
    */
    import java.util.HashMap;
    public class Solution {
     /**左程云思路:除了这个还有不用链表的思路。
         * 算法步骤:遍历两遍链表,第一遍将仅仅将数赋值给map中的值,第二遍将指针指向赋值。注意保存头指针的位置。
         * 1.第一遍遍历,key是第一个链表中的节点,value是复制后的链表节点,但是指针都指向null。
         * 2.第二遍遍历,将相对应的next和random均复制。
         * @param pHead
         * @return
         */
        public RandomListNode Clone(RandomListNode pHead)
        {
            HashMap<RandomListNode, RandomListNode> map =new HashMap<RandomListNode, RandomListNode>();
            RandomListNode current = pHead; //保存头结点
            while (current != null) {//第一遍遍历
    			map.put(current,new RandomListNode(current.label));// hashmap里面,key放的是之前的链表节点,value现在只放值
    			current = current.next;
    		}
            current = pHead;
            while (current != null) {//第二遍遍历
            	//现在map中是1--1'  2--2'。为了让1'指向2'  要给1'的next赋值, 要找1'就得get(1)。值是2',要找2'就是get(1.next)
    			map.get(current).next = map.get(current.next); 
    			map.get(current).random = map.get(current.random);
    			current = current.next;
    		}
            return map.get(pHead);
        }
    }

    6、两个链表的第一个公共结点

    题目描述

    输入两个链表,找出它们的第一个公共结点

    /*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
    	
        /**采用了左程云的代码思想:
         * 首先,如果相交,那么尾节点一定是一样的。
         * 接下来,谁长谁就先走一定的步数,然后一起走,肯定是同时到达相交的点。
         * @param pHead1
         * @param pHead2
         * @return
         */
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        	 if (pHead1 == null || pHead2 == null)
        		 return null;
        	 ListNode  cur1 = pHead1;
        	 ListNode  cur2 = pHead2;
        	 int n = 0;
        	 while(cur1.next != null) {
        		 n++; //记录长度
        		 cur1 = cur1.next;
        	 }
        	 while(cur2.next != null) {
        		 n--;
        		 cur2 = cur2.next;
        	 }
        	 if(cur1 != cur2)
        		 return null;
        	 cur1 = n > 0 ? pHead1:pHead2;// n大于0  说明cur1要先走一部分。
        	 cur2 = cur1 == pHead1 ?pHead2:pHead1;//cur2 等于另一个
        	 n= Math.abs(n);
        	 while(n !=0 ) {
        		 n--;    //先cur1走完这部分
        		 cur1 = cur1.next;
        	 }
        	 while(cur1 != cur2) {
        		 cur1 = cur1.next;
        		 cur2 = cur2.next;
        	 }
        	return cur1;	 
        }
    }

    7、链表中环的入口节点

    给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

    思路:

    1.   第一步,找环中相汇点。分别用p1,p2指向链表头部, 
    2.  * p1每次走一步,p2每次走二步,直到p1==p2找到在环中的相汇点。 

    通过141题,我们知道可以通过快慢指针来判断是否有环,现在我们假设两个指针相遇在z点,如图

    那么我们可以知道fast指针走过a+b+c+b

    slow指针走过a+b

    那么2*(a+b) = a+b+c+b

    所以a = c

    那么此时让slow回到起点,fast依然停在z,两个同时开始走,一次走一步

    那么它们最终会相遇在y点,正是环的起始点

    /*
     public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
    	/**
    	 * 主要思路就是一快 一慢两个指针,如果有环,最终快的肯定能追上慢的,
    	 * 找环的入口的思路见博客。
    	 * @param pHead
    	 * @return
    	 */
        public ListNode EntryNodeOfLoop(ListNode pHead)
        {
            if (pHead == null || pHead.next == null) {
    			return null;
    		}
            ListNode fast = pHead;
            ListNode slow = pHead;
            while(fast != null && fast.next != null) {//因为fast每次要走两步,所有需要判断fast的下一个是否为空  
            	slow = slow.next;
            	fast = fast.next.next;//一个走一步 一个走两步
            	if(slow == fast) {
            		fast = pHead;
            		while(slow != fast) {
            			slow = slow.next;
            			fast = fast.next;
            		}
            		return slow;
            	}
            }
            return null;
        }
    }

    8、删除链表中重复的节点

    题目描述

    在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5

    重点是第一个也可能是重复的点,因此新建一个preNode节点保存前一个节点

    /*
     public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
         /**
         * 主要参考博客的解题思路
         * @param pHead
         * @return
         */
        public ListNode deleteDuplication(ListNode pHead)
        {
                if(pHead == null)
                	return null;
                // 新建一个节点,防止头结点被删除
                ListNode firstNode = new ListNode(-1);
                firstNode.next = pHead;
                ListNode p = pHead;
                // 指向前一个节点
                ListNode preNode = firstNode;
                while (p!=null &&p.next !=null) {//注意条件的顺序,否则不对 因为如果p为null,p.next肯定异常
    				if(p.val == p.next.val) {
    					int val = p.val;
    					 // 向后重复查找
    					while (p != null&&p.val == val) {
    						p = p.next;
    					}
    					// 上个非重复值指向下一个非重复值:即删除重复值
    					preNode.next = p;
    				}
    				else {
    					 // 如果当前节点和下一个节点值不等,则向后移动一位
    					preNode = p;
    					p = p.next;
    				}
    			}
                return firstNode.next;
                
        }
    }

    9、链表回文结构--左神

    十、非剑指offer

    • 1、 左神的

    给定一个字符串str,str表示一个公式,公式里可能有整数,加减乘除符号和左右括号,返回公式计算的结果。例如,str = 48×((70-65)-43)+8×1。返回-1816。

    【说明】

    1. 可以认定给定的字符串一定是正确的公式,不需要对str做公式有效性检查。

    2. 如果是负数就需要有括号括起来,比如4*(-3)。但如果负数作为公式的开头或者括号部分的开头,则可以没有括号,比如-3*4和(-3*4)都是合法的。

    3. 不需要考虑溢出问题
    import java.util.LinkedList;
    
    /**
     * 算法顺序大致如下:
     * 没有括号的时候: 1、执行value,碰到加减乘除,则执行addNum将其中原有的乘除法运算完,把结果放到队列中,跳出此方法。然后把符号放进去。
     *                     保证其中没有加减乘除导致无法知道优先级。
     *                  2、全部遍历完毕,则执行addNum把乘除法计算完毕,然后把最后一个数字放入。
     *                  3、执行getNum 计算队列中的加减法,没有优先级问题,可以直接进行运算即可。
     * 有括号的情况下:1、执行value,按上述第一步执行,碰到括号,则进入递归,去按上述所有的步骤计算括号里面的。
     *                  2、剩下的按照上边的算法继续计算。
     * Created by shixi_shengzhi on 2018/9/9
     */
    public class Main {
    
    
        public static int getValue(String str) {
            return value(str.toCharArray(), 0)[0];
        }
    
        public static int[] value(char[] str, int i) {
            LinkedList<String> que = new LinkedList<String>();
            int pre = 0;
            int[] bra = null;
            while (i < str.length && str[i] != ')') {
                if (str[i] >= '0' && str[i] <= '9') {
                    pre = pre * 10 + str[i++] - '0';
                } else if (str[i] != '(') { //+ - * / ,每当碰到运算符号就先把里面的乘除法运算完,保证队列里面都是加减法
                    addNum(que, pre);// 计算完乘除法,将结果放到队列中 没有运算把之前的数放入
                    que.addLast(String.valueOf(str[i++]));
                    pre = 0;
                } else { // 碰到符号(
                    bra = value(str, i + 1); //重新递归上述过程。返回括号中的结果以及位置
                    pre = bra[0];
                    i = bra[1] + 1;
                }
            }
            //公式执行完或者碰到 )
            addNum(que, pre); //计算乘除法
            return new int[]{getNum(que), i}; //计算公式中还保留的加减法
        }
    
        /**
         * 计算乘除法,把乘除法的结果还有加减号在放在队列中。
         *
         * @param que
         * @param num
         */
        public static void addNum(LinkedList<String> que, int num) {
            if (!que.isEmpty()) {
                int cur = 0;
                String top = que.pollLast();
                if (top.equals("+") || top.equals("-")) {
                    que.addLast(top);
                } else {
                    cur = Integer.valueOf(que.pollLast());
                    num = top.equals("*") ? (cur * num) : (cur / num);
                }
            }
            que.addLast(String.valueOf(num));
        }
    
        /**
         * 计算队列中的加减法
         *
         * @param que
         * @return
         */
        public static int getNum(LinkedList<String> que) {
            int res = 0;
            boolean add = true;
            String cur = null;
            int num = 0;
            while (!que.isEmpty()) {
                cur = que.pollFirst();
                if (cur.equals("+")) {
                    add = true;
                } else if (cur.equals("-")) {
                    add = false;
                } else {
                    num = Integer.valueOf(cur);
                    res += add ? num : (-num);
                }
            }
            return res;
        }
    
        public static void main(String[] args) {
            String exp = "48*((70-65)-43)+8*1";
            exp = "3+5*6";
            exp = "3+4*5+6";
            System.out.println(getValue(exp));
    //        System.out.println(getValue(exp));
    //
    //        exp = "4*(6+78)+53-9/2+45*8";
    //        System.out.println(getValue(exp));
    //
    //        exp = "10-5*3";
    //        System.out.println(getValue(exp));
    //
    //        exp = "-3*4";
    //        System.out.println(getValue(exp));
    //
    //        exp = "3+1*4";
    //        System.out.println(getValue(exp));
    
        }
    
    
    }
    

    展开全文
  • offer题目及答案

    万次阅读 多人点赞 2017-04-06 19:07:25
    offer最近在牛客网上刷剑offer的题目,现将题目和答案总结如下
  • 静脉识别技术

    千次阅读 多人点赞 2017-08-11 16:29:29
    静脉识别是静脉识别的一种,首先通过静脉识别仪取得个人手指静脉分布图,从手指静脉分布图依据专用比对算法提取特征值,通过近红外光线照射,利用CCD摄像头获取手指静脉的图像,将手指静脉的数字图像存贮在...
  • JAVA剑OFFER个人总结

    万次阅读 2020-07-04 10:04:04
    股票的最大利润 剑Offer 64 面试题65. 不用加减乘除做加法 面试题66. 构建乘积数组 面试题67. 把字符串转换成整数 面试题68 - I. 二叉搜索树的最近公共祖先 面试题68 - II. 二叉树的最近公共祖先 面试题03. 数组...
  • 3.2 ls命令:显示当前目录下的文件   ls 是最常见的目录操作命令,主要作用是显示目录下的内容。这个命令的基本信息如下: 命令名称:ls。 英文原意:list。 所在路径:/bin/ls。 执行权限:所有用户。 功能...
  • Offer——咪咕笔试题+知识点总结情景回顾 时间:2016.10.09 15:00-16:30 地点:山东省网络环境智能计算技术重点实验室 事件:咪咕笔试 ![这里写图片描述](http://img.blog.csdn.net/20161010141449988) 知识点...
  • C++如何获取当前路径下所有文件的文件名 今天我遇到了这样一个任务:要求编写一个程序,统计和这个程序在同一目录下(及其子目录)所有文件的单词数。...1. 如何获取当前程序所在文件夹的路径 2....
  • 声明:本文转至Big大鸟的博客下,转载的名为《什么叫大数据 大数据的概念》一文,链接地址http://blog.csdn.net/qq_36738482/article/details/728235091、大数据定义 对于“大数据”(Big data)研究机构Gartner给...
  • Offer——知识点储备--Linux基本命令+Makefile

    万次阅读 多人点赞 2016-11-08 20:01:27
    Offer——知识点储备–Linux基本命令1.linux下查看进程占用cpu的情况(top);格式 top [-] [d delay] [q] [c] [S] [s] [i] [n] 主要参数 d:指定更新的间隔,以秒计算。 q:没有任何延迟的更新。如果使用者有...
  • Offer--排序算法小结

    万次阅读 多人点赞 2016-07-29 08:31:47
    Offer来了(Java版)——排序算法小结前言 毕业季转眼即到,工作成为毕业季的头等大事,必须得认认真真...这样的学习方法百害而无一益,只因自己缺少了思索,未能真正理解到算法的核心精髓所在。下面系统的对快速排序、堆
  • 什么是汇编语言

    万次阅读 多人点赞 2018-11-19 21:21:37
    汇编语言(assembly language)是一种用于电子计算机、微处理器、微控制器或其他可编程器件的低级语言,亦称为符号语言。在汇编语言中,用助记符(Mnemonics)代替机器...普遍说,特定的汇编语言和特定的机器语言...
  • 一、C#获取当前路径的方法:1. System.Diagnostics.Process.GetCurrentProcess().MainModule.FileName-获取模块的完整路径。2. System.Environment.CurrentDirectory-获取和设置当前目录(该进程从中启动的目录)的...
  • 什么是缓冲区溢出?有什么危害?原因是什么?

    万次阅读 多人点赞 2018-09-22 09:03:48
    缓冲区溢出是当计算机向缓冲区填充数据时超出了缓冲区本身的容量,溢出的数据覆盖在合法数据上。    危害有以下两点:  1、程序崩溃,导致拒绝服务  2、跳转并且执行一段恶意代码  原因:造成缓冲区溢出...
  • 基站定位也就是"LBS定位",全称是Location Based Service,它包括两层含义:首先是确定移动设备或用户所在的地理位置;其次是提供与位置相关的各类信息服务。意与定位相关的各类服务系统,简称"定位服务"。 另外...
  • 有序数组的平方 贪心 贪心算法(又称贪婪算法)是,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。 贪心算法不是对所有问题都能...
  • 可能是全网最好的MySQL重要知识点/面试题总结

    万次阅读 多人点赞 2019-06-29 20:20:34
    文章目录什么是MySQL?事务相关什么是事务?事物的四大特性(ACID)介绍一下?并发事务带来哪些问题?事务隔离级别有哪些?MySQL的默认隔离级别是?索引相关为什么索引能提高查询速度什么是最左前缀原则?注意避免冗余索引...
  • 然而有时候这个地址簿也经常给你错路,明明距离你 500 米就有个吃饭的地方,非要把你推荐到 5 公里外。为什么会出现这样的情况呢? 还记得吗?当我们发出请求解析 DNS 的时候,首先,会先连接到运营商本地的 DNS ...
  • 当前目录下查找包含 hello 字符串的 后缀名为 .c 的文件: find . -name "*.c" | xargs grep -H "hello" 附:(转) 1. Grep简介 Grep (global search regular expression(RE) and print out the line,全面...
  • 什么是CAS机制?

    万次阅读 多人点赞 2018-03-12 18:28:16
    我们现在来说什么是ABA问题。假设内存中有一个值为A的变量,存储在地址V中。 此时有三个线程想使用CAS的方式更新这个变量的值,每个线程的执行时间有略微偏差。线程1和线程2已经获取当前值,线程3还未获取当前...
  • 在Java中,所有对象都能够被作为"监视器monitor"——一个拥有一个独占锁,一个入口队列和一个等待队列的实体entity。所有对象的非同步方法都能够在任意时刻被任意线程调用,此时不需要考虑加锁的问题。而对于对象...
  • 什么是SoC?什么是IP核?它们有什么关系?

    万次阅读 多人点赞 2017-12-19 20:23:12
     可综合的Delta-Sigma DAC(术语Delta-Sigma分别算术差与和,即Δ-∑DAC),是Xilinx公司提供的免费IP核,可从网上下载得到。  Delta-Sigma DAC使用数字技术,因而它不受温度的影响,并且能在一片可编程...
  • 什么是数据中台?全面解读数据中台

    千次阅读 多人点赞 2019-06-04 16:49:54
    “中台”早期是由美军的作战体系演化而来的,技术上说的“中台”主要是学习这种高效、灵活和强大的指挥作战体系。阿里在今年发布“双中台+ET”数字化转型方法论,“双中台”的是数字中台和业务中台。 数据...
  • 数据及大数据的本质到底是什么

    千次阅读 2019-02-22 17:43:23
    最近几年,数据问题进入哲学视野。对于哲学家们探索的数据本质特征,我们可以从以下几个方面来把握。 数据与大数据 技术进步,主要是计算机、网络和各种类型的传感器以及云...大数据的是所涉及的数据量规模...
  • 当前,国内新型冠状病毒肺炎的防控工作进入关键时期。随着各地陆续有企业开始复工复业,人员流动也开始有所增加。如何对人员流动加以管控,如何准确识别潜在的传染风险,成为摆在各地防控部门面前的难...
  • 转载请标明出处: ...本文出自:【奥特曼超人的博客】 ...到底要不要留在当前城市? 高考后选择专业事关重大,这里用某某某的xxx数据来源做个python二维分析: 数据来源先不公开,先提取几个重点: 2018届 毕业...
  • kafka中的ISR、AR又代表什么?ISR伸缩又是什么

    万次阅读 多人点赞 2019-06-21 14:09:24
    什么是LSO? ​ LSO特指LastStableOffset。它具体与kafka的事物有关。 ​ 消费端参数——isolation.level,这个参数用来配置消费者事务的隔离级别。字符串类型,“read_uncommitted”和“read_committed...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 197,139
精华内容 78,855
关键字:

当前所在地指的是什么