筆試編程題

兩數之和（浦發）

兩數之和

我們保證輸出結果必然存在且唯一，陣列索引從1開始

只允許在solution方法內完成代碼，不允許呼叫庫函式，不允許在solution之外撰寫其他函式

思路

因為有序，雙指標即可解決，注意溢位問題即可

code

//C代碼
void solution(int* nums,int len_nums,int target,int*result,int len_result){
	int left = 0,right = len_nums - 1;
	while(left<right){
		if(nums[right]>target-nums[left])
			--right;
		else if(nums[left]<target-nums[right])
			++left;
		else{
			result[0]=left+1,result[1]=right+1;
			break;
		}
	}
}

回文數字判斷（浦發）

回文數

1表示true,0表示false

只允許在solution方法內完成代碼，不允許呼叫庫函式，不允許在solution之外撰寫其他函式

思路

數學解法：
1.計算n有多少位
2.得出10^(n-1)
3.分次取高位與低位，比較；相同則對n舍棄最高位與最低位，繼續對比即可
輔助陣列解法：
分割n的每一位（假設n長cnt），存進陣列arr;

for(int i = 0;i<cnt/2;++i)
	if(arr[i]!=arr[cnt-1-i])
		return 0;
return 1;

code

//C代碼
int solution(int n){
	if(n<0)//排除負數
		return 0;
	int cnt = 1;
	int tmp_n = n;
	while(tmp_n/=10)//計算n的位數
		++cnt;
	int div = 1;
	for(int i = 1;i<cnt;++i)//得到10^(n-1)，作為除數
		div*=10;
	while(n){
		if(n/div != n%10)//最高位與個位不同
			return 0;
		n%=10;//丟掉最高位
		n/=10;//丟掉個位
		div/=100;//更新除數
	}
	return 1;
}

陣列乘積（浦發）

現有一串長度不固定的陣列，陣列內部為亂序排列，可能包含重復元素，先需要計算陣列中每個元素粗自己外其他所有元素的乘積，

【樣例輸入1】[2,3,4,5,6]
【樣例輸出1】[360,240,180,144,120]
【決議1】
3x4x5x6=360，2x4x5x6=240,2x3x5x6=180，……
【樣例輸入2】[5,2,9,9,9,1,8,1,9,4]
【樣例輸出2】[419904,1049760,233280,……]
【決議2】與第一個例子類似，不再具體列舉程序

只允許在solution方法內完成代碼，不允許呼叫庫函式，不允許在solution之外撰寫其他函式

思路

暴力解法1：
使用雙重回圈即可解決，遇到算過的數字復制乘積即可，
暴力解法2：
陣列元素全乘起來，運用除法計算結果
乘積表解法3：
構建left,right乘積表即可解決

乘積表解法code

//C代碼
void solution(int* arr, int arr_len, int* res,int res_len) {
	int dk = arr_len;
	while (dk /= 2) {//希爾排序
		for (int i = dk; i < arr_len; ++i) {
			if (arr[i - dk] > arr[i]) {
				int tmp = arr[i], j = i - dk;
				for (; j >= 0 && arr[j] > tmp; j-=dk)
					arr[j + dk] = arr[j];
				arr[j + dk] = tmp;
			}
		}
	}
	int* left = (int*)malloc(sizeof(int) * res_len);
	int* right = (int*)malloc(sizeof(int) * res_len);
	for (int i = 0; i < res_len; ++i) {//構建左乘積表
		if (arr[i] == arr[0]) {
			left[i] = 1;
			continue;
		}
		left[i] = left[i - 1] * arr[i - 1];
		int k = i + 1;
		while (arr[k] == arr[i])
			left[k++] = left[i];
		i = k - 1;
	}
	for (int i = res_len - 1; i >= 0; --i) {//構建右乘積表
		if (arr[i] == arr[res_len-1]) {
			right[i] = 1;
			continue;
		}
		right[i] = right[i + 1] * arr[i + 1];
		int k = i - 1;
		while (arr[k] == arr[i])
			right[k--] = right[i];
		i = k + 1;
	}
	for (int i = 0; i < res_len; ++i)
		res[i] = left[i] * right[i];
}

【若題目要求輸出順序，則該題應使用暴力解法】

魔法二進制（美團）

現有一個二進制序列，假如你會一個魔法，可以消除這個二進制序列中的任意相鄰3個數字，現在請你計算此二進制序列被施加魔法后，二進制序列中0與1的最大數目差，（也可以不使用魔法，魔法只能使用一次）

輸入描述：
第一行是一個正整數n表示二進制序列的長度
第二行是一個長度為n的二進制序列
輸出描述：
輸出一個正整數，表示施加魔法后二進制序列中0與1的最大數目差

eg.
輸入：
5
00001
輸出：
3

思路

暴力解法：
先統計01數目，然后遍歷使用魔法，統計差值即可

code

#python代碼
def BinTest(inp,n):
    if not n:#長度為0
        return 0
    zero_cnt,one_cnt = 0,0
    for x in inp:#統計01數目
        if x == 1:
            one_cnt += 1
        elif x == 0:
            zero_cnt += 1
    res = abs(zero_cnt-one_cnt)#不使用魔法的01數目差
    for i in range(0,n-2):
        tmp_zero,tmp_one = zero_cnt,one_cnt
        for j in range(i,i+3):#消除inp[i:1:i+2]
            if inp[j] == 1:
                tmp_one-=1
            else:
                tmp_zero-=1
        res = max(res,abs(tmp_one-tmp_zero))
    return res

n = int(input())
inp = list(map(int,input()))
print(BinTest(inp,n))

……美團題的其他一言難盡，1道忘記了，還有3道完全沒想法，