精华内容
下载资源
问答
  • 欧拉路径的定义:对于无向图来说,欧拉路径就是通过每条边有且...首先回想一下图的定义,图中有v个顶点,那么着v个顶点中有0个或者个或者以上的顶点度数为奇数。接下来,求欧拉路径就相当于用笔画一个图,笔可

    欧拉路径的定义:对于无向图来说,欧拉路径就是通过每条边有且只有一次,如果遍历的起始点和终止点都是一个顶点的话,那么就说这个图存在欧拉环。


    上图中有三个例子,分别是欧拉路径和欧拉环,以及非欧拉路径。那么怎么来判断一个图中是否含有欧拉路径或者欧拉环呢。首先回想一下图的定义,图中有v个顶点,那么着v个顶点中有0个或者两个或者两个以上的顶点度数为奇数。接下来,求欧拉路径就相当于用笔画一个图,笔可以经过每一个顶点,画出某一条边有且只有一次,而不用离开纸张的表面。

    如果一个图中含有一条欧拉路径,那么它就被称为半欧拉的。先看看第一幅图,含有欧拉路径图的特点,除了顶点0和顶点4之外,其他的顶点的度数都是偶数,这这个图中是2.

    看第二幅图,所有的顶点的度数都是偶数,之后第三幅图,有4个顶点的度数是奇数。那么就能得到非欧拉路径和欧拉路径的区别就是非欧拉路径有超过2个以上的顶点度数为奇数。

    给定欧拉环的算法:

    1,对于所有度数不为0的顶点和他们之间的边组成的图进行检验,看看是否他们组成的图是连通的,如果所有顶点的度数都为0,那么我们可以说这个图是含有欧拉路径的。

    2,判断所有的顶点的度数是否为偶数。

    欧拉路径算法:

    1,对于所有度数不为0的顶点和他们之间的边组成的图进行检验,判断他们组成的图是否是连通的。

    2,对于所有第一步检验的顶点,判断他们之中有奇数度数的个数,如果超过2个以上度数为奇数,那么此图不含欧拉路径。

    下面是代码:

    #include<iostream>
    #include<list>
    using namespace std;
    
    class Graph {
    	int vexNum;
    	list<int>* adjacents;
    public:
    	Graph(int _vexNum);
    	~Graph();
    	void addEdge(int v, int w);
    	void DFSUtil(int v, bool* visited);
    	bool isConnected();
    	int isEulerian();
    };
    
    Graph::Graph(int _vexNum) {
    	vexNum = _vexNum;
    	adjacents = new list<int>[vexNum];
    }
    
    Graph::~Graph() {
    	delete []adjacents;
    }
    
    void Graph::addEdge(int v, int w) {
    	adjacents[v].push_back(w);
    	adjacents[w].push_back(v);
    }
    
    void Graph::DFSUtil(int v, bool *visited) {
    	visited[v] = true;
    	list<int>::iterator iter;
    	for (iter = adjacents[v].begin(); iter != adjacents[v].end(); iter++)
    		if (false == visited[*iter])
    			DFSUtil(*iter, visited);
    }
    
    bool Graph::isConnected() {
    	int v;
    	bool* visited = new bool[vexNum];
    	for (v = 0; v < vexNum; v++)
    		visited[v] = false;
    	for (v = 0; v < vexNum; v++)
    		if (0 != adjacents[v].size())
    			break;
    	if (v >= vexNum)
    		return true;
    	DFSUtil(v, visited);
    	for (v = 0; v < vexNum; v++)
    		if (false == visited[v] && adjacents[v].size() > 0)
    			return false;
    	return true;
    } 
    
    int Graph::isEulerian() {// 0 represents non eulerian, 1 represents eulerian path, 2 represents eulerian cycle
    	bool rst = isConnected();
    	if (!rst)
    		return 0;
    	int v;
    	int odd = 0;
    	for (v = 0; v < vexNum; v++)
    		if (adjacents[v].size() & 0x01)
    			odd++;
    	if (odd > 2)
    		return 0;
    	return odd ? 1 : 2;
    }
    
    void test(Graph& g) {
    	int rst = g.isEulerian();
    	if (0 == rst)
    		cout << "there is no eulerian path or cycle" << endl;
    	else if (1 == rst)
    		cout << "there is a eulerian path" << endl;
    	else
    		cout << "there is a eulerian cycle" << endl;
    }
    
    int main(int argc, char* argv[]) {
    	Graph g1(5);
        g1.addEdge(1, 0);
        g1.addEdge(0, 2);
        g1.addEdge(2, 1);
        g1.addEdge(0, 3);
        g1.addEdge(3, 4);
        test(g1);
     
        Graph g2(5);
        g2.addEdge(1, 0);
        g2.addEdge(0, 2);
        g2.addEdge(2, 1);
        g2.addEdge(0, 3);
        g2.addEdge(3, 4);
        g2.addEdge(4, 0);
        test(g2);
     
        Graph g3(5);
        g3.addEdge(1, 0);
        g3.addEdge(0, 2);
        g3.addEdge(2, 1);
        g3.addEdge(0, 3);
        g3.addEdge(3, 4);
        g3.addEdge(1, 3);
        test(g3);
     
        // Let us create a graph with 3 vertices
        // connected in the form of cycle
        Graph g4(3);
        g4.addEdge(0, 1);
        g4.addEdge(1, 2);
        g4.addEdge(2, 0);
        test(g4);
     
        // Let us create a graph with all veritces
        // with zero degree
        Graph g5(3);
        test(g5);
    	cin.get();
    	return 0;
    }
    


    展开全文
  • 函数find 的功能是查找串s1 中是否包含指定的词(s2 指向),如果存在则返回第1出现的位置,否则返回-1。约定串中的词由1个或1个以上的空格符分隔。 2.定义函数void Merge(int a[], int n, int b[], ...
  • 20、完善过滤机制,在留言板、相片和博客评论等处的信息,如果包含4位以上数字或email信息者,发布失败,弹出完善资料,通过站内联系或者升级vip之类的友情提示! 21、保留uchome和uc架构,方便后续版本的升级,方便...
  • 20、完善过滤机制,在留言板、相片和博客评论等处的信息,如果包含4位以上数字或email信息者,发布失败,弹出完善资料,通过站内联系或者升级vip之类的友情提示!21、保留uchome和uc架构,方便后续版本的升级,方便...
  •  3、 双击下载的文件包setup.exe,开始安装过程,根据提示进行操作,完成安装(系统将会自动重起两次)  4、 如果在安装过程中出现一些“读文件错误”之类的提示,可能是安装文件在下载过程中损坏,重新下载  5...
  • <ol><li>num 的长度小于 10002 且 ≥ k</li><li>num 不会包含任何前导零</li></ol> 题解: 这道题的初步感觉是挺简单的,但是仔细想了之后发现并不简单。 可以把问题分解为:当前选择是移除1个...
  • Metadata Tag类似,包含Tag Header和Tag Data个子树,并且对应子项的详细信息也都列出; file header info, metadata info, tag position info —— 包含File Header + Metadata Tag的详细信息,Video&Audio Tags...
  • JVM垃圾回收算法

    2021-01-08 08:12:40
    前一篇提到了判断内存对象是否可回收的种算法:Reference Counting GC、Tracing GC。 从垃圾内存的回收角度看,大部分垃圾收集器遵从了分代收集(Generational Collection)理论。其包含 3 个经验假说: 绝大...

    前一篇提到了判断内存对象是否可回收的两种算法:Reference Counting GC、Tracing GC。

     

    从垃圾内存的回收角度看,大部分垃圾收集器遵从了分代收集(Generational Collection)理论。其包含 3 个经验假说:

    • 绝大多数对象都是朝生夕死

    • 熬过越多次垃圾收集过程的对象就越难消亡

    • 跨代引用相对于同代引用来说仅占极少数

     

    基于以上假说

    • 常用的收集器把 Java Heap 划分为不同的区域,根据对象熬过的回收次数,分配到不同的内存区域

    • 绝大部分新分配的对象生存时间较短,放到一个区域

    • 多次熬过垃圾回收的对象放到一个区域,低频回收

     

    基于此

    • Java Heap 一般划分了新生代(Young Generation)和老年代(Old Generation)

    • 一般新生代分配新对象,熬过多次回收的对象移到老年代

    • 建立 Remembered Set,把老年代划分为若干小块,标识出跨代引用的小块在新生代 GC 时被纳入 GC Roots 扫描,解决跨代引用问题

     

    以上过程中

    • 新生代的垃圾收集,叫:Minor GC 或 Young GC

    • 老年代的垃圾收集,叫:Major GC 或 Old GC

    • 新生代 + 部分老年代垃圾收集,叫:混合收集,Mixed GC

    • 整堆 Heap + 方法区的收集,叫:Full GC

     

    针对新生代与老年代回收垃圾内存的特点,提出了 3 种不同的算法:

    1、标记-清除算法(Mark-Sweep)

    标记需回收对象,统一回收;或标记存活对象,回收未标记对象。

    缺点:

    • 大量对象需要标记与清除时,效率不高

    • 标记、清除产生的大量不连续内存碎片,导致无法分配大对象

     

    2、标记-复制算法(Mark-Copy)

    可用内存等分两块,使用其中一块 A,用完将存活的对象复制到另外一块 B,一次性清空 A,然后改分配新对象到 B,如此循环。

    缺点:

    • 不适合大量对象不可回收的情况,换句话说就是仅适合大量对象可回收,少量对象需复制的区域

    • 只能使用内存容量的一半,浪费较多内存空间


    3、标记-整理算法(Mark-Compact)

    标记存活的对象,统一移到内存区域的一边,清空占用内存边界以外的内存。

    缺点:

    • 移动大量存活对象并更新引用,需暂停程序运行

     

    不同的垃圾收集器,在不同的内存区域,对这 3 种算法进行了取舍与整合。

     

     


    【Java学习资源】整理推荐

     

     


    【Java面试题与答案】整理推荐

     

    展开全文
  • 题目:给定一个正整数,看作字符串,判断这个数是否包含两次或者两次以上的子串。 如“12121”就包含两次“12”, 再如”12345“就不包含重复的子串。 一、std::string的find接口介绍 首先解决一个问题,判定...

    今天做了一个上机题,题目很简单,正好重温下std::string类的一些接口以及stringstream的简单用法。

    题目:给定一个正整数,看作字符串,判断这个数是否包含两次或者两次以上的子串。

    如“12121”就包含两次“12”,

    再如”12345“就不包含重复的子串。

     

    一、std::string的find接口介绍

    首先解决一个问题,判定一个串t是否在串s中出现过的次数。这个可以使用std::string提供的find接口。

    这个接口的原型为:

    size_t find(string&str, size_t pos = 0);
    
    size_t find(char*s, size_t pos = 0);
    
    size_t find(char*s, size_t pos, size_type n);
    
    size_t find(char c, size_t pos =0);

    重载的4个接口里,返回类型均为size_t类型。

    如果找到对应的pattern,那么返回pattern在s中的第一个下标位置。

    如果查找失败,那么返回string::npos,这个值定义为常量-1

    static const size_t npos = -1;

     

    参数中的pattern既可以是string类型,也可以是char*类型,也可以是单个字符,所以常见的查找的对象基本被包含了。

    其中第三个接口被用来查找无“\0”结果的字符数组/buffer。查找的长度为n。

    string s = "abcdefg12";
    char t[3]={'d','e','f'};
    size_t idx = s.find(t, 0, 3);
    //cout << idx << endl;//3

     

    如果不指定n,那么就是第二个find声明,即期望patter为"\0"结尾的字符串

    pos指的是从母串s中开始查找的位置下标。

     

    二、利用find接口查找重复子串

     

    const int TIMES = 2;
    
    bool check_dup_str(string& s, string& t)
    {
       size_t idx = 0;
      size_t beg = 0;
      idx = s.find(t, beg);
      while(string::npos != idx) {
        ++count;
        beg = idx + t.length();
        idx = s.find(t, beg);
      }
      
      if (count >= TIMES) {
        return true;
      } else {
        return false;
      }
    
    }

     

    函数check_dup_str用来检测t在s中出现的次数是否大于等于2,如果是返回true,否则返回false。

    这里使用了find的第一个重载的接口,t为对应的pattern, pos为母串中开始查找的位置。每次查找到一个pattern后,计数,同时跳过pattern的长度,在余下的母串中继续查找。

     

    三、完成题目

      这里直接蛮力解决,找出所有的子串,然后调用check_dup_str进行检查,一旦找到第一个满足的情况就退出。

    int check_dup_str(string& s)
    {
        bool found_flag = false;
        for (int i = 0; !found_flag && i < s.length()-1; i++) {
            for (int j = i+1; j < s.length(); j++) {
                string tmp_str = s.substr(i, j-i+1);
                if (is_t_in_s_2(s, tmp_str)) {
                    found_flag = true;
                    break;
                }
            }
        } // for
        
        if (found_flag) {
            return 1;
        } else {
            return 0;
        }
    }

    蛮力枚举子串就不多说,这里提下,退出两层循环的常用方法:“内部break+外部布尔变量”

    这里找到第一个满足的子串就退出函数。或者在内部for中直接return出来。

    如果需要在两层for之后继续其他逻辑,不想直接return,那么就内部先break出来,由于break只能退出一层,为了同时退出外层循环,可以break之前设置一个flag,这里是found_flag,使得退出内部for之后,found_flag为true,同时在外层循环中设置对这个flag的依赖。

    当外层for需要继续迭代的时候,由于依赖了内部设置的flag,因此会直接退出外层for循环,这样就实现了二层循环的退出。

     

    这应该是大一时候学习的方法吧,汗,早就忘记了,今天也是急中生智想出来:(。

     

    四、main函数

    int _tmain(int argc, _TCHAR* argv[])
    {
        int input;
        cin >> input;
        string str;
        stringstream ss;
        ss << input;
        ss >> str;
        cout << check_dup_str(str) << endl;
        return 0;
    }

    这里提到一下stringstream的用法,其实在C的<stdio。h>中包含了一些int/char/char*之间的转换,而stringstream则是采用对象封装的形式实现了这些基本常用类型之间的转换。老式转换中<stdio.h>,需要小心处理申请的缓冲区大小。如itoa, atoi等。

    而stringstream内部封装了buffer,可以根据具体的转换类型自行管理缓冲区,因此带来了方便。

    本题中将int转型为string类型。当然也可以string到int,类比同样可以char*到int等。(char*到string,string(char*), 再到int)

     

     

    转载于:https://www.cnblogs.com/crafet/p/3661567.html

    展开全文
  • HDU3518 Boring counting

    2019-10-06 17:32:24
    要求统计出现两次以上不重叠的子串,其实就是统计出现两次以上不重叠的后缀的前缀,不难想到height数组。 相邻的后缀只有包含和被包含关系,或者不在同一块内,重复出现的前缀肯定在这块的height里,所以我们统计...

    后缀数组

    要求统计出现两次以上不重叠的子串,其实就是统计出现两次以上不重叠的后缀的前缀,不难想到height数组。

    相邻的后缀只有包含和被包含关系,或者不在同一块内,重复出现的前缀肯定在这块的height里,所以我们统计连续块内最小和最大的sa相减判断是否满足条件即可。

    #include <bits/stdc++.h>
    #define INF 0x3f3f3f3f
    #define full(a, b) memset(a, b, sizeof a)
    #define __fastIn ios::sync_with_stdio(false), cin.tie(0)
    #define pb push_back
    using namespace std;
    using LL = long long;
    inline int lowbit(int x){ return x & (-x); }
    inline int read(){
        int ret = 0, w = 0; char ch = 0;
        while(!isdigit(ch)){
            w |= ch == '-', ch = getchar();
        }
        while(isdigit(ch)){
            ret = (ret << 3) + (ret << 1) + (ch ^ 48);
            ch = getchar();
        }
        return w ? -ret : ret;
    }
    template <typename A>
    inline A __lcm(A a, A b){ return a / __gcd(a, b) * b; }
    template <typename A, typename B, typename C>
    inline A fpow(A x, B p, C lyd){
        A ans = 1;
        for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;
        return ans;
    }
    const int N = 2000;
    string s;
    LL ans;
    
    namespace SuffixArray{
    
        string s;
        int sa[N], t[N], t2[N], c[N], rank[N], height[N];
    
        void build(int m, int n){
            int *x = t, *y = t2;
            for(int i = 0; i < m; i ++) c[i] = 0;
            for(int i = 0; i < n; i ++) c[x[i] = s[i]] ++;
            for(int i = 0; i < m; i ++) c[i] += c[i - 1];
            for(int i = n - 1; i >= 0; i --) sa[--c[x[i]]] = i;
            for(int k = 1; k <= n; k <<= 1){
                int p = 0;
                for(int i = n - k; i < n; i ++) y[p++] = i;
                for(int i = 0; i < n; i ++){
                    if(sa[i] >= k) y[p++] = sa[i] - k;
                }
                for(int i = 0; i < m; i ++) c[i] = 0;
                for(int i = 0; i < n; i ++) c[x[y[i]]] ++;
                for(int i = 0; i < m; i ++) c[i] += c[i - 1];
                for(int i = n - 1; i >= 0; i --) sa[--c[x[y[i]]]] = y[i];
                swap(x, y);
                p = 1, x[sa[0]] = 0;
                for(int i = 1; i < n; i ++){
                    x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && sa[i - 1] + k < n &&
                            sa[i] + k < n && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p ++;
                }
                if(p >= n) break;
                m = p;
            }
    
            int k = 0;
            for(int i = 0; i < n; i ++) rank[sa[i]] = i;
            for(int i = 0; i < n; i ++){
                if(!rank[i]) continue;
                if(k) k --;
                int j = sa[rank[i] - 1];
                while(s[i + k] == s[j + k]) k ++;
                height[rank[i]] = k;
            }
        }
    }
    
    using SuffixArray::build;
    using SuffixArray::sa;
    using SuffixArray::height;
    
    bool solve(int k){
        bool good = false;
        int l = INF, r = 0;
        for(int i = 1; i < s.size(); i ++){
            if(height[i] >= k){
                l = min(l, min(sa[i], sa[i - 1]));
                r = max(r, max(sa[i], sa[i - 1]));
            }
            else{
                if(r - l >= k) ans ++, good = true;
                l = INF, r = 0;
            }
        }
        if(r - l >= k) ans ++, good = true;
        return good;
    }
    
    int main(){
    
        __fastIn;
    
        while(cin >> s && s != "#"){
            SuffixArray::s = s;
            build(128, (int)s.size());
            ans = 0;
            for(int i = 1; i <= (s.size() + 1) / 2; i ++){
                if(!solve(i)) break;
            }
            cout << ans << endl;
        }
        return 0;
    }

    转载于:https://www.cnblogs.com/onionQAQ/p/11411380.html

    展开全文
  • poj3693

    2015-05-06 15:27:00
    我们考虑穷举这个子串长度l,如果某个这个长度的子串出现了两次以上 那他一定包含包含某两个字符s[l*m+1],s[l*(m+1)+1] 这样,我们先判断每对字符能延伸多长(先求LCP,然后判断是否能再向前延伸) 穷举长度L 的...
  • 题目思路:二分答案,然后分组,看一组中是否包含所有字符串,且每个字符串出现两次及两次以上,然后距离差大于等于k。 #include #include #include #include #include #include #include #include #include #...
  • 但是一些个性化的校验以上注解就无能为力了,譬如校验两次输入的密码是否一致。但是ScriptAssert为我们提供了个性化检验参数的能力。 以用户注册为例。在用户注册时我们要校验输入密码与确认密码是否一致,和用户名...
  • CF 1379

    2020-07-30 23:45:11
    '需要定为某一字母,问是否可以使得’abacaba’存在且只存在一。 思路:暴力判。 字符串可能原先就有个或以上’abacaba’ 如果只有一个,那么把’?'都填成’z’就好 如果没有,试着去填出一个‘abacaba’,但是...
  • 算法-滑动窗口

    2020-07-01 13:46:46
    例如以上求连续无重复最大字符串长度,我们可以直接个for循环进行记录比较一直到循环结束,但是如果用滑动窗口只需一循环即可; 先确定左指针指向数组首位,并取元素i=0 此时窗口宽度为1,我们开始判断窗口是否...
  • 以上两个源文件必须包含头文件T_Game.h 1、要话一个3*3的棋盘。 2.接着是下棋 下棋布置下一,所以使用循环。一直下到有结果时退出循环。 每下一,需要判断一。 do { (1)首先人先下 下完, (2)判断是否赢了...
  • 若该学生出现两次以上缺勤或者连续三次及以上迟到则需要接受惩罚。请你判断该学生是否该接受惩罚并返回布尔类型。 字符串中只包含‘A’,‘D’,'L’三种大写字母。 字符串长度不超过10000。 样例 1: 输入样例1: ...
  • "[字符集]" :匹配字符集的任意一个即可,超过个即以上的不录入 例图: "[^字符集]":不包含需要的字符集,但是超过一个即以上的不录 例图: "":vi/vim中一行的开头 例图: [需求数字]:包含需求的数字,任何位置...
  • 自己编写的串口软件,主要应用于固定收发命令的调试过程。所有的命令可以导入导出。 下面是介绍: ...停止××毫秒时间不发送,方便在发送大文件时,用户对比收发是否一致,一旦丢包,用户可以重新设置 发送。
  • UIBK操作系统实验室2018 该存储库包含在2018年夏季学期完成OS实验室练习所... 考勤是强制性的,不能参加两次以上可能会导致不及格。 如果参加了练习,则练习仅算作已完成。 注:为了成功完成此过程中,你需要得到测试
  • 题解:首先,交换区间反转的顺序对结果是没有任何影响的,此外,可以知道对于一个区间进行两次以上的反转是多余的。问题被转化成需要被反转的区间的集合,考虑一下最左端的牛,包含这头牛的区间只有一个,因此这头牛...
  • j2ee实验报告

    2018-06-11 17:48:23
    实验1 j2ee环境搭建 一、实验目的和要求 安装JDK,安装Web Server,IDE,搭建开发环境,完成第一...请检查邮件地址中是否包含“@”符号 请提取邮件地址的域名 请提取邮件地址的用户名,将其转化为Date类型 ………………
  • Windows家族,.NET Framework 2.0及以上版本 IIS 5.0及以上版本 本书14~16章所附代码的运行环境 Windows家族,Apache 2.0及以上版本 PHP 5.0及以上版本 本书17~18章所附代码的运行环境 Windows家族,Tomcat ...
  • Windows家族,.NET Framework 2.0及以上版本 IIS 5.0及以上版本 本书14~16章所附代码的运行环境 Windows家族,Apache 2.0及以上版本 PHP 5.0及以上版本 本书17~18章所附代码的运行环境 Windows家族,Tomcat ...
  • 从互联网下载两次以上的音乐,照片,视频或应用程序。 通过蓝牙接收的文件两次或更多次。 缓存的图像或缩略图,某些媒体应用程序创建它们。 备份文件,一些备份应用程序创建它们。 Search Duplicate File 功能...
  • 设置抽奖总人数、奖项及每个奖项的人数,默认包含两个奖项,如果不想抽取默认的奖项,可以设置该奖项数量为 0 可以新增自定义的奖项,新增后必须将奖项人数设置大于 0 才会在抽奖奖项列表中显示 抽奖结果 显示抽取的...
  • 设置抽奖总人数、奖项及每个奖项的人数,默认包含两个奖项,如果不想抽取默认的奖项,可以设置该奖项数量为 0 可以新增自定义的奖项,新增后必须将奖项人数设置大于 0 才会在抽奖奖项列表中显示 抽奖结果 显示抽取的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 404
精华内容 161
关键字:

两次以上是否包含两次