算法

每日leetcode-213

  1. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
  偷窃到的最高金额 = 1 + 3 = 4 。

解答

直接用两个dp，一个表示在抢劫了第一家的情况下的（也就是不抢最后一家），另一个表示不抢第一家的情况下的，两个分别计算得到结果最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return nums[0];
        }
        auto dp = vector<int>(len, 0);
        auto dp_without_0 = vector<int>(len, 0);
        dp[0] = nums[0];
        dp[1] = max(dp[0], nums[1]);
        dp_without_0[1] = nums[1];
        for (int i = 2; i < len; i++) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
            dp_without_0[i] = max(dp_without_0[i - 1], dp_without_0[i - 2] + nums[i]);
        }
        return max(dp[len - 2], dp_without_0[len - 1]);
    }
};

另一个解答

可以降低空间复杂度，不用vector了，直接用两个变量来表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int rob(vector<int>& nums) {
        int len = nums.size();
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return nums[0];
        }
        int dp_pre = nums[0], dp_now = max(dp_pre, nums[1]);
        int dp_pre_without_0 = 0, dp_now_without_0 = nums[1];
        int temp;
        for (int i = 2; i < len; i++) {
            temp = max(dp_now, dp_pre + nums[i]);
            dp_pre = dp_now;
            dp_now = temp;
            temp = max(dp_now_without_0, dp_pre_without_0 + nums[i]);
            dp_pre_without_0 = dp_now_without_0;
            dp_now_without_0 = temp;
        }
        return max(dp_pre, dp_now_without_0);
    }
};
算法

每日leetcode-135

135. 分发糖果

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

  • 每个孩子至少分配到 1 个糖果。
  • 相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:

输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

解答

因为只需要看孩子和左右的人的大小关系，所以可以从左到右先过一遍，再从右到左过一遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int candy(vector<int>& ratings) {
        int len = ratings.size();
        vector<int> a(len, 1), b(len, 1);
        for (int i = 0; i < len - 1; i++) {
            if (ratings[i] < ratings[i + 1]) {
                a[i + 1] = a[i] + 1;
            }
        }
        for (int i = len - 1; i > 0; i--) {
            if (ratings[i] < ratings[i - 1]) {
                b[i - 1] = b[i] + 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < len; i++) {
            ans += max(a[i], b[i]);
        }
        return ans;
    }
};

时间和空间如下：

1
2
执行用时 :40 ms, 在所有 C++ 提交中击败了23.20%的用户
内存消耗 :19.8 MB, 在所有 C++ 提交中击败了5.06%的用户

一个数组

其实可以只用一个数组，不用开俩数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int candy(vector<int>& ratings) {
        int len = ratings.size();
        vector<int> a(len, 1);
        for (int i = 0; i < len - 1; i++) {
            if (ratings[i] < ratings[i + 1]) {
                a[i + 1] = a[i] + 1;
            }
        }
        int ans = a[len - 1];
        for (int i = len - 1; i > 0; i--) {
            if (ratings[i] < ratings[i - 1]) {
                a[i - 1] = max(a[i - 1], a[i] + 1);
            }
            ans += a[i - 1];
        }
        return ans;
    }
};

不过时间和空间没啥大的区别

官方题解中的常数空间

把大小看成是一座山，山底是1，山顶是左侧升高的个数和右侧下降的个数的最大值。

到底部之后就可以直接把之前的up和down都统计一下。

要特别注意平着的时候。

算法

每日leetcode-128

  1. 最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 *O(n)*。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 `[1, 2, 3, 4]。它的长度为 4。

https://leetcode-cn.com/problems/longest-consecutive-sequence/

简单解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        vector<tuple<int, int>> intervals;
        for (auto i = nums.begin(); i != nums.end(); i++) {
            bool ok = false;
            for (auto t = intervals.begin(); t != intervals.end(); t++) {
                if (get<0>(*t) == *i) {
                    ok = true;
                    break;
                }
                if (get<0>(*t) > *i) {
                    bool done_with_first = false;
                    if (t != intervals.begin()) { // 需要检查前一个
                        if (get<1>(*(t - 1)) == (*i) - 1) { // 前一个需要和这个数字合并
                            if (get<0>(*t) == (*i) + 1) { // 前面一个后面一个刚好加上数字合并
                                get<1>(*(t - 1)) = get<1>(*t);
                                intervals.erase(t);
                            } else { // 只把前面的和这个数字合并
                                get<1>(*(t - 1)) = *i;
                            }
                            done_with_first = true;
                        }
                        else if (get<1>(*(t - 1)) >= (*i)) {
                            // 已经有了，不用管了
                            done_with_first = true;
                        }
                    }
                    if (!done_with_first) {
                        // 前面的不用合并，检查后面的
                        if (get<0>(*t) == (*i) + 1) { // 后面一个刚好加上数字合并
                            *t = make_tuple(*i, get<1>(*t));
                        } else {
                            // 需要加上这个数字
                            intervals.insert(t, make_tuple(*i, *i));
                        }
                    }
                    ok = true;
                    break;
                }
            }
            if (!ok) {
                if (intervals.begin() != intervals.end()) {
                    if (get<1>(*(intervals.end() - 1)) == *i - 1) {
                        get<1>(*(intervals.end() - 1)) = *i;
                        continue;
                    }
                    if (get<1>(*(intervals.end() - 1)) > *i - 1) {
                        continue;
                    }
                }
                intervals.emplace_back(*i, *i);
            }
        }
        int ans = 0;
        for (auto t = intervals.begin(); t != intervals.end(); t++) {
            ans = max(get<1>(*t) - get<0>(*t) + 1, ans);
        }
        return ans;
    }
};

里面有几点要注意：

  1. 要注意新的数字和之前的interval的内容可以相连的时候（包括没有比这个数字大，但是可以和最后一个相连的情况）
  2. 要注意可以有重复的数字，比如[0,0,1,-1]

但是这样的话比较慢，如下：

1
2
执行用时 :28 ms, 在所有 C++ 提交中击败了15.55%的用户
内存消耗 :12.2 MB, 在所有 C++ 提交中击败了5.04%的用户

好的解答

官方题解的做法，直接将所有数字加到HashSet里面，对每个数字：

  • 如果比他小1的在这个set里面，就不用找了；
  • 找从它开始连续增加1的序列的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> numbers;
        for (auto i = nums.begin(); i != nums.end(); i++) {
            numbers.insert(*i);
        }
        int ans = 0;
        for (auto i = numbers.begin(); i != numbers.end(); i++) {
            if (numbers.find(*i - 1) != numbers.end()) {
                continue;
            }
            int cur = *i;
            int len = 1;
            while (numbers.find(cur + 1) != numbers.end()) {
                cur++;
                len++;
            }
            ans = max(len, ans);
        }
        return ans;
    }
};
算法

每日leetcode-面试题-04-08-

面试题 04.08. 首个共同祖先

设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

1
2
3
4
5
6
7
    3
   / \
  5   1
 / \ / \
6 2 0 8
  / \
 7   4

示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输入: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* tNode = NULL;

    int checkRoot(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (tNode || !root) {
            return 0;
        }
        int base = 0;
        if (root == p) {
            base = 1;
        }
        if (root == q) {
            base = 2;
        }
        int ans = base + checkRoot(root->left, p, q) + checkRoot(root->right, p, q);
        if (ans == 3 && !tNode) {
            tNode = root;
        }
        return ans;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        tNode = NULL;
        checkRoot(root, p, q);
        return tNode;
    }
};

其实没有必要去判断这个节点下面有左还是右还是都有，有一个更简单的做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 返回最低的共同祖先，如果p和q中只有一个元素在下面的话就返回这个元素
        if (!root) {
            return NULL;
        }
        if (root == p || root == q) { // 如果root就是p或者q，就说明root是共同祖先或者是p和q本身
            return root;
        }
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left && right) {
            return root;  // 共同祖先
        }
        if (left) {
            return left;
        }
        if (right) {
            return right;
        }
        return NULL;
    }
};

直接来判断可能是首个共同祖先。这个节点本身是p或者q的话，他就可能是首个共同祖先；如果左右子树里面不同时有p或者q的话，就肯定不是第一个共同祖先了。

另一种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 返回最低的共同祖先，如果p和q中只有一个元素在下面的话就返回这个元素
        if(root == nullptr || root == p || root == q) return root;
        TreeNode *left = lowestCommonAncestor(root->left,p,q);
        TreeNode *right = lowestCommonAncestor(root->right,p,q);
        if(left && right) return root;
        if(left) return left;
        return right;
    }
};

如果要返回NULL的时候返回root自己，也不会有影响。

使用—软件—Django

django-一些网址资源

admin显示

https://www.runoob.com/django/django-admin-manage-tool.html

https://www.cnblogs.com/liu--huan/articles/10548050.html

分页

https://www.cnblogs.com/donghaiming/p/11007505.html

filter 或关系

https://blog.csdn.net/guan__ye/article/details/80053744

manytomany

https://www.cnblogs.com/lovershowtime/p/11361198.html

要加上一定属性的话

使用through

https://blog.csdn.net/zhaoyingm/article/details/8652471?utm_source=distribute.pc_relevant.none-task

修改后直接migrate是不行的

需要先删除这个字段做migrate，之后再加上做一次

https://my.oschina.net/bestraven/blog/870562

去重

.distinct()

https://www.jianshu.com/p/49d3dc15dd06

使用—软件—Django

django简单服务流程

由于一些很扯淡的兼容性问题，用的是1.11的django，不过这几个命令好像一直没有变。

创建项目

django-admin startproject HelloWorld

https://www.runoob.com/django/django-first-app.html

创建model

先创建app：django-admin startapp TestModel

再接下来在settings.py中找到INSTALLED_APPS这一项，添加上创建的app

做makemigrations和migrate的操作。

https://www.runoob.com/django/django-model.html

RESTFUL API禁用csrf

注释掉setting里的

1
# 'django.middleware.csrf.CsrfViewMiddleware',

https://www.jianshu.com/p/f69b241e0894?utm_source=oschina-app

login使用

django自带的user类的基础上，修改变成自己的user类

1
2
3
4
5
6
7
8
9
10
from django.contrib.auth.models import AbstractUser


class UserProfile(AbstractUser):
    class Meta:
        verbose_name = "个人信息"
        verbose_name_plural = verbose_name

    def __str__(self):
        return self.username

之后再在setting里面加上AUTH_USER_MODEL = 'info.UserProfile', 这里的info是自己的app名字

JSON形式登录退出验证及错误情况处理

view文件里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
from django.shortcuts import render
from django.http import HttpResponse
from info.consts import StatusCode
from functools import wraps
from info.models import *
from django.contrib import auth
import json


# Create your views here.


def response_json(o):
    return HttpResponse(json.dumps(o, ensure_ascii=False), content_type="application/json,charset=utf-8")


# 做一个装饰器方便后面进行登录状态监测
def login_required_json(f):
    @wraps(f)
    def inner(request, *arg, **kwargs):
        try:
            if request.user.is_authenticated:
                return f(request, *arg, **kwargs)
        except:
            pass
        return response_json({
            'code': StatusCode.NEED_LOGIN_ERROR,
            'msg': "请先登录",
            'data': {}
        })

    return inner


def param_error_json(msg="参数或者方法错误"):
    return response_json({
        'code': StatusCode.WRONG_PARAM,
        'msg': msg,
        'data': {}
    })


def response_ok_json(data):
    return response_json({
        'code': StatusCode.OK,
        'msg': '',
        'data': data
    })


def login(request):
    if request.method == "POST":
        try:
            username = request.POST.get('username')
            password = request.POST.get('password')
        except:
            return param_error_json()

        user = auth.authenticate(username=username, password=password)
        if user:
            # 验证成功 登陆
            auth.login(request, user)
            return response_ok_json({
                "type": "login",
                "authority": request.user.is_superuser
            })
        return param_error_json('用户名或密码错误，请重试')
    return param_error_json()

@login_required_json
def logout(request):
    if request.method == "POST":
        auth.logout(request)
        return response_ok_json({
            "type": "logout"
        })
    return param_error_json()

consts文件里面是这样的：

1
2
3
4
5
6
class StatusCode:
    OK = 0
    NEED_LOGIN_ERROR = 1
    INTERNAL_ERROR = 2
    AUTH_FAILED = 3
    WRONG_PARAM = 4

postman测试

正常发送测试就行，注意密码其实是加密存储的，所以创建用户的时候可以用createsuperuser指令，也可以用model的create_user函数。不能直接操作数据库放进去。

https://blog.csdn.net/check2255/article/details/70338497

POSTMAN的时候注意，因为是post方法，所以参数是写在Body而不是Param里面的。

POSTMAN

算法

每日leetcode-126

给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:

如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:

输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

输出:
[
[“hit”,”hot”,”dot”,”dog”,”cog”],
  [“hit”,”hot”,”lot”,”log”,”cog”]
]
示例 2:

输入:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

输出: []

解释: endWord “cog” 不在字典中，所以不存在符合要求的转换序列。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-ladder-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

一个简单的BFS。

每一轮检查上一轮的时候加进去的单词的相邻单词，发现没有检查过的就加进去。

直接用两个变量存储每一轮加进去的点和剩下的单词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Solution {
public:
    bool is_change_one(const string& a, const string& b) {
        int lena = a.size();
        int diff = 0;
        for (int i = 0; i < lena; i++) {
            if (a[i] != b[i]) {
                diff += 1;
            }
        }
        return diff == 1;
    }

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        int all_size = wordList.size();  // wordList
        map<string, vector<vector<string>>> shortest_record;
        vector<vector<string>> temp;
        vector<string> t2;
        t2.push_back(beginWord);
        temp.push_back(t2);
        shortest_record[beginWord] = temp;

        // start node
        set<string> available;  // 没有处理的
        set<string> lasttime; // 上次的单词
        lasttime.insert(beginWord);
        bool end_in = false;
        for (auto i = wordList.begin(); i != wordList.end(); i++) {
            available.insert(*i);
            if (*i == endWord) {
                end_in = true;
            }
        }
        
        if (!end_in) {
            return vector<vector<string>>();
        }

        while (!lasttime.empty()) {
            bool got_ans = false;
//            cout << "\nLasttime: ";
//            for (auto tt = lasttime.begin(); tt != lasttime.end(); tt++) {
//                cout << " " << *tt;
//            }
//            cout << "\nAva: ";
//            for (auto tt = available.begin(); tt != available.end(); tt++) {
//                cout << " " << *tt;
//            }
//            cout << "\n======";
            vector<vector<string>> result;
            for (auto cand = lasttime.begin(); cand != lasttime.end(); cand++) {
                if (is_change_one(*cand, endWord)) {
                    got_ans = true;
                    vector<vector<string>> &a = shortest_record[*cand];
                    for (auto ttt = a.begin(); ttt != a.end(); ttt++) {
                        result.push_back(vector<string>(*ttt));
                        (*(result.end() - 1)).push_back(endWord);
                    }
                }
            }
            if (got_ans) {
                return result;
            }
            set<string> new_lasttime;
            set<string> new_available;
            for (auto now = available.begin(); now != available.end(); now++) {
                bool got_ans = false;
                vector<vector<string>> result;
                for (auto cand = lasttime.begin(); cand != lasttime.end(); cand++) {
                    if (is_change_one(*cand, *now)) {
                        got_ans = true;
                        vector<vector<string>> &a = shortest_record[*cand];
                        for (auto ttt = a.begin(); ttt != a.end(); ttt++) {
                            result.push_back(vector<string>(*ttt));
                            (*(result.end() - 1)).push_back(*now);
                        }
                    }
                }
                if (got_ans) {
                    shortest_record[*now] = result;
                    new_lasttime.insert(*now);
                }
                else {
                    new_available.insert(*now);
                }
            }
            available = move(new_available);
            lasttime = move(new_lasttime);
        }
        return vector<vector<string>>();
    }
};

但是用了一秒多。

24ms的示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    vector<vector<string>> res;
    unordered_map<string, vector<string>> hash;
    
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> dirc(wordList.begin(), wordList.end());
        if (dirc.find(endWord) == dirc.end()) return res;
        unordered_set<string> beginw{beginWord};
        unordered_set<string> endw{endWord};
        int flag1 = 0, flag2 = 0;  //第一个是否找到最短序列标志, 第二个是否反转标志。
        
        while (!beginw.empty()) {
            unordered_set<string> tmp;
            for (auto str : beginw) dirc.erase(str);
            for (auto str : beginw) { //每次都是对beginw进行操作，所以后面有判断让beginw比endw小
                for (int i = 0; i < str.size(); ++i) {
                    string s = str;
                    for (char j = 'a'; j <= 'z'; ++j) {
                        s[i] = j;
                        if (dirc.find(s) == dirc.end()) continue;  // 在候选里面没有现在判断的这个可能的下一个
                        if (endw.find(s) != endw.end()) flag1 = 1;// 已经到头了
                        else tmp.insert(s);// 接下来就是从这个开始进行搜索
                        flag2 ? hash[s].push_back(str) : hash[str].push_back(s);// 记录一下前后关系  // 刚开始flag2是0，所以刚开始的时候是把s记录在str的里面
                    } 
                }
            }
            if (flag1) break;  //已经找到最短序列退出循环。
            if (tmp.size() <= endw.size()) // 判断让beginw比endw小
                beginw = tmp;
            else {
                beginw = endw; endw = tmp; 
                flag2 = !flag2;  //这里需要使用！反转。
            }
        }
        vector<string> ans = {beginWord};
        dfs(ans, beginWord, endWord);
        return res;
    }
    
    void dfs(vector<string>& ans, string& begin, string& end) {
        if (begin == end) {
            res.emplace_back(ans);
            return;
        }
        if (hash.find(begin) == hash.end()) return;
        for (auto str : hash[begin]) {
            ans.emplace_back(str);
            dfs(ans, str, end);
            ans.pop_back();
        }
    }
};
  1. 用了unordered_set而不是set，区别可以见https://cloud.tencent.com/developer/article/1338333，性能上差的还是挺多的
  2. 构造函数可以直接用unordered_set dirc(wordList.begin(), wordList.end());，不必写个for循环来整；
  3. 两个方向进行操作，让比较少的一头开始；
  4. unordered_set进行find操作是很快的
  5. 记录的时候没有必要记录到这个节点的全部路径，只用记录下来从上一个节点的路径就可以了，最后用一个深搜就行（因为现在最多的能连上的层数就是最短的，不会有更长的能连起来的）
语言—Python

list和set运行效率

list和set中进行增加、减少的操作都是比较消耗资源的，所以尽量定长

Leetcode 204，计数小于n的质数有多少个：

用set来写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def countPrimes(self, n: int) -> int:
        data = set(range(2, n))
        primes = set()
        while data:
            t = data.pop()
            primes.add(t)
            if t ** 2 > n:
                break
            for i in range(2, n // t + 1):
                try:
                    data.remove(i * t)
                except:
                    pass
        return len(primes) + len(data)

用list来写：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        l = [1] * n      # l为记录1至n-1是否为质数的列表
        l[0] = l[1] = 0       # 0和1不是质数
        for i in range(2, int(n ** 0.5) + 1):
            if l[i] == 1:           # 若i为质数
                l[2*i:n:i] = [0] * ((n - i - 1) // i)    # i的整数倍都不是质数
        return sum(l)

时间差别很大。后者显著要快。