Leecode 每日一题

  感觉打过 ACM 之后,不写题总感觉学习的时候少了点什么。不希望把这份手艺拉下,但是因为疫情导致原定的省赛,区域赛都遥遥无期,曾经一起熬夜打 CF(Codeforces) 的乐趣也都没了。专业知识继续补足,项目这个暑假不打算写了,搭环境属实让我绝望。准备捡起祖传的手艺每日坚持一更 Leecode,不过当天如果题太难,我就换一个,难度的话基本保证在中等以上,如上。

2020/09/01

486. 预测赢家月初的第一题我就不会写,上来直接整懵了,看了题解 "零和博弈",我只理解了暴搜的解法, $DP$,是在没看太懂。对于暴搜而言,只看局部(当前问题),在当前的 $[L, R]$ 内,当前选手的最优解是什么,判断二者的差值,即为答案。

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        return check(0, nums.size() - 1, nums, 1) >= 0;
    }
private:
    int check(int l, int r, vector<int>& nums, int trun){
        if(l == r)
            return nums[l]*trun;
    
        int score_l = nums[l]*trun + check(l+1, r, nums, -trun);
        int score_r = nums[r]*trun + check(l, r-1, nums, -trun);

        return max(score_l*trun, score_r*trun)*trun;
    }
};

2020/08/31

  最近几天都在忙着返校相关的章程,没有时间继续每日一题,但是把中间空上的已经补上了,后续慢慢继续写了
841. 钥匙和房间,$BFS$ 遍历一下图联通即可

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        if(rooms.empty())
            return true;
        n = rooms.size(); m = rooms[0].size();
        queue<int> que;
        while(!que.empty())
            que.pop();
        que.push(0);
        while(!que.empty()){
            int x = que.front(); que.pop();
            vis[x] = 1;
            for(auto& i:rooms[x])
                if(vis[i] == 0)
                    que.push(i);
        }

        for(int i = 0;i < rooms.size();i++)
            for(int j = 0;j < rooms[i].size();j++)
                if(vis[rooms[i][j]] == 0)
                    return false;


        return true;
    }
private:
    int n, m;
    int vis[5000] = {0};
};

复杂度分析

  • 时间复杂度:$O(n+m)$,其中 $n$ 是房间的数量,$m$ 是所有房间中的钥匙数量的总数。
  • 空间复杂度:$O(n)$,其中 $n$ 是房间的数量。主要为队列的开销。

2020/08/26

17. 电话号码的字母组合,中等题怎么全是搜索。。。。这跟全排列差不多

class Solution {
public:
	void Init() {
		Mp[2] = { "abc" };
		Mp[3] = { "def" };
		Mp[4] = { "ghi" };
		Mp[5] = { "jkl" };
		Mp[6] = { "mno" };
		Mp[7] = { "pqrs" };
		Mp[8] = { "tuv" };
		Mp[9] = { "wxyz" };
	}

	void dfs(int pos) {
		if (pos == digits.size()){
            ans.push_back(tmp);
            return ;
        }
			
        int t = digits[pos] - '0';
		for (int i = 0; i < Mp[t].size(); i++) {
            int t = digits[pos] - '0';
			tmp.push_back(Mp[t][i]);
			dfs(pos + 1);
			tmp.pop_back();
		}
	}

	vector<string>& letterCombinations(string digits) {
        if(digits.size() == 0)
            return ans;
		Init();
		this->digits = digits;
		dfs(0);
		return ans;
	}
private:
	vector<string> ans;
	string digits;
	string Mp[1000];
	string tmp = "";
};

复杂度分析
dRcRW8.png


2020/08/25

491. 递增子序列,二进制枚举或者 $DFS$,去重

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
            dfs(0, nums, INT_MIN);
            return ans;
    }

    void dfs(int pos, vector<int>& nums, int last){
        if(pos == nums.size()){
            if(tmp.size() >= 2)
                ans.push_back(tmp);
            return ;    
        }
        
        if(nums[pos] >= last){	//如果当前的值大于等于上一次的优先放进去
            tmp.push_back(nums[pos]);
            dfs(pos+1, nums, nums[pos]);
            tmp.pop_back();
        }
        if(nums[pos] != last){	//放进去后,不选择当前的值,直接跳过选下一个
            dfs(pos+1, nums, last);
        }
    }

private:
    vector<int> tmp;
    vector<vector<int>> ans;
};

复杂度分析

  • 时间复杂度:$O(2^n \cdot n)$。仍然需要对子序列做二进制枚举,枚举出的序列虽然省去了判断合法性和哈希的过程,但是仍然需要 $O(n)$ 的时间添加到答案中。
  • 空间复杂度:$O(n)$。这里临时数组的空间代价是 $O(n)$,递归使用的栈空间的空间代价也是 $O(n)$。

2020/08/24

459. 重复的子字符串,直接暴力也可以用 $KMP$,好久没用发现已经忘了 $KMP$ 算法了,记得当初学的时候一连学了几天才明白 $next$ 数组的作用,打比赛的时候也很少去写字符串处理的题,只记得 $KMP$ 是处理模式串匹配的,剩下的全忘了,就会大力出奇迹了。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        for(int i = 1;i <= s.size()-1;i++){	//枚举子字符串长度
            if(s.size()%i != 0)
                continue;
            bool flag = true;
            for(int j = 0,k = 0;j < s.size();j++,k = (k+1)%i){
                if(s[j] != s[k]){
                    flag  = false;
                    break;
                }
            }
            if(flag)
                return flag;
        }
        return false;
    }
};

复杂度分析

  • 时间复杂度:$O(n^2)$ 其中 $n$ 是字符串 $s$ 的长度。枚举 $i$ 的时间复杂度为 $O(n)$,遍历 $s$ 的时间复杂度为 $O(n)$,相乘即为总时间复杂度。
  • 空间复杂度:$O(1)$。
第二题

42. 接雨水,看到这个样例的图片第一反应单调栈,果不其然,我忘了单调栈怎么写了,单调栈可以在 $O(n)$ 的时间复杂度内处理出每个点左右两边第一个比它大值,针对本题而言,保证单调栈内高度递增,当出现比当前栈顶元素高的柱子时,代表从该柱子往右,不可能再用以栈顶元素为边界接水,直接出栈即可,建议看题解,比较清楚

class Solution {
public:
    int trap(vector<int>& height) {
        for(int i = 0;i < height.size();i++){
            while(!s.empty() && height[s.top()] < height[i]){	//当 i 柱子高于栈顶柱子,把它前面的都算上,就单调栈把
                int cur = s.top(); s.pop();
                if(s.empty())
                    break;
                int l = s.top();
                int h = min(height[i], height[l]) - height[cur];
                ans += (i - l - 1)*h;
            }
            s.push(i);
        }
        return ans;
    }
private:
    stack<int> s;
    int ans = 0;
};

复杂性分析

  • 时间复杂度:$O(n)$
    • 单次遍历 $O(n)$,每个条形块最多访问两次(由于栈的弹入和弹出),并且弹入和弹出栈都是 $O(1)$ 的。
  • 空间复杂度:$O(n)$。 栈最多在阶梯型或平坦型条形块结构中占用 $O(n)$ 的空间。

2020/08/21

201. 数字范围按位与,第一时间没想到求二进制下的最长公共子串,位运算这方面一点也不行,还是脑子不够用转不过来。大概描述一下。
既然要找所有数字的二进制位按位 & 后的结果,那么最后的结果中有 $1$ 的那一位必须是所有位置都为 $1$, $[m, n]$中有一位不为 $1$,那么该位为 $0$(&,类似于二进制乘法)。分情况讨论

  • $m == n$ 时,这直接返回就行不用多说
  • $m < n$ 时,前缀和肯定是以 $m$ 的第一个二进制下 $1$ 的位置,因为比该位置更靠前的一定都是 $0$。例如 $[1, 4]$, $4$ 的二进制为 $100$,那么在 $1$ 的第一个二进制位之前都会被 & 为 $0$,都是无意义的,主要看 $1$ 之后的位置。当右边界缩小为 $m$ 时,此时后面的所有位置都填充 $0$,即为答案。为何要填充为 $0$? 因为假设从第 $i$ 个位置结束最长公共子串,前 $i$ 位均相同,第 $i+1$ 位开始不同,由于 $[m,n]$ 连续,所以第 $i+1$ 位在 $[m,n]$ 的数字范围从小到大列举出来一定是前面全部是 $0$,后面全部是 $1$,具体的证明看官方题解把
class Solution {
public:
    int& rangeBitwiseAnd(int &m, int &n) {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
        while(m < n){
            n = n & (n-1);	//每次消掉最后一位
        }
        return n;
    }
};

2020/08/22

679. 24 点游戏 $DFS$ 全排列进行暴搜,每次选择两个数字进行加、减、乘、除 $4$ 操作,当进行到最后一位时判断是否为 $24$,即可。一共有 $4$ 个数字 $4$ 种操作运算符
  首先,从 $4$ 个元素中选择两个共有 $6$ 种选择,并选择加、减、乘、除 $4$ 种运算操作之一,用得到的结果取代选出的 $2$ 个数字,剩下 $3$ 个数字。
  然后在剩下的 $3$ 个数字中有序地选出 $2$ 个数字,共有 $3$ 种选法,并选择 $4$ 种运算操作之一,用得到的结果取代选出的 $2$ 个数字,剩下 $2$ 个数字。
  最后剩下 $2$ 个数字,有 $2$ 种不同的顺序,并选择 $4$ 种运算操作之一。
  因此,一共有

$$(6*2 \times 4) \times (3*2 \times 4) \times (1*2 \times 4) = 9216$$

种不同的可能性。(每个都 $*2$,因为每种运算都有两种循序 a+b、 b+a)。

实现时,有一些细节需要注意

  • 除法运算为实数除法,因此结果为浮点数,列表中存储的数字也都是浮点数。在判断结果是否等于 $24$ 时应考虑精度误差,这道题中,误差小于 $10^{-6}$ 可以认为是相等。
  • 进行除法运算时,除数不能为 $0$,如果遇到除数为 $0$ 的情况,则这种可能性可以直接排除。由于列表中存储的数字是浮点数,因此判断除数是否为 $0$ 时应考虑精度误差,这道题中,当一个数字的绝对值小于 $10^{-6}$时,可以认为该数字等于 $0$。
class Solution {
public:
    bool judgePoint24(vector<int>& nums) {
        vector<double> num;
        for(int i = 0;i < nums.size();i++){	//全都转化为 double
            num.push_back(nums[i]*1.0);
        }
        solve(num);
        return flag;
    }

    void solve(vector<double>& nums){
        if(flag)	//如果已经有一个情况为 true,直接一直返回即可
            return ;
        if(nums.size() < 0)		//如数组长队为0,直接返回
            return ;
        if(nums.size() == 1){		。。如果只剩一个数字,判断该点是不是24
            if(fabs(nums[0] - TARGET) < EPS){
                flag = true;
                return ;
            }
        }

        for(int i = 0;i < nums.size();i++){	//选取第一个数字
            for(int j = 0;j < nums.size();j++){	//选取第二个数字
                if(i == j)
                    continue;
                vector<double> residual;	//存放剩余的数字
                residual.clear();
                double a = nums[i], b = nums[j];
                for(int k = 0;k < nums.size();k++){	//把没选到的数字放在另一个数组内,于选中的数组拼成新的数组
                    if(i != k && k != j)
                        residual.push_back(nums[k]);
                }
                //a+b
                residual.push_back(a+b);
                solve(residual);
                residual.pop_back();

                //a-b
                residual.push_back(a-b);
                solve(residual);
                residual.pop_back();

                //b-a
                residual.push_back(b-a);
                solve(residual);
                residual.pop_back();

                //a*b
                residual.push_back(a*b);
                solve(residual);
                residual.pop_back();

                //a/b
                if(b != 0){
                    residual.push_back(a/b);
                    solve(residual);
                    residual.pop_back();
                }

                //b/a
                if(a != 0){
                    residual.push_back(b/a);
                    solve(residual);
                    residual.pop_back();
                }
            }
        }
    }
private:
    static constexpr int TARGET = 24;
    static constexpr double EPS = 1e-6;
    bool flag = false;
};

复杂度分析

  • 时间复杂度:$O(1)$。一共有 $9216$ 种可能性,对于每种可能性,各项操作的时间复杂度都是 $O(1)$,因此总时间复杂度是 $O(1)$,听起来挺离谱的

  • 空间复杂度:$O(1)$。空间复杂度取决于递归调用层数与存储中间状态的列表,因为一共有 $4$ 个数,所以递归调用的层数最多为 $4$,存储中间状态的列表最多包含 $4$ 个元素,因此空间复杂度为常数。


2020/08/21

111. 二叉树的最小深度,$DFS$左右子树的大小,然后取 $min$

class Solution {
public:
    int minDepth(TreeNode *root) {
        if (root == nullptr) {
            return 0;
        }

        if (root->left == nullptr && root->right == nullptr) {
            return 1;
        }

        int min_depth = INT_MAX;
        if (root->left != nullptr) {
            min_depth = min(minDepth(root->left), min_depth);
        }
        if (root->right != nullptr) {
            min_depth = min(minDepth(root->right), min_depth);
        }

        return min_depth + 1;
    }
};

复杂度分析

  • 时间复杂度:$O(N)$,其中 $N$ 是树的节点数。对每个节点访问一次。

  • 空间复杂度:$O(H)$,其中 $H$ 是树的高度。空间复杂度主要取决于递归时栈空间的开销,最坏情况下,树呈现链状,空间复杂度为 $O(N)$。平均情况下树的高度与节点数的对数正相关,空间复杂度为 $O(\log N)$。

29. 两数相除,要求不使用乘法、除法和 mod 运算符。那就只能用加减法了,举例说明,例如当前的除数是 $11$,被除数 $3$,那么首先看 $3$ 能是小于 $11$,的那么让 $3$翻倍得到 $6$,也是小于 $11$ 的,那么证明 $11 \div 3 > 2$,再让 $6$ 翻倍得到 $12 > 11$,那么 $2 < 11 \div 3 < 4$,此时让 $11 - 6 -> 5$,再让 $5$ 去进行如上计算,递归得到答案,为什么要拆成 $11 - (32)$,因为 $11 = 32 + 3*1 + 2$,上述过程就是实现这个等式。对于例如 $0, 1, -1$的特殊情况(越界)进行特判即可

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend == 0) return 0;
        if(divisor == 1) return dividend;
        if(divisor == -1){
            if(dividend > INT_MIN)
                return -dividend;
            return INT_MAX;
        }

        long long divd = dividend, divr = divisor; //确定符号,并且全都转化为正数运算
        int flag = 1;
        if((divd < 0 && divr > 0) || (divd > 0 && divr < 0))
            flag = -1;
        divd = abs(divd);
        divr = abs(divr);

        long long res = div(divd, divr);
        if(flag > 0)
            return res > INT_MAX?INT_MAX:res;
        return -res;
    }

    int div(long long a, long long b){
        if(a < b)	//如果 a < b,那么代表 a 里面没有一个 b
            return 0;
        int cnt = 1;
        long long tb = b;
        while((tb + tb) < a){//模拟上述过程,不断让被除数翻倍
            tb += tb;
            cnt += cnt;
        }
        return cnt + div(a - tb, b);
    }
};

复杂度分析

  • 时间复杂度:好难算啊,针对每次翻倍的操作是 $log$,但是递归里面又是一个 $log$
  • 空间复杂度:$O(1)$,维护了几个变量

2020/08/20

529. 扫雷游戏,这题读题真的累,但是就是 $DFS/BFS$ 一遍就行,好像 $Leecode$ 中等题搜索偏多啊。

class Solution {
public:
    int dir_x[8] = {0, 1, 0, -1, 1, 1, -1, -1};
    int dir_y[8] = {1, 0, -1, 0, 1, -1, 1, -1};

    void dfs(vector<vector<char>>& board, int x, int y) {
        int cnt = 0;
        for (int i = 0; i < 8; ++i) {
            int tx = x + dir_x[i];
            int ty = y + dir_y[i];
            if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size()) {
                continue;
            }
            cnt += board[tx][ty] == 'M';
        }
        if (cnt > 0) {
            board[x][y] = cnt + '0';
        } else {
            board[x][y] = 'B';
            for (int i = 0; i < 8; ++i) {
                int tx = x + dir_x[i];
                int ty = y + dir_y[i];
                if (tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size() || board[tx][ty] != 'E') {
                    continue;
                }
                dfs(board, tx, ty);
            }
        }
    }

    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int x = click[0], y = click[1];
        if (board[x][y] == 'M') {
            board[x][y] = 'X';
        } else {
            dfs(board, x, y);
        }
        return board;
    }
};

复杂度分析

  • 时间复杂度:$O(nm)$,其中 $n$ 和 $m$ 分别代表面板的宽和高。最坏情况下会遍历整个面板。
    空间复杂度:$O(nm)$。空间复杂度取决于递归的栈深度,而递归栈深度在最坏情况下有可能遍历整个面板而达到 $O(nm)$。

第二题

19. 删除链表的倒数第N个节点两种解法,一种是先统计这个链表有多少的节点,假设链表有 $cnt$ 个节点,那么要删除倒数第 $N$ 个节点,就是删除正数第 $cnt - N + 1$ 个节点,但是开开始前要先添加一个哑节点, $dummy$,用于防止出现删除头节点的情况。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);	//哑节点
        dummy->next = head;
        ListNode* tmp = head;
        int cnt = 0, delval = 0;
        while(tmp != nullptr){
            cnt++;
            tmp = tmp->next;
        }
        //cout << cnt << endl;
        int delpos = cnt - n;	//要删除的是 cnt - n + 1,那么该节点的前一个就是 cnt - n
        tmp = dummy;
        while(delpos > 0) {
            delpos--;
            tmp = tmp->next;
        }
        tmp->next = tmp->next->next;
        return dummy->next;
    }
};

双指针方法,定义两个指针,始终保持两个指针的间隔距离为 $N$,当一个指针指到结尾时,另一个指针就是待删除的点,和上面的时间复杂度差不多。

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode *dummyNode = new ListNode(0);
        dummyNode->next = head;
        ListNode *firstNode = dummyNode, *secondNode = dummyNode;

        for (int i = 1; i <= n; ++i) {
            secondNode = secondNode->next;
        }
        
        while (secondNode->next != nullptr) {
            secondNode = secondNode->next;
            firstNode = firstNode->next;
        }

        firstNode->next = firstNode->next->next;

        return dummyNode->next;
    }
};

复杂度分析

  • 时间复杂度:$O(L)$,该算法对列表进行了两次遍历,首先计算了列表的长度 $L$ 其次找到第 $(L−n)$ 个结点。 操作执行了 $2L - n$ 步,时间复杂度为 $O(L)$。
  • 空间复杂度:$O(1)$,就多开了一个哑节点。

2020/08/19

647. 回文子串,$Manacher$板子,在 $Manacher$ 算法中,处理出来的 $p[i]$ 数组表示,以 $i$ 为对称中心能延展的最长回文串长度。例如如下字符串 $aba$,经过转化后变成 $@#a#b#a#$,可以发现,每个字符的 $p[i]$ 至少为 $2$,例如字符 $a$。而 $b$ 的 $p[i] = 4$,那么以 $b$ 为中心构成的回文字符串有$4$个, 其中有一半是 $#$开头的,所以以 $b$ 为中心实际的回文串长度为 $p[i] \div 2$

class Solution {
public:
    int countSubstrings(string s) {
        return Manacher(s);
    }

    void Init(string s){
        tmp[0] = '@';
        tmp[1] = '#';
        len1 = s.size();
        for(int i = 0;i < len1;i++){
            tmp[i*2 + 2] = s[i];
            tmp[i*2 + 3] = '#';
        }
        len2 = strlen(tmp);
    }

    int Manacher(string s){
        Init(s);
        for(int i = 1;i < len2;i++){
            if(i < mx)
                p[i] = min(mx - i, p[2*id - i]);
            else 
                p[i] = 1;
            while(tmp[i + p[i]] == tmp[i - p[i]])
                p[i]++;
            if(i + p[i] > mx){
                mx = i+p[i];
                id = i;
            }
            ans += (p[i] / 2);
        }
        return ans;
    }
private:
    int mx = 0, id = 0, p[2005] = {0}, len1, len2;
    char tmp[2005];
    int ans = 0;
};

复杂度分析

  • 时间复杂度:$O(n)$。即 $Manacher$ 算法的时间复杂度.
    空间复杂度:$O(n)$。

2020/08/18

109. 有序链表转换二叉搜索树,很容易想到,从中位数建树,因为链表有序,中位数建树一定能满足两边平衡,然后递归建树即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
	ListNode* Find(ListNode* left, ListNode* right) {
		ListNode* l = left;
		ListNode* mid = left;
		while (l != right && l->next != right) {
			l = l->next; //每次跳两位,中位数跳一位,算是一个规律吧,自己画一下就知道了
			l = l->next;
			mid = mid->next;
		}
		return mid;
	}

	TreeNode* Build(ListNode* left, ListNode* right) {
		if (left == right)
			return nullptr;
		ListNode* mid = Find(left, right);
		TreeNode* root = new TreeNode(mid->val);
		root->left = Build(left, mid);
		root->right = Build(mid->next, right);
		return root;
	}

	TreeNode* sortedListToBST(ListNode* head) {
		return Build(head, nullptr);
	}
};

复杂度分析

  • 时间复杂度:$O(n \log n)$,其中 $n$ 是链表的长度。
  • 空间复杂度:$O(\log n)$,这里只计算除了返回答案之外的空间。平衡二叉树的高度为 $O(\log n)$,即为递归过程中栈的最大深度,也就是需要的空间。

2020/08/17

110. 平衡二叉树,就 $DFS$ 统计树高可解,也可以通过判断子树是否为平衡二叉树递归求解

class Solution {
public:
	int Hight(TreeNode* root) {
		if (root == nullptr)
			return 0;
		int lchildHight = Hight(root->left);//一直向下递归,到根节点返回 0
		int rchildHight = Hight(root->right);
		if (lchildHight == -1 || rchildHight == -1 || abs(lchildHight - rchildHight) > 1)
			return -1;  //只要有一个子树不符合,那么该树即不是平衡二叉树
		else
			return max(lchildHight, rchildHight) + 1;
	}
	bool isBalanced(TreeNode* root) {
		return Hight(root) >= 0;
	}
};

复杂度分析

  • 时间复杂度:$O(n)$,其中 $n$ 是二叉树中的节点个数。使用自底向上的递归,每个节点的计算高度和判断是否平衡都只需要处理一次,最坏情况下需要遍历二叉树中的所有节点,因此时间复杂度是 $O(n)$。
  • 空间复杂度:$O(n)$,其中 $n$ 是二叉树中的节点个数。空间复杂度主要取决于递归调用的层数,递归调用的层数不会超过 $n$。
第二题

5. 最长回文子串,$Manacher$ 马拉车算法板子,看到学长在腾讯一面的时候被问到,来复习一下,推荐一个讲解的链接Manacher(马拉车)————O(n)回文子串

class Solution {
public:
	string longestPalindrome(string s) {
		init(s);
		len1 = s.size(); len2 = strlen(t);
		Manacher();
		int pos = 0, cnt = -1;
		for (int i = 0; i < len2; i++) {
			if (cnt < p[i] - 1) {
				cnt = p[i]- 1;
				pos = i;
			}
		}
		string ans = "";
		for (int i = pos - cnt; i < pos+cnt; i++) {
			if (t[i] != '#')
				ans.push_back(t[i]);
		}
		return ans;
	}
private:
	void init(string s) {
		t[0] = '@';
		t[1] = '#';
		for (int i = 0; i < s.size(); i++) {
			t[i * 2 + 2] = s[i];
			t[i * 2 + 3] = '#';
		}
	}
	void Manacher() {
		for (int i = 1; i < len2; i++) {
			if (i < mx)
				p[i] = min(p[2 * id - i], mx - i);
			else
				p[i] = 1;
			while (t[i + p[i]] == t[i - p[i]])
				p[i]++;
			if (p[i] + i > mx) {
				mx = p[i] + i;
				id = i;
			}
		}
	}
private:
	char t[3005];
	int id = 0, mx = 0, p[3005] = {0}, len1, len2;
	/*
	*	t:		翻倍处理后的字符串
	*	id:		当前的对称中心
	*	mx:		以id为对称中心,半径为 p[id] 的边界
	*	p:		记录以 i 为中心,的会问长度
	*	len1:	s的长度
	*	len2:	t的长度 = s*2 + 2
	*/
};

复杂度分析:

  • 时间复杂度:$O(N)$,$Manacher$ 算法只有在遇到还未匹配的位置时才进行匹配,已经匹配过的位置不再匹配,因此对于字符串 $S$ 的每一个位置,都只进行一次匹配,算法的复杂度为 $O(N)$。
  • 空间复杂度:$O(N)$,只维护了几个变量,一个翻倍的字符串,一个记录答案的数组。

2020/08/16

733. 图像渲染,就简单搜索找连通块,没什么东西

class Solution {
public:
    const int dx[4] = {1, 0, 0, -1};
    const int dy[4] = {0, 1, -1, 0};
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        int currColor = image[sr][sc];
        if (currColor == newColor) return image;
        int n = image.size(), m = image[0].size();
        queue<pair<int, int>> que;
        que.emplace(sr, sc);
        image[sr][sc] = newColor;
        while (!que.empty()) {
            int x = que.front().first, y = que.front().second;
            que.pop();
            for (int i = 0; i < 4; i++) {
                int mx = x + dx[i], my = y + dy[i];
                if (mx >= 0 && mx < n && my >= 0 && my < m && image[mx][my] == currColor) {
                    que.emplace(mx, my);
                    image[mx][my] = newColor;
                }
            }
        }
        return image;
    }
};

复杂度分析

  • 时间复杂度:$O(n\times m)$,其中 $n$ 和 $m$ 分别是二维数组的行数和列数。最坏情况下需要遍历所有的方格一次。
  • 空间复杂度:$O(n\times m)$,其中 $n$ 和 $m$ 分别是二维数组的行数和列数。主要为队列的开销。
第二题

2. 两数相加,直接模拟加法,然后进行一个链表反转。理论上可以优化,直接在 $l1$ 于 $l2$ 的基础上进行修改,将加和后的值直接存入其中一个,实现差不多,我写的比较麻烦,正好也训练一下我链表的操作。

class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		ListNode* head = new ListNode(0);
		while (l1 != nullptr && l2 != nullptr) {
			int x = l1->val;
			int y = l2->val;
			int ans = x + y + add;
			ListNode* tmp = new ListNode(0);
			tmp->val = ans % 10;
			add = ans / 10;
			tmp->next = head->next;
			head->next = tmp;
			l1 = l1->next;
			l2 = l2->next;
		}
		while (l1 != nullptr) {
			int x = l1->val;
			ListNode* tmp = new ListNode(0);
			tmp->val = add + x;
			add = tmp->val / 10;
			tmp->val %= 10;

			tmp->next = head->next;
			head->next = tmp;
			l1 = l1->next;
		}
		while (l2 != nullptr) {
			int x = l2->val;
			ListNode* tmp = new ListNode(0);
			tmp->val = add + x;
			add = tmp->val / 10;
			tmp->val %= 10;
			
			tmp->next = head->next;
			head->next = tmp;
			l2 = l2->next;
		}
		if (add != 0) {
			ListNode* tmp = new ListNode(add);
			tmp->next = head->next;
			head->next = tmp;
		}
		head = head->next;
		ListNode* rever = nullptr, * next = nullptr;
		while (head) {
			next = head->next;
			head->next = rever;
			rever = head;
			head = next;
		}

		return rever;
	}
private:
	int add;
};

复杂度分析

  • 时间复杂度:$O(\max(m, n))$,假设 $m$ 和 $n$ 分别表示 $l1$ 和 $l2$ 的长度,上面的算法最多重复 $\max(m, n)$次,翻转链表最多需要 $\max(m, n) + 1$次。
  • 空间复杂度:空间复杂度:$O(\max(m, n))$, 新列表的长度最多为 $\max(m,n) + 1$。
第三题

5489. 两球之间的磁力二分板子,最大化最小值,也没什么好说的

class Solution {
public:
	bool check(vector<int>& position, int mid, int m) {
		int cnt = 1,pos = position[0];
		while (true) {
			int tpos = lower_bound(position.begin(), position.end(), pos + mid) - position.begin();
			if (tpos != position.size()) {
				pos = position[tpos];
				cnt++;
			}
			else
				break;
		}
		return cnt >= m;
	}
	int maxDistance(vector<int>& position, int m) {
		sort(position.begin(), position.end());
		int n = position.size();
		int l = 1, r = position[n - 1];
		int ans = 0;
		while (l <= r) {
			int mid = (l + r) / 2;
			if (check(position, mid, m)) {
				ans = mid;
				l = mid + 1;
			}
			else {
				r = mid - 1;
			}
		}
		return ans;
	}
};

复杂度分析

  • 时间复杂度:总时间复杂度 $O(n * log n)$,首先对于数组的排序,$sort$, 时间复杂度 $O(n * log n)$,二分答案 $O(log n)$,$check$ 函数 $O(log n)$
  • 空间复杂度:$O(1)$,只维护了几个变量

2020/08/15

546. 移除盒子好难的 DP 啊,看题解看了好久才明白。建议去查看这个题解讲的比较清楚

class Solution {
public:
	int removeBoxes(vector<int>& boxes) {
		box = boxes;
		return solve(0, boxes.size() - 1, 0);
	}
	int solve(int i, int j, int k) {
		if (i > j)
			return 0;

		if (dp[i][j][k] != 0)
			return dp[i][j][k];

		while (i < j && box[j] == box[j - 1]) {
			j--;
			k++;
		}

		dp[i][j][k] = solve(i, j-1, 0) + (k+1)*(k+1);

		for (int p = i; p < j; p++) {
            if (box[p] == box[j]) {
                dp[i][j][k] = max(dp[i][j][k], solve(p + 1, j - 1, 0) + solve(i, p, k + 1));
            }
        }
        printf("%d %d %d %d\n", i, j, k, dp[i][j][k]);
		return dp[i][j][k];
	}
public:
	vector<int> box;
	int dp[101][101][101] = { 0 };
};

2020/08/14

第一题

今天的每日一题比较简单,括号匹配,所以更新两题

class Solution {
public:
    bool isValid(string s) {
		for (int i = 0; i < s.size(); i++) {
			if (s[i] == '(' || s[i] == '[' || s[i] == '{')
				sta.push(s[i]);
			else {
				if (sta.empty())
					return false;
				char tmp = sta.top(); sta.pop();
				if (s[i] == ')' && tmp == '(')
					continue;
				else if (s[i] == ']' && tmp == '[')
					continue;
				else if (s[i] == '}' && tmp == '{')
					continue;
				return false;
			}
		}
		if (!sta.empty())
			return false;
		return true;
    }
public:
	stack<char> sta;
};

复杂度分析

  • 时间复杂度:$O(n)$,其中 $n$ 是字符串 $s$ 的长度。
  • 空间复杂度:$O(n + |\Sigma|)$,其中 $\Sigma$ 表示字符集,本题中字符串只包含 $6$ 种括号,$|\Sigma| = 6$。栈中的字符数量为 $O(n)$,而哈希映射使用的空间为$ O(|\Sigma|)$,相加即可得到总空间复杂度。

第二题

3. 无重复字符的最长子串
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

类似滑动窗口。由于它需要寻找的是一个最长字串,只需要从左到右遍历一下,对于每一个出现的字符记录一个 vis 数组,用于标记出现的位置,当 vis 数组不为 $0$ 时,代表该字母以前出现过,那么只需要用当前的位置 $i$ 减去曾经这个字符出现的位置 $vis[s[i]]$,就能得出中间的序列是能用的,但是会出现 $abba$,这种,所以在记录一个 $lastpos$ 用于记录,如果这个点上一次出现的位置比我更新的位置要早,那么上次的点的位置就是无意义的。例如 abba,过程如下

规定 i 从 1开始,那么,s[i-1],即可获取原串
i = 1 时,
	s[i-1] = a
	vis[s[i-1]] = 0 -> visvis[s[i-1]] = 1
	cnt = 1
	lastpos = 0
	ans = 1
i = 2 时
	s[i-1] = b
	vis[s[i-1]] = 0 -> vis[s[i-1]] = 2
	cnt = 2
	lastpos = 0
	ans = 2
i = 3 时
	s[i-1] = b
	vis[s[i-1]] = 2
	cnt = i - vis[s[i-1]]  -> cnt = 1
	lastpos = vis[s[i-1]] -> lastpos = 2 //在2号位置更新过了,代表2号以前的位置都不是可取的了
	vis[s[i-1]] = 3
	ans = 2
i = 4 时
	s[i-1] = a
	vis[s[i-1]] = 1,此时出现的点小于上次更新的点,所以该次记录无效
	cnt = 2
	lastpos = 2
	ans = 2

感觉说的不清,但是意思很对,剩下的看注释把

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		int ans = 0, cnt = 0, lastpos = 0;
		for (int i = 1; i <= s.size(); i++) {
			if (vis[s[i-1]] != 0 && lastpos < vis[s[i-1]]) {  //当字符串上一次出现的位置
				cnt = i - vis[s[i-1]];
				lastpos = vis[s[i - 1]]; //记录当前更新的节点,该节点以前都是非法的
			}
			else {
				cnt++;
			}
			vis[s[i-1]] = i;
			ans = max(ans, cnt);
		}
		return ans;
	}
public:
	int vis[200] = {0};  //用于记录字符出现的位置
};

时间复杂度分析:

  • 时间复杂度:$O(N)$,其中 $N$ 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。
  • 空间复杂度:$O(|\Sigma|)$,其中 $\Sigma$ 表示字符集(即字符串中可以出现的字符),$|\Sigma|$ 表示字符集的大小。在本题中没有明确说明字符集,因此可以默认为所有 $ASCII$ 码在 $[0, 128)$ 内的字符,即 $|\Sigma| = 128$。我们需要用到哈希集合来存储出现过的字符,而字符最多有 $|\Sigma|$ 个,因此空间复杂度为 $O(|\Sigma|)$。

2020/08/13

43. 字符串相乘
就大数乘法,我直接暴力做的,模拟乘法 + 大数加法就行了,好像还可以优化竖式,数学大佬 FFT 优化属实牛逼
下面是偷题解的图片
大数乘法.png
这个直接模拟就行,不过比我之前学的大数模板简单的多,记得刚学C语言内会,一个大数80多行写几个小时还要疯狂 DeBug。

class Solution {
public:
    string multiply(string num1, string num2) {
        if (num1 == "0" || num2 == "0")
            return "0";
        string ans = "0";
        int len1 = num1.size(), len2 = num2.size();
        for (int i = len1 - 1; i >= 0; i--) {
            string curr = "";
            int add = 0;
            for (int j = len1 - 1; j > i; j--)
                curr.push_back('0');

            int x = num1[i] - '0';
            for (int j = len2 - 1; j >= 0; j--) {
                int y = num2[j] - '0';
                int ret = x * y + add;
                curr.push_back((ret % 10) + '0');
                add = ret / 10;
            }
            if (add != 0)
                curr.push_back(add + '0');
            reverse(curr.begin(), curr.end());
            ans = AddString(ans, curr);
        }
        return ans;
    }

    string AddString(string& num1, string num2) {
        int i = num1.size() - 1, j = num2.size() - 1, add = 0;
        string ans = "";
        while (i >= 0 || j >= 0 || add != 0) {
            int x = (i >= 0) ? (num1[i] - '0') : 0;
            int y = (j >= 0) ? (num2[j] - '0') : 0;
            int ret = x + y + add;
            ans.push_back((ret % 10)+'0');
            add = ret / 10;
            i--; j--;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

时间复杂度分析:

  • 时间复杂度:$O(nm + m^{2})$ ,其中 $n$ 和 $m$ 分别代表 $num1$ 于 $num2$ 的长度。需要从右往左遍历 $num2$,对于 $num2$ 的每一位都需要和 $num1$ 进行相乘,因此计算乘积的总次数为 $nm$。字符串相加一共会有 $n$ 次操作,相加的字符串长度最大为 $n + m$,因此字符串相加的时间复杂度为$O(n(n+m))$
  • 空间复杂度:$O(n + m)$,空间的大小取决于中间存储的字符串大小,最大长度 $m+n$。

优化解法,舒适思路清奇,感觉看官方的题解比较清楚,就不过多赘述,类似找规律

class Solution {
public:
	string multiply(string num1, string num2) {
        cin.tie(nullptr);
        cout.tie(nullptr);
		if (num1 == "0" || num2 == "0")
			return "0";
		int len1 = num1.size(), len2 = num2.size();
		vector<int> ans(len1 + len2);
		for (int i = len1 - 1; i >= 0; i--) {
			int x = num1[i] - '0';
			for (int j = len2 - 1; j >= 0; j--) {
				int y = num2[j] - '0';
				int ret = x * y;
				ans[i + j + 1] += x * y;
			}
		}

		for (int i = len1 + len2 - 1; i >= 0; i--) {
			if (ans[i] > 9) {
				ans[i - 1] += ans[i] / 10;
				ans[i] = ans[i] % 10;
			}
		}

		string ret = "";
		for (int i = 0; i < len1 + len2; i++) {
			if (i == 0 && ans[i] == 0)
				continue;
			ret.push_back(ans[i] + '0');
		}
		return ret;
	}
};

2020/08/12

133. 克隆图
给你无向连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。

题解

怎么感觉中等题好多搜索,这个就是直接裸的BFS/DFS就行,开个map,映射一下即可

代码示例

class Solution {
public:
    map<Node*, Node*> mp;
public:
    Node* cloneGraph(Node* node) {
        if (node == nullptr)
            return node;
        if (mp[node] != nullptr) //如果这个点已经被访问过,直接返回就行
            return mp[node];
        Node* clonenode = new Node(node->val);
        mp[node] = clonenode;
        for (auto it = node->neighbors.begin(); it != node->neighbors.end(); it++) {
            clonenode->neighbors.emplace_back(cloneGraph(*it));
        }
        return clonenode;
    }
};

复杂度分析

  • 时间复杂度:$O(N)$,其中 $N$ 表示节点数量。深度优先搜索遍历图的过程中每个节点只会被访问一次。
  • 空间复杂度:$O(N)$,存储克隆节点和原节点的哈希表需要 $O(N)$ 的空间,递归调用栈需要 $O(H)$ 的空间,其中 $H$ 是图的深度,经过放缩可以得到 $O(H)=O(N)$,因此总体空间复杂度为 $O(N)$。

2020/08/11

130. 被围绕的区域
给定一个二维矩阵,让把所有被 $X$ 包围 $O$ ,变成 $X$,不包括边界的 $O$。

题解

  第一眼看过去类似于找联通块,想到了从一个 $O$ 开始 $BFS$ 去探寻找到的点,然后如果这个点能联通的所有点有一个不符合条件(里面有边界点)那么这一串都不符合。又想到添加一个 map 去标记那些被搜过的点,防止第二次遇到又搜一边,然后添加了一堆东西,空间开销巨大。后来反过来想,可以从边界点往内部搜效果是一样的,一边搜一边修改原数组中的值,例如从边界 $O$ 开始搜,所有能到达的点都设置为 $A$,那么最后遍历原数组时,所有是 $A$ 的都变回 $O$,所有是 $O$ 的都是 $X$,即可

代码示例

class Solution {
public:
	using P = pair<int, int>;
	queue<P> que;
	int n, m;
	int nextstep[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }; //四个方向

	void solve(vector<vector<char>>& board) {
		n = board.size();
		if (n == 0)
			return;
		m = board[0].size();
		//取出边界的店
		for (int i = 0; i < n; i++) {
			if (board[i][0] == 'O')
				que.push(P(i, 0));
			if (board[i][m - 1] == 'O')
				que.push(P(i, m - 1));
		}
		for (int i = 1; i < m - 1; i++) {
			if(board[0][i] == 'O')
				que.push(P(0, i));
			if (board[n - 1][i] == 'O')
				que.push(P(n - 1, i));
		}

		while (!que.empty()) {
			P now = que.front(); que.pop();
			board[now.first][now.second] = 'T';//替换成不合格的点
			for (int i = 0; i < 4; i++) {
				int tx = now.first + nextstep[i][0];
				int ty = now.second + nextstep[i][1];
				if (tx < 0 || ty < 0 || tx >= n || ty >= m || board[tx][ty] != 'O')
					continue;
				que.push(P(tx, ty));
			}
		}

        for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				board[i][j] = (board[i][j] == 'T') ? 'O' : 'X';//修改回去
			}
		}
	}
};

复杂度分析

  • 时间复杂度:$O(n\times m)$,其中 $n$ 和 $m$ 分别为矩阵的行数和列数。广度优先搜索过程中,每一个点至多只会被标记一次。
  • 空间复杂度:$O(n\times m)$,其中 $n$ 和 $m$ 分别为矩阵的行数和列数。主要为广度优先搜索的队列的开销。

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://neo00.top/archives/leecode每日一题