小米笔试热身战

本文主要是介绍小米笔试热身战，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

小米笔试热身战

有一个二维数组a[1...100 , 1...65]有100行，65列，我们以行序为主序，如果该数组的基地址是10000，且每个元素占2个存储单元，请问a[56 , 22]的存储地址是。注意是下标是从1开始的.
参考答案
17192
10000 + ((56 - 1) * 65 + （22-1）) * 2 = 17192
22减1，最后计算的是a[56.22]的起始地址，即a[56.21]的结束地址

运算（93&-8）的结果为
88
解析：

0101 1101&1000 1000的补码

0101 1101&1111 0111+1=0101 1101&1111 1000=0101 1000=88

he的平方=she。h、e、s代表的数字 1 2 3 。s,h,e不能为0.

1 2

2 5

3 6

代码：直接撸

public class Main {public static void main(String[] args) {for(int i = 10; i < 100; i++){int tem = (int)Math.pow(i,2);if(i == tem%100){System.out.println(i);break;}}}
}

两个人，A的速度为a，B的速度为b,在一直路上相向而行。在A、B距离为s的时候，A放出一个鸽子C，速度为c，C飞到B后，立即掉头飞向A，遇到A在掉头飞向B......就这样在AB之间飞来飞去，直到A、B相遇，假设a=40， b=60， c=400， s=100，这期间鸽子共飞行路程为

答案：400

A和B之间的距离是100，那话费的时间就是100/(40+60)=1,而鸽子的速度是400，那飞行路程就是400*1=400

世界上有10种人，一种懂二进制，一种不懂。那么你知道两个int32整数m和n的二进制表达，有多少个位(bit)不同么？

输入例子1:

1999 2299

输出例子1:

7code:

public class Solution {/*** 获得两个整形二进制表达位数不同的数量* * @param m 整数m* @param n 整数n* @return 整型*/public static int countBitDiff(int m, int n)  {String string  = Integer.toBinaryString(m);String string2  = Integer.toBinaryString(n);int len = string.length()-1;int len2 = string2.length()-1;int cnt = 0;while(len >= 0 && len2 >= 0) {if(string.charAt(len) != string2.charAt(len2)){cnt++;}len--;len2--;}while(len >= 0){if(string.charAt(len) == '1') {cnt++;}len--;}while(len2 >= 0){if(string2.charAt(len2) == '1') {cnt++;}len2--;}return cnt;      }
}

风口的猪-中国牛市
风口之下，猪都能飞。当今中国股市牛市，真可谓“错过等七年”。给你一个回顾历史的机会，已知一支股票连续n天的价格走势，以长度为n的整数数组表示，数组中第i个元素（prices[i]）代表该股票第i天的股价。假设你一开始没有股票，但有至多两次买入1股而后卖出1股的机会，并且买入前一定要先保证手上没有股票。若两次交易机会都放弃，收益为0。设计算法，计算你能获得的最大收益。输入数值范围：2<=n<=100,0<=prices[i]<=100

输入例子1:

3,8,5,1,7,8

输出例子1:

12题解：先动态规划算出从i到j的最大值，最后直接在二维数组里遍历找到符合条件的最大值。
把一排数切成两排或者说不切得出最大值。
code:


public class Main {public static void main(String[] args) {int [] prices = {2,3};System.out.println(calculateMax(prices)); }public static int calculateMax(int[] prices) {int sum = 0;int len = prices.length;int arr[][] = new int[len+1][len+1];for(int i = 0; i < len-1; i++){for(int j = i+1; j < len; j++){if(prices[j]-prices[i] > arr[i][j-1]){arr[i][j] = prices[j]-prices[i];}else{arr[i][j] = arr[i][j-1];}}}for(int i = 0; i <= len-2; i++) {for(int j = i+1; j <= len-1; j++){int  temp = arr[i][j] + arr[j+1][len-1];if(sum < temp){sum = temp;}}	 }return sum;}}

git是一种分布式代码管理工具，git通过树的形式记录文件的更改历史，比如： base'<--base<--A<--A' ^ | --- B<--B' 小米工程师常常需要寻找两个分支最近的分割点，即base.假设git 树是多叉树，请实现一个算法，计算git树上任意两点的最近分割点。（假设git树节点数为n,用邻接矩阵的形式表示git树：字符串数组matrix包含n个字符串，每个字符串由字符'0'或'1'组成，长度为n。matrix[i][j]=='1'当且仅当git树种第i个和第j个节点有连接。节点0为git树的根节点。）

解题思路：

多叉树寻找最近公共父节点问题

从矩阵构造出father数组，father数组保存每个节点的父节点。
记录从根节点到带求节点A和B的路径。
比较路径，找到最近的公共节点。
由于矩阵给的双向关系，构造father数组时，需要从根节点0开始，从上层往下层构造。
用双向队列记录根节点到本节点的路径，双向队列可以往对头加节点，也可以从对头取节点。

code:

import java.util.Queue;
import java.util.Deque;
import java.util.ArrayDeque;
public class Solution {/*** 返回git树上两点的最近分割点* * @param matrix 接邻矩阵，表示git树，matrix[i][j] == '1' 当且仅当git树中第i个和第j个节点有连接，节点0为git树的跟节点* @param indexA 节点A的index* @param indexB 节点B的index* @return 整型*/public int getSplitNode(String[] matrix, int indexA, int indexB) {if (indexA == indexB) return indexA;int len = matrix.length;// 构造一个father数组，存放每个节点的父节点int[] father = new int[len];// 标志数组int[] flag = new int[len];// 根节点的父节点为-1father[0] = -1;// 根节点 已经访问过flag[0] = 1;Queue<Integer> children = new ArrayDeque<>();children.offer(0);// 构造father数组，从根节点0开始while (!children.isEmpty()) {int parent = children.poll();char[] chars = matrix[parent].toCharArray();for (int i = 0; i < chars.length; i++) {if (flag[i] != 1 && chars[i] == '1') {// 设置父节点father[i] = parent;// 将其加入孩子队列children.offer(i);// 标记为 访问过flag[i] = 1;}}}int ia = indexA;int ib = indexB;// 记录从根节点到本节点的路径Deque<Integer> queueA = new ArrayDeque<>();Deque<Integer> queueB = new ArrayDeque<>();while (ia != -1) {queueA.addFirst(ia);ia = father[ia];}while (ib != -1) {queueB.addFirst(ib);ib = father[ib];}// 找到公共父节点int commonParent = 0;while (queueA.peekFirst() == queueB.peekFirst()) {commonParent = queueA.peekFirst();queueA.pollFirst();queueB.pollFirst();}return commonParent;}}

时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
给定一个句子（只包含字母和空格），将句子中的单词位置反转，单词用空格分割, 单词之间只有一个空格，前后没有空格。
比如：
（1） “hello xiao mi”-> “mi xiao hello”
输入
输入数据有多组，每组占一行，包含一个句子(句子长度小于1000个字符)
输出
对于每个测试示例，要求输出句子中单词反转后形成的句子

样例输入
hello xiao mi
样例输出
mi xiao hello

import java.util.Scanner;
public class Main {public static void main(String args[]){Scanner scan = new Scanner(System.in);while (scan.hasNext()) {String str = scan.nextLine();String[] ss = str.split(" ");System.out.print(ss[ss.length-1]);for (int i = ss.length - 2; i >= 0; i--) {System.out.print(" " + ss[i]);}System.out.println();        }scan.close();}
}

无意中逛知乎遇到的题，闲来没事试着敲下。
问题
“一副从1到n的牌，每次从牌堆顶取一张放桌子上，再取一张放牌堆底，
直到手里没牌，最后桌子上的牌是从第一张到最后一张的排列，梳理牌的排列顺序的算法。”

例如：
原数据：1 2 3 4 5
第一次：3 4 5 2 1
第二次：5 2 4 3
第三次：4 2 5
第四次：2 4
1,3,5,4,2

import java.util.Queue;
import java.util.Deque;
import java.util.ArrayDeque;
import java.util.Scanner;public class Main {public static void main(String[] args) {Deque<Integer> deque = new ArrayDeque<Integer>();Scanner in = new  Scanner(System.in);int n = in.nextInt();for(int i = 0; i < n; i++){deque.offer(in.nextInt());}StringBuffer str = new StringBuffer();while(deque.size() != 0){str.append(","+deque.peekFirst());deque.pollFirst();if(deque.size() != 0){Integer temp = deque.pollFirst();deque.offer(temp);}}System.out.println(str.substring(1));}}

code:

import java.util.Scanner;public class Solution {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while(scanner.hasNext()){int m = scanner.nextInt();TreeNode rootNode = new TreeNode(scanner.nextInt());createTree(rootNode, rootNode.val, scanner.nextInt());	for(int i=1;i<m-1;i++){createTree(rootNode, scanner.nextInt(), scanner.nextInt());}int height = getTreeHeight(rootNode);System.out.println(height);}scanner.close();}/*** 求树的高度* @param rootNode* @return*/private static int getTreeHeight(TreeNode rootNode) {if(rootNode==null){return 0;}int nLeft = getTreeHeight(rootNode.left);int nRight = getTreeHeight(rootNode.right);return (nLeft>nRight)?(nLeft+1):(nRight+1);}/*** 建树* @param root* @param father* @param childVal*/public static void createTree(TreeNode root,int father,int childVal){if(root==null){return;}if(root!=null && root.val==father){if(root.left==null){//左孩子为空即将其作为左孩子节点root.left = new TreeNode(childVal);}else{//作为右孩子节点root.right = new TreeNode(childVal);}return;}createTree(root.left, father, childVal);createTree(root.right, father, childVal);}
}/*** 对象： 树**/
class TreeNode{TreeNode left;TreeNode right;int val;public TreeNode(int val) {this.val = val;}}

直接dfs也是帅气的

#include<stdio.h>    
#include<iostream>    
#include<math.h>    
#include<stdlib.h>    
#include<ctype.h>    
#include<algorithm>    
#include<vector>    
#include<string.h>    
#include<queue>    
#include<stack>    
#include<set>    
#include<map>    
#include<sstream>    
#include<time.h>    
#include<utility>    
#include<malloc.h>    
#include<stdexcept>    
#include<iomanip>    
#include<iterator>    
#include<string>using namespace std;int n, ans;vector<int> a[101000];
void dfs(int u, int num)
{ans = max(ans, num);for (int i = 0;i < a[u].size();i++){int v = a[u][i];dfs(v, num + 1);}
}int main()
{while (scanf("%d", &n) != EOF){int u, v;for (int i = 0;i < 1010;i++)a[i].clear();for (int i = 1;i < n;i++){scanf("%d%d", &u, &v);a[u].push_back(v);}ans = 0;for (int i = 0;i < n;i++){dfs(i, 1);}printf("%d\n", ans);}return 0;
}

锻炼下java的编码能力，再来个java版本瞧瞧


import java.util.Scanner;
import java.util.Vector;public class Main {static int cnt = 0;public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();Vector<Vector<Integer>> vector =  new Vector<Vector<Integer>>();for(int i = 0; i < n; i++) {Vector<Integer> vector2  = new Vector<Integer>();vector.addElement(vector2);}int a = 0;int b = 0;for(int i = 0; i < n-1; i++) {a = in.nextInt();b = in.nextInt();vector.get(a).addElement(b);}for(int i = 0; i < n; i++){dfs(vector, i,1);}System.out.println(cnt);}public static void dfs(Vector<Vector<Integer>> vector, int u, int num){cnt = Math.max(cnt, num);for(int i = 0; i < vector.get(u).size(); i++){dfs(vector, vector.get(u).get(i), num + 1);}}
}

有n个1~23的整数，写一个算法，求出有多少个相互不同的子集合的和为24点。

输入描述:

输入数据包含一组
每组的第一行包括一个整数n(1 <= n <= 23)
第二行包括n个整数1 <= 整数 <= 23）
输出描述:

对于每个测试实例，要求输出能组成24点的所有子集合的数量（子集合相互不同）。如果不存在，则输出0。每个测试实例的输出占一行。

示例1

输入

4
1 2 22 23
输出

2

思路：直接递归


import java.util.Scanner;public class Main {static int  cnt = 0;public static void main(String[] args) {Scanner in = new Scanner(System.in); int n = in.nextInt();int arr[] = new int[n];for(int i = 0; i < n; i++) {arr[i] = in.nextInt();}d(arr,0,0, n);System.out.println(cnt);}public static void d(int arr[],int sum, int index, int len){if(sum > 24){return;}if(sum == 24){cnt++;return;}if(index == len){return;}d(arr, sum + arr[index], index+1, len);d(arr, sum, index+1, len);}}

三角形

设计一个整形三角形，三角形的每一行都比上一行多出一个数，每个数都等于它上方（如果有的话）与左上方两个数字之和，如下面所示：

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

。。。。。。

现在给你一个数，请算出它最开始出现在第几行。

输入：

一个正长整型数，保证为长整型的整数

输出：

这个数最开始出现的行数

样例输入：

1
4
10

样例输出：

1
5
6

code:

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n=in.nextInt();int[] a = new int[n+2];int pre=1;for(int i=1;i<=n+1;i++){ for(int j=1;j<=i+1;j++){ int cur=a[j];a[j]=pre+cur;  pre=cur;if(a[j]==n){System.out.println(i);return;}}}}
}

朋友圈问题-并查集解法

假如已知有n个人和m对好友关系（存于数字r）。如果两个人是直接或间接的好友（好友的好友的好友...），则认为他们属于同一个朋友圈，请写程序求出这n个人里一共有多少个朋友圈。
假如：n = 5，m = 3，r = {{1 , 2} , {2 , 3} , {4 , 5}}，表示有5个人，1和2是好友，2和3是好友，4和5是好友，则1、2、3属于一个朋友圈，4、5属于另一个朋友圈，结果为2个朋友圈。

// 简单的并查集应用
#include<stdio.h>
#include<stdlib.h>
int set[5];inline int find(int x)           //带路径优化的并查集查找算法
{int i, j, r;r = x;while (set[r] != r)r = set[r];i = x;while (i != r){j = set[i];set[i] = r;i = j;}return r;
}
inline void merge(int x, int y)     //优化的并查集归并算法
{int t = find(x);int h = find(y);if (t < h)set[h] = t;elseset[t] = h;
}int friends(int n, int m, int r[11][2])
{int i, count;for (i = 1; i <= n; ++i)    //初始化并查集，各点为孤立点，分支数为n set[i] = i;for (i = 0; i < m; ++i)merge(r[i][0], r[i][1]);count = 0;for (i = 1; i <= n; ++i){if (set[i] == i)++count;}return count;
}int main(void){/* int r[11][2] = { { 1, 5 }, { 3, 5 }, { 4, 5 }, { 1, 4 }, { 5, 6 }, { 8, 1 }, { 9, 20 }, { 98, 11 }, { 13, 76 }, { 98, 77 }, { 2, 1 } };*/int r[5][2] = { { 1, 2 }, { 2, 3 }, {4,5}};int i;for (i = 0; i < sizeof(r[5][2]) / sizeof(r[0]);i++){merge(r[i][0],r[i][1]);}printf("%d\n",friends(5, 3, r));system("PAUSE");return 0;
}

电话号码分身

题目描述

继MIUI8推出手机分身功能之后，MIUI9计划推出一个电话号码分身的功能：首先将电话号码中的每个数字加上8取个位，然后使用对应的大写字母代替

（"ZERO", "ONE", "TWO", "THREE", "FOUR",

"FIVE", "SIX", "SEVEN", "EIGHT", "NINE"），

然后随机打乱这些字母，所生成的字符串即为电话号码对应的分身。

import java.util.Scanner;public class Main {static int cnt = 0;public static void main(String[] args) {Scanner in = new Scanner(System.in);int T = in.nextInt();in.nextLine();while(T != 0) {String string = in.nextLine();StringBuffer sBuilder = new StringBuffer();int num[] = new  int[10];sBuilder.append(string);int tem = 0;while(sBuilder.length() != 0){if((tem = sBuilder.indexOf("Z")) != -1){sBuilder.deleteCharAt(tem);sBuilder.deleteCharAt(sBuilder.indexOf("E"));sBuilder.deleteCharAt(sBuilder.indexOf("R"));sBuilder.deleteCharAt(sBuilder.indexOf("O"));num[2]++;}else if((tem = sBuilder.indexOf("W")) != -1){sBuilder.deleteCharAt(tem);sBuilder.deleteCharAt(sBuilder.indexOf("T"));sBuilder.deleteCharAt(sBuilder.indexOf("O"));num[4]++;}else if((tem = sBuilder.indexOf("X")) != -1){sBuilder.deleteCharAt(tem);sBuilder.deleteCharAt(sBuilder.indexOf("S"));sBuilder.deleteCharAt(sBuilder.indexOf("I"));num[8]++;}else if((tem = sBuilder.indexOf("U")) != -1){sBuilder.deleteCharAt(tem);sBuilder.deleteCharAt(sBuilder.indexOf("F"));sBuilder.deleteCharAt(sBuilder.indexOf("O"));sBuilder.deleteCharAt(sBuilder.indexOf("R"));num[6]++;}else if((tem = sBuilder.indexOf("G")) != -1){sBuilder.deleteCharAt(tem);sBuilder.deleteCharAt(sBuilder.indexOf("E"));sBuilder.deleteCharAt(sBuilder.indexOf("I"));sBuilder.deleteCharAt(sBuilder.indexOf("H"));sBuilder.deleteCharAt(sBuilder.indexOf("T"));num[0]++;}else if((tem = sBuilder.indexOf("F")) != -1){sBuilder.deleteCharAt(tem);sBuilder.deleteCharAt(sBuilder.indexOf("I"));sBuilder.deleteCharAt(sBuilder.indexOf("V"));sBuilder.deleteCharAt(sBuilder.indexOf("E"));num[7]++;}else if((tem = sBuilder.indexOf("V")) != -1){sBuilder.deleteCharAt(tem);sBuilder.deleteCharAt(sBuilder.indexOf("S"));sBuilder.deleteCharAt(sBuilder.indexOf("E"));sBuilder.deleteCharAt(sBuilder.indexOf("E"));sBuilder.deleteCharAt(sBuilder.indexOf("N"));num[9]++;}else if((tem = sBuilder.indexOf("I")) != -1){sBuilder.deleteCharAt(tem);sBuilder.deleteCharAt(sBuilder.indexOf("N"));sBuilder.deleteCharAt(sBuilder.indexOf("N"));sBuilder.deleteCharAt(sBuilder.indexOf("E"));num[1]++;}else if((tem = sBuilder.indexOf("O")) != -1){sBuilder.deleteCharAt(tem);sBuilder.deleteCharAt(sBuilder.indexOf("N"));sBuilder.deleteCharAt(sBuilder.indexOf("E"));num[3]++;}else if((tem = sBuilder.indexOf("T")) != -1){sBuilder.deleteCharAt(tem);sBuilder.deleteCharAt(sBuilder.indexOf("H"));sBuilder.deleteCharAt(sBuilder.indexOf("R"));sBuilder.deleteCharAt(sBuilder.indexOf("E"));sBuilder.deleteCharAt(sBuilder.indexOf("E"));num[5]++;}}for(int i = 0; i <= 9; i++){for(int j = 0; j < num[i]; j++){System.out.print(i);}}System.out.println();T--;}}}

这里写图片描述