iOS套路面试题之必考笔试手写算法题

由于iOS就业市场经历过被培训机构一火车一火车输送人才的阶段,所以各大公司都喜欢出一点基础算法笔试题,在下不才,做了一些题目的总结,如有补充或者错误,跪谢各位私信提醒我~~~

以下基本上以C语言实现为主

1.不用中间变量,用两种方法交换A和B的值?

// 1.中间变量
void swap(int a, int b) {
   int temp = a;
   a = b;
   b = temp;
}

// 2.加法
void swap(int a, int b) {
   a = a + b;
   b = a - b;
   a = a - b;
}

// 3.异或(相同为0,不同为1. 可以理解为不进位加法)
void swap(int a, int b) {
   a = a ^ b;
   b = a ^ b;
   a = a ^ b;
}

2.求最大公约数?

/** 1.直接遍历法 */
int maxCommonDivisor(int a, int b) {
    int max = 0;
    for (int i = 1; i <=b; i++) {
        if (a % i == 0 && b % i == 0) {
            max = i;
        }
    }
    return max;
}
/** 2.辗转相除法 */
int maxCommonDivisor(int a, int b) {
    int r;
    while(a % b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return b;
}

// 扩展:最小公倍数 = (a * b)/最大公约数

3.模拟栈操作?

 /**
 *  栈是一种数据结构,特点:先进后出
 *  练习:使用全局变量模拟栈的操作
 */
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
//保护全局变量:在全局变量前加static后,这个全局变量就只能在本文件中使用
static int data[1024];//栈最多能保存1024个数据
static int count = 0;//目前已经放了多少个数(相当于栈顶位置)

//数据入栈 push
void push(int x){
    assert(!full());//防止数组越界
    data[count++] = x;
}
//数据出栈 pop
int pop(){
    assert(!empty());
    return data[--count];
}
//查看栈顶元素 top
int top(){
    assert(!empty());
    return data[count-1];
}

//查询栈满 full
bool full() {
    if(count >= 1024) {
        return 1;
    }
     return 0; 
}

//查询栈空 empty
bool empty() {
    if(count <= 0) {
        return 1;
    }
    return 0;
}

int main(){
    //入栈
    for (int i = 1; i <= 10; i++) {
        push(i);
    }
  
    //出栈
    while(!empty()){
        printf("%d ", top()); //栈顶元素
        pop(); //出栈
    }
    printf("\n");
    
    return 0;
}

4.排序算法?

选择排序、冒泡排序、插入排序三种排序算法可以总结为如下:
都将数组分为已排序部分和未排序部分。

  1. 选择排序将已排序部分定义在左端,然后选择未排序部分的最小元素和未排序部分的第一个元素交换。
  2. 冒泡排序将已排序部分定义在右端,在遍历未排序部分的过程执行交换,将最大元素交换到最右端。
  3. 插入排序将已排序部分定义在左端,将未排序部分元的第一个元素插入到已排序部分合适的位置。

选择排序

/** 
 *  【选择排序】:最值出现在起始端
 *  
 *  第1趟:在n个数中找到最小(大)数与第一个数交换位置
 *  第2趟:在剩下n-1个数中找到最小(大)数与第二个数交换位置
 *  重复这样的操作...依次与第三个、第四个...数交换位置
 *  第n-1趟,最终可实现数据的升序(降序)排列。
 *
 */
void selectSort(int *arr, int length) {
    for (int i = 0; i < length - 1; i++) { //趟数
        for (int j = i + 1; j < length; j++) { //比较次数
            if (arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

冒泡排序

/** 
 *  【冒泡排序】:相邻元素两两比较,比较完一趟,最值出现在末尾
 *  第1趟:依次比较相邻的两个数,不断交换(小数放前,大数放后)逐个推进,最值最后出现在第n个元素位置
 *  第2趟:依次比较相邻的两个数,不断交换(小数放前,大数放后)逐个推进,最值最后出现在第n-1个元素位置
 *   ……   ……
 *  第n-1趟:依次比较相邻的两个数,不断交换(小数放前,大数放后)逐个推进,最值最后出现在第2个元素位置 
 */
void bublleSort(int *arr, int length) {
    for(int i = 0; i < length - 1; i++) { //趟数
        for(int j = 0; j < length - i - 1; j++) { //比较次数
            if(arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        } 
    }
}

5.折半查找(二分查找)

/**
 *  折半查找:优化查找时间(不用遍历全部数据)
 *
 *  折半查找的原理:
 *   1> 数组必须是有序的
 *   2> 必须已知min和max(知道范围)
 *   3> 动态计算mid的值,取出mid对应的值进行比较
 *   4> 如果mid对应的值大于要查找的值,那么max要变小为mid-1
 *   5> 如果mid对应的值小于要查找的值,那么min要变大为mid+1
 *
 */ 

// 已知一个有序数组, 和一个key, 要求从数组中找到key对应的索引位置 
int findKey(int *arr, int length, int key) {
    int min = 0, max = length - 1, mid;
    while (min <= max) {
        mid = (min + max) / 2; //计算中间值
        if (key > arr[mid]) {
            min = mid + 1;
        } else if (key < arr[mid]) {
            max = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

6.9*9乘法表?

main(){
 int x,y,z;
 for(x=1;x<=9;x++){
  for(y=1;y<=x;y++) {
   z=x*y;
   printf("%d*%d=%d  ",y,x,z);
  }
  printf("\n");
 }
}

6.设一个数为n,则在C语言中其个位、十位、百位、千位依次这样计算:n/1%10,n/10%10,n/100%10,n/1000%10?

int main(){
    int n = 123456;
    int unitPlace = n / 1 % 10;
    int tenPlace = n / 10 % 10;
    int hundredPlace = n / 100 % 10;
    int thousandPlace = n / 1000 % 10;
    printf("个位:%d\n十位:%d\n百位:%d\n千位:%d\n", unitPlace, tenPlace, hundredPlace, thousandPlace);
 
    getchar();
    return 0;
}

7.把一个int数组的第一个元素和最后一个元素的值互换?

int[] a={2,3,4,5,7};
int temp=a[0];
a[0]=a[a.length-1];
a[a.length-1]=temp;

8. 从键盘输入一个整数n,请输入1,2,……,n的所有排列如n=3,则输出为

1 2 3

1 3 2

2 1 3

2 3 1

void perm(int* data, int n, int curr){
if (curr==n-1){
for (int i = 0; i < n; ++i)
printf("%d", data[i]);
printf("\n");
}else{
for (int i = curr; i < n; ++i){
int t;
t = data[curr], data[curr] = data[i], data[i] = t;
perm(data, n, curr+1);
t = data[curr], data[curr] = data[i], data[i] = t;
     }
  }
}
int main(){
int array[128] = {0};
int n = 0, i = 0;

scanf("%d", &n);/*没有数据合法性检查*/
for (i = 0; i < n; ++i) 
array[i] = i+1;
perm(array, n, 0);
return 0;
}

9.输入一个正整数,将其逆序输出。例如,输入12345,输出54321?

void main(){
long n,m;
printf("输入一个正整数");
scanf("%d",&n);
while(n!=0){ 
m=n%10;
n=n/10;
printf("%d",m);
    }
} 

10.利用条件运算符的嵌套来完成此题:学习成绩>=90分的同学用A表示,60-89分之间的用B表示, 60分以下的用C表示。

void main(){
int grade;
printf("Inter grade:");
scanf("%d",&grade);
if(grade>=90&&grade<100)
printf("Grade is:A\n");
else if(grade>=60&&grade<=89)
printf("Grade is:B\n");
else if(grade<60&&grade>=0)
printf("Grade is:C\n");
else printf("error\n");

11.判断素数

//判断m是不是素数的方法:让m被i(i由2变到k=sqrt(m))除
//如果m能被某一个i(2到k之间的整数)整除则m必然不是素数
void main(){
int m,i,k;
printf("please enter an integer number:");
scanf("%d",&m);
k=sqrt(m);
for(i=2;i<=k;i++)
if(m%i==0) break;
if(i>k)
printf("%d is a prime number.\n",m);
else printf("%d is not a prime number.\n",m);
}

12.编程求1+(1+2)+…+(1+2+…+n),n的值由键盘输入。要求使用for语句实现

void main(){
int j,k,i,sum=0,n=1,m,a=0;
printf("输入累加到几:");
scanf("%d",&j);
for(i=1;i<=j;i++){
sum=sum+n;
n++;
for(m=1;m<=1;m++){
a=a+sum;
   }
 }
printf("该数为%d\n",a);
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,378评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,356评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,702评论 0 342
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,259评论 1 279
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,263评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,036评论 1 285
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,349评论 3 400
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,979评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,469评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,938评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,059评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,703评论 4 323
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,257评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,262评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,485评论 1 262
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,501评论 2 354
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,792评论 2 345

推荐阅读更多精彩内容