algo; xueke huawei interview

1

2

3

code fake

1. 全排列 递归

abbcd
bbacd
babcd

字符串的（所有可能的）排列组合 解法：

def perm(s=''):
    if len(s) <= 1:
        return [s]
    sl = []
    for i in range(len(s)):
        for j in perm(s[0:i] + s[i + 1:]):
            sl.append(s[i] + j)
    return sl


def main():
    # 可能包含重复的串
    perm_nums = perm('abb')
    # 对结果去重
    no_repeat_nums = list(set(perm_nums))
    print('perm_nums', len(perm_nums), perm_nums)
    print('no_repeat_nums', len(no_repeat_nums), no_repeat_nums)
    pass


if __name__ == '__main__':
    main()

# my_string 是一个字符list
res = []
def helper(my_string, current_position):
    if (current_position = len(my_string) - 1):
        res.append(my_string)
    else:
        for i in range(current_position, len(my_string) - 1):
            if isExist(my_string, current_position, i) is False:
                swap(my_string, current_position, i)
                helper(my_string, current_position + 1)
                swap(my_string, i, current_position)

    def isExist(your_string, cur, i):
        for k in range(cur, i) :
            if your_string[k] == your_string[i]:
                return True
        return False

2 字典序最小的字符串; 不会

3:最短路径 + 一个花费限制

floyd

A = [][]# 假设A里面 你已经读入 道路长度 （len)和 道路花费 (cost)
back_trace_path = [][]
def minPath(n: int):
    total_cost = 0
    for v in range(n):
        for i in range(n):
            for j in range(n):
                if (A[i][j].len > A[i][v].len + A[v][j].len):
                    A[i][j].len = A[i][v].len + A[v][j].len
                    back_trace_path[i][j] = v

    def go_back_the_min_path(u, v, your_back_trace_path):
        if your_back_trace_path[u][v] == 0:
            total_cost = total_cost + A[u][v].cost
        else: 
            mid_point = your_back_trace_path[u][v];
            go_back_the_min_path(u, mid_point, your_back_trace_path)
            go_back_the_min_path(mid_point, v, your_back_trace_path)

    go_back_the_min_path(1, N, back_trace_path)
    if total_cost < K:
        print(A[1][N])# 存在小于K 花费的 最短路径
    else:
        print("-1")

typedef struct          
{        
    char vertex[VertexNum];                                //顶点表         
    int edges[VertexNum][VertexNum];                       //邻接矩阵,可看做边表         
    int n,e;                                               //图中当前的顶点数和边数         
}MGraph; 

MGraph my_graph;

void 接受输入的c家家函数（）{
    int n, m; //有n，m 个输入吧
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int 路的这头，路的那头
        scanf()
        my_graph.edges[路的这头][路的那头] = 路的长度
    }
}

void Floyd(MGraph g)
{
 　　int A[MAXV][MAXV];
 　　int path[MAXV][MAXV];
 　　int i,j,k,n=g.n;
 　　for(i=0;i<n;i++)
    　　for(j=0;j<n;j++)
    　　{ 　　
             A[i][j]=g.edges[i][j];
         　　 path[i][j]=-1;
     　 }
 　　for(k=0;k<n;k++)
 　　{ 
      　　for(i=0;i<n;i++)
         　　for(j=0;j<n;j++)
             　　if(A[i][j]>(A[i][k]+A[k][j]))
             　　{
                   　　A[i][j]=A[i][k]+A[k][j];
                   　　path[i][j]=k;
              　 } 
    　} 
}