小题小做 | 真迹绝 真心能给谁
Cobb 740 1

查找最长公共子串


#include <iostream>
#include <string>
using namespace std;

// 查找最长公共子串
int main()
{
    string str1, str2;
    cin >> str1 >> str2;

     // 记录最长的公共子串
    int max = 0;

    for (int i = 0; i < str1.size(); i++)
    {
        int offset = 0;
        for (;;)
        {
            int j = str2.find(str1[i], offset);
            if (j == string::npos)
                break;

            int size = 0;
            for (int m = i, n = j; str1[m] != '\0' && str2[n] != '\0'; m++, n++)
            {
                if (str1[m] == str2[n])
                    size++;
                else
                    break;
            }

            if (size > max)
            {
                max = size;
            }
            offset = j + 1;
        }

    }
    cout << max << endl;
}

查找1000以内的完数

int main()
{
    vector<int> v;
    for (int i = 1; i < 1000; i++)
    {
        // 判断i是否是完数
        int sum = 0;
        for (int j = 1; j <= i / 2; j++)
        {
            if (i % j == 0)
            {
                sum += j;
                v.push_back(j);
                // v[k++] = j;
            }
        }

        // 输出打印
        if (sum == i)
        {
            cout << i << "是完数:";
            for (int k = 0; k < v.size() - 1; k++)
            {
                cout << v[k] << ",";
            }
            // v.back(); 访问容器的最后一个元素
            cout << v[v.size() - 1] << endl;
        }
        v.clear();
    }
}

括号匹配(栈)


bool IsSignMatchAll(string signStr)
{
    // 括号数量为奇数,则不匹配,直接返回
    if (signStr.size() % 2 != 0)
    {
        return false;
    }

    stack<char> s;
    char cmp;
    for (char ch : signStr)
    {
        if (ch == '{' || ch == '(' || ch == '[')
        {
            s.push(ch);
        }
        else
        {
            switch (ch)
            {
            case '}':
                cmp = '{';
                break;
            case ')':
                cmp = '(';
                break;
            case ']':
                cmp = '[';
                break;
            }
            if (s.empty())
                return false;
            char top = s.top();
            s.pop();
            if (top != cmp)
                return false;
        }
    }

    return s.empty();
}

笔试面试题目:阿里选班长

文章出自

题目: 已知数组中有一个数字出现的次数,超过数组长度的一半,要求找出这个数字。

方案一:暴力排序

排序是最容易想到的一种方法。由于目标元素的次数超过数组长度的一半,所以排序后直接取中间元素就行。

阿里巴巴会出这么简单的题目吗?有点搞笑!我们知道,基于比较的排序,时间复杂度能达到O(NlogN), 但这不是最好的方法,无法通过面试。

方案二:计数统计

既然题目的意思是求出这个次数超过一半的元素,那就对次数进行计数吧,直接搞个hashmap就行了。此时,时间复杂度是O(N), 但空间复杂度也是O(N),无法通过面试。

而且要注意到,使用计数法的时候,漏用了题目中的信息:超过数组长度的一半。显然,这是不合理的。这就跟你高考数学一样,你发现有个条件居然没用到,而你把题目做出来了,那是很值得怀疑的。

方案三:摩尔投票

接下来,我们来介绍一种很巧妙的思路,即摩尔投票法,时间复杂度是O(N), 空间复杂度是O(1),能满足面试要求。思路是怎样的呢?

我们来看一种现实中的投票场景: 班级要开始选班长 要求半数以上通过 选出来的就是班长

我们先来看一种简单的情况:假如只有2个人A和B竞争班长这一职位。那么,在大家投票后,我们从投票箱中取数后,可以这样统计: 先抽一张票,如果是A,则记录当前胜利者为A,票数:1 再抽一张票,如果是A,则记录当前胜利者为A,票数:2 再抽一张票,如果是B,则抵消,记录当前胜利者为A,票数:1 再抽一张票,如果是B,则抵消,记录无当前胜利者 再抽一张票,如果是A,则记录当前胜利者为A,票数:1 ... 如此循环,直到所有票统计完毕,最后有票的一方,就是胜利者,就是大家选出来的班长。

如上只是两方进行PK, 那么,当候选人为多人时,也可以使用类似的思路,这里的前提条件就是:一定存在多余半数票的候选人。

当多方进行PK时,占据着半数以上票数的班长,可以任性地抵消任何人的票,而且其他人之间的相互抵消也不会撼动班长的位置。

有的朋友看到这里,可能觉得有点绕,那么,我们一起来看看程序,并打印关键步骤,有兴趣的朋友可以对照程序和结果理解下。

阿里巴巴主要是用Java编程, 但也有C++岗位,如下是对应的C++程序代码:

//不相同的就抵消,相同的计数+1
#include <iostream>
using namespace std;

int solution(int a[], int n) {    
  int count = 0, value = a[0];
  for(int i = 0; i < n; i++)
  {
    printf("log, i=%d, count=%d, value=%d\n", i, count, value);
    if(count == 0)
    {
      value = a[i];
    }

    if(a[i] == value)
    {
      count++;
    }
    else
    {
      count--;
    } 
  }

  return value;
}


int main()
{
   int a[]={6,2,5,3,4,2,2,2,2,5};
   int n = sizeof(a) / sizeof(a[0]);
   cout << solution(a, n) << endl;
   return 0;
}

log, i=0, count=0, value=6
log, i=1, count=1, value=6
log, i=2, count=0, value=6
log, i=3, count=1, value=5
log, i=4, count=0, value=5
log, i=5, count=1, value=4
log, i=6, count=0, value=4
log, i=7, count=1, value=2
log, i=8, count=2, value=2
log, i=9, count=3, value=2
2

C++11的LAMBDA使用一例:华容道求解

C++11的LAMBDA使用一例:华容道求解

一个FORK的面试题

题目出处,深入分析

在fork的时候,缓存被复制到了最终的子进程空间!

指针数组和数组指针

若有语句int a[4],p,q[4];且O<=i<4,则错误的赋值是 (A)p=a. (B)q[i]=a[i] (C) p=q[i] (D)p=&a[2][1]

![2N4ZVL(K[52_VP7V~%O_MC

小题小做 | 真迹绝 真心能给谁

例:
3. int a[10]; 问下面哪些不可以表示 a[1] 的地址? ( A )
A. a+sizeof(int) 
B. &a[0]+1       
C. (int*)&a+1   
D. (int*)((char*)&a+sizeof(int))  
/*
考察知识:指针运算
万能的指针运算公式:
Type* a;
a + n;   &a[1] ==> (unsigned int)a + 4   // a[0]是个int型,所以这是a[1]的地址

值相同,类型不同
&a ==》 int(*)[10]   数组类型
a  ==》 int*     指针类型

(unsigned int)a + n * sizeof(Type)
A. (unsigned int)a + 4 * 4
B. (unsigned int)(&a[0]) + 1 * 4
C. (int*)&a 转成 a ==> a + 1 ==> a[1]
D. (unsigned int)a + 4 * 1

*/
评论区

索引目录