Posted on | Edited on | In |

对Linux的引导方式等不是很了解，终于还是付出了一晚上折腾的代价。

编译内核

按照Ubuntu Documentation上走，https://wiki.ubuntu.com/KernelTeam/GitKernelBuild。

每一步都比较清楚吧，1-11步走下来基本没有碰到问题。

唯一一个问题在于，make时，选核的数量2、3都不可以，这一点还是不解。

GRUB相关使用

本来引导不会去折腾它，但是装完的Linux 4.14.0-rc5似乎不支持IPV4，这很难过，想换回去。于是，去改grub。

GRUB配置方式

https://help.ubuntu.com/community/Grub2/Setup

https://help.ubuntu.com/community/Grub2/Setup#Configuring_GRUB_2

配置方式：

1
2
sudo vi /etc/default/grub
sudo update-grub

常用配置：

  • GRUB_DEFAULT: 0, “…”, saved
  • GRUB_SAVEDEFAULT: true

改完之后发现一个很严重的问题，不小心看错改成memtest了，很尴尬，而且，HIDDEN_TIMEOUT是0，都没机会弹出窗口，没办法，尝试LiveCD进入然后操作。

外部系统修复GRUB

在PD的虚拟机配置里，添加CD镜像，然后进入：

  1. mount相应盘
  2. chroot
  3. 进行更改

自己之前遇到没办法update-grub的问题，在网上找到了如下解决方法：

https://askubuntu.com/questions/145241/how-do-i-run-update-grub-from-a-livecd

最后，更新grub引导之后终于正常，长舒一口气。

还是需要学习一些知识啊。

Posted on | Edited on | In |

virtualenv

1
2
3
4
virtualenv env
source /bin/active
# deactive
deactive

pip

pip用国内源

1
pip install ... -i http://mirrors.aliyun.com/pypi/simple/

pip 导出配置，按配置安装

1
2
pip freeze > requirement.txt
pip install -r requirement.txt

Posted on | Edited on | In , |

受人指导配置了OpenGL开发环境，记下备忘

安装库

1
brew install glew glfw

CLion cmake配置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
cmake_minimum_required(VERSION 3.8)
project(graph)
set(CMAKE_CXX_STANDARD 11)
# find library
find_library(OPENGL OpenGL)
find_library(GLFW glfw)
find_library(GLEW glew)
# link them
link_libraries(${GLEW} ${GLFW} ${OPENGL})
set(SOURCE_FILES main.cpp)
add_executable(graph ${SOURCE_FILES})

写代码

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
#include <iostream>
#include <GL/glew.h>
#include <GLFW/glfw3.h>
const int SCR_WIDTH = 800;
const int SCR_HEIGHT = 600;
int main()
{
    // glfw: initialize and configure
    glfwInit();
    glfwWindowHint(GLFW_CONTEXT_VERSION_MAJOR, 3);
    glfwWindowHint(GLFW_CONTEXT_VERSION_MINOR, 3);
    glfwWindowHint(GLFW_OPENGL_PROFILE, GLFW_OPENGL_CORE_PROFILE);
    glfwWindowHint(GLFW_OPENGL_FORWARD_COMPAT, GL_TRUE); // uncomment this statement to fix compilation on OS X
    GLFWwindow* window = glfwCreateWindow(SCR_WIDTH, SCR_HEIGHT, "LearnOpenGL", NULL, NULL);
    if (window == NULL)
    {
        std::cout << "Failed to create GLFW window" << std::endl;
        glfwTerminate();
        return -1;
    }
    glfwMakeContextCurrent(window);
    // glad: load all OpenGL function pointers
    GLenum err = glewInit();
    if(err != GLEW_OK) {
        std::cout << "glewInit failed: " << glewGetErrorString(err) << std::endl;
        exit(1);
    }
    // render loop
    while (!glfwWindowShouldClose(window))
    {
        // input
        // ......
        // glfw: swap buffers and poll IO events (keys pressed/released, mouse moved etc.)
        glfwSwapBuffers(window);
        glfwPollEvents();
    }
    // glfw: terminate, clearing all previously allocated GLFW resources.
    glfwTerminate();
    return 0;
}

学习资源

https://learnopengl-cn.github.io/

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/largest-rectangle-in-histogram/description/

想法

贪心？DP？

DP的话，似乎要N^2的复杂度

先用DP试一下，就是算i~j之间的最小值吧

唔，用DP，简单地算最小值，然后处理，TLE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        if not heights:
            return 0
        if len(heights) == 1:
            return heights[0]
        dp = [[0 for j in range(len(heights))] for i in range(len(heights))]
        for i in range(len(heights)):
            dp[i][i] = heights[i]
        for l in range(1, len(heights)):
            for i in range(l, len(heights)):
                dp[i - l][i] = min(dp[i - l][i - 1], dp[i][i])
        ans = 0
        for i in range(len(heights)):
            for j in range(len(heights)):
                if dp[i][j] * (j - i + 1) > ans:
                    ans = dp[i][j] * (j - i + 1)
        return ans

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/minimum-size-subarray-sum/description/

想法

逐个遍历，然后保存最小的序列？是不是想得太简单点了，复杂度的话，O(n^2)，这应该是上界，一般不会这会多吧

答案

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
class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        sum = 0
        sum += nums[0]
        if sum > s:
            return 1
        a = 0
        ans = sys.maxsize
        for b in range(1, len(nums)):
            sum += nums[b]
            while sum >= s:
                ans = min(ans, b - a + 1)
                sum -= nums[a]
                a += 1
        if ans == sys.maxsize:
            return 0
        else:
            return ans

回顾

准确的复杂度自己也说不清楚，应该能得到一个上界小于O(n^2)

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/group-anagrams/description/

想法

这个题实际上想法应该就是那样的吧，遍历，然后维护一个个的集合，hash到相应的集合中

用python做了下，主要的时间花在了研究python的语法上

这道题用C/C++还真要花点功夫

自己最先想的是把一个字符串hash到一个独立的数上，就是只要字母相同，顺序不同是一个hash，但是没有找到这样的一个hash函数

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        m = {}
        for str in strs:
            inserted = False
            tmp = ''.join(sorted(str))
            if tmp in m:
                m[tmp].append(str)
                inserted = True
            else:
                m[tmp] = [str]
        return list(m.values())

回顾

高级语言一些封装好的东西，真的是太方便了

看了别人的解答，有这样的一个hash函数而自己没有想到

用素数！
每个字母用一个素数表示
于是，一个str用每个字母的乘积表示，这不会重复！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from functools import reduce
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
        m = {}
        for s in strs:
            # v = reduce(lambda x, y: prime[ord(x) - 97] * prime[ord(y) - 97], s)
            v = 1
            for c in s:
                v *= prime[ord(c) - 97]
            if v in m:
                m[v].append(s)
            else:
                m[v] = [s]
        return list(m.values())

用py写了下，本以为会beat >90%，没想到不快反慢了，这可能是python的原因吧，或者python本身的dictionary很高效

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/jump-game-ii/description/

想法

贪心！
首先想到的两个字，但是又不知道具体怎么用了，可能忘记了贪心的核心思想…

其实也就是一张图，求最短路径，但是图相关的算法基本上全忘了

遍历，更新，应该就是这样吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        a = [sys.maxsize] * len(nums)
        a[0] = 0
        for i, n in enumerate(nums):
            for j in range(1, n + 1):
                if i + j < len(a):
                    a[i + j] = min(a[i + j], a[i] + 1)
        return a[-1]

算是比较暴力的解决办法，不出所料，TLE…
毕竟是hard的题，不会那么简单吧

贪心，深度优先

答案

参考一个人写的贪心的答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        end = 0
        furthest = 0
        for i, n in enumerate(nums[:-1]):
            furthest = max(furthest, i + n)
            if i == end:
                ans += 1
                end = furthest
        return ans

回顾

这个答案很精巧

贪心，抓住关键点：能通过一步，走到最远的地方

经典

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/different-ways-to-add-parentheses/description/

想法

这个应该有多种解法吧
转化为构建二叉树？

反正图省事，先用DP做一下，基本上就是算出每两个元素间可能的结果…
这样的话，要开一个三维的数组，因为dp[i][j]位置要存的是一个数组
不考虑，而且好像也不是那么回事

如果递归地遍历地话，会不会超时

其实，运算符就是一个二叉树的非叶结点，其有多少种组合，就会有多少种运算方式
这只是抽象出来了，如何写呢？

不会…

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def diffWaysToCompute(self, input):
        """
        :type input: str
        :rtype: List[int]
        """
        ans = []
        for i, c in enumerate(input):
            if c in '+-*':
                for x in self.diffWaysToCompute(input[:i]):
                    for y in self.diffWaysToCompute(input[i + 1:]):
                        ans.append(eval(`x` + c + `y`))
        if not ans:
            return [int(input)]
        return ans

回顾

其实，简单的递归，就可以了，想的太多而没有动手去写

我想应该有更好的方法，但是，不想了…

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/maximal-square/description/

想法

直觉告诉我，这是用DP做的
但如果很单纯地算各个大小的块的话，空间太浪费了

没有想法，看别人的解答

答案

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(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0
        max_size = [[0 for i in range(len(matrix[0]))] for j in range(len(matrix))]
        for i in range(len(matrix)):
            max_size[i][0] = int(matrix[i][0])
            
        for i in range(len(matrix[0])):
            max_size[0][i] = int(matrix[0][i])
            
        for i in range(1, len(matrix)):
            for j in range(1, len(matrix[0])):
                if int(matrix[i][j]) == 0:
                    max_size[i][j] = 0
                else:
                    max_size[i][j] = min(max_size[i - 1][j - 1], max_size[i][j - 1], max_size[i - 1][j]) + 1
        
        return max([max(l) for l in max_size]) ** 2

根据别人的想法写出来的

回顾

其实DP的确是运用在此处的，但是自己没有找到所谓的state equation，关系等式

而在这个题目中，关键的关系等式就是：

1
max_size[i][j] = min(max_size[i - 1][j], max_size[i][j - 1], max_size[i - 1][j - 1]) + 1

自己最开始想的是计算出每一点是最大的，认为会浪费太多的时间，便是其实并不知道每个点最终能够有多大的空间，而是要讨论其中一个（比如右下角）最后能张成多大的空间就可以了，这是关键！

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

想法

经典题目，思路是清楚的，就是具体怎么写需要想想

反正是建树，递归做

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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* helper(vector<int>::iterator prebegin, vector<int>::iterator preend, vector<int>::iterator inbegin, vector<int>::iterator inend) {
        if (prebegin == preend)
            return NULL;
        TreeNode *root = new TreeNode(*prebegin);
        auto inmid = std::find(inbegin, inend, *prebegin);
        root->left = helper(prebegin + 1, prebegin + (inmid - inbegin) + 1, inbegin, inmid);
        root->right = helper(prebegin + (inmid - inbegin) + 1, preend , inmid + 1, inend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return helper(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    }
};

回顾

一次AC

这算是一次对C++的vector与iterator操作的熟悉吧，如何传递一个子的vector，需要iterator来帮助
如果用python做，肯定超省劲

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if not inorder:
            return
        mid = preorder.pop(0)
        idx = inorder.index(mid)
        root = TreeNode(mid)
        root.left = self.buildTree(preorder, inorder[:idx])
        root.right = self.buildTree(preorder, inorder[idx + 1:])
        
        return root