大公司面试经典数据结构与算法题C#/Java解答

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

几个大公司（IBM、MicroSoft and so on）面试经典数据结构与算法题C#解答

1.链表反转

我想到了两种比较简单的方法

第一种是需要开一个新的链表，将原链表的元素从后到前的插入到新链表中（也就是原链表第一个元素被插入成新链表的最后一个元素）。

第二种是不需要开新的链表，而是逐步反转原链表中元素的指向，例如：

原链表是 1->2->3->4->null 被逐步修改为 ①2->1->null、3->4->null ②3->2->1->null、4->null ③4->3->2->1->null

最后再将head指向4。

namespace 链表反转
{
class Node
{
public int Num { get; set; }
public Node Next { get; set; }
}
class Program
{
static void Main(string[] args)
{
NodeList list = new NodeList();
list.Add();
list.Add();
list.Add();
list.Add();
list.Add();
list.Reverse1();
list.Print(); NodeList list1 = list.Reverse();
list1.Print(); Console.ReadKey();
}
} class NodeList
{
public Node Head { get; set; }
public void Add(int num)
{
if (Head == null)
{
Head = new Node();
Head.Next = new Node() { Num = num };
}
else
{
Node tn = Head;
while (tn.Next != null)
{
tn = tn.Next;
}
tn.Next = new Node() { Num = num };
}
} public void Print()
{
Node tn = Head;
while(tn.Next!=null)
{
tn = tn.Next;
Console.WriteLine(tn.Num);
}
} //需要开新链表的反转
public NodeList Reverse()
{
NodeList list = new NodeList();
Node tn = Head;
Node newTn = null;
while (tn.Next != null)
{
tn = tn.Next;
if (newTn == null)
{
newTn = new Node() { Num = tn.Num };
}
else
{
newTn = new Node() { Num = tn.Num,Next=newTn };
}
}
list.Head = new Node();
list.Head.Next = newTn;
return list;
} //不需要开新链表的反转
public void Reverse1()
{
Node n1 = Head.Next;
Node n2 = Head.Next.Next;
//第一个节点也就是反转后的最后一个节点，Next要指向null
Node first = Head.Next;
first.Next = null;
//如果链表为空或者链表只有一个元素那就无需调整
if (n2 == null || n1 ==null)
{
return;
}
//先用Head指向n2的下一个元素，再将n2的Next指向n1，最后将n1和n2向右移动
while (n2.Next != null)
{
Head.Next = n2.Next;
n2.Next = n1;
n1 = n2;
n2 = Head.Next;
}
//最后要将头结点指向链表反转前的最后一个元素
Head.Next = n2;
//因为判断条件只调整到最后一个元素的前一个元素，所以要调整最后一个元素的Next指向
n2.Next = n1;
}
}

2.字符串查找第一个不重复的字母

基本原理：第一遍遍历字符串时，用hash表存储每个字符出现的次数，第二遍遍历字符串时，筛选出第一个hash中对应保存的出现次数为1的字符。

namespace 字符串查找第一个不重复的字母
{
class Program
{
static Hashtable hash = new Hashtable();
static void Main(string[] args)
{
string s = "asfgasjfoiwoeqkwzxc";
Count(s);
Console.WriteLine(Search(s));
Console.ReadKey();
} static void Count(string s)
{
for (int i = ; i < s.Length; i++)
{
if (hash.Contains(s[i]))
{
hash[s[i]] = (int)hash[s[i]]+;
}
else
{
hash[s[i]] = ;
}
}
} static char Search(string s)
{
for (int i = ; i < s.Length; i++)
{
if ((int)hash[s[i]] == )
{
return s[i];
}
}
return '#';
}
}
}

3.有一个已经排序的数组（升序），数组中可能有正数、负数或0，求数组中元素的绝对值最小的数，要求，不能用顺序比较的方法（复杂度需要小于O（n）），可以使用任何语言实现

基本原理：找到正负数分界点0，如果存在就是0，不存在就比较它左右两个数的绝对值。

（PS:为了方便我写到一个JUnit方法中）

public class testAlgorithm {
@Test
public void Fun(){
int[] a = {-8,-7,-5,1,3,5}; int middle = (a.length-1)/2;
int result = middle; if (a[middle]==0){
System.out.println("The smallest number is "+a[middle]);
return;
}
//find the demarcation point
else{
if(a[result]>0){
while(a[result]>0){
result = result - 1;
}
if(Math.abs(a[result])>a[result+1]){
System.out.println("The smallest number is "+a[result+1]);
return;
}
else{
System.out.println("The smallest number is "+a[result]);
return;
}
}
else{
while(a[result]<0){
result = result + 1;
}
if(a[result]>Math.abs(a[result+1])){
System.out.println("The smallest number is "+a[result+1]);
return;
}
else{
System.out.println("The smallest number is "+a[result]);
return;
}
} } }}