面试题—小算法20题

1、IP转换成整数及整数转换成IP

Java实现：

package com.mian.demo;

public class IpToInt {
    public static void main(String[] args) {
        String ip="192.168.12.90";
        int ipInt=ipToInt(ip);
        System.out.println(ipInt);
        String ipStr=intToIp(ipInt);
        System.out.println(ipStr);
    }
    private static String intToIp(int ip){
        StringBuilder sb=new StringBuilder();
        for(int i=3;i>=0;--i){
            int ipa=(ip>>(8*i))&(0xff);
            System.out.print(ipa+" ");
            sb.append(String.valueOf(ipa)+".");
        }
        return new String(sb).substring(0,sb.length()-1);
    }
    private static int ipToInt(String ip){
        int res=0;
        String[] arr=ip.split("\.");
        for(int i=0;i<arr.length;++i){
            int ipa=Integer.parseInt(arr[i]);
            System.out.print(ipa+" ");
            res=(res<<8)|ipa;//用+也可以,但是位运算更快
        }
        return res;
    }
}

View Code

C++实现：

 1 #include <iostream>
 2 #include <string>
 3 
 4 using namespace std;
 5 
 6 int ip_to_int(string ip)
 7 {
 8     size_t idx = 0;
 9     string str = "";
10     int ret = 0;
11 
12     while (true)
13     {
14         idx = ip.find_first_of('.');
15         str = ip.substr(0, idx);
16         int ipa = atoi(str.c_str());
17         ret = (ret << 8) | ipa;//用+也可以,但是位运算更快
18         ip = ip.substr(idx + 1);
19         if (idx == string::npos)
20             break;
21     }
22 
23     return ret;
24 }
25 
26 string int_to_ip(int ip)
27 {
28     string str = "";
29     for (int i = 3; i >= 0; --i)
30     {
31         int ipa = (ip >> (8 * i))&(0xff);
32         str.append(to_string(ipa) + ".");
33     }
34 
35     return str.substr(0, str.size() - 1);
36 }
37 
38 int main()
39 {
40     string ip = "192.168.12.90";
41     int p = ip_to_int(ip);
42     cout << p << endl;
43     cout << int_to_ip(p) << endl;
44 
45     return 0;
46 }

View Code

2、给一个字符串表示IP地址，检测是否合法

Java实现：

package com.mian.demo;

import java.util.Scanner;

public class IsValidIp {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()) {
            String input = sc.next();
            System.out.println(isValidIp(input));
        }
    }
    private static boolean isValidIp(String ip){
        int size=ip.length();
        if(ip.isEmpty()||size<7||size>15){
            return false;
        }
        String[] arr=ip.split("\.");
        if(arr.length!=4){
            return false;
        }
        for(int i=0;i<arr.length;++i){
            if(arr[i].length()>1&&arr[i].charAt(0)=='0'){
                return false;
            }
            for(int j=0;j<arr[i].length();++j){
                if(arr[i].charAt(j)<'0'||arr[i].charAt(j)>'9'){
                    return false;
                }
            }
        }
        for(int i=0;i<arr.length;++i){
            int tmp=Integer.parseInt(arr[i]);
            if(i==0){
                if(tmp<1||tmp>255){
                    return false;
                }
            }else{
                if(tmp<0||tmp>255){
                    return false;
                }
            }
        }
        return true;
    }
}

View Code

C++实现：

 1 #include<iostream>
 2 #include<vector>
 3 #include<string>
 4 
 5 using namespace std;
 6 
 7 bool isValidIp(string &ip)
 8 {
 9     int size = ip.size();
10     if (ip.empty() || size < 7 || size>15)
11         return false;
12     vector<string> arr;
13     size_t idx = 0;
14     while (true)
15     {
16         idx = ip.find_first_of('.');
17         arr.push_back(ip.substr(0, idx));
18         ip = ip.substr(idx + 1);
19         if (idx == string::npos)
20             break;
21     }
22     if (arr.size() != 4)
23         return false;
24     for (int i = 0; i < arr.size(); ++i)
25     {
26         if (arr[i].size() > 1 && arr[i][0] == '0')
27             return false;
28         for (int j = 0; j < arr[i].size(); ++j)
29             if (arr[i][j]<'0' || arr[i][j]>'9')
30                 return false;
31     }
32     for (int i = 0; i < arr.size(); ++i)
33     {
34         int tmp = atoi(arr[i].c_str());
35         if (i == 0)
36         {
37             if (tmp < 1 || tmp>255)
38                 return false;
39         }
40         else
41         {
42             if (tmp < 0 || tmp>255)
43                 return false;
44         }
45     }
46     return true;
47 }
48 
49 int main()
50 {
51     string str;
52     while (cin >> str)
53         cout << isValidIp(str) << endl;
54 
55     return 0;
56 }

View Code

3、杨辉三角

Java实现：

package com.mian.demo;

import java.util.ArrayList;
import java.util.List;

public class YangHuiSanJiao {
    public static void main(String[] args) {
        int[][] res=yangHuiSanJiao(10);
        for(int i=0;i<res.length;++i){
            for(int k=0;k<res.length-i;++k){
                System.out.print(" ");
            }
            for(int j=0;j<res[i].length;++j){
                System.out.print(res[i][j]+" ");
            }
            System.out.println();
        }
    }
    private static int[][] yangHuiSanJiao(int n){
        int[][] res=new int[n][n];
        for(int i=0;i<n;++i){
            res[i]=new int[i+1];
        }
        for(int i=0;i<n;++i){
            res[i][0]=1;
            res[i][i]=1;
            for(int j=1;j<i;++j){
                res[i][j]=res[i-1][j]+res[i-1][j-1];
            }
        }
        return res;
    }
}

View Code

C++实现：

 1 #include<iostream>
 2 #include<vector>
 3 
 4 using namespace std;
 5 
 6 vector<vector<int>> yanghui(int n)
 7 {
 8     vector<vector<int>> res(n, vector<int>());
 9     for (int i = 0; i < n; ++i)
10     {
11         res[i].resize(i + 1);
12         res[i][0] = 1;
13         res[i][i] = 1;
14     }
15     for (int i = 1; i < n; ++i)
16         for (int j = 1; j < i; ++j)
17             res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
18 
19     return res;
20 }
21 
22 int main()
23 {
24     int n;
25     while (cin >> n)
26     {
27         vector<vector<int>> res = yanghui(n);
28         for (int i = 0; i < n; ++i)
29         {
30             for (int k = 0; k < n - i; ++k)
31                 cout << " ";
32             for (int j = 0; j < res[i].size(); ++j)
33                 if (j == 0)
34                     cout << res[i][j];
35                 else
36                     cout << " " << res[i][j];
37             cout << endl;
38         }
39     }
40 
41     return 0;
42 }

View Code

4、定义一个函数求字符串长度，要求该函数体中不能声明任何一个变量（不使用额外变量，实现strlen函数）

 1 #include <iostream>  
 2 
 3 using namespace std;
 4 
 5 int getLen(char *str)
 6 {
 7     if (*str == '')
 8         return 0;
 9 
10     return getLen(str + 1) + 1;
11 }
12 
13 int getLength(char *str)
14 {
15     return *str ? (getLength(str + 1) + 1) : 0;
16 }
17 
18 
19 int main()
20 {
21     char str[] = "abcde";
22     int len1 = getLen(str);
23     cout << len1 << endl;
24     int len2 = getLength(str);
25     cout << len2 << endl;
26 
27     return 0;
28 }

View Code

5、两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。

Java实现：

package com.mian.demo;

import java.util.Stack;

public class IsPopOrder {
    public static void main(String[] args) {
        int[] pushV={ 1,2,3,4,5 };
        int[] popV1={ 4,5,3,2,1 };
        int[] popV2={ 4,3,5,1,2 };
        boolean t=isPopOrder(pushV,popV1);
        boolean f=isPopOrder(pushV,popV2);
        System.out.println(t+" "+f);
    }
    private static boolean isPopOrder(int[] pushV,int[] popV){
        int psize=pushV.length;
        int osize=popV.length;
        if(psize!=osize){
            return false;
        }
        Stack<Integer> stk=new Stack<>();
        int popIndex=0;
        for(int i=0;i<psize;++i){
            stk.push(pushV[i]);
            while(!stk.isEmpty()&&stk.peek()==popV[popIndex]){
                ++popIndex;
                stk.pop();
            }
        }
        return stk.isEmpty();
    }
}

View Code

C++实现：

 1 #include<iostream>
 2 #include<vector>
 3 #include<stack>
 4 
 5 using namespace std;
 6 
 7 bool isPopOrder(vector<int> &pushV, vector<int> &popV)
 8 {
 9     int psize = pushV.size();
10     int osize = popV.size();
11     if (psize == 0 || osize == 0 || psize != osize)
12         return false;
13     stack<int> stk;
14     int popIndex = 0;
15     for (int i = 0; i < psize; ++i)
16     {
17         stk.push(pushV[i]);
18         while (!stk.empty() &&stk.top() == popV[popIndex])
19         {
20             ++popIndex;
21             stk.pop();
22         }
23     }
24     return stk.empty();
25 }
26 
27 int main()
28 {
29     vector<int> pushV = { 1,2,3,4,5 };
30     vector<int> popV1 = { 4,5,3,2,1 };
31     vector<int> popV2 = { 4,3,5,1,2 };
32     bool t = isPopOrder(pushV, popV1);
33     bool f = isPopOrder(pushV, popV2);
34     cout << t << endl;
35     cout << f << endl;
36 
37     return 0;
38 }

View Code

6、逆序对数

Java实现：

package com.mian.demo;

public class InversePairs {
    static int pairNum;
    public static void main(String[] args){
        int[] arr={ 7,5,6,4 };
        InversePairs inversePairs=new InversePairs();
        int res=inversePairs.inversePairs(arr);
        System.out.println(res);
    }
    private int inversePairs(int[] arr){
        pairNum=0;
        if(arr!=null){
            mergeSort(arr,0,arr.length-1);
        }
        return pairNum;
    }
    private void mergeSort(int[] arr,int low,int high){
        int mid=(low+high)>>1;
        if(low<high){
            mergeSort(arr,low,mid);
            mergeSort(arr,mid+1,high);
            mergeCore(arr,low,mid,high);
        }
    }
    private void mergeCore(int[] arr,int left,int mid,int right){
        int[] tmp=new int[right-left+1];
        int i=left;
        int j=mid+1;
        int k=0;
        while(i<=mid&&j<=right){
            if(arr[i]<arr[j]) {
                tmp[k++] = arr[i++];
            }else{
                tmp[k++]=arr[j++];
                pairNum+=mid-i+1;
            }
        }
        while(i<=mid){
            tmp[k++]=arr[i++];
        }
        while(j<=right){
            tmp[k++]=arr[j++];
        }
        for(int m=0;m<tmp.length;++m){
            arr[left+m]=tmp[m];
        }
    }
}

View Code

C++实现：

View Code

7、找零问题

Java实现：

package com.mian.demo;

import java.lang.reflect.Field;

public class FindMinMoney {
    public static void main(String[] args) {
        FindMinMoney fm=new FindMinMoney();
        fm.findMinMoney(18,new int[]{1,2,5,8,10});
    }
    private void findMinMoney(int money,int[] coin){
        int[] coinNum=new int[money+1];
        int[] coinValue=new int[money+1];
        coinNum[0]=0;
        for(int i=1;i<=money;++i){
            int minNum=i;
            int usedMoney=0;
            for(int j=0;j<coin.length;++j){
                if(i>=coin[j]){
                    if(coinNum[i-coin[j]]+1<=minNum&&(i==coin[j]||coinValue[i-coin[j]]!=0)){
                        minNum=coinNum[i-coin[j]]+1;
                        usedMoney=coin[j];
                    }
                }
            }
            coinNum[i]=minNum;
            coinValue[i]=usedMoney;
        }
        if(coinValue[money]==0){
            System.out.println("找不开零钱");
        }else{
            System.out.println("需要最少硬币个数为："+coinNum[money]);
            System.out.print("硬币分别为: ");
            while(money>0){
                System.out.print(coinValue[money]+" ");
                money-=coinValue[money];
            }
        }
    }
}

View Code

C++实现：

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 //money需要找零的钱,coin可用的硬币,n硬币种类  
 6 void findMin(int money, int *coin, int n)
 7 {
 8     int *coinNum = new int[money + 1]();//存储1...money找零最少需要的硬币的个数  
 9     int *coinValue = new int[money + 1]();//最后加入的硬币，方便后面输出是哪几个硬币  
10     coinNum[0] = 0;
11 
12     for (int i = 1; i <= money; i++)
13     {
14         int minNum = i;//i面值钱，需要最少硬币个数  
15         int usedMoney = 0;//这次找零，在原来的基础上需要的硬币  
16         for (int j = 0; j<n; j++)
17         {
18             if (i >= coin[j])//找零的钱大于这个硬币的面值  
19             {
20                 if (coinNum[i - coin[j]] + 1 <= minNum && (i == coin[j] || coinValue[i - coin[j]] != 0)) 
21                 {
22                     minNum = coinNum[i - coin[j]] + 1;  
23                     usedMoney = coin[j];
24                 }
25             }
26         }
27         coinNum[i] = minNum;
28         coinValue[i] = usedMoney;
29     }
30 
31     //输出结果  
32     if (coinValue[money] == 0)
33         cout << "找不开零钱" << endl;
34     else
35     {
36         cout << "需要最少硬币个数为：" << coinNum[money] << endl;
37         cout << "硬币分别为:";
38         while (money>0)
39         {
40             cout << coinValue[money] << " ";
41             money -= coinValue[money];
42         }
43     }
44     delete[]coinNum;
45     delete[]coinValue;
46 }
47 int main()
48 {
49     int Money = 18;
50     int coin[] = { 1,2,5,9,10 };
51     findMin(Money, coin, 5);
52 
53     return 0;
54 }

View Code

8、字符串翻转

Java实现：

package com.mian.demo;

public class ReverseString {
    public static void main(String[] args) {
        String str="abcdef";
        ReverseString rs=new ReverseString();
        String res=rs.reverseString(str);
        System.out.println(res);
    }
    private String reverseString(String str){
        int n=str.length();
        if(n==0||str.isEmpty()){
            return str;
        }
        char[] chars=str.toCharArray();
        for(int i=0,j=n-1;i<j;++i,--j){
            char c=chars[i];
            chars[i]=chars[j];
            chars[j]=c;
        }
        return new String(chars);
    }
}

View Code

C++实现：

 1 #include<iostream>
 2 
 3 void reverseStr(char *str, int n)
 4 {
 5     for (int i = 0, j = n - 1; i < j; ++i, --j)
 6     {
 7         char c = str[i];
 8         str[i] = str[j];
 9         str[j] = c;
10     }
11 }
12 
13 int main()
14 {
15     char c[] = "abcdef";
16     int size = strlen(c);
17     std::cout << c << std::endl;
18     reverseStr(c, size);
19     std::cout << c << std::endl;
20 
21     return 0;
22 }

View Code

9、判断两个日期之间相隔的天数

参考：https://www.cnblogs.com/xiangxiaodong/archive/2012/02/14/2351883.html

Java实现：

package com.mian.demo;

public class DiffDay {
    public static void main(String[] args) {
        int year1 = 2017, month1 = 9, day1 = 23;
        int year2 = 2018, month2 = 3, day2 = 25;
        DiffDay diffDay=new DiffDay();
        int diff=diffDay.getDiffDay(year1,month1,day1,year2,month2,day2);
        System.out.println(diff);
    }
    private int getDiffDay(int year1,int month1,int day1,int year2,int month2,int day2){
        int d1=getDay(year1,month1,day1);
        int d2=getDay(year2,month2,day2);
        int res=0;
        if(year1==year2){
            res=Math.abs(d1-d2);
        }else if(year1>year2){
            for(int i=year2+1;i<year1;++i){
                if(isLeap(i)){
                    res+=366;
                }else{
                    res+=365;
                }
            }
            res+=d1;
            if(isLeap(year2)){
                res+=(366-d2);
            }else{
                res+=(365-d2);
            }
        }else{
            for(int i=year1+1;i<year2;++i){
                if(isLeap(i)){
                    res+=366;
                }else{
                    res+=365;
                }
            }
            res+=d2;
            if(isLeap(year1)){
                res+=(366-d1);
            }else{
                res+=(365-d1);
            }
        }
        return res;
    }
    private int getDay(int year,int month,int day){
        int days=0;
        int d=0;
        for(int i=1;i<month;++i){
            switch (i){
                case 1:
                case 3:
                case 5:
                case 7:
                case 8:
                case 10:
                case 12:
                    d=31;
                    days+=d;
                    break;
                case 2:
                    if(isLeap(year)){
                        d=29;
                    }else{
                        d=28;
                    }
                    days+=d;
                    break;
                case 4:
                case 6:
                case 9:
                case 11:
                    d=30;
                    days+=d;
                    break;
            }
        }
        return days+day;
    }
    private boolean isLeap(int year){
        if((year%4==0&&year%100==0)||year%400==0){
            return true;
        }
        return false;
    }
}

View Code

C++实现：

 1 #include<iostream>
 2 #include<iostream>
 3 
 4 using namespace std;
 5 
 6 bool isLeap(int year)
 7 {
 8     if ((year % 4 == 0 && year % 100)|| year % 400==0)
 9         return true;
10     return false;
11 }
12 
13 int getDay(int year, int month, int day)
14 {
15     int res = 0;
16     int d = 0;
17     for (int i = 1; i < month; ++i)
18     {
19         switch (i)
20         {
21             case 1:
22             case 3:
23             case 5:
24             case 7:
25             case 8:
26             case 10:
27             case 12:
28                 d = 31;
29                 res += d;
30                 break;
31             case 2:
32                 if (isLeap(year))
33                     d = 29;
34                 else
35                     d = 28;
36                 res += d;
37                 break;
38             case 4:
39             case 6:
40             case 9:
41             case 11:
42                 d = 30;
43                 res += d;
44                 break;
45         }        
46     }
47     return res + day;
48 }
49 
50 int main()
51 {
52     int year1 = 2017, month1 = 9, day1 = 23;
53     int year2 = 2018, month2 = 3, day2 = 25;
54     int d1 = getDay(year1, month1, day1);
55     int d2 = getDay(year2, month2, day2);
56     int res = 0;
57     if (year1 == year2)
58         cout << std::abs(d1-d2) << endl;
59     else
60     {
61         if (year1 > year2)
62         {
63             for (int i = year2 + 1; i < year1; ++i)
64             {
65                 if (isLeap(i))
66                     res += 366;
67                 else
68                     res += 365;
69             }
70             res += d1;
71             if (isLeap(year2))
72                 res += (366 - d2);
73             else
74                 res += (365 - d2);
75         }
76         else if (year2 > year1)
77         {
78             for (int i = year1 + 1; i < year2; ++i)
79             {
80                 if (isLeap(i))
81                     res += 366;
82                 else
83                     res += 365;
84             }
85             res += d2;
86             if (isLeap(year1))
87                 res += (366 - d1);
88             else
89                 res += (365 - d1);
90         }
91         cout << res << endl;
92     }
93 
94     return 0;
95 }

View Code

10、给定A, B两个整数，不使用除法和取模运算，求A/B的商和余数。

Java实现：

package com.mian.demo;

public class Divide {
    public static void main(String[] args){
        divide(10,3);
    }
    private static void divide(int a,int b){
        for(int i=2;i<a;++i){
            if(i*b>a){
                System.out.println((i-1)+" "+(a-((i-1)*b)));
                break;
            }
        }
    }
}

View Code

C++实现：

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 void divide(int a, int b)
 6 {
 7     for (int i = 2; i < a; ++i)
 8         if (i*b > a)
 9         {
10             cout << (i - 1) << " " << (a - (i - 1)*b) << endl;
11             break;
12         }
13 }
14 
15 int main()
16 {
17     divide(10, 3);
18 
19     return 0;
20 }

View Code

11、压缩驼峰字符串

Java实现:

package com.mian.demo;

public class CamelAndSnakeString {
    public static void main(String[] args){
        String s = "get_set_where";
        System.out.println(camelString(s));
        String str="getSetWhere";
        System.out.println(snakeString(str));
    }
    private static String camelString(String str){
        int size=str.length();
        if(size==0||str.isEmpty()){
            return str;
        }
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<size;++i){
            if(str.charAt(i)=='_'){
                continue;
            }
            if(i!=0&&str.charAt(i-1)=='_'){
                sb.append(new Character(str.charAt(i)).toString().toUpperCase());
            }else {
                sb.append(str.charAt(i));
            }
        }
        return new String(sb);
    }
    private static String snakeString(String str){
        int size=str.length();
        if(size==0||str.isEmpty()){
            return str;
        }
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<size;++i){
            if(str.charAt(i)>='A'&&str.charAt(i)<='Z'){
                sb.append('_'+new Character(str.charAt(i)).toString().toLowerCase());
            }else{
                sb.append(str.charAt(i));
            }
        }
        return new String(sb);
    }
}

View Code

C++实现：

 1 #include<iostream>
 2 #include<string>
 3 
 4 using namespace std;
 5 
 6 string snakeString(string &str)
 7 {
 8     int size = str.size();
 9     if (size == 0 || str.empty())
10         return "";
11     string res = "";
12     for (int i = 0; i < str.size(); ++i)
13     {
14         if (islower(str[i]))
15             res += str[i];
16         else
17         {
18             res += '_';
19             res += tolower(str[i]);
20         }
21     }
22     return res;
23 }
24 
25 string camelString(string &s)
26 {
27     int size = s.size();
28     if (size == 0 || s.empty())
29         return "";
30     string res = "";
31     for (int i = 0; i < s.size(); ++i)
32     {
33         if (s[i]=='_')
34             continue;
35         if (i!=0&&s[i - 1] == '_')
36             res += toupper(s[i]);
37         else
38             res += s[i];
39     }
40     return res;
41 }
42 
43 int main()
44 {
45     string str = "getSetWhere";
46     cout << snakeString(str) << endl;
47     string s = "get_set_where";
48     cout << camelString(s) << endl;
49 
50     return 0;
51 }

View Code

12、除去s1中与s2中相同的字符

Java实现：

package com.mian.demo;

import java.util.Arrays;

public class Squeeze {
    public static void main(String[] args) {
        String str1 = "abcde";
        String str2 = "ace";
        System.out.println(squeeze(str1, str2));
    }

    private static String squeeze(String str1, String str2) {
        int i = 0, j = 0, k = 0;
        StringBuilder sb = null;
        while (j < str2.length()) {
            sb = new StringBuilder();
            while (i < str1.length()) {
                if (str1.charAt(i) != str2.charAt(j)) {
                    sb.append(str1.charAt(i));
                }
                ++i;
            }
            str1 = new String(sb);
            i = k = 0;
            ++j;
        }
        return str1;
    }
}

View Code

C++实现：

 1 #include <stdio.h>
 2 
 3 void squeeze(char s1[], char s2[])
 4 {
 5     int i, j, k;
 6     i = j = k = 0;
 7 
 8     while (s2[j] != '')
 9     {
10         while (s1[i] != '')
11         {
12             if (s2[j] != s1[i])
13                 s1[k++] = s1[i];
14             i++;
15         }
16         s1[k] = '';
17         i = k = 0;
18         j++;
19     }
20 }
21 
22 int main()
23 {
24     char s1[10] = { 'a','b','c','d','e',0 };
25     char s2[10] = { 'a','c','e',0 };
26 
27     squeeze(s1, s2);
28     printf("%s
", s1);
29     return 0;
30 }

View Code

13、给定n个数，要求比较1.5n次同时找出最大值和最小值

分析：要求比较次数为1.5n，使用一般的逐个遍历每个元素然后判断其是否为最大最小值是需要2n次比较的。现在考虑采用，每次从数组中取出两个元素，判断其大小，然后再分别判断其是否是最大或最小值，这样一次处理两个元素，每一次比较3次，最终的比较次数就是n/2*3=1.5n。

Java实现：

package com.mian.demo;

public class FindMaxMin {
    public static void main(String[] args){
        int num[]={2, 4, 5, 6, 8, 3, 7, 1, 9, 10 };
        findMaxMin(num);
    }
    private static void findMaxMin(int[] arr){
        int size=arr.length;
        if(size==0||arr==null){
            return;
        }
        int max=Integer.MIN_VALUE;
        int min=Integer.MAX_VALUE;
        int i=0;
        int j=size-1;
        int tmin,tmax;
        int count=0;
        while(i<j){
            if(arr[i]<arr[j]){
                tmax=arr[j];
                tmin=arr[i];
                ++count;
            }else{
                tmax=arr[i];
                tmin=arr[j];
                ++count;
            }
            if(min>tmin){
                min=tmin;
            }
            if(max<tmax){
                max=tmax;
            }
            count+=2;
            ++i;
            --j;
        }
        System.out.println("The max number is "+max);
        System.out.println("The min number is "+min);
        System.out.println("Compare number is "+count);
    }
}

View Code

C++实现：

 1 #include<cstdio>
 2 #include<iostream>
 3 
 4 void find_max_min(int num[], int n)
 5 {
 6     int i = 0, j = n - 1;
 7     int max = INT_MIN;
 8     int min = INT_MAX;
 9     int tmax, tmin;
10     int count = 0; /*用来统计比较次数*/
11 
12     while (i < j)
13     {
14         if (num[i] < num[j])
15         {
16             tmax = num[j];
17             tmin = num[i];
18             ++count;
19         }
20         else
21         {
22             tmax = num[i];
23             tmin = num[j];
24             ++count;
25         }
26         if (min > tmin)
27             min = tmin;
28         if (max < tmax)
29             max = tmax;
30         count += 2; /*上面的两次比较*/
31         ++i;
32         --j;
33     }
34     printf("The max number is: %d.
", max);
35     printf("The min number is: %d.
", min);
36     printf("Compare number is: %d.
", count);
37 }
38 
39 int main()
40 {
41     int num[10] = { 2, 4, 5, 6, 8, 3, 7, 1, 9, 10 };
42     find_max_min(num, 10);
43 
44     return 0;
45 }

View Code

14、按照map的value进行排序，并按value有序输出

package com.mian.demo;

import java.util.*;

public class MapValueSort {
    public static void main(String[] args){
        Map<String,Integer> map=new HashMap<>();
        map.put("three",3);
        map.put("nine",9);
        map.put("zero",0);
        map.put("five",5);
        map.put("two",2);
        map.put("six",6);
        MapValueSort m=new MapValueSort();
        Map<String,Integer> res=m.mapValueSort(map);
        for(String key:res.keySet()){
            System.out.println(key+" "+res.get(key));
        }
    }
    private <T extends Comparable> Map<String,T> mapValueSort(Map<String,T> map){
        int size=map.size();
        if(size==0||map==null){
            return map;
        }
        List<Map.Entry<String,T>> list=new ArrayList<>();
        for(Map.Entry<String,T> entry:map.entrySet()){
            list.add(entry);
        }
        Collections.sort(list, new Comparator<Map.Entry<String, T>>() {
            @Override
            public int compare(Map.Entry<String, T> o1, Map.Entry<String, T> o2) {
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        LinkedHashMap<String,T> m=new LinkedHashMap<>();
//        Map<String,T> m=new HashMap<>();
//        Map<String,T> m=new TreeMap<>();
        for(Map.Entry<String,T> entry:list){
            m.put(entry.getKey(),entry.getValue());
        }
        return m;
    }
}

View Code

15、找出数组里出现次数超过总数1/3的数(可能存在一个也可能存在两个)

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res=new ArrayList<Integer>();
        if(nums==null||nums.length==0){
            return res;
        }
        int a=nums[0],cnta=0;
        int b=nums[0],cntb=0;
        for (int num : nums) {
            if (num == a) {
                ++cnta;
            }else if(num == b) {
                ++cntb;
            }else if(cnta == 0) {
                a = num;
                cnta=1;
            }else if(cntb == 0) {
                b = num;
                cntb=1;
            }else{
                --cnta;
                --cntb;
            }
        }
        cnta=0;
        cntb=0;
        for(int num:nums){
            if(num==a){
                ++cnta;
            }else if(num==b){
                ++cntb;
            }
        }
        if(cnta>nums.length/3){
            res.add(a);
        }
        if(cntb>nums.length/3){
            res.add(b);
        }
        return res;
    }
}

View Code