小呆呆
2小时前
  • 奇数环:由奇数条边形成的一个环

  • 二分图:当且仅当图中不含有奇数环,两个集合内部的内部没有边

算法1

使用bfs

  • 约定染的颜色有1颜色和2颜色

41b46b2c8e294ac48ffc02fde325002.png

时间复杂度 $O(m + n)$

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int n;
    static int m;
    static int N = 100010;
    static int M = 2100010;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static int[] color = new int[N];//共1和2两种不同的颜色
    static boolean[] st = new boolean[N];
    public static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    public static boolean bfs()
    {
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i = 1;i <= n;i++)
        {
            //若该点为染色
            if(color[i] == 0)
            {
                color[i] = 1;
                queue.add(i);
                while(!queue.isEmpty())
                {
                    int t = queue.poll();
                    for(int j = h[t] ;j != -1;j = ne[j])
                    {
                        int k = e[j];
                        if(color[k] == 0)
                        {
                            color[k] = 3 - color[t];
                            queue.add(k);
                        }
                        else if(color[k] == color[t]) return false;
                    }
                }
            }
        }
        return true;


    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] str1 = reader.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        m = Integer.parseInt(str1[1]);
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            String[] str2 = reader.readLine().split(" ");
            int a = Integer.parseInt(str2[0]);
            int b = Integer.parseInt(str2[1]);
            add(a,b);
            add(b,a);
        }

        if(bfs()) System.out.println("Yes");
        else System.out.println("No");


    }

}


算法2

使用dfs(注意:在这里使用java会直接爆栈hh)

  • dfs(u,c)表示把u号点染色成c颜色,并且判断从u号点开始染其他相连的点是否染成功

时间复杂度 $O(m + n)$

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int n;
    static int m;
    static int N = 100010;
    static int M = 200010;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int idx = 0;
    static int[] color = new int[N];//共1和2两种不同的颜色
    static boolean[] st = new boolean[N];
    public static void add(int a,int b)
    {
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    //dfs(u,c)表示把u号点染色成c颜色,并且判断从u号点开始染其他相连的点是否成功
    public static boolean dfs(int u,int c)
    {
        color[u] = c;
        for(int i = h[u];i != -1;i = ne[i])
        {
            int j = e[i];
            if(color[j] == 0)
            {
                if(!dfs(j,3 - c)) return false;
            }
            else if(color[j] == c) return false;//颜色重复
        }
        return true;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] str1 = reader.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        m = Integer.parseInt(str1[1]);
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            String[] str2 = reader.readLine().split(" ");
            int a = Integer.parseInt(str2[0]);
            int b = Integer.parseInt(str2[1]);
            add(a,b);
            add(b,a);
        }
        boolean flag = true;//标记是否染色成功
        for(int i = 1;i <= n;i++)
        {
            //若未染色
            if(color[i] == 0)
            {
                if(!dfs(i,1)) 
                {
                    flag = false;
                    break;
                }
            }
        }
        if(flag) System.out.println("Yes");
        else System.out.println("No");
    }
}




小呆呆
3小时前

算法分析

21276d14946625a97ee0ba2d2dc39f6.png

时间复杂度 $O(mlogm)$

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;


public class Main {
    static int n;
    static int m;
    static int q;
    static int N = 100010;
    static int M = 200010;
    static int INF = 0x3f3f3f3f;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int idx = 0;
    static boolean[] st = new boolean[N];
    static List<PIIs> list = new ArrayList<PIIs>();
    static int[] p = new int[N];
    public static void add(int a,int b,int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    //找到祖宗编号,并进行路径压缩
    public static int find(int x)
    {
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    }
    public static int kruskal()
    {
        int res = 0;
        int cnt = 0;//计算走过的边数
        Collections.sort(list);
        for(int i = 1;i <= n;i++) p[i] = i;

        for(PIIs item : list)
        {
            int a = item.getA();
            int b = item.getB();
            int w = item.getW();
            a = find(a);
            b = find(b);
            if(a != b) 
            {
                p[a] = b;
                res += w;
                cnt ++;
            }
        }
        if(cnt < n - 1) return INF;
        return res;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] str1 = reader.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        m = Integer.parseInt(str1[1]);
        while(m -- > 0)
        {
            String[] str2 = reader.readLine().split(" ");
            int a = Integer.parseInt(str2[0]);
            int b = Integer.parseInt(str2[1]);
            int c = Integer.parseInt(str2[2]);
            add(a,b,c);
            list.add(new PIIs(a,b,c));
        }
        int t = kruskal();
        if(t == INF) System.out.println("impossible");
        else System.out.println(t);

    }

}
class PIIs implements Comparable<PIIs>
{
    private int a;
    private int b;
    private int w;
    public int getA()
    {
        return this.a;
    }
    public int getB()
    {
        return this.b;
    }
    public int getW()
    {
        return this.w;
    }
    public PIIs(int a,int b,int w)
    {
        this.a = a;
        this.b = b;
        this.w = w;
    }
    @Override
    public int compareTo(PIIs o) {
        // TODO 自动生成的方法存根
        return Integer.compare(w, o.w);
    }

}



小呆呆
4小时前

算法分析

a209dc1bdc0bf0a07abd792625e3d15.png

时间复杂度 $O(n^2)$

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {
    static int n;
    static int m;
    static int q;
    static int N = 510;
    static int INF = 0x3f3f3f3f;
    static int[][] g = new int[N][N];
    static int[] dist = new int[N];//表示到集合的最短距离
    static boolean[] st = new boolean[N];
    public static int prim()
    {
        Arrays.fill(dist, INF);
        int res = 0;
        for(int i = 0;i < n;i++)
        {
            int t = -1;
            for(int j = 1;j <= n;j++)
            {
                if(!st[j] && (t == -1 || dist[t] > dist[j]))
                    t = j;
            }
            if(i != 0 && dist[t] == INF) return INF;
            //标记已加入集合
            st[t] = true;
            if(i != 0) res += dist[t];
            //用t更新其他点
            for(int j = 1;j <= n;j++) dist[j] = Math.min(dist[j], g[t][j]);
        }
        return res;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] str1 = reader.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        m = Integer.parseInt(str1[1]);
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
            {
                g[i][j] = INF;
            }
        while(m -- > 0)
        {
            String[] str2 = reader.readLine().split(" ");
            int a = Integer.parseInt(str2[0]);
            int b = Integer.parseInt(str2[1]);
            int c = Integer.parseInt(str2[2]);
            g[a][b] = Math.min(g[a][b], c);
            g[b][a] = Math.min(g[b][a], c);
        }
        int t = prim();
        if(t == INF) System.out.println("impossible");
        else System.out.println(t);

    }

}




一笑奈何
4小时前

题目描述

blablabla

C++ 代码

#include<iostream>
using namespace std;

int pi(int x)
{
    int temp = 0;
    while (x != 0) {
        if (temp > INT_MAX / 10 || temp < INT_MIN / 10)
            return 0;
        temp = temp * 10 + x % 10;
        x = x / 10;
    }
    return temp;
}





defddr
5小时前

题目描述

给你一个整数数组 nums,请你找出并返回能被三整除的元素最大和。

样例

示例 1:

输入:nums = [3,6,5,1,8]
输出:18
解释:选出数字 3, 6, 1 和 8,它们的和是 18(可被 3 整除的最大和)。
示例 2:

输入:nums = [4]
输出:0
解释:4 不能被 3 整除,所以无法选出数字,返回 0。
示例 3:

输入:nums = [1,2,3,4,4]
输出:12
解释:选出数字 1, 3, 4 以及 4,它们的和是 12(可被 3 整除的最大和)。
 

提示:

1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4


算法1

最后数组和 只有三种情况
1 除以3余0 直接返回
2 除以3余1 那么要么减少一个除以3余1的数字 或者减少两个除以3余2的数字
3 除以3余2 那么要么减少一个除以3余2的数字 要么减少两个除以3余1的数字

C++ 代码

class Solution {
public:
    vector<int> v[3];
int Check(int singleIdx,int doubleIdx,int sum)
{
    //如果减少两个数目的那个数组记录都不到2个 那么肯定只有减少一个数字的方案
    if (v[doubleIdx].size() < 2) {
            return sum - v[singleIdx][0];
        }
        else if (v[singleIdx].size() == 0) {
            //如果减少一个数目的方案 不可行(单个数组记录一个元素都没有)
            //那么减少两个数字的方案一定可行
            return sum - v[doubleIdx][0] - v[doubleIdx][1];
        }
        else {
            //减少两个数字和减少一个数字的方案都可行 选取和少的那种方案
            int rem = v[singleIdx][0];
            if (rem > (v[doubleIdx][0] + v[doubleIdx][1]))  rem = (v[doubleIdx][0] + v[doubleIdx][1]);

            return sum - rem;
        }
}

int maxSumDivThree(vector<int>& nums) {
    int sum = 0;
    for (int i = 0; i < nums.size(); i++)
    {
        sum += nums[i];
        if (nums[i] % 3 == 1) {
            v[1].push_back(nums[i]);
        }
        else if(nums[i] % 3 == 2){
            v[2].push_back(nums[i]);
        }
    }

    sort(v[1].begin(), v[1].end());
    sort(v[2].begin(), v[2].end());
    int sum_n = sum % 3;

    if (sum_n == 0) return sum;
    if (sum_n == 1) {
        //减少两个v2 和一个v1 选择
        return Check( 1, 2,sum);
    }

    if(sum_n == 2){
        //减少两个v1 和一个v2 选择
        return Check( 2, 1,sum);
    }

    return -1;
}

};



defddr
5小时前

题目描述

给出一个满足下述规则的二叉树:

root.val == 0
如果 treeNode.val == x 且 treeNode.left != null,那么 treeNode.left.val == 2 * x + 1
如果 treeNode.val == x 且 treeNode.right != null,那么 treeNode.right.val == 2 * x + 2
现在这个二叉树受到「污染」,所有的 treeNode.val 都变成了 -1。

请你先还原二叉树,然后实现 FindElements 类:

FindElements(TreeNode* root) 用受污染的二叉树初始化对象,你需要先把它还原。
bool find(int target) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

样例

1.jpg

输入:
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
输出:
[null,false,true]
解释:
FindElements findElements = new FindElements([-1,null,-1]); 
findElements.find(1); // return False 
findElements.find(2); // return True 

2.jpg

输入:
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
输出:
[null,true,true,false]
解释:
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False

3.jpg

输入:
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
输出:
[null,true,false,false,true]
解释:
FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // return True
findElements.find(3); // return False
findElements.find(4); // return False
findElements.find(5); // return True

提示:

TreeNode.val == -1
二叉树的高度不超过 20
节点的总数在 [1, 10^4] 之间
调用 find() 的总次数在 [1, 10^4] 之间
0 <= target <= 10^6


算法1

使用数组表示二叉树 根为x 则左子树为2x+1 右子树为2x+2
恰好索引就是题目中各个节点的值

那么建立一个数组 记录输入二叉树所拥有的节点 查询就非常简单 直接根据查询值看该数组的索引是否已经标记

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class FindElements {
public:

    vector<int> record;

void Dfs(TreeNode* root, int k) {
    if (root == NULL)
        return;
    root->val = k;
    record[k] = 1;

    Dfs(root->left, k * 2 + 1);
    Dfs(root->right, k * 2 + 2);
}

 FindElements(TreeNode* root) {
    record.resize(10000000, -1);
    Dfs(root, 0);
}

bool find(int target) {
    return record[target] == 1;
}

};

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */




Stella-W
6小时前

第二道题

感觉刷完算法基础课的大部分题就可以做kickstart了,原来看的很懵b的题现在思路都很直白了。1.5倍走起

对与二分有了更深的理解,二分往往用于找到边界值,把数据分成满足和不满足的两种类别,可用于解决
求最小值最大或者最小值最小问题

斜 45 度正方形
思路:二分一个k,然后从所有已有补给站bfs k层,然后找到所有没覆盖的点。
之后建站看是否能在k步内覆盖到,如果可以接受k,如果拒绝再继续二分k。

曼哈顿距离性质,二分,bfs




枫叶银鱼
8小时前

题目描述

给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

样例

示例1:

输入: "aacecaaa"
输出: "aaacecaaa"

示例2:

输入: "abcd"
输出: "dcbabcd"

算法1

(KMP) $O(n)$

暴力做法是逐次尝试添加字符,看是否能构成回文串,这里添加字符的顺序是从末尾开始,首先尝试添加末尾字符,然后尝试添加末两位字符等等,注意这里要逆序后才能添加。最多枚举$n$次,每次判断需要$O(n)$的复杂度,总时间复杂度为$O(n^2)$。

可以注意到如果添加 $k$ 个字符就能构成回文串,等价于字符串前 $n - k$ 个字符是回文的,而回文的定义是正反都一样,所以问题转化为字符串从第一个字符开始,最长的回文子串是多少。这个可以利用KMP中的next数组来求,回想到next[i]等于以i为结尾的字符串的最长公共前后缀的长度,注意这里前缀和后缀是不包含最后一个和第一个字符的,不然对每个字符串而言最长公共前后缀就是本身了。

我们可以将字符串逆序拼接到原字符串后形成的新字符串记为t,长度设为m,那么next[m]就是原字符串的从第一个字符开始的最长回文子串。注意在拼接t的时候要先在原字符串后添加一个不存在的字符,不然对于字符串aaaa来说形成的t串的 $next[m] = 2n - 1$,超过了原字符串的长度。

这里next[i]中的i代表着第 $i$ 个字符,下标是从1开始的,显然next[1] = 0,因为只有一个字符的时候不存在前后缀,所以长度为0。而字符串的下标是从0开始的,为了方便处理,我们可以在字符串首加一个字符使得下标也从1开始。

而求next[i]则可以利用递推或者叫动态规划的思想在 $O(n)$ 的时间对每个$i$都求出来,假如已经求出了next[0],...,next[i - 1],我们令j = next[i - 1],然后我们先比较第 $i$ 个字符和第 $j + 1$ 个字符是否相等,如果相等那么next[i] = j + 1并且更新j,不然我们就利用next数组来不断的进行回退,即j = next[j]。这里始终维护对于每个i而言,j是可能匹配的最大位置,j + 1是将要匹配的位置。

C++ 代码

class Solution {
public:
    string shortestPalindrome(string s) {
        string t = "#" + s + "#" + string(s.rbegin(), s.rend());
        int n = t.size() - 1;
        vector<int> ne(n + 1, 0);

        for (int i = 2, j = 0; i <= n; i ++ ) {
            while (j && t[i] != t[j + 1]) j = ne[j];
            if (t[i] == t[j + 1]) j ++ ;
            ne[i] = j;
        }
        string rev = s.substr(ne[n]);
        reverse(rev.begin(), rev.end());
        return rev + s;
    }
};

这里也可以让next和字符串的下标都从 $0$ 开始,不过j变成了要匹配的位置,回退的时候要用next[j - 1], next数组的含义同样是下标以 $i$ 为结尾的字符串的最长公共前后缀长度,所以next[0] = 0。这种写法对求next数组的递推思想体现的更明显一些。

class Solution {
public:
    string shortestPalindrome(string s) {
        string t = s + "#" + string(s.rbegin(), s.rend());
        int n = t.size();
        vector<int> ne(n, 0);

        for (int i = 1, j; i < n; i ++ ) {
            j = ne[i - 1];
            while (j && t[i] != t[j]) j = ne[j - 1];
            if (t[i] == t[j]) j ++ ;
            ne[i] = j;
        }
        string rev = s.substr(ne[n - 1]);
        reverse(rev.begin(), rev.end());
        return rev + s;
    }
};



小呆呆
17小时前

算法分析

(y总真言,简单易懂)

  • f[i, j, k]表示从i走到j的路径上除了i, j以外不包含点k的所有路径的最短距离。那么f[i, j, k] = min(f[i, j, k - 1), f[i, k, k - 1] + f[k, j, k - 1]
    因此在计算第k层的f[i, j]的时候必须先将第k - 1层的所有状态计算出来,所以需要把k放在最外层。

  • 读入邻接矩阵,将次通过动态规划装换成从ij的最短距离矩阵

  • 在下面代码中,判断从a到b是否是无穷大距离时,需要进行if(t > INF/2)判断,而并非是if(t == INF)判断,原因是INF是一个确定的值,并非真正的无穷大,会随着其他数值而受到影响,t大于某个与INF相同数量级的数即可

时间复杂度 $O(n^3)$

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
    static int n;
    static int m;
    static int q;
    static int N = 210;
    static int INF = 0x3f3f3f3f;
    static int[][] d = new int[N][N];
    public static void floyd()
    {
        for(int k = 1;k <= n;k++)
            for(int i = 1;i <= n;i++)
                for(int j = 1;j <= n;j++)
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] str1 = reader.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        m = Integer.parseInt(str1[1]);
        q = Integer.parseInt(str1[2]);
        for(int i = 1;i <= n;i++)
        {
            for(int j = 1;j <= n;j++)
            {
                if(i == j) d[i][j] = 0;
                else d[i][j] = INF;
            }
        }
        while(m -- > 0)
        {
            String[] str2 = reader.readLine().split(" ");
            int a = Integer.parseInt(str2[0]);
            int b = Integer.parseInt(str2[1]);
            int c = Integer.parseInt(str2[2]);
            d[a][b] = Math.min(d[a][b], c);//若有重边选择短的边
        }
        floyd();
        while(q -- > 0)
        {
            String[] str3 = reader.readLine().split(" ");
            int a = Integer.parseInt(str3[0]);
            int b = Integer.parseInt(str3[1]);
            int t = d[a][b];
            if(t > INF / 2) System.out.println("impossible");
            else System.out.println(t);

        }

    }

}




小呆呆
17小时前

算法分析

使用spfa算法解决是否存在负环问题

  • 1、dist[x] 记录当前1到x的最短距离

  • 2、cnt[x] 记录当前最短路的边数,初始每个点到1号点的距离为0,只要他能再走n步,即cnt[x] >= n,则表示该图中一定存在负环,由于从1到x至少经过n条边时,则说明图中至少有n + 1个点,表示一定有点是重复使用

  • 3、若dist[j] > dist[t] + w[i],则表示从t点走到j点能够让权值变少,因此进行对该点j进行更新,并且对应cnt[j] = cnt[t] + 1,往前走一步

注意:该题是判断是否存在负环,并非判断是否存在从1开始的负环,因此需要将所有的点都加入队列中,更新周围的点
af80e800140cbcf01e93d657d712a60.png

时间复杂度 一般:$O(m)$ 最坏:$O(nm)$

参考文献

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int n;
    static int m;
    static int N = 2010;
    static int M = 10010;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int idx = 0;
    static int[] dist = new int[N];//记录当前1到x的最短距离
    static int[] cnt = new int[N];//从1到点到x经过的边数 
    static boolean[] st = new boolean[N];

    public static void add(int a,int b,int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;

    }
    public static boolean spfa()
    {
        Queue<Integer> queue = new LinkedList<Integer>();
        //将所有点进入队列
        for(int i = 1;i <= n;i++)
        {
            queue.add(i);
            st[i] = true;
        }
        while(!queue.isEmpty())
        {
            int t = queue.poll();
            st[t] = false;
            for(int i = h[t]; i != -1;i = ne[i])
            {
                int j = e[i];
                if(dist[j] > dist[t] + w[i])
                {
                    dist[j] = dist[t] + w[i];
                    cnt[j] = cnt[t] + 1; 

                    if(cnt[j] >= n) return true;
                    if(!st[j])
                    {
                        queue.add(j);
                        st[j] = true;
                    }


                }
            }
        }
        return false;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] str1 = reader.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        m = Integer.parseInt(str1[1]);
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            String[] str2 = reader.readLine().split(" ");
            int a = Integer.parseInt(str2[0]);
            int b = Integer.parseInt(str2[1]);
            int c = Integer.parseInt(str2[2]);
            add(a,b,c);
        }
        if(spfa()) System.out.println("Yes");
        else System.out.println("No");
    }

}