由于iOS就業(yè)市場經(jīng)歷過被培訓(xùn)機(jī)構(gòu)一火車一火車輸送人才的階段，所以各大公司都喜歡出一點(diǎn)基礎(chǔ)算法筆試題，在下不才，做了一些題目的總結(jié)，如有補(bǔ)充或者錯(cuò)誤，跪謝各位私信提醒我~~~
以下基本上以C語言實(shí)現(xiàn)為主
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. 可以理解為不進(jìn)位加法）
void swap(int a, int b) {
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
2.求最大公約數(shù)?
/** 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.輾轉(zhuǎn)相除法 */
int maxCommonDivisor(int a, int b) {
int r;
while(a % b > 0) {
r = a % b;
a = b;
b = r;
}
return b;
}
// 擴(kuò)展：最小公倍數(shù) = (a * b)/最大公約數(shù)
3.模擬棧操作?
/**
* 棧是一種數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)：先進(jìn)后出
* 練習(xí)：使用全局變量模擬棧的操作
*/
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
//保護(hù)全局變量：在全局變量前加static后，這個(gè)全局變量就只能在本文件中使用
static int data[1024];//棧最多能保存1024個(gè)數(shù)據(jù)
static int count = 0;//目前已經(jīng)放了多少個(gè)數(shù)(相當(dāng)于棧頂位置)
//數(shù)據(jù)入棧 push
void push(int x){
assert(!full());//防止數(shù)組越界
data[count++] = x;
}
//數(shù)據(jù)出棧 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.排序算法?
選擇排序、冒泡排序、插入排序三種排序算法可以總結(jié)為如下：
都將數(shù)組分為已排序部分和未排序部分。
- 選擇排序?qū)⒁雅判虿糠侄x在左端，然后選擇未排序部分的最小元素和未排序部分的第一個(gè)元素交換。
- 冒泡排序?qū)⒁雅判虿糠侄x在右端，在遍歷未排序部分的過程執(zhí)行交換，將最大元素交換到最右端。
- 插入排序?qū)⒁雅判虿糠侄x在左端，將未排序部分元的第一個(gè)元素插入到已排序部分合適的位置。
選擇排序
/**
* 【選擇排序】：最值出現(xiàn)在起始端
*
* 第1趟：在n個(gè)數(shù)中找到最小(大)數(shù)與第一個(gè)數(shù)交換位置
* 第2趟：在剩下n-1個(gè)數(shù)中找到最小(大)數(shù)與第二個(gè)數(shù)交換位置
* 重復(fù)這樣的操作...依次與第三個(gè)、第四個(gè)...數(shù)交換位置
* 第n-1趟，最終可實(shí)現(xiàn)數(shù)據(jù)的升序（降序）排列。
*
*/
void selectSort(int *arr, int length) {
for (int i = 0; i < length - 1; i++) { //趟數(shù)
for (int j = i + 1; j < length; j++) { //比較次數(shù)
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
冒泡排序
/**
* 【冒泡排序】：相鄰元素兩兩比較，比較完一趟，最值出現(xiàn)在末尾
* 第1趟：依次比較相鄰的兩個(gè)數(shù)，不斷交換（小數(shù)放前，大數(shù)放后）逐個(gè)推進(jìn)，最值最后出現(xiàn)在第n個(gè)元素位置
* 第2趟：依次比較相鄰的兩個(gè)數(shù)，不斷交換（小數(shù)放前，大數(shù)放后）逐個(gè)推進(jìn)，最值最后出現(xiàn)在第n-1個(gè)元素位置
* …… ……
* 第n-1趟：依次比較相鄰的兩個(gè)數(shù)，不斷交換（小數(shù)放前，大數(shù)放后）逐個(gè)推進(jìn)，最值最后出現(xiàn)在第2個(gè)元素位置
*/
void bublleSort(int *arr, int length) {
for(int i = 0; i < length - 1; i++) { //趟數(shù)
for(int j = 0; j < length - i - 1; j++) { //比較次數(shù)
if(arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
5.折半查找（二分查找）
/**
* 折半查找：優(yōu)化查找時(shí)間（不用遍歷全部數(shù)據(jù)）
*
* 折半查找的原理：
* 1> 數(shù)組必須是有序的
* 2> 必須已知min和max（知道范圍）
* 3> 動(dòng)態(tài)計(jì)算mid的值，取出mid對應(yīng)的值進(jìn)行比較
* 4> 如果mid對應(yīng)的值大于要查找的值，那么max要變小為mid-1
* 5> 如果mid對應(yīng)的值小于要查找的值，那么min要變大為mid+1
*
*/
// 已知一個(gè)有序數(shù)組, 和一個(gè)key, 要求從數(shù)組中找到key對應(yīng)的索引位置
int findKey(int *arr, int length, int key) {
int min = 0, max = length - 1, mid;
while (min <= max) {
mid = (min + max) / 2; //計(jì)算中間值
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.設(shè)一個(gè)數(shù)為n，則在C語言中其個(gè)位、十位、百位、千位依次這樣計(jì)算：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("個(gè)位:%d\n十位:%d\n百位:%d\n千位:%d\n", unitPlace, tenPlace, hundredPlace, thousandPlace);
getchar();
return 0;
}
7.把一個(gè)int數(shù)組的第一個(gè)元素和最后一個(gè)元素的值互換？
int[] a={2,3,4,5,7};
int temp=a[0];
a[0]=a[a.length-1];
a[a.length-1]=temp;
8. 從鍵盤輸入一個(gè)整數(shù)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);/*沒有數(shù)據(jù)合法性檢查*/
for (i = 0; i < n; ++i)
array[i] = i+1;
perm(array, n, 0);
return 0;
}
9.輸入一個(gè)正整數(shù)，將其逆序輸出。例如，輸入12345，輸出54321？
void main(){
long n,m;
printf("輸入一個(gè)正整數(shù)");
scanf("%d",&n);
while(n!=0){
m=n%10;
n=n/10;
printf("%d",m);
}
}
10.利用條件運(yùn)算符的嵌套來完成此題：學(xué)習(xí)成績>=90分的同學(xué)用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.判斷素?cái)?shù)
//判斷m是不是素?cái)?shù)的方法：讓m被i（i由2變到k=sqrt(m)）除
//如果m能被某一個(gè)i（2到k之間的整數(shù)）整除則m必然不是素?cái)?shù)
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語句實(shí)現(xiàn)
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("該數(shù)為%d\n",a);
}
