- 相關(guān)推薦
嵌入式工程師面試中常出現(xiàn)的算法
嵌入式系統(tǒng)是以應(yīng)用為中心，以計(jì)算機(jī)技術(shù)為基礎(chǔ)，并且軟硬件可裁剪，適用于應(yīng)用系統(tǒng)對(duì)功能、可靠性、成本、體積、功耗有嚴(yán)格要求的專(zhuān)用計(jì)算機(jī)系統(tǒng)。下面YJBYS小編為大家整理了關(guān)于嵌入式工程師面試中經(jīng)常出現(xiàn)的算法文章，希望對(duì)你有所幫助。
二分查找的代碼.
int bfind(int* a,int len,int val)
{
int m = len/2;
int l = 0;
int r = len;
while(l!=m && r!= m)
{
if(a[m] > val)
{
r = m;
m = (m+l)/2;
}
else if(a[m] < val)
{
l = m;
m = (m+r)/2;
}
else
return m;
}
return -1; //沒(méi)有找到
}
寫(xiě)出在母串中查找子串出現(xiàn)次數(shù)的代碼.
int count1(char* str,char* s)
{
char* s1;
char* s2;
int count = 0;
while(*str!='\0')
{
s1 = str;
s2 = s;
while(*s2 == *s1&&(*s2!='\0')&&(*s1!='0'))
{
s2++;
s1++;
}
if(*s2 == '\0')
count++;
str++;
}
return count;
}
查找第一個(gè)匹配子串位置,如果返回的是s1長(zhǎng)度len1表示沒(méi)有找到
size_t find(char* s1,char* s2)
{
size_t i=0;
size_t len1 = strlen(s1)
size_t len2 = strlen(s2);
if(len1-len2<0) return len1;
for(;i {
size_t m = i;
for(size_t j=0;j {
if(s1[m]!=s2[j])
break;
m++;
}
if(j==len)
break;
}
return i }
寫(xiě)出快速排序或者某種排序算法代碼
快速排序:
int partition(int* a,int l,int r)
{
int i=l-1,j=r,v=a[r];
while(1)
{
while(a[++i] while(a[--j]>v) if(j<=i) break;
if(i>=j)
break;
swap(a[i],a[j]);
}
swap(a[i],a[r]);
return i;
}
void qsort(int* a,int l,int r)
{
if(l>=r) return;
int i = partition(a,l,r);
qsort(a,l,i-1);
qsort(a,i+1,r);
}
冒泡排序:
void buble(int *a,int n)
{
for(int i=0;i {
for(int j=1;j {
if(a[j] {
int temp=a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
}
}
插入排序：
void insertsort(int* a,int n)
{
int key;
for(int j=1;j {
key = a[j];
for(int i=j-1;i>=0&&a[i]>key;i--)
{
a[i+1] = a[i];
}
a[i+1] = key;
}
}
出現(xiàn)次數(shù)相當(dāng)頻繁
實(shí)現(xiàn)strcmp函數(shù)
int strcmp11(char* l,char* r)
{
assert(l!=0&&r!=0);
while(*l == *r &&*l != '\0') l++,r++;
if(*l > *r)
return 1;
else if(*l == *r)
return 0;
return -1;
}
實(shí)現(xiàn)字符串翻轉(zhuǎn)
void reserve(char* str)
{
assert(str != NULL);
char * p1 = str;
char * p2 = str-1;
while(*++p2); //一般要求不能使用strlen
p2 -= 1;
while(p1 {
char c = *p1;
*p1++ = *p2;
*p2-- = c;
}
}
將一個(gè)單鏈表逆序
struct list_node
{
list_node(int a,list_node* b):data(a),next(b) //這個(gè)為了測(cè)試方便
{}
int data;
list_node* next;
};
void reserve(list_node* phead)
{
list_node* p = phead->next;
if(p == NULL || p->next == NULL) return; //只有頭節(jié)點(diǎn)或一個(gè)節(jié)點(diǎn)
list_node* p1=p->next;
p->next=NULL;
while(p1!=NULL)
{
p = p1->next;
p1->next = phead->next;
phead->next = p1;
p1 = p;
}
}
測(cè)試程序：
list lt;
lt.phead = new list_node(0,0);
lt.phead->next = new list_node(1,0);
lt.phead->next->next = new list_node(2,0);
lt.phead->next->next->next = new list_node(3,0);
lt.reserve();
list_node * p = lt.phead;
while(p)
{
coutnext;
}
循環(huán)鏈表的節(jié)點(diǎn)對(duì)換和刪除。
//雙向循環(huán)
list_node* earse(list_node* node)
{
// if(node == rear) return node->next; //對(duì)于頭節(jié)點(diǎn)可判斷也可不判斷。最好加上
list_node* next = node->next;
next->prev = node->prev;
node->prev->next = next;
delete node;
retrun next;
}
//單項(xiàng)循環(huán)
list_node* earse(list_node* node)
{
// if(node == rear) return node->next; //對(duì)于頭節(jié)點(diǎn)可判斷也可不判斷。最好加上
list_node* p = rear;
while(p->next != node) p=p->next;
p->next = node->next;
delete node;
retrun p->next;
}
將一個(gè)數(shù)字字符串轉(zhuǎn)換為數(shù)字."1234" -->1234
int atoii(char* s)
{
assert(s!=NULL);
int num = 0;
int temp;
while(*s>'0' && *s<'9')
{
num *= 10;
num += *s-'0';
s++;
}
return num;
}
出現(xiàn)次數(shù)相當(dāng)頻繁
.實(shí)現(xiàn)任意長(zhǎng)度的整數(shù)相加或者相乘功能。
void bigadd(char* num,char* str,int len)
{
for(int i=len;i>0;i--)
{
num[i] += str[i];
int j = i;
while(num[j]>=10)
{
num[j--] -= 10;
num[j] += 1;
}
}
}
.寫(xiě)函數(shù)完成內(nèi)存的拷貝
void* memcpy( void *dst, const void *src, unsigned int len )
{
register char *d;
register char *s;
if (len == 0)
return dst;
if ( dst > src ) //考慮覆蓋情況
{
d = (char *)dst + len - 1;
s = (char *)src + len - 1;
while ( len >= 4 ) //循環(huán)展開(kāi)，提高執(zhí)行效率
{
*d-- = *s--;
*d-- = *s--;
*d-- = *s--;
*d-- = *s--;
len -= 4;
}
while ( len-- )
{
*d-- = *s--;
}
}
else if ( dst < src )
{
d = (char *)dst;
s = (char *)src;
while ( len >= 4 )
{
*d++ = *s++;
*d++ = *s++;
*d++ = *s++;
*d++ = *s++;
len -= 4;
}
while ( len-- )
{
*d++ = *s++;
}
}
return dst;
}
出現(xiàn)次數(shù)相當(dāng)頻繁
編寫(xiě)類(lèi)String的構(gòu)造函數(shù)、析構(gòu)函數(shù)和賦值函數(shù)，已知類(lèi)String的原型為：
class String
{
public:
String(const char *str = NULL); // 普通構(gòu)造函數(shù)
String(const String &other); // 拷貝構(gòu)造函數(shù)
~ String(void); // 析構(gòu)函數(shù)
String & operate =(const String &other); // 賦值函數(shù)
private:
char *m_data; // 用于保存字符串
};
解答：
//普通構(gòu)造函數(shù)
String::String(const char *str)
{
if(str==NULL)
{
m_data = new char[1]; // 得分點(diǎn)：對(duì)空字符串自動(dòng)申請(qǐng)存放結(jié)束標(biāo)志'\0'的空
//加分點(diǎn)：對(duì)m_data加NULL 判斷
*m_data = '\0';
}
else
{
int length = strlen(str);
m_data = new char[length+1]; // 若能加 NULL 判斷則更好
strcpy(m_data, str);
}
}
// String的析構(gòu)函數(shù)
String::~String(void)
{
delete [] m_data; // 或delete m_data;
}
//拷貝構(gòu)造函數(shù)
String::String(const String &other) // 得分點(diǎn)：輸入?yún)?shù)為const型
{
int length = strlen(other.m_data);
m_data = new char[length+1]; //加分點(diǎn)：對(duì)m_data加NULL 判斷
strcpy(m_data, other.m_data);
}
//賦值函數(shù)
String & String::operate =(const String &other) // 得分點(diǎn)：輸入?yún)?shù)為const型
{
if(this == &other) //得分點(diǎn)：檢查自賦值
return *this;
delete [] m_data; //得分點(diǎn)：釋放原有的內(nèi)存資源
int length = strlen( other.m_data );
m_data = new char[length+1]; //加分點(diǎn)：對(duì)m_data加NULL 判斷
strcpy( m_data, other.m_data );
return *this; //得分點(diǎn)：返回本對(duì)象的引用
}
剖析：
能夠準(zhǔn)確無(wú)誤地編寫(xiě)出String類(lèi)的構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、賦值函數(shù)和析構(gòu)函數(shù)的面試者至少已經(jīng)具備了C++基本功的60%以上!
在這個(gè)類(lèi)中包括了指針類(lèi)成員變量m_data，當(dāng)類(lèi)中包括指針類(lèi)成員變量時(shí)，一定要重載其拷貝構(gòu)造函數(shù)、賦值函數(shù)和析構(gòu)函數(shù)，這既是對(duì)C++程序員的基本要求，也是《Effective C++》中特別強(qiáng)調(diào)的條款。
實(shí)現(xiàn)strcpy
char * strcpy( char *strDest, const char *strSrc )
{
assert( (strDest != NULL) && (strSrc != NULL) );
char *address = strDest;
while( (*strDest++ = * strSrc++) != ‘\0’ );
return address;
}
編寫(xiě)一個(gè)函數(shù)，作用是把一個(gè)char組成的字符串循環(huán)右移n個(gè)。比如原來(lái)是“abcdefghi”如果n=2，移位后應(yīng)該是“hiabcdefgh”
函數(shù)頭是這樣的：
//pStr是指向以'\0'結(jié)尾的字符串的指針
//steps是要求移動(dòng)的n
void LoopMove ( char * pStr, int steps )
{
//請(qǐng)?zhí)畛?..
}
解答：
正確解答1：
void LoopMove ( char *pStr, int steps )
{
int n = strlen( pStr ) - steps;
char tmp[MAX_LEN];
strcpy ( tmp, pStr + n );
strcpy ( tmp + steps, pStr);
*( tmp + strlen ( pStr ) ) = '\0';
strcpy( pStr, tmp );
}
正確解答2：
void LoopMove ( char *pStr, int steps )
{
int n = strlen( pStr ) - steps;
char tmp[MAX_LEN];
memcpy( tmp, pStr + n, steps );
memcpy(pStr + steps, pStr, n );
memcpy(pStr, tmp, steps );
}
【嵌入式工程師面試中常出現(xiàn)的算法】相關(guān)文章：
鋼琴?gòu)椬嘀谐３霈F(xiàn)的問(wèn)題07-27
日語(yǔ)口語(yǔ)中常出現(xiàn)的終助詞03-08
經(jīng)典C語(yǔ)言面試算法題03-17
嵌入式軟件工程師認(rèn)證03-03