Yongjin

Posted on In Disqus:

LeetCode 241 周赛

好久没写题解&总结了T^T

5759. 找出所有子集的异或总和再求和

dfs遍历

开始写的时候还在想怎么遍历数组的所有子集，后来憋了个dfs出来：

class Solution {
public:
    int calSubset(vector<int>& nums,int cur,int xorval)
    {
        if (cur >= nums.size())
            return 0;
        int sum = 0;
        xorval ^= nums[cur];
        sum += xorval;
        // 尝试选择后面的任意一个数字进行组合
        for (int i=cur+1;i<nums.size();i++)
            sum += calSubset(nums,i,xorval);
        return sum;
    }
    int subsetXORSum(vector<int>& nums) {
        int res = 0;
        // 子集可以从 [0,n) 任意数字开始
        for (int i=0;i<nums.size();i++)
            res += calSubset(nums,i,0);
        return res;
    }
};

后来看题解看到了两种很好的办法：

二进制枚举所有子集

  • 用一个长度等于数组长度的二进制数来表示子集的情况，这个二进制数的每一位对应数组每一位是取还是不取（取为1，不取为0）。
  • e.g. 1001 表示取数组的第一位和第四位
  • 这个二进制数的所有可能的取值与数组的所有子集是一一对应的，所以我们只需要从0枚举到1<<数组长度n
class Solution {
public:
    int subsetXORSum(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        // 枚举所有子集
        for (int i=0;i<(1<<n);i++)
        {
            // 枚举子集中要取的位置
            int cur = 0;
            for (int j=0;j<n;j++)
            {
                if (i & (1<<j))
                    cur ^= nums[j];
            }
            ans += cur;
        }
        return ans;
    }
};

数学方法

class Solution {
public:
    int subsetXORSum(vector<int>& a) {
        int t=0; 
        for (auto i:a)
            t|=i;
        return t<<(a.size()-1);
    }
};

5760. 构成交替字符串需要的最小交换次数

题意：将任意一个01字符串串转化为01必须相邻的字符串，可任意交换两个字符

  1. 先判断是否有解，有解的条件：
    1. 字符串长度为奇数：0和1的个数相差1
    2. 字符串长度为偶数：0和1的个数相等
  2. 求最小交换次数
    1. 我们不需要关心具体交换了哪两个字符，因为所有01都是等价的，可任意交换的。
    2. 目标字符串是已知的
      1. 字符串长度为奇数：”010…010” 或 “101…101”
      2. 字符串长度为偶数：”101…010” 或 “010…010”
      3. 所以无论字符串长度是奇数还是偶数，目标字符串只有两种：
        1. “0101…”
        2. “1010…”
    3. 我们只需要比较当前字符串与目标字符串不同的字符数量即可
      1. 因为每交换一次会使不同的字符数量 -2
      2. 如果不同的字符数量是奇数的话，那说明我们是无法得到这个目标字符串的
      3. 如果不同的字符数量是偶数的话，交换次数就是不同的字符数量/2
class Solution {
public:
    int minSwaps(string s) {
        int cnt1 = 0;
        int cnt0 = 0;
        int ans = 0;
        // 判断是否有解
        for (char ch:s)
        {
            if (ch == '0')
                ++cnt0;
            else
                ++cnt1;
        }
        if ((s.size() & 1) && !(abs(cnt0-cnt1)==1))
            return -1;
        if (!(s.size() & 1) && (cnt0 != cnt1))
            return -1;

        // 求最小交换次数
        // 求当前字符串与 "1010..." 的不同的字符数量
        int ans0 = 0;
        for (int i=0;i<s.size();i++)
        {
            char ch = (i&1)? '0':'1';
            if (s[i] != ch)
                ++ans0;
        }
        // 求当前字符串与 "0101..." 的不同的字符数量
        int ans1=0;
        for (int i=0;i<s.size();i++)
        {
            char ch = (i&1)? '1':'0';
            if (s[i] != ch)
                ++ans1;
        }
        // 因为每交换一次会使不同的字符数量-2
        // 如果不同的字符数量是奇数的话，那说明我们是无法得到这个目标字符串的
        // 如果不同的字符数量是偶数的话，交换次数就是不同的字符数量/2
        ans0 = (ans0 & 1)? s.size():(ans0>>1);
        ans1 = (ans1 & 1)? s.size():(ans1>>1);
        ans = min(ans1,ans0);
        return ans;
    }
};

5761. 找出和为指定值的下标对

  • 注意观察数据范围，用哈希表即可解决。
  • 先给nums1排序，这样在count()中当tot-x < 1时可以直接结束
class FindSumPairs {
public:
    vector<int> a,b;
    unordered_map<int,int> m;
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) : a(nums1),b(nums2){
        sort(a.begin(),a.end());
        for (int each:b)
            ++m[each];
    }
    
    void add(int index, int val) {
        --m[b[index]];
        b[index] += val;
        ++m[b[index]];
    }
    
    int count(int tot) {
        int res = 0;
        for (int x:a)
        {
            if (tot-x < 1)
                break;
            res += m[tot-x];
        }
        return res;
    }
};

5762. 恰有 K 根木棍可以看到的排列数目

  • 当时时间不太够，猜是斯特林数，去查了查觉得也不太像，于是就去吃饭啦

DP

  • 状态定义：f(i,j)表示用长度从1到i的木棍排成一排，从左侧可以看到恰好j根木棍的方案数
  • 最优子结构：
    • 如何证明？
  • 状态转移
    • f(i,j) = f(i-1,j-1) + (i-1)*f(i-1,j)
    • i-1 -> i j不变：在原i-1根木棍中插入，在原方案数上进行排列
    • i-1 -> i j-1 -> j：加入长度为i的木棍，让它排在最后面
class Solution {
public:
    typedef long long ll;
    ll f[1005][1005];
    int rearrangeSticks(int n, int k) {
        f[0][0] = 1;
        const ll mod = 1000000007;
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=i;j++)
            {
                f[i][j] = f[i-1][j-1] + (i-1)*f[i-1][j];
                f[i][j] %= mod;
            }
        }
        return f[n][k];
    }
};

斯特林数

Posted on In Disqus:

CSC3050 Project 1 MIPS Assembler & Simulator

This project implements a MIPS assembler and simulator in a single simulator.cpp file. The assembler and the simulator are designed separately so that each of them is supposed to work independently.

Code: https://github.com/doutv/MIPS-Assembler-Simulator

Ref:

Features

Nested class

Ref:

class Assembler
{
  public:
    inline static vector<string> data_seg;
    inline static vector<string> text_seg;
    inline static vector<string> output;
    class Scanner
    {
      Assembler &assembler;
    };
    class Parser
    {
      Assembler &assembler;
    };
}

Hash table mapping machine code to function pointer

Ref:

Hash table unordered_map<string, function<void(const string &)>> can replace numerous conditional statements (if else if).
In its generating function gen_opcode_to_func , std::bind should be used to locate the function pointer of the current Simulator instance. e.g.

// in void Simulator::gen_opcode_to_func(unordered_map<string, function<void(const string &)>> &m)
m.emplace("000100", bind(&Simulator::instr_beq, this, placeholders::_1));

Thus, the code is much more neater when calling the corresponding function.

// in void Simulator::exec_instr(const string &mc)
if (opcode == R_opcode[0] || opcode == R_opcode[1])
{
    // R instructions
    string funct = mc.substr(mc.size() - 6, 6);
    auto it = opcode_funct_to_func.find(opcode + funct);
    if (it == opcode_funct_to_func.end())
        signal_exception("function not found!");
    (it->second)(mc);
}

Throw exception instead of exit

Ref:

exit() will not go back through the call stack up to main cleaning everything up.
I define istream and ostream in main() function, if I call exit() during the program,
the streams cannot destruct properly, thus no output to files.

static void signal_exception(const string &err)
{
    throw invalid_argument(err);
}
// in main()
try
{
    if it should exit
    {
        signal_exception(exit_msg);
    }
}
catch (const exception &e)
{
    cerr << e.what() << endl;
}

Test multiple cases with makefile

Ref:

PROM = simulator
TEST_DIR = ./test
ASM_TESTS = 1 2 3 4 5 6 7 8 9 10 11 12 a-plus-b fib memcpy-hello-world
SIM_TESTS = a-plus-b fib memcpy-hello-world

.PHONY: all clean
.ONESHELL:

all: $(PROM) asm_test sim_test
    @echo "All tests passed!"

$(PROM): $(PROM).cpp
    g++ $(PROM).cpp -o $(PROM) -std=c++17

clean:
    rm $(PROM)
    rm $(TEST_DIR)/*.tasmout
    rm $(TEST_DIR)/*.out

asm_test: $(PROM)
    for t in $(ASM_TESTS); do \
        ./$(PROM) $(TEST_DIR)/$$t.asm $(TEST_DIR)/$$t.tasmout 2>&1; \
        diff -q $(TEST_DIR)/$$t.asmout $(TEST_DIR)/$$t.tasmout > /dev/null || \
        echo "Test $$t failed"; \
    done
    echo -e "All assembler tests passed!\n"


sim_test: $(PROM)
    for t in $(SIM_TESTS); do \
        ./$(PROM) $(TEST_DIR)/$$t.asm $(TEST_DIR)/$$t.in $(TEST_DIR)/$$t.out 2>&1; \
        diff -q $(TEST_DIR)/$$t.out $(TEST_DIR)/$$t.simout > /dev/null || \
        echo "Test $$t failed"; \
    done
    echo -e "All simulator tests passed!\n"

Tricks

  • Use fixed width integer types such as int32_t instead of int.
  • Get the maximum possible number of a data type, e.g. the maximum number for int16_t is numeric_limits<int16_t>::max()
  • Conversion between binary string std::string and integer int32_t
    • int to binary string: bitset<str_length>(int32_t_number).to_string()
    • binary string to int: stoi(str,nullptr,base=2)
  • Detect overflow by __builtin_add_overflow , __builtin_sub_overflow , __builtin_mul_overflow.
  • inline static Declare and initialize static member variables together in class.
    • https://www.zhihu.com/question/375445099
    • 在 C++17 加入了内联静态成员变量，只要在声明成员变量时， 在static前加入 inline，就能顺便定义了它，还可初始化它，这就不用在类外定义了。
  • static const Declare and initialize constant member variables in class.
  • #define , #ifdef , #endif Use C preprocessor to help debug.
  • Conversion between std::string and std::array
    • std::string -> std::array<char,size>
    • copy
    • word_t word;
string word_str = bitset<word_size>(get_regv(rt)).to_string();
copy(word_str.begin(), word_str.end(), word.data());
    • std::array<char,size> -> std::string
    • std::string constructor
    • word_t word = get_word_from_memory(addr);
string word_str(&word[0], word_size);

Posted on In Disqus:

非递减序列

https://leetcode-cn.com/problems/non-decreasing-array/

解题思路

解题关键是遇到$nums[i]>nums[i+1]$时，应该怎么处理？

  1. 找到第一处 $nums[i]>nums[i+1]$ ，改 $nums[i]$ 还是 $nums[i+1]$ 呢？
    1. 改 $nums[i]=nums[i+1]$ : 当且仅当 $nums[i-1]\leq nums[i+1]$ 时，因为需要保证 $nums[i-1] \leq nums[i] = nums[i+1]$
    2. 改 $nums[i+1] = nums[i]$ , $nums[i-1] \leq nums[i] = nums[i+1]$ 一定成立
    3. 然而我们应该优先改第一种情况 $nums[i]=nums[i+1]$ ，因为这样做是无后效性的，而第二种情况更改了 $nums[i+1]$ 的值，可能会破坏后面的单调递增序列，如这样一个序列： 1 100 2 3

代码

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int cnt=0;
        for (int i=0;i<nums.size()-1;i++)
        {
            if (nums[i]>nums[i+1])
            {
                if (cnt)
                    return 0;
                ++cnt;
                if (i==0)
                    continue;
                if (i>0 && nums[i-1]<=nums[i+1])
                {
                    nums[i]=nums[i+1];
                    continue;
                }
                nums[i+1]=nums[i];
            }
        }
        return 1;
    }
};

总结

分析完才发现这居然是一道贪心题。
做这种题不能面向用例测试，若是在面试时遇到这题我估计就凉了，简单题一点也不简单呀，不能小看简单题！我们需要认真拿出纸笔分析题目。

Posted on Disqus:

移动语义及拷贝优化

来源：

移动构造copy constructor和移动赋值move constructor

struct Foo {
  Foo() { cout << "Constructed" << endl; }
  Foo(const Foo &) { cout << "Copy-constructed" << endl; } // lvalue
  Foo(Foo &&) { cout << "Move-constructed" << endl; } // rvalue
  ~Foo() { cout << "Destructed" << endl; }
};

拷贝构造函数中是对传进来的对象进行了实实在在的拷贝工作；而移动构造函数中只是对传进来的对象进行了所有权的转让，即掏空传进来的对象，然后把所有权转给当前对象。

std::move

编译器只对右值引用才能调用转移构造函数和转移赋值函数，而所有命名对象都只能是左值引用。如果已知一个命名对象不再被使用而想对它调用转移构造函数和转移赋值函数，也就是把一个左值引用当做右值引用来使用，应该使用std::move，这个函数以非常简单的方式将左值引用转换为右值引用。

std::move的实现即使将一个对象强制转型为右值引用类型的对象而已，并不做任何移动工作。

拷贝优化Copy Elision

减少不必要的拷贝构造

  • RVO Regular Return Value Optimization:
    • If you return an object by value, the compiler is allowed to elude copying.
    • Foo f() {
return Foo();
}
  • NRVO Named Return Value Optimization: 
    • Foo f() {
    Foo foo;
    return foo;
}
  • Guaranteed copy elision
    • 为什么需要 Guaranteed copy elision ？因为要写 copy constructor 和 move constructor
    • The main problem is that, without guaranteed elision, you cannot get rid of the move and copy constructor, because elision might not take place.
    • https://zhuanlan.zhihu.com/p/22821671

类型转换

  • const_cast 转型掉（移除）常量性或易变性
  • static_cast 一般类型转换，用隐式和用户定义转换的组合在类型间转换
  • dynamic_cast 类指针转换，沿继承层级向上、向下及侧向，安全地转换到其他类的指针和引用
  • reinterpret_cast 强制转换，通过重新解释底层位模式在类型间转换

overload operator

参考：https://zh.cppreference.com/w/cpp/language/operators
pay attention to signatures and parameters

    • 复制赋值 copy assignment
      • T& T::operator=(const T&)
    • 移动赋值 move assignment
      • T& T::operator=(T&&)
  • +=
  • =

ub undefined behavior

Posted on In Disqus:

我最近一直在思索这个问题：为什么当代大学生&工作后年轻人似乎压力这么大？据我观察，GPA是压力的一大来源。我校不少人执着于GPA，甚至心情由GPA决定。
从现实角度出发：
不管是就业/授课型研究生/研究型研究生&博士，GPA都是一个重要的评价标准，所以如果自己现在不能确定毕业去向，那么卷GPA是最佳选择。

  • 如果选择了就业，以互联网行业为例，GPA就显得不那么重要了，实习&项目经历，技术水平这些会更加重要，混个3.0就好。
  • 如果选择了授课型研究生，那么GPA几乎是最重要的了。
  • 如果选择了走科研方向，读研究型研究生&博士，那么科研成果&科研能力更重要。

上大学后评价体系是变得多元化了，但是这也意味着我们需要在多个赛道上面与他人竞争：GPA，科研，比赛，活动，社会实践，实习，人际关系，身体&心理健康，甚至感情经历。

那么怎样才能走出竞争（卷）的怪圈呢？
在社会竞争愈演愈烈的当下，为了生存适当地竞争是有必要的，但是我觉得不能把人生意义寄托在外在事物（如GPA）之上，而应该寄托在一些自洽，超越的东西之上，那样我的人生意义就不依赖于外物，它是最高的，自我满足的。正如《尼各马可伦理学》中所言：Good must be the ultimate end or object of human life: something that is in itself completely satisfying. 每个人心中的good可能不一样，但是应该满足这个原则。
个人认为读哲学，了解不同的哲学思想，寻找自己的人生意义，或许会有一点帮助。通过了解不同的哲学思想，我可以从一个超越的角度去看待世界。时时刻刻用超越的角度来看待世界太难了，偶尔用用还是很好的。最近我喜欢上了老庄哲学，相对主义和道法自然太妙了。我是从实用主义的角度来读哲学的，不必全部采纳一派哲学思想，完全可以根据个人喜好挑选部分观点。读哲学还是一个动态发展的过程，5年前的我喜爱的哲学观点就跟现在不太一样。

诚然，在很多人看来人生意义只是活着的一个借口罢了，人还是活在现实中的，还是需要卷的。但找到意义后，会卷地更开心吧哈哈。

现在的我想当鲲鹏，退出卷的行列。然而我修为不够，不敢不做作业，不敢放弃GPA，不敢放弃读研的机会，不敢忍受物质的贫乏，不敢当一个自由职业者，不敢在25岁时辞职去旅游/换完全不同的工作，不敢放弃那“光明”的未来–这就是有所待吧。

Posted on In Disqus:

编译并导入Linux内核

reference:

  • 虚拟机硬盘空间要足够大，否则编译过程中空间会炸掉
  • 首次编译且安装的命令：
    sudo make mrproper 
sudo make clean 
sudo make menuconfig
sudo make -j4 
sudo make modules_install
sudo make install
reboot
  • 更改某些源文件后不需要重新编译：
    sudo make bzImage
sudo make modules_install
sudo make install
reboot
  • 按住shift键进入grub启动菜单选择内核

Posted on Disqus:

第一次技术面试

我的第一次技术面试献给了字节跳动。

考完期末考以后，可能觉得自己期末考考得太差了，GPA准备升天，再加上看清了学校CS课程的不足之处，所以想在其他方面证明自己的能力，于是想到了去找实习~

  • 第一个投的是腾讯，因为腾讯有员工班车接送，实习会比较方便，而且听说腾讯的工作强度相对较小，是我的理想公司之一。投了腾讯以后等了好几天没有回音，
  • 于是去投华为，想着我前几个月刚拿的华为软挑32强应该会有点用吧，说不定可以直接录取我，毕竟只是去实习而不是秋招。事实上华为回应也蛮快的，HR过几天就加我微信了，然而她告诉我现在是秋招的时间，日常实习生要到12月才开始招。
  • 最后我才想到了字节跳动，找到了在字节任职的一位学长，问了他一些职业发展相关的问题，他也给了我很多指导。在此也要感谢给我职场&人生指导的几位学长学姐，让我对将来发展的路径清晰了很多~谢谢你们！投了字节后几天就收到了HR电话约面试时间，我决定就约这几天的，不把这事情往后面拖了，再多准备一周时间也没必要。
  • 面试前根据学长的建议看了一下操作系统、计算机网络、数据库一些相关的知识点，但是我又不想像应试教育那样背下来，一方面是觉得这样对我的技术并无提升，另一方面如果面试官换一个问法/深入追问我照样答不出来。其实如果是从通过面试的角度来说，背知识点肯定是有用的，能够应付很多面试官的提问。我还刷了LeetCode上字节的几道算法题。
  • 其实整个面试的过程我觉得我个人还是比较放松的，能够放平自己的心态，和面试官以一种对话的方式去交流，和面试官的沟通也比较顺畅，但是嘛，就是自己的硬实力不足。
    • 第一道算法题没做出来，我后来上网搜了下这题，其实真的很有难度，440. 字典序的第K小数字，就算我不在面试环境下我也很难在短时间内想到正确的解法。
    • 第二道题是数据库相关的，给你一个业务需求，存储用户及订单信息，要求设计数据库结构及实现几个查询，如何用索引来优化查询？这题蛮好的，可惜我对数据库索引的了解几乎为零😂。
    • 还有以下问题：c++中static作用；http和https区别，ssl原理，非对称加密。
    • 最后还考了一道智力题：在岛上有100只老虎和1只羊，老虎可以吃草，但他们更愿意吃羊。如果每次只有一只老虎可以吃羊，而且一旦他吃了羊，他自己就变成羊；而且所有的老虎都是聪明而且完全理性的，他们的第一要务是生存。 请问最后这只羊会不会被吃？如果是n只老虎和一只羊呢？这道题我想到了它有点像递归，如果有一个老虎吃了羊，那么问题规模就缩小为99只老虎和1只羊。然而我以为没有一只老虎会吃羊，其实在想到递归以后，应该去找递归的初始状态，从底向上地推，1只老虎和1只羊->2只老虎和1只羊->…，这样就能发现规律了：如果老虎数目是奇数，那么羊肯定被吃，如果是偶数，那么羊肯定不会被吃。真的蛮有趣的
  • 其实面试完以后我是松了一口气的，对于面试的结果我早有预料，因为字节招实习生的标准和招正式员工的标准是一样的，我的确还有许多知识、技术要学，所以过面试反而是小概率事件。主要是来体验互联网大厂面试的流程，反正面试不用钱🐶。

Posted on Disqus:

博客折腾日记

主题

一次偶然的机会打开了别人的博客，它的界面很好看，于是我自己也想做一个。
他用的是hexo+next，我一开始用的主题是yilia，这个主题配置简单，就是有点丑，而且很久没更新了。
配置好后发现：文章预览有问题，主页展示了整篇文章，这个地方折腾了好久，有一天突然又能自动截断了……

但是后来我上Github找到一个非常好看的主题hexo-theme-matery，这个的配置教程超级好，基本都覆盖到了。
有一些没覆盖到的内容可以去Issues找或者搜索代码，比如：

  1. mathjax默认全局打开:/layout/post.ejs的最后一个if(xxx)改成if(1)即可

其实博客关键还是内容，内容为王，外观再漂亮也只是衬托罢了。

搜索引擎收录

Google

上Google Search Console，有多种验证方式来确认网站是归属你所有的。
我用了最简单的那种方式：在/public下加一个.html文件。

一个小技巧

将需要放在/public的文件放在/source下面，这样每次hexo d，这些文件都会自动复制到/public下面。

  • CNAME github自定义域名所需文件
  • googlexxxx.html google域名验证文件

从github pages转到腾讯云服务器

由于某些不可描述的原因，github pages被墙了，正逢腾讯云做活动，买了个100/年的小服务器做blog。

文章没了（感谢zjh的反馈）
通过Git钩子将hexo博客自动部署到ubuntu服务器：这篇文章写的很好，设置成功后，只需要hexo d就可以将博客自动部署到服务器上。在这里我补充一点我遇到的问题： 

git clone root@server_ip:/var/repo/hexo_static.git

这一步中会提示没有权限，但是我明明已经给服务器添加了密钥对，并将私钥保存到本地了啊，这是为什么呢？
在我的windows电脑上.ssh/config是这样的：

Host blog
    HostName 106.52.xxx.xxx
    User ubuntu
    IdentityFile C:\\Users\\Jason\\.ssh\\blog.pem

而且我用这条命令也是可以正常登录服务器的

ssh -o "IdentitiesOnly=yes" -i C:\\Users\\Jason\\.ssh\\blog.pem ubuntu@106.52.xxx.xxx

事实上这条命令与

ssh blog

是等价的，Host相当于给这个ssh配置起了一个别名

所以在_config.yml中

然而我发现备案太麻烦了，而且不能开留言功能，先放着吧呜呜。

hexo d 某些时候不好用的原因

明明我变更了文章内容，但是hexo d有时候并不会将它推送上去，目前推测到的原因是hexo不会识别某篇文章内部的变更，它只会跟踪有没有新增/减少文章。

这时候我们就需要hexo clean, hexo g, hexo d。

Posted on In Disqus:

TeaBreak网站后端笔记

TeaBreak是一个类知乎的校内问答网站，目前提供问答与文章功能。

我负责的是网站的后端，框架是django。我之前从未用过django，那就现学呗。
把django tutorial过一遍，了解了里面的一些概念和整个开发的流程。

设计数据库

  • 目标是做一个类知乎的问答网站
  • 先画ER Diagram，设计了user,question,answer,comment这几个表
  • 那评论别人的评论该怎么做呢？
  • 我上知乎查了一下这个问题，发现了解决方案，只要在comment中加一个外键reply_comment_id就好了
  • 在这个问题下面，我发现了另外一个问题：如何设计数据库使每个用户只能点赞/踩同一个回答/评论一次呢？
  • 参考了别人的回答，添加answer_vote来存储某个用户对某条回答的投票信息，comment_vote来存储某个用户对某条评论的投票信息。
  • 初步的数据库设计：
  • ER Diagram

django中建立ORM模型

django中的数据库在models.py中定义，用的是ORM。

遇到的一些问题及解决方案：

  • 用于分类的字段，如gender只有两个取值，该如何表示？可以使用Choices来显式定义:
    class Gender(models.TextChoices):
    MAN = 'M'
    WOMAN = 'W'
gender = models.CharField(max_length=1, choices=Gender.choices)
    Choices此处在纯后端的django中其实只起到了代码注释的作用，在生成的数据库语句中不会产生任何不同。也就是说，gender="A"也是可以的。
  • 外键（foreign key）中的on_delete该如何设置？
    • 这是一个有关设计哲学的问题
    • 对于on_delete的6种模式介绍，stackoverflow上面有精彩的回答
    • CASCADE是最严谨的模式，例如一个用户被删除了，那么他所有的回答和评论都会被删除，这样能最好地保证数据库的完整性（integrity）
    • SET_NULL能最好地保护数据不丢失，哪怕误操作删掉了一个用户，他所有的回答和评论都保存在数据库中，不会丢失。知乎上有时会看到“已注销用户”就是这个道理，虽然他的个人信息可能被永久删除了，但是他的回答和评论都保存在数据库中。（当然我不确定知乎是否采用了这种模式）
    • 我最后选择了SET_NULL：
      user_id = models.ForeignKey(User, on_delete=models.SET_NULL, null=True, db_column="user_id")

API Document

生成出的API文档十分美观
API Document Example

django前后端分离实践

django是自带前端界面的，但在我们的项目中，django只负责后端部分，前端用react完成。

由于我们项目较小，核心开发人员只有三人，我负责后端部分，另外两位同学负责前端，所以我们是一边完善API文档一边写程序的。后端只需要提供API，根据相应的请求返回对应的json。下面讲一些常用的函数/功能：

  • body_dict = json.loads(request.body.decode('utf-8')) 读取POST中的字段
  • dict.get python字典的get方法
  • models.save() 更改某个model后保存
  • get_object_or_404 获取单个符合条件的model
  • models.objects.filter 返回一个queryset包含符合条件的所有model

Convert Django Model object to dict

StackOverflow上面对这个问题的解答

我在项目中主要采用了2种方法：

  1. model_to_dict：返回特定列且不需要返回外键的场景中。
  2. StackOverflow上的custom functionto_dict：返回model的所有字段。

to_dict也可以只返回model的特定列，写法如下：

def to_dict(instance, except_fields=[]):
    opts = instance._meta
    d = {}
    for f in chain(opts.concrete_fields, opts.private_fields):
        if f.name in except_fields:
            continue
        d[f.name] = f.value_from_object(instance)
    for f in opts.many_to_many:
        if f.name in except_fields:
            continue
        d[f.name] = [i.id for i in f.value_from_object(instance)]
    return d

用户登录系统设计

用户成功登录后，用set_cookie方法将token（一串随机生成的字符串作为用户身份标识）放在用户的cookie中。在需要验证用户身份的场景中，只需要验证用户cookie中的token与数据库中该user_id对应的token是否相等即可，省去了每次登录的麻烦。token有过期时间，如果token过期了就相当于无效，用户需要重新登录获取新生成的token。

由于我并没有采用django中的身份验证模块，因此以下操作都需手动进行：生成token和过期日期expired_date，存储到数据库中，进行token比对。为了减少重复代码，我使用了装饰器来进行token比对：

def post_token_auth_decorator(api):
    @wraps(api)
    def token_auth(request):
        body_dict = json.loads(request.body.decode('utf-8'))
        user = get_object_or_404(User, user_id=body_dict.get("user_id"))
        if request.COOKIES.get("token") != user.token:
            raise Exception("token incorrect")
        if user.expired_date < datetime.now():
            raise Exception("token expire")
        return api(request)
    return token_auth

在需要验证用户身份的场景中，如所有的POST操作，只需要在API前加上@post_token_auth_decorator即可。事实上，POST的API使用了2个装饰器（注意先后顺序）：

@require_http_methods(["POST"])
@post_token_auth_decorator
def alter_user_info(request):

P.S. 装饰器教程，注意看下面的第一篇笔记

使用secrets库中的token_urlsafe方法生成token并set_cookie：

from secrets import token_urlsafe

user.token = token_urlsafe(TOKEN_LENGTH)
user.expired_date = datetime.now() + timedelta(days=TOKEN_DURING_DAYS)
response = HttpResponse({"message": "User register successfully"}, content_type='application/json')
response.set_cookie("token", user.token)

后端项目规范

随着我们团队开发人员的增多（前端2人+后端2人），提高协作效率显得尤为重要，为此我定义了后端项目规范。

后端工作流程workflow

  • 流程：API Document -> git checkout feature切换到feature分支进行开发 -> models.py -> views.py -> urls.py -> postman testing on localhost -> git commit & sync -> postman testing on cloud server这一步可以省略，一般在本地通过测试以后，服务器上应该也不会出现问题 -> 通过测试后将feature分支合并到master -> 上线部署 -> API Document
  • models.py数据库设计
    • 一般情况不需要更改，更改过多时迁移migrate会遇到错误，遇到错误的解决方法见Database。
  • views.pyAPI设计:
    • 大部分的工作会在这里完成。最好是先在API文档中定义好request和response。
    • 查django官方文档或者google解决，也可参考之前的代码，POST和GET两种接口的写法几乎是固定的。
  • urls.py后端路由:
    • 将views.py里面的函数映射到某个url上，一般在完成views.py后修改。
    • 小心两个url发生冲突。例如：api/handbook/<str:category>/<int:order>/与api/handbook/category/<str:category>/会发生冲突
  • 注意API文档要与views.py，urls.py同步更新。

git使用规范

  • 双分支管理：master+feature分支，master是服务器上跑的稳定版本，feature是开发中的不稳定版本，feature分支需要经过测试以及前后端沟通后才能发布到master分支。
  • commit信息要写完整，写详细，解决了某某需求，修复了某某bug，建议用中文来写，这样容易表达出自己的意思，如：API: 修改get_suggested_questions接口，按照问题下的回答的点赞总数从大到小排序。
  • 单次commit最好对应confluence中的一个需求，或是解决了一个bug。
  • 除了紧急修复运行中的bug，其他情况不要直接在服务器上面改代码，网站容易崩。

数据库注意事项

  • ⚠尽量不要直接操作数据库，而是通过已经写好的API来操作。
  • tips：下载mysql workbench来可视化管理数据库，进行敏感操作（更改/删除）时要小心。
  • /ciwkbe/settings.py里面选好数据库的.cnf文件
  • python manage.py makemigrations qa
  • python manage.py migrate qa
  • migrate迁移过程中发生错误怎么办？
    • 首先查看错误信息，常见的有：将某个字段改为unique时，由于该字段已经存在重复的数据，不满足unique constraint，数据库会报错。
    • 有些错误可以通过django的引导来更改，比如提供一个default值。
    • 而像上面所提到的错误则需要手动更改重复的数据，使该列满足unique constraint。
    • 有时候migrate进行了一部分，剩下另一部分由于出错而没有进行，或已经直接对数据库进行了相应更改。此时可以找到对应的迁移文件/qa/migrations/xxxx_auto_yyyy.py，手动将已经迁移的部分删除，再进行migrate。为了避免下次migrate因migrate不完整而出错，我的解决方法是：migrate全部完成后，将对应的迁移文件/qa/migrations/xxxx_auto_yyyy.py删除，再python manage.py makemigrations qa重新生成完整的迁移文件，然后通过该命令跳过该迁移python manage.py migrate qa xxxx --fake（xxxx是当次迁移文件的编号）

Posted on In Disqus:

Google KickStart Round E

这次做的有点菜😓

High Buildings

题意：构造一个以a[1]为首且长度为a的最长不下降序列，以a[n]为尾且长度为b的最长不上升序列，这两个序列的公共部分长度为c。

考场上不知道哪里的边界情况没处理好，而且没利用好不下降/不上升的一个性质：$a[i]\leq a[i+1]$，可以构造为$a[i]=a[i+1]$。以下代码参考自榜1。

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <unordered_map>
#include <string>
using namespace std;

typedef long long ll;

void solve()
{
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    int lena = a - c;
    int lenb = b - c;
    if (lena + lenb + c > n || (lena + lenb + c == 1 && n >= 2))
    {
        printf("IMPOSSIBLE\n");
        return;
    }
    if (n == 1)
    {
        printf("1\n");
        return;
    }
    if (n == 2)
    {
        if (c == 2)
            printf("1 1\n");
        else if (a == 2)
            printf("1 2\n");
        else if (b == 2)
            printf("2 1\n");
        return;
    }
    vector<int> ans;
    for (int i = 1; i <= lena; i++)
        ans.push_back(2);
    for (int i = 1; i <= c; i++)
        ans.push_back(3);
    for (int i = 1; i <= lenb; i++)
        ans.push_back(2);
    int extra = n - lena - lenb - c;
    if (extra)
        ans.insert(ans.begin() + 1, extra, 1);
    for (int i = 0; i < n; i++)
        printf("%d ", ans[i]);
    printf("\n");
}

int main()
{
    int T;
    cin >> T;
    cin.ignore();
    for (int caseNum = 1; caseNum <= T; caseNum++)
    {
        printf("Case #%d: ", caseNum);
        solve();
    }
    return 0;
}

Toys

这题想了一会正解，没想出来，又懒得写暴力，所以就没做了。看了正解之后发现，其实我已经想到一大半了……

如果一个toy不能无限玩：$R_i>\sum_{j\neq i}E_j=\sum_j E_j-E_i$，所以能无限玩的toy满足：$R_i+E_i\leq SUM$, where $SUM$ is the sum of all selected toys $E_i$.

最优解：每次尝试移除$R_i+E_i$最大的toy，因为如果移除其他的toy，such as $j$, $R_i+E_i>SUM$依然成立。

Posted on In Disqus:

1562. 查找大小为M的最新分组

参考自大佬的视频教程：https://www.bilibili.com/video/BV1Xp4y1v7Nj?p=4

  • 用并查集维护1的连通信息
  • 具体来说：f[i]表示i所在的连续1的代表节点的位置，这里我们选用的代表节点是连续一段1右侧第一个0的位置。思考题：为什么选这个位置呢？能否选其他位置呢？
  • 并查集维护额外信息：siz[i]维护的是某一段连续1的长度，该段代表节点为i。
  • cnt[i]维护siz[i]==i的数量，类似于桶排序，cnt[i]=3表示有3段连续1的长度为i。

code

const int M=1e5+5;
int f[M],siz[M],cnt[M];
class Solution {
public:
    int find(int x)
    {
        if (x!=f[x])
            f[x]=find(f[x]);
        return f[x];
    }
    int findLatestStep(vector<int>& arr, int m) 
    {
        int n=arr.size();
        for (int i=0;i<=n+1;i++)
        {
            f[i]=i;
            siz[i]=0;
            cnt[i]=0;
        }
        cnt[0]=n;
        int ans=-1;
        for (int i=0;i<n;i++)
        {
            int p=arr[i];
            f[p]=p+1;
            int fp=find(p);
            cnt[siz[p]]--;
            cnt[siz[fp]]--;
            siz[fp]=siz[p]+siz[fp]+1;
            siz[p]=0;
            cnt[siz[fp]]++;
            if (cnt[m])
                ans=i+1;
        }
        return ans;
    }
};

Posted on In Disqus:

5490. 吃掉 N 个橘子的最少天数

一道平平无奇的记忆化搜索题目，题面已经把递归方程给我们了。

现在的问题是$n\leq 2e9$，如何实现记忆化呢？这里可以用到$unordered_map$来存储状态，因为所需要的状态远远小于$2e9$，直接开一个$2e9$大小的数组是不可能的。

code

class Solution {
public:
    unordered_map<int,int> dp;
    int f(int n)
    {
        if (n==1)
            return 1;
        if (n==2||n==3)
            return 2;
        if (dp.find(n)!=dp.end())
            return dp[n];
        int res=min(f(n/2)+n%2+1,f(n/3)+n%3+1);
        dp[n]=res;
        return res;
    }
    int minDays(int n) {
        dp.clear();
        return f(n);
    }
};
0%