算法笔试题 - 高飞网
191 人阅读

算法笔试题

2017-07-28 02:09:46

实现字符串翻转

思路1:利用数组的随机访问特性,遍历字符串的数组,按转置的方式将内容放到新数组中。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void reverse(char* str,char* newstr)
{
    if(str==NULL||newstr==NULL){
        return ;
    }   
    int len = strlen(str);
    for(int i=0;i<len/2;i++)
    {   
        newstr[i]=str[len-1-i]; 
        newstr[len-1-i]=str[i];
    }   
}

int main(){
    char* str = "zhonghua12";
    printf("input :%s\n",str);
    int len = strlen(str);
    char * newstr = malloc(len*sizeof(char));
    reverse(str,newstr);
    printf("output:%s\n",newstr);
    
}


思路2:利用栈结构,遍历一遍数组,将数组顺序的放入栈,然后再逆序的弹栈放到新字符串数组中

void reverse(char* str,char* newstr)
{
    if(str==NULL||newstr==NULL){
        return ;
    }
    int len = strlen(str);
    Stack stack ;
    for(int i=0;i<len;i++)
    {
        stack.push(str[i]);
    }
    while(!empty(stack)){
        newstr[i]=pop(stack);
    }

}


找出数组中唯一的重复元素

A[100]存放100个整数,这些整数是从1-99中取的,只有一个数是重复的,请找出这个数,并考虑时间和空间复杂度。

思路1:哈希法,即用bit-map,因为数组从0~99,数值从1~99,因此可以将数值放到bit-map中,如果某位放置两次,即说明重复了。

    //hash
    public static int findDup1(int arr[]){
        byte tmp[] = new byte[100];
        int findNum = 0;
        for(int i=0;i<99;i++){
            if(tmp[arr[i]]==1){
                findNum = arr[i];
                break;
            }
            tmp[arr[i]]=1;
        }
        return findNum; 
    }


思路2:位运算法。由公式:a^b^a=b,可知出现偶数次为0,出现奇数次会出现。

    //hash  利用公式 a^b^a=b
    public static int findDup2(int arr[]){
        int findNum = arr[0];
        for(int i=1;i<100;i++){
            findNum ^= i;
            findNum ^=arr[i];
        }   
        return findNum; 
    }


思路3:求和法,求出1+...+99的和,再求数组中所有数的和,两者之差,即为重复的数。

    //求和法
    public static int findDup3(int arr[]){
        int sum = (1+99)*99/2;
        int sum2 = 0;
        for(int i=0;i<100;i++){
            sum2 += arr[i];
        }
        int findNum = sum2-sum;
        return findNum;
    }


模拟strstr

    写一个函数,判断字符串str2是否是str1的子串,如果是返回出现的位置,否则返回-1

//模拟strstr:判断字符串str2是否是str1的子串
public class StrStr{
    public static void main(String[] args){
        String str1 = "helloworld";
        String str2 = "world";
        int index = strstr(str1,str2);
        System.out.println(str2+"在"+str1+"中出现位置:"+index); 
    }   

    public static int strstr(String str1,String str2){
        if(str1==null||str2==null){
            return -1; 
        }   
        if(str2.length()>str1.length()){
            return -1; 
        }   
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        for(int i=0;i<chars1.length;i++){
            int j=0;
            if(chars1[i]==chars2[j]){//第一个相同的
                while(chars1[i++]!=chars2[j++]){
                    break;
                }   
                return i-1;
            }   
        }   
        return -1; 
    }   
}


逆波兰算法

    字符串78+((4-3)-5)求值

    思路:关于逆波兰式求解四则运算,原理请参考:栈的应用——四则运算表达式求值

import java.util.*;
//用逆波兰式实现四则运算
public class Calc{
	public static void main(String[] args){
		String exp = "78 + ( ( 4 - 3 ) - 5 )";
		int res = calc(exp);
		System.out.println(exp+"="+res);

	}
	public static int calc(String exp){
		String arr[] = exp.split(" ");
		//先转为后缀表达式
		Stack<String> stack = new Stack<String>();
		StringBuffer sb = new StringBuffer();
		for(String e:arr){
			if(isNum(e)){//数字就输出
				sb.append(e).append(" ");
			}else if("+".equals(e)||"-".equals(e)||"(".equals(e)){//+-左括号进栈
				stack.push(e);
			}else if(")".equals(e)){//右括号时将栈中元素出栈
				String x = null;
				do{
					x = stack.pop();
					if("(".equals(x)){//只到左括号位置
						break;
					}
					sb.append(x).append(" ");
				}while(true);
			}
		}
		while(!stack.empty()){
			sb.append(stack.pop()).append(" ");
		}
		System.out.println("后缀表达式为:"+sb.toString());
		//后缀表达式,计算
		stack.clear();
		arr = sb.toString().trim().split(" ");
		for(String e:arr){
			if(isNum(e)){//数字就进栈
				stack.push(e);
			}else{
				int num1 = Integer.parseInt(stack.pop());
				int num2 = Integer.parseInt(stack.pop());
				if("+".equals(e)){
					int res = num2+num1;
					stack.push(res+"");
				}else if("-".equals(e)){
					int res= num2-num1;
					stack.push(res+"");
				}
			}
		}
		int result = Integer.parseInt(stack.pop());
		return result;
	}

	public static boolean isNum(String s){
		char cs[] = s.toCharArray();
		for(char c:cs){
			if(c<'0'||c>'9'){
				return false;
			}
		}
		return true;
	}
}


如何搜索一维数组中重复元素的个数


import java.util.*;

public class DupCntInAdd{
    public static void main(String[] args){
        int[] arr ={12,12,12,13,13,14,14,14,14,0};
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();

        for(int a:arr){
            Integer cnt = map.get(a);
            if(cnt==null){
                map.put(a,1);
            }else{
                map.put(a,cnt+1);
            }   
        }   
        System.out.println(map);
    }   
}



还没有评论!
23.20.162.200