精华内容
下载资源
问答
  • 微软笔试题

    2021-01-30 17:20:13
    题目三 \quad给一个无向图,N个顶点,M条边,0为起点,N-1为终点,每条边初始权值为 1。图中除普通节点外有 4 种节点。 第一种:走过这种节点后的两条边权值翻倍(Sand) 第二种:走过这种节点后的两条边权值减半 ...

    题目三

    \quad给一个无向图,N个顶点,M条边,0为起点,N-1为终点,每条边初始权值为 1。图中除普通节点外有 4 种节点。

    • 第一种:走过这种节点后的两条边权值翻倍(Sand)
    • 第二种:走过这种节点后的两条边权值减半 (Nitro)
    • 第三种:走到这个节点就停止,不能再走了(Cop)
    • 第四种:走到这个节点,下一条边的权值+1(Crash)

    求节点 0 到 N-1 的最短权值和路径。

    输入样例:第一行为点数和边数;第二行为n个字符串表示这n个点的属性;接下来有m行,每行两个节点编号,表示这两个节点有一条无向边连接。
    7 8
    None Cop Sand None Nitro None None
    0 1
    0 2
    1 2
    2 3
    2 4
    3 6
    4 5
    5 6
    

    思路:直接爆搜求出所有0到n-1节点的路径(Cop类型的节点不予考虑),然后再一一计算路径,找出最短权值和路径。

    #include <iostream>
    #include <vector>
    #include <unordered_map>
    using namespace std;
    
    const int N = 110;
    vector<int> E[N];  // 邻接表存边
    unordered_map<int, string> attr;  // 记录节点属性
    vector<int> path;  // 存路径
    int vis[N];
    
    vector<int> res;
    double dis = 1e18;
    double calc(vector<int> &path){
    	double cost = 0.0;
    	int e = path.size() - 1; // 边数
    	vector<double> edgeWeight(e, 1.0);  // 初始化各个边的权值为1
    	for(int i = 0; i < e; i ++ ){
    		int node = path[i];
    		if(attr[node] == "Sand"){
    			edgeWeight[i] *= 2;
    			if(i + 1 < e) edgeWeight[i + 1] *= 2;
    		}
    		else if(attr[node] == "Nitro"){
    			edgeWeight[i] /= 2;
    			if(i + 1 < e) edgeWeight[i + 1] /= 2;
    		}
    		else if(attr[node] == "Crash"){
    			edgeWeight[i] += 1;
    		}
    	}
    	for(auto w: edgeWeight) cost += w;
    		return cost;
    }
    void dfs(int u, int end){
    	// 当这个点不是终点且属性是Cop时无法通过
    	if(u != end && attr[u] == "Cop") return;
    	path.push_back(u);
    	vis[u] = 1;
    	if(u == end){
    		double cost = calc(path);  // 计算这条路径的花费
    		if(cost < dis){
    			dis = cost;
    			res = path;
    		}
    	}
    	for(auto v: E[u]){
    		if(vis[v]) continue;
    		dfs(v, end);
    	}
    	path.pop_back();
    	vis[u] = 0;
    }
    int main(int argc, char const *argv[])
    {
    	int n, m; cin >> n >> m;  //点数和边数	
    	for(int i = 0; i < n; i ++ ){  // 读入节点属性
    		string s; cin >> s;
    		attr[i] = s;
    	}
    	for(int i = 0; i < m; i ++ ){
    		int u, v; cin >> u >> v;
    		E[u].push_back(v);
    		E[v].push_back(u);
    	}
    	dfs(0, n - 1);  // 起点和终点的所有路径
    
    	// 输出最小花费
    	cout << dis << endl;
    	// 输出最短路径
    	for(auto node: res) cout << node << " ";
    	return 0;
    }
    
    展开全文
  • Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式,... 用Dijkstra算法求解无向图的最短路径 - 潘建锋 | Mind Seeker​taohuawu.club微软编程比赛里面的一道难度系数5...

    fb162a1028f8213bbab2441f90093a71.png
    Dijkstra算法是典型的算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。      
    用Dijkstra算法求解无向图的最短路径 - 潘建锋 | Mind Seekertaohuawu.club

    微软编程比赛里面的一道难度系数5%的编程题目如下:

    bacb9ba51b1ecd2b61bc1189e85daf2f.png

    577fc602d01422b8ab2b39da7cb15766.png

    Dijkstra算法是用来求解图中顶点到另外其他顶点的最短路径的,根据题目,我们可以把每两个岛屿往来所花的最少金币当成图中的边权值,由此可以用Dijkstra算法来解决这个问题。

    19c8ee37a0300f42d7b96ed07b8ac7b3.png

    根据图来建立权值矩阵:

    int[][] W = { { 0, 1, , -1, -1, -1-1-1 -1}, { 1, 0, 3, 7, 5, -1-1-1-1}, { 5, 3, 0, -1, 1, 7, -1-1-1-1 }, { -1, 7, -1, 0, 2, -1,3-1-1 }, { -1, 5, 1, 2, 0, 3, 6, 9-1}, {-1-1-1, 36-1, 0 2, 7} {-1-1-1-1952, 0, 4} {-1-1-1-1-1-1, 7, 4, 0} };
    // (-1表示两边不相邻,权值无限大)
    

    最终实现如下(java):

    package wxt;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    
    //这个算法用来解决无向图中任意两点的最短路径  
    public class Dijkstra {
      public static int dijkstra(int[][] W1, int start, int end) {  
          boolean[] isLabel = new boolean[W1[0].length];// 是否标号  
          int[] indexs = new int[W1[0].length];// 所有标号的点的下标集合,以标号的先后顺序进行存储,实际上是一个以数组表示的栈  
          int i_count = -1;//栈的顶点  
          int[] distance = W1[start].clone();// v0到各点的最短距离的初始值  
          int index = start;// 从初始点开始
          int presentShortest = 0;//当前临时最短距离  
    
          indexs[++i_count] = index;// 把已经标号的下标存入下标集中  
          isLabel[index] = true;  
    
          while (i_count<W1[0].length) {  
              // 第一步:标号v0,即w[0][0]找到距离v0最近的点  
    
              int min = Integer.MAX_VALUE;  
              for (int i = 0; i < distance.length; i++) {  
                  if (!isLabel[i] && distance[i] != -1 && i != index) {  
                      // 如果到这个点有边,并且没有被标号  
                      if (distance[i] < min) {  
                          min = distance[i];  
                          index = i;// 把下标改为当前下标  
                      }  
                  }  
              }  
              if (index == end) {//已经找到当前点了,就结束程序  
                  break;  
              }  
              isLabel[index] = true;//对点进行标号  
              indexs[++i_count] = index;// 把已经标号的下标存入下标集中  
              if (W1[indexs[i_count - 1]][index] == -1 
                      || presentShortest + W1[indexs[i_count - 1]][index] > distance[index]) {  
                  // 如果两个点没有直接相连,或者两个点的路径大于最短路径  
                  presentShortest = distance[index];  
              } else {  
                  presentShortest += W1[indexs[i_count - 1]][index];  
              }  
    
              // 第二步:将distance中的距离加入vi  
              for (int i = 0; i < distance.length; i++) {  
                  // 如果vi到那个点有边,则v0到后面点的距离加  
                  if (distance[i] == -1 && W1[index][i] != -1) {// 如果以前不可达,则现在可达了  
                      distance[i] = presentShortest + W1[index][i];  
                  } else if (W1[index][i] != -1 
                          && presentShortest + W1[index][i] < distance[i]) {  
                      // 如果以前可达,但现在的路径比以前更短,则更换成更短的路径  
                      distance[i] = presentShortest + W1[index][i];  
                  }  
    
              }  
          }  
          //如果全部点都遍历完,则distance中存储的是开始点到各个点的最短路径  
          return distance[end] - distance[start];  
      }  
      private static class Island{
          public int x,y;
      }
      public static void main(String[] args) {  
          ArrayList<Island> arr=new ArrayList<Island>();
          // 建立一个权值矩阵  
    
          int [][] Test={
                  {0,1,4},{1,0,1},{4,1,0}
          };
          Scanner input=new Scanner(System.in);
          int num=input.nextInt();
          for (int i = 0; i < num; i++) {
              Island island=new Island();
              island.x=input.nextInt();
              island.y=input.nextInt();
              arr.add(island);
        }
          int [][] t=new int[num][num];
          for (int i = 0; i < t.length; i++) {
              for (int j = 0; j < t.length; j++) {
                t[i][j]=Math.min(Math.abs(arr.get(i).x-arr.get(j).x), Math.abs(arr.get(i).y-arr.get(j).y));
            }
    
        }
          System.out.println(dijkstra(t, 0,num-1));  
    
      }  
    }

    我是潘少,人生这么长,做个有趣的人,写点有趣的文字。此文章首发于我的个人公众号 - 潘建锋,欢迎关注,代码、故事、灵魂,那里都有。

    关于我mp.weixin.qq.com
    4da6d6833cf8222dd0cceeb47c5a0405.png
    展开全文
  • 一道微软笔试题

    2019-09-25 01:44:25
    上周末, 新鲜出炉的. ...题目不难, 不过按照微软一贯的作风, 这种题目的目的不是在于考察学生会不会写程序(当然, 要是写不出就不太好了), 而是在于考察学生是不是能够考虑到方方面面的问题, "于细微处见功...

    上周末, 新鲜出炉的.

    已知一个字符串, 只含常见可打印ascii字符以及空格和换行, 要求进行如下过滤:
    1, 过滤掉前导空白和后导空白;
    2, 中间的连续空白字符, 只保留一个;
    3, 删除换行前后的空白字符;

    题目不难, 不过按照微软一贯的作风, 这种题目的目的不是在于考察学生会不会写程序(当然, 要是写不出就不太好了), 而是在于考察学生是不是能够考虑到方方面面的问题, "于细微处见功力".

    本着"测试先行"的原则, 可以先从测试用例入手, 如下所示:

    // Test cases for leading & trailing spaces.
    char arr00[] = "hello_world";
    char arr01[] = "hello world";
    char arr02[] = "  hello world";
    char arr03[] = "hello world  ";
    char arr04[] = "  hello world  ";
    // Test cases for consecutive  spaces.
    char arr05[] = "hello    world";
    char arr06[] = "  hello    world  ";
    // Test cases for spaces around new-lines.
    char arr07[] = "hello  \n   world  ";
    char arr08[] = "  hello    world   \n ";
    char arr09[] = "\n  hello    world   \n ";
    // Corner cases
    char arr10[] = "   ";
    char arr11[] = "\n";
    char arr12[] = "  \n  ";
    

    更多的测试用例, 希望读者可以补充.

    有了这些测试用例, 再考虑如何实现. 从前往后走, 需要频繁地移动后面的内存, 不如从后往前走.

    完整代码如下:

    #include <stdio.h>
    #include <assert.h>
    #include <string.h>
    
    // Test cases for leading & trailing spaces.
    char arr00[] = "hello_world";
    char arr01[] = "hello world";
    char arr02[] = "  hello world";
    char arr03[] = "hello world  ";
    char arr04[] = "  hello world  ";
    // Test cases for consecutive  spaces.
    char arr05[] = "hello    world";
    char arr06[] = "  hello    world  ";
    // Test cases for spaces around new-lines.
    char arr07[] = "hello  \n   world  ";
    char arr08[] = "  hello    world   \n ";
    char arr09[] = "\n  hello    world   \n ";
    // Corner cases
    char arr10[] = "   ";
    char arr11[] = "\n";
    char arr12[] = "  \n  ";
    
    void filter_spaces(char *str, size_t len)
    {
        char *dst   = str + len - 1;
        char *curr  = str + len - 1;
    
        while (*curr == ' ' && curr >= str)
            --curr; // remove trailing spaces;
        if (curr < str) { // all spaces.
            *str = '\0';
            return;
        }
        int after_space = 0;
        int around_newline = 0;
        while (curr >= str) {
            switch (*curr) {
            case ' ':
                if (after_space) { // a space followed by another space, omit it.
                    --curr;
                } else if (around_newline) { // a space around a newline, omit it.
                    --curr;
                } else {
                    after_space = 1;
                    *dst-- = *curr--;
                }
                break;
            case '\n':
                around_newline = 1;
                if (after_space) { // remove last recorded space.
                    assert(*(dst + 1) == ' ');
                    ++dst;
                    after_space = 0;
                }
                *dst-- = *curr--;
                break;
            default: // other chars
                *dst-- = *curr--;
                after_space = 0;
                around_newline = 0;
                break;
            }
        }
        ++dst;
        if (*dst == ' ') // remove leading spaces.
            ++dst;
        // now the filtered string size is ( (str + size) - dst + 1 ),
        // including the trailing '\0'
        memmove(str, dst, (str + len) - dst + 1);
        
    }
    
    #define TEST_STR(str) do {\
        filter_spaces(str, strlen(str));\
        printf(#str ": \"%s\"\n", str);\
    } while(0);
    
    int main(int argc, char *argv[])
    {
        TEST_STR(arr00);
        TEST_STR(arr01);
        TEST_STR(arr02);
        TEST_STR(arr03);
        TEST_STR(arr04);
        TEST_STR(arr05);
        TEST_STR(arr06);
        TEST_STR(arr07);
        TEST_STR(arr08);
        TEST_STR(arr09);
        TEST_STR(arr10);
        TEST_STR(arr11);
        TEST_STR(arr12);
    
        return 0;
    }
    

    注意最后的memmove, 因为这两块内存可能是重叠(overlap)的, 所以memcpy或者strcpy都不可行.

    转载于:https://www.cnblogs.com/qsort/archive/2011/05/30/2063605.html

    展开全文
  • 微软笔试题 回忆(回文方面)

    千次阅读 2020-03-25 23:47:18
    这道当年我没有做出来,主要还是对动态规划掌握的不够熟练。 题目: 最少射击几次 N个瓶子都有编号,每次能射击1个或多个瓶子,如果是回文的就能一次性击倒。最少几次能全击倒? 测试 输入:[1, 2] 输出...


    这道题当年我没有做出来,今天微软笔试又碰到了类似的题目

    狠心要将这一块吃透

    主要还是对动态规划掌握的不够熟练。

     

    去年的题目: 最少射击几次

    N个瓶子都有编号,每次能射击1个或多个瓶子,如果是回文的就能一次性击倒。最少几次能全击倒?

     

    测试

    输入:[1, 2]

    输出:2

     

    输入:[1,3,4,1,5]

    输出:3

    说明:第一次先射3,变成[1,3,1,5],因为有[1,3,1]回文可以一次击倒,剩下[5]再一次

     

    解题思路:

    使用动态规划,我们可以将射击分为一系列子任务,用动态规划熟悉的表格表示,score[ i ] [ j ]表示要击倒 i 到 j 瓶子至少需要几次

    那么首先就可以知道score[0 ][0] 、score[1][1]、score[2][2] 、、、都为1(原因很显然,只有一个杯子,当然需要一次)

    接下来,就继续扩大范围,看两个两个杯子

    接下来是三个 三个

    一次递增

     

    我们可以看到 如果  第 j 个杯子 与 第 j + i个杯子相等

    那么 score[j][j+i] 就可以等于 scores[j + 1][j + i - 1] ,也就是夹在他们中间的一段(因为动态规划,规模小的已经最优)

    但是这里我们还需要考虑scores[j][j + k] + scores[j + k + 1][j + i] 这样的情况(也就是把整段切分为前后两段)

     

    综合以上思路,某位大佬的代码如下:

    参考代码:

    //
    //  main.cpp
    //  leetcodeTest
    //
    //  Created by Qiucheng LIN on 2020/3/25.
    //  Copyright © 2020 Qiucheng LIN. All rights reserved.
    //
    
    
    
    #include <vector>
    #include <climits>
    #include <iostream>
    using namespace std;
     
    int main() {
        int N = 8;
        vector<int> bottles = { 1,2,3,2,9,8,9,1 };
        
        vector<vector<int>> scores(N, vector<int>(N));
        for (int i = 0; i < N; i++)
        {
            scores[i][i] = 1;
        }
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < N - i; j++) {
                int min_score = INT_MAX;
                if (bottles[j] == bottles[j + i]) {
                    min_score = i > 1 ? scores[j + 1][j + i - 1] : 1;
                }
                for (int k = 0; k < i; k++) {
                    int temp = scores[j][j + k] + scores[j + k + 1][j + i];
                    if (temp < min_score) {
                        min_score = temp;
                    }
                }
                scores[j][j + i] = min_score;
                
            }
            
        }
        cout << scores[0][N - 1];
        return 0;
    }
    

     

     

    今年的题目:

    第二题也是关于回文的

    第二题:

    给一个字符串,每次可以移除其中一个字符,或者移除一个回文子串,求 全部移除所需最少次数

    例如:14315.先移除3,再移除141,再移除5,得到最少次数3.

     

    其实理解一下题意就会发现一模一样。

    展开全文
  • 1. 给定一个数组是t时刻的位移,找出所有连续的速度相等的时刻,要求t>=2 例子[-1,1,3,3,3,2,3,2,1,0] (0,2), (2,4),(6,9),(6,8),(7,9) 双指针,然后数学知识找规律。...2. 给定一个数组,数组中的元素范围是[1...
  • 微软笔试题编程实现

    2019-09-29 16:52:11
    在网上看到了一些微软笔试题,第一遍的做错了很多,自己就试着编程实现,其实是一些简单的题目。 下面这道:连续整数之和为1000的共有几组? 答案分析是这样的:首先1000为一个解。连续数的平均值设为x,1000...
  • 微软笔试题《Arithmetic Puzzles》题解,里面有详细答案
  • 本文主要介绍的是C语言位运算的一道题,这是微软笔试题中的一道比较简单的的题目,希望对于广大读者学习C语言有一些帮助。深入了解C语言小知识,看题讲程序作用: int func(x) { int countx =0; while(x) {...
  • 这个题是hiho一下第73周的一个题目,微软的一个笔试题,题目链接:点这里.这题代码量大,时间也挺短的,而且还要想出几种剪枝,要求挺高的.     题目: 给定一个由字母组成的等式,其中每一个字母表示一个数字。...
  • 17年微软笔试题

    2017-10-18 21:55:01
    #include #include #include #include #include #include using namespace std; /* * 儿子在父亲后面跟父亲一起跑步 * 父亲的起点在x,儿子的起点在y * 父亲速度为每步x米 * 父亲总共跑了 n steps ...* 儿子
  • 微软笔试题B.pdf

    2015-08-30 13:54:53
    微软笔试题B.pdf,答案在牛客网,自己做完对答案,0积分,免费下载!
  • 微软笔试题A.pdf

    2015-08-30 13:53:42
    微软笔试题A.pdf答案在牛客网,自己做完对答案,0积分,免费下载!
  • 算法题 94:前序中序遍历(微软笔试题) 题目:如果一个二叉树的前序遍历结果是abcdefg,下面哪一个是可能的中序遍历结果? A、abcdefg B、gfedcba C、bcdefga D、bceadfg **********************************...
  • MS interview question 微软笔试题,以前在微软里面搜集到的

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,604
精华内容 641
关键字:

微软笔试题