算法的世界

NOTE:

请分别使用C/C++以及Java语言完成文中编码内容,即每个题目给出两种语言的实现。每个主题是一篇文章,里面含有4个算法题,欢迎认领。

另外,该系列文章的主要目的是带大家熟悉面试中常见算法题目的解题思路,所以对于Java版本,除去基本的Java API例如String.length(),List.size()等,请尽量不要使用Java中为我们封装好的API,例如String.split(), String.replace(), Collections.sort()等。

试想一下面试的时候遇到要求写一个排序算法,如果我们给出的答案是Collections.sort(),那不就等于把天聊死了么。。。 一些题目有多种解法,其中时间和空间复杂度可能不尽相同,如果方便请给出两种对比解法并比较其时间和空间效率

  • 字符串,数组,List
    1. 给定一个英文句子,每个单词之间都是由一个或多个空格隔开,请翻转句子中的单词顺序(包括空格的顺序),但单词内字符的顺序保持不变。例如输入”www google com “,则应输出” com google www”。 1.1. 接上题,面试官会继续提问,我们得到的” com google www”需要被用作一个URL的参数,所以这里需要的处理是去掉开头结尾的无效空格,并将两个单词中间的每一个空格都替换为”%20″。例如” com google www”应被转换为”com%20%20google%20www”,请给出转换函数。
    2. 给定一个整数数组,请实现一个函数来调整数组中数字的顺序,使得所有奇数都位于偶数之前。 2.1. 接上题,面试官会继续要求改造此函数使其能够保证原先输入数组的奇数内部顺序以及偶数内部顺序,即如果输入为{2,1,3,6,4,7,8,5},则输出应为{1,3,7,5,2,6,4,8},奇数之间的相互顺序和偶数之间的相互顺序不得被改变。
    3. 请利用数组实现一个简易版的List,需要实现poll和push两个接口,前者为移除并获得队头元素,后者为向队尾添加一个元素,并要求能够自动扩容(扩容逻辑可参考ArrayList)。
    4. 一个整数数组中有一个数字出现的次数超过了数组长度的一半,请找出这个数字。如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2},由于2出现了5次,超过了数组长度的一半,因此应输出2。 4.1. 这个题目有很多变种,其中一个引申为输入的是一个对象数组,该对象无法比较大小,只能利用equals()方法比较是否相等,此时该如何解(若要用到O(n)的辅助空间,能否避免?)。
  • 链表
    1. 给定一个单向链表的头结点对像,请写出一个函数,反转该链表并输出反转后链表的头结点。链表节点定义如下:class Node { int value; Node next; }
    2. 给定一个单向链表,求链表的中间节点,若节点总数为奇数,则返回中间节点,若为偶数,则返回中间两个节点中的任意一个。(可否一次遍历解决问题)2.1. 接上题,用类似的方法可否判断一个单向链表中是否含有环,同样要求在一次遍历中完成。class Node { int value; Node next; }
    3. 给定两个单向链表,请找出它们的第一个公共节点,节点定义如下:class Node { int value; Node next; }
    4. 给定一个单向链表,其节点的value为整数,请根据value的大小对链表进行升幂排序,并给出实现的时间和空间复杂度,链表节点如下:class Node { int value; Node next; }4.1. 能否在时间复杂度O(nlogn)的情况下完成排序?
    1. 给定一个二叉树,请写一个函数输出该二叉树的镜像(最简单的镜像,就是根节点不变,其左右孩子互换位置),要求不得使用递归。二叉树的节点定义如下:class TreeNode { int value; TreeNode left; TreeNode right; }
    2. 给定一个二叉树的根节点,请按行从上到下Z字形(即如果第n行是从左至右打印的,则从右至左打印第n+1行)打印出该二叉树所有节点的值。二叉树节点如下:class TreeNode { int value; TreeNode left; TreeNode right; }
    3. 给定一个二叉树的根节点,请写一个函数判断该二叉树是否是平衡二叉树(平衡二叉树的定义是一颗二叉树,其任意节点的左右子树的深度相差不超过1)。二叉树节点定义如下:class TreeNode { int value; TreeNode left; TreeNode right; }
    4. 输入一个整数数组,请写一个函数判断该数组是否是一棵二叉查找树的后序遍历序列。该二叉查找树的节点值为整数,定义如下:class TreeNode { int value; TreeNode left; TreeNode right; }
  • 栈和队列,位运算
    1. 请用两个栈实现一个队列,实现队头出队,队尾入队的功能。1.1. 请用两个队列实现一个栈,实现其入栈出栈的功能。
    2. 输入两个整数数组,第一个表示一个栈的压入序列,请写一个函数,判断第二个数组是否为该栈的出栈序列,假设数组中的所有数字均不相等。
    3. 给定一个整数,请写一个函数判断该整数的奇偶性。3.1. 接上题,同样给定一个整数,请写一个函数判断该整数是不是2的整数次幂。3.2. 再继续,给定一个整数,请写一个函数判断该整数的二进制表示中1的个数。
    4. 给定一个整数数组,已知该数组中只有一个数字只出现了一次,其余数字都出现了两次,请写一个函数找出这个只出现一次的数字,要求时间复杂度O(n),空间复杂度O(1)。4.1. 接上题,同样的要求,如果该数组中有两个数字只出现一次,请找出这两个数字。
  • 查找,排序
    1. 给定一个二维整数数组,该二维数组每一行都是从左到右升幂排序,且每一列都是从上至下升幂排序。输入一个整数,请写一个函数判断该整数是否位于给定的二维数组中。
    2. 把一个整数数组最开始的若干个元素搬到数组末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,请输出该旋转数组的最小元素。例如{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,其最小值为1。
    3. 输入n个整数,找出其中最小的k个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4.3.1. 上述题目,面试官会要求不得修改输入数组,此时该如何解答?
    4. 在数组中的两个数字,如果前面的大于后面的,则这两个数字组成一个逆序对。输入一个整数数组,求出该数组中逆序对的总数。要求考虑时间复杂度的优化。

“算法的世界”的2个回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注