前言

2019去哪儿网春招笔试编程题，去哪儿网的春招笔试编程题还是挺难的，再做一遍，总结总结。

题目

找最短的转换序列

题目记不太清，大致是给一个初始单词和一个最终单词，同时给定一个单词列表，初始单词每次可以更改一个字母，找出最短的序列使得初始单词经过若干步转化为最终单词，并且转换的单词必须出现在单词列表中，存在的话，返回序列长度，否则返回0。

比如：
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

最短转换序列为： "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回 5.

注意：单词长度都是固定的，并且都是小写字母。

思路：用广度优先搜索～先将beginWord放入队列中，然后将队列中的每一个单词从头到尾换26个字母一遍～如果换后的单词在字典中能找到～而且没有被访问过～（如果每次都找访问过的就死循环啦，不停的变来变去变同一个咋办～）那就将这个单词放入队列中继续变换～直到有一次发现在字典中找到单词的时候，这个单词恰好是endWord为止～

很像二叉树的层次遍历，找到endword后，直接返回所在的层数。

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int length = 1;
        unordered_set<string> wordSet;
        for(auto iter = wordList.begin();iter!=wordList.end();++iter){
            wordSet.insert(*iter);
        }
        queue<string> sq;
        unordered_set<string> visitSet;
        sq.push(beginWord);
        while(!sq.empty()){   //队列不为空
            int size = sq.size();
            ++length;
            while(size--){
                string word = sq.front();
                sq.pop();
                for(int i=0;i<word.size();++i){
                    string newword = word;
                    for(int j=0;j<26;++j){
                        newword[i] = 'a' + j;
                        if(wordSet.find(newword)!=wordSet.end() && visitSet.find(newword) == visitSet.end()){  //存在且未被访问
                            if(newword == endWord) return length;
                            visitSet.insert(newword);
                            //加入到队列中
                            sq.push(newword);
                        }
                    }
                }
            }
        }
        return 0;
    }
};

第二题

题意：从给定数组中找到一组数字，要求这组数字之和等于target。另外，数组中的数字不允许被使用多次，但如果一开始就存在多个的话，可以使用多次。

比如给一个集合：[10,1,2,7,6,1,5] 和目标值8，输出

[1, 7]

[1, 2, 5]

[2, 6]

[1, 1, 6]

解题思路：显然先排序，然后dfs。其中有一点要注意的是：因为不能重复，所以要跳过一样的数字。以上面为例，如果不跳过重复的1的话，会出现多个：[1,7]。

递归流程图：以1,1,1,2为例，target = 3，输出[1,1,1]、[1,2];

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <unordered_set>
using namespace std;
void helper(vector<int> &candidates,int target,vector<int> &path,vector<vector<int>> &result,int start){
    int len = candidates.size();
    if(target==0){
        result.push_back(path);
        return;
    }
    for(int i=start;i<len;++i){
        if(i>start && candidates[i]==candidates[i-1]){  //避免再同一层中出现，去除重复
            continue;
        }
        if(target<candidates[i]) return;   //剪枝，目标值小于待遍历值时，不用继续往下搜寻了
        path.push_back(candidates[i]);
        helper(candidates,target-candidates[i],path,result,i+1);
        path.pop_back();
    }
}
vector<vector<int>> combinationSum(vector<int> &candidates,int target){
    vector<int> path;
    vector<vector<int>> result;
    sort(candidates.begin(),candidates.end());   //排序
    //递归
    helper(candidates,target,path,result,0);
    return result;
}
int main(){
    //所有的数都是正整数
    vector<int> candidates = {10,1,2,7,6,1,5};
    int target = 8;
    sort(candidates.begin(),candidates.end());
    vector<vector<int>> result = combinationSum(candidates,target);
    for(auto ivec : result){
        for(auto ele : ivec) cout<<ele<<" ";
        cout<<endl;
    }
    return 0;
}