1.编写一个函数，将一个十六进制字符串转换成整数返回。
既然是编程，那我们就应该有个转换的思路，虽然jdk封装了很多常用的处理问题的方法，但我们应该自己理解理解。
public calss FeelTheBase{
public static int hexToDemcial(String hex){
int sum=0;
int n=0,length=hex.length();
char[] chhex=hex.toUpperCase().toCharArray();
for(int i=0;i<length;i++) {
if(chhex[length-i-1]>'9'&&chhex[length-i-1]<='F') {
switch(chhex[length-i-1]){
case 'F':
n=15;
break;
case 'E':
n=14;
break;
case 'D':
n=13;
break;
case 'C':
n=12;
break;
case 'B':
n=11;
break;
case 'A':
n=10;
break;
}
}else {
n=chhex[length-i-1]-'0';
}
sum+=n*(1<<(4*i));//主要就是这一段!!!
}
return sum;
}
public static void main(String[] args){
String str_hex="abc";
System.out.println("十六进制="+str_hex+"转十进制="+hexToDemcial(str_hex));
}
}
解释：代码很简单，我们主要来解释 “sum+=n(1<<(4*i))” 是什么意思。首先将十六进制转换成二进制（以abc为例）：
1010 1011 1100（'abc'的二进制）
不难计算abc的十进制：10*28(211+29) + 11*24(27+25+24) + 12*20(23+22)
通过计算，我们发现了一个规律，从最低4位开始的十六进制字符转换成十进制整数依次呈24倍率关系！
2.请设计一个类，该类在同一个进程中只能有一个实例，且该实例允许外部访问。
分析：很明显，这个就是设计模式中的单例模式，随手写下基本构造：
public class singleClass{
private static singleClass single = new singleClass();
public singleClass getSingleClass(){
return single;
}
}
3.编写一个函数，求一个数的二进制表示中位为1的个数，例如9的二进制表示为1001，位为1的个数为2。
分析：不知道出这个题寓意何为，看到求二进制我一下子就想到了Integer.toBinaryString()方法，但感觉这样做的话不对劲，这道题可能是要考察我们的转换思路，那好不多BB下面来敲敲敲代码：
public class BinaryQuestion {
public static void main(String[] args) {
}
/**
* @explain 使用除基倒取余法，依次将余数添加到字符串中
* @param num
* @return
*/
public static int radixDivide(int num) {
int n = 0;
StringBuilder str = new StringBuilder();
while(num!=0) {
str.append(num%2);
num=num/2;
}
char[] ch=str.toString().toCharArray();
for(char c : ch) {
if('1'==c)
n++;
}
return n;
}
/**
* @explain 直接使用Integer.toBinaryString()方法直接计算出二进制
* 快速，方便。
* @param num
* @return
*/
public static int sumOfOne(int num) {
String binary=Integer.toBinaryString(num);
char[] ch=binary.toCharArray();
int n=0;
for(char c : ch) {
if('1'==c)
n++;
}
return n;
}
/**
* @explain 我们知道，在计算机处理中，数都是二进制的，同时根据&（与运算）的方式，我们知道
* 0&0=0,0&1=0,1&1=1我们可以根据这个一位一位的将十进制的二进制求出来
* @param num int型 有32位
* @return
*/
public static String logicalShift(int num) {
StringBuilder bin=new StringBuilder();
//从最高位依次&1得到结果
for(int n=31;n>=0;n--)
bin.append((num>>>n&1));
return bin.toString();
}
}
4.给定一个整数数组（元素值不重复）和目标值，找出数组中两个和等于目标值的数（元素不能重复利用）
例如：数组nums=[1,2,5,7],目标值target=6 --->返回[0,2],因为nums[0]+nums[2]=6
思路:
一、既然是数组，先来最暴力的、野蛮的干法
即依次遍历，一个一个揪出来，那么这样来时间复杂度就为O（n^2）
二、哈希表
野蛮的方法在大数据的情况下，肯定时间会消耗不少，那我们就用空间来换时间，使用哈希表，因为哈希表的特性，查询的时间复杂度理想化下为O(1)，我们可以依次遍历数组nums，同时回过头判断哈希表里是否有我们想要的值(target-nums[i])，如果没有则将遍历过的数据nums[i]存放在哈希表中，否则取出目标，打印出结果。
代码如下：
public class Solution {
/**
* @title 暴力算法
* @param nums 目标数组
* @param target 目标值
* @return 在目标数组中的两个数位置的索引
* @summary 时间复杂度O(n^2),空间复杂度O(1)
*/
public static int[] twoSumViolence(int[] nums,int target) {
int[] result = new int[2];
for(int i=0;i<nums.length-1;i++) {
for(int j=i+1;j<nums.length;j++) {
if(target==nums[i]+nums[j]) {
result[0]=i;
result[1]=j;
return result;
}
}
}
return null;
}
/**
* @title 哈希表查找算法
* @param nums 要查找的数组
* @param target 目标数
* @return 元素下标数组
* @summary 时间复杂度O(n),空间复杂度O(n)
*/
public static int[] twoSumHashTable(int[] nums,int target) {
int[] result = new int[2];
Hashtable table=new Hashtable();
for(int i=0;i<nums.length;i++) {
if(table.containsKey(target-nums[i])) {
result[0]=(int) table.get(target-nums[i]);
result[1]=i;
return result;
}
table.put(nums[i],i);
}
return null;
}
public static void main(String[] args) {
int[] nums= {1,3,5,7,8,213,123,5,32,7345,234,345,1231,4324,9};
int target=16;
//使用暴力算法
int[] results_01=twoSumViolence(nums, target);
//使用哈希表
int[] result_02=twoSumHashTable(nums, target);
//打印结果
System.out.println(Arrays.toString(results_01));
System.out.println(Arrays.toString(result_02));
}
}
5.这里有 100 张写着数字 1~100 的牌，并按顺序排列着。最开始所有
牌都是背面朝上放置。某人从第 2 张牌开始，隔 1 张牌翻牌。然后第 2,4 , 6, …, 100 张牌就会变成正面朝上。
接下来，另一个人从第 3 张牌开始，隔 2 张牌翻牌（原本背面朝上
的，翻转成正面朝上；原本正面朝上的，翻转成背面朝上）。再接下来，又有一个人从第 4 张牌开始，隔 3 张牌翻牌。
像这样，从第 n 张牌开始，每隔 n－ 1 张牌翻牌，直到没有可翻动 的牌为止。
问：最后所有牌不再变动的时候，求所以背面朝上的号码。
用Java实现的代码
public class TurnOverCard {
public static void main(String[] args){
//getNumber01();
getNumber02();
}
/**
* @thinking 我们知道，牌一开始是背面朝上的，第一次翻牌正面朝上，第二次翻牌背面朝上，即对于同一张牌
* 翻了n次，n为奇数的时候是正面朝上，n为偶数的是背面朝上。所以对于此题的问题是找出被"翻了偶数次
* 的牌的号码"。
* 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
* 第一次（2起始） 0 2 0 4 0 6 0 8 0 10 0 12 0 14 0 16
* 第二次（3起始） 0 2 3 4 0 0 0 8 9 0 0 0 0 0 15 16
* 第三次（4起始） 0 2 3 0 0 0 0 0 9 0 0 12 0 0 15 0
* 第四次（5起始） 0 2 3 0 5 0 0 0 9 10 0 12 0 0 0 0
* .
* .
* .
* 通过观察，我们发现号码牌和翻牌的第几次起始位置有某种联系，比如号码牌6 ：以2、3、6作为起始翻牌才能够翻到号码牌6
* 如号码牌15 ：以3、5、15作为起始位置才能够翻到号码牌15
* 即对于号码牌的每一个约数（1除外，因为我们是从第2作为第一次起始位置）按照从小到大排序依次作为第几次翻牌的起始位置
* 就可以知道会不会翻到这个号码的牌了！！！
*
* 回到我们的问题，我们得出"翻了偶数次的牌的号码"作为结果---->可以再次得出号码牌约数为奇书数个（
* 因为还有1是任何正整数的约数）的为我们想要的结果，如果想到这就觉得结束了那就还是小年轻。
*
* 慢慢已经接近答案了，我们再次深入的思考下，我们随便找出约数个数为奇数的号码
* 例如：16 --->1 2 4 8 16
* 25 --->1 5 15
* 36 --->1 2 3 4 6 9 18 36
* 发现没，都是平方数！！！好嘛，结果等于直接口算！！！
*/
public static void getNumber02(){
int carSum=100;
int result=1;
while(result*result<=carSum){
System.out.print(result*result+" ");
result++;
}
}
/**
* @title 使用HashMap+遍历循环
* 时间复杂度O（n^2）
* 空间复杂度O(n)
*/
public static void getNumber01(){
//使用HasMap储存每张牌的状态和号码
HashMap cards=new HashMap();
//牌组默认是"false",即背面朝上
for(int i=1;i<=100;i++){
cards.put(i,"false");
}
//通过遍历根据要求改变牌的状态
for(int i=2;i<=100;i++) {
for (int j = i; j <= 100; j += i) {
if (cards.get(j).equals("false")) {
cards.replace(j, "true");
} else {
cards.replace(j, "false");
}
}
}
//遍历打印出背面朝上的牌的号码
for(int i=1;i<=100;i++){
if(cards.get(i).equals("false"))
System.out.print(i+" ");
}
}
}
6.假设要把长度为 n 厘米的木棒切分为 1 厘米长的小段，但是 1 根木
棒只能由 1 人切分，当木棒被切分为 3 段后，可以同时由 3 个人分别切
分木棒。
求最多有 m 个人时，最少要切分几次？
例如:n ＝ 8， m ＝ 3 时如下所示，切分 4 次就可以了。
== == == == | == == == == 第一次
== == | == == == == | == == 第二次
== | == == | == == | == == == 第三次
== == == == == == == | == 第四次
== == == == == == == == 最终切完结果
用Java实现的代码
public class DivideClub {
public static void main(String[] args){
System.out.println(getTimes(20,3,1));
System.out.println(getTimes02(20,3));
}
/**
* @thought 采用递归的思想
* @param length 木棒长度
* @param people 人的个数
* @param currents 木棒的个数
* @return 切了多少次
*/
public static int getTimes(int length,int people,int currents){
if(currents>=length){
return 0;
}else if(currents<people){
return 1+getTimes(length,people,currents*2);
}else{
return 1+getTimes(length,people,currents+people);
}
}
/**
* @though 反向思维，将厘米的木棒组合成length长度即可，
* 即people个人只要组合的长度为length长度
* @param length
* @param people
* @return
*/
public static int getTimes02(int length,int people){
int counts=0;
int currents=1;//当前木棒长度
while(currents<=length){
currents+=currents<people?currents:people;
counts++;
}
return counts;
}
}
7.面试题：如何在不使用循环的情况下，求出一个数的二进制中1的个数？
