牛客刷题题目（算法）（自用）

进制转换

https://www.nowcoder.com/practice/8f3df50d2b9043208c5eed283d1d4da6?tpId=37&tqId=21228&rp=1&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37&difficulty=undefined&judgeStatus=undefined&tags=&title=%E8%BF%9B%E5%88%B6

字符串操作

HJ5 进制转换

\hspace{15pt}对于给定的十六进制数，输出其对应的十进制表示。\hspace{15pt}在本题中，十六进制数的格式为：\texttt{0x} 开头，后跟若干个十六进制数字（ \texttt{0-9} 和 \texttt{A-F} ）。其中，\texttt{A-F} 依次代表 10-15 。

    if (s[i] >= 'A' && s[i] <= 'F') {
      sum = sum * 16 + (s[i] - 'A' + 10);		// 记得-'A'
    } else {
      sum = sum * 16 + (s[i] - '0');
    }

HJ1 字符串最后一个单词的长度

\hspace{15pt}对于给定的若干个单词组成的句子，每个单词均由大小写字母混合构成，单词间使用单个空格分隔。输出最后一个单词的长度。

    while (cin >> s);		// 直接while，一直覆盖，读到最后一个单词
    cout << s.size();

HJ17 坐标移动

我们定义一个无限大的二维网格上有一个小人，小人初始位置为 (0,0)(0,0) 点，小人可以读取指令上下左右移动。

一个合法的指令由三至四个符号组成：∙ ∙第一个符号为 "A/D/W/S""A/D/W/S" 中的一个，代表小人移动的方向；分别代表向左、向右、向上、向下移动；记某个时刻小人的坐标为 (x,y)(x,y) ，向左移动一格即抵达 (x−1,y)(x−1,y) 、向右移动一格即抵达 (x+1,y)(x+1,y) 、向上移动一格即抵达 (x,y+1)(x,y+1) 、向下移动一格即抵达 (x,y−1)(x,y−1) 。∙ ∙最后一个符号为 ";"";" ，代表指令的结束，该符号固定存在；∙ ∙中间为一个 1-991-99 的数字，代表小人移动的距离。如果你遇到了一个不合法的指令，则直接忽略；例如，指令 "A100;""A100;" 是不合法的，因为 100100 超出了 1-991-99 的范围；"Y10;""Y10;" 也是不合法的，因为 YY 不是 "A/D/W/S""A/D/W/S" 中的一个。

输出小人最终的坐标。

int x = 0, y = 0;
inline bool isOp(char c) {
    return (c == 'S' || c == 'A' || c == 'D' || c == 'W');
}
inline bool isNumber(char c) {
    return (c >= '0' && c <= '9');
}
void moveOp(int step, char op) {
    switch (op) {
        case 'A':
            x -= step;
            break;
        case 'D':
            x += step;
            break;
        case 'S':
            y -= step;
            break;
        case 'W':
            y += step;
            break;
        default:
            break;
    }
}
 
int main() {
    string s;
    cin >> s;
    string subs;
    int step = 0;
    int i = 0;
    while (i < s.size()) {
        auto pos = s.find(';', i);		//从索引位置 i 开始查找字符 ; 首次出现的位置
        if (pos == string::npos) {		//string中，若没找到，pos 会被赋值为 std::string::npos。
            break;
        }
        subs = s.substr(i, pos - i);	//从i开始，长度为pos-i的子字符串
        // "W4;"
        if (isOp(subs[0]) && subs.size() == 2) {
            if (isNumber(subs[1])) {
                step = subs[1] - '0';
                moveOp(step, subs[0]);
            }
        }
        // "W40;"
        else if (isOp(subs[0]) && subs.size() == 3) {
            if (isNumber(subs[1]) && isNumber(subs[2])) {
                step = (subs[1] - '0') * 10 + subs[2] - '0';
                moveOp(step, subs[0]);
            }
        }
        i = pos + 1;
    }
    cout << x << ',' << y;
}

HJ106 字符逆序

\hspace{15pt}对于给定的由小写字母和空格混合构成的字符串 s，将其翻转后输出。\hspace{15pt}保证给定的字符串 s 的首尾不为空格。

int main() {
    string str;
    getline(cin, str);		// 通过这种方式可以读取一整行字符串，中间有空格也没事
    reverse(str.begin(),str.end());
    cout << str << endl;
}

HJ31 单词倒排

\hspace{15pt}对于给定的若干个单词组成的句子，每个单词均由大小写字母构成，单词间使用非字母字符分隔。输出以单词为单位逆序排放的结果，即仅逆序单词间的相对顺序，不改变单词内部的字母顺序。\hspace{15pt}特别地，在输出结果中，去除原有的分隔符，转而使用单个空格间隔单词。

int main() {
    char c;
    string ans, tmp;
    while (cin.get(c)) {
        if (isalpha(c)) {		// 判断是不是字母（包括大写和小写）
            tmp = tmp + c;
        } else {
            if (!tmp.empty()) {
                if (!ans.empty()) {
                    ans = tmp + ' ' + ans;	// 拼接字符串
                    tmp.clear();		// 清空字符串
                } else {
                    ans = tmp;
                    tmp.clear();
                }
            }
        }
    }
    cout << ans << endl;
}

其他操作

string s;
int asc = (int) s[i]; //能够获取ASCII码

位运算

HJ33 整数与IP地址间的转换

原理：ip地址的每段可以看成是一个0-255的整数，把每段拆分成一个二进制形式组合起来，然后把这个二进制数转变成一个长整数。

举例：一个ip地址为10.0.3.193

每段数字             相对应的二进制数

10                   00001010

0                    00000000

3                    00000011

193                  11000001

组合起来即为：00001010 00000000 00000011 11000001,转换为10进制数就是：167773121，即该IP地址转换后的数字就是它了。

数据范围：保证输入的是合法的 IP 序列

void ipToNum(string ip) {
    long num[4] =  {0, 0, 0, 0};	//不用long会装不下
    int count = 0;
    for (int i = 0; i < ip.size(); i++) {
        if (ip[i] == '.') {
            count++;
        } else {
            num[count] = num[count] * 10 + ip[i] - '0';
        }
    }
    // 数据内部存储的都是二进制
    long output =  (num[0] << 24) | (num[1] << 16) | (num[2] << 8) | (num[3]);	//左移位后，用位或连接
    cout << output << endl;
}

void numToIp(long num) {
    string output = "";
    output += to_string((num >> 24) & 0xff);	// 右移24位后，位与11111111（低八位掩码）
    output += ".";
    output += to_string((num >> 16) & 0xff);	// to_string()将数字转化为string
    output += ".";
    output += to_string((num >> 8) & 0xff);
    output += ".";
    output += to_string(num & 0xff);
    cout << output << endl;
}

HJ62 查找输入整数二进制中1的个数

对于给定的整数 n ，求解他在二进制表示下的 1 的个数。

    int n;
    cin >> n;
    int cnt = 0;
    while (n) {
        if (n & 1) {
            cnt++;
        }
        n >>= 1;
    }
    cout << cnt << endl;

#include <bitset>
#include <iostream>
using namespace std;
 
int main() {
    int n, m;
    cin >> n >> m;
    int cnt = 0;
    bitset<32> bitn(n);
    bitset<32> bitm(m);
    cout << bitn.count() << endl;
    cout << bitm.count() << endl;
 
 
}

迭代

HJ6 质数因子

对于给定的整数 n ，从小到大依次输出它的全部质因子。即找到这样的质数 p_1, p_2, \cdots, p_k ，使得 n = p_1 \times p_2 \times \cdots \times p_k 。

    int n;
    cin >> n;
    bool hasPrime = false;
    for (int i = 2; i * i <= n; i++) {		//质数因子i不会超过sqrt(n)
        while (n % i == 0) {
            cout << i << " ";
            n /= i;
            hasPrime = true;
        }
    }
    if (n!=1) {		// 1不是质数
        cout << n;
    }

动态规划

AB34 跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：。要求：时间复杂度： ，空间复杂度： 。

    int jumpFloor(int number) {
        // write code here
        if (number<2) {
            return 1;
        }
        else {
            return (jumpFloor(number-1)+jumpFloor(number-2));
        }
    }

    int jumpFloor(int number) {
        // write code here
	    // 初始化
        int dp[41]={0};
        dp[0] = 0, dp[1] = 1, dp[2] = 2;
	  	// 状态转移方程
        for (int i=3; i<=number; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[number];
    }

    int jumpFloor(int number) {
        // write code here
        int a = 1, b = 2, c;
        if (number == 1) {		//记得要先考虑number=1和2的情况
            return 1;
        } 
        else if (number == 2) {
            return 2;
        } 
        else {
            for (int i = 3; i <= number; i++) {		//因为这里隐含条件是 number>=3
                c = a + b;
                a = b;
                b = c;
            }
            return c;
        }
    }

HJ103 Redraiment的走法

Redraiment 是走梅花桩的高手。现在，地上有 nn 个梅花桩排成一排，从前到后高度依次为 h1,h2,…,hnh1​,h2​,…,hn​。Redraiment 可以任选一个梅花桩开始，向后跳到任意一个比当前高度高的梅花桩上。求 Redraiment 最多可以跳过多少个梅花桩。

int main() {
    int n, h, res=0;
    cin >> n;
    vector<int> vec;
    vector<int> dp(n,1);
    for(int i=0; i<n; i++){
        cin >> h;
        vec.push_back(h);
    }
    for (int i=1; i<n; i++) {   //dp[i]为跳到第i个时，已经跳了几个
        for (int j=0; j < i; j++) { //dp[i]必定是从0~（i-1）的状态跳过来的
            if (vec[j] < vec[i]) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        res = max(dp[i],res);
    }
    cout << res << endl;
}

广度优先搜索

AB20 走迷宫

给定一个的网格，在网格中每次在不超过边界的情况下可以选择向上、向下、向左、向右移动一格。网格中的一些格子上放置有障碍物，放有障碍物的格子不能到达。求从(x_s,y_s)到(x_t,y_t)最少的移动次数。若不能到达，输出-1。

    const int next[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1} };
    vector<vector<int>> dist(n, vector<int>(m, 0)); // 存放从起点移动到网格中某个点时的移动次数
    queue<pair<int, int>> q; //记录最新到达的那些节点（水蔓延的边界）
    vector<vector<bool>> flag(n,vector<bool>(m, false)); // 走过的点标记为true
    q.push({xs,ys});
    dist[xs][ys] = 0;
    flag[xs][ys] = true;
    while (!q.empty()) {
        int x, y;
        x = q.front().first;
        y = q.front().second;
        for (int i = 0; i < 4; i++) {
            int nextx = x + next[i][0];
            int nexty = y + next[i][1];
            if (nextx < 0 || nextx >= n || nexty < 0 || nexty >= m) continue;
            if (map[nextx][nexty]=='.' && flag[nextx][nexty]==false){
                dist[nextx][nexty] = dist[x][y] + 1;
                q.push({nextx,nexty});
                flag[nextx][nexty] = true;
            }
        }
        q.pop();
    }
 
    if(dist[xt][yt] != 0){
        cout << dist[xt][yt];
    }
    else{
        cout << -1;
    }

深度优先搜索

面试题 08.07. 无重复字符串的排列组合

无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。

示例 1：

 输入：S = "qwe"
 输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

示例 2：

 输入：S = "ab"
 输出：["ab", "ba"]

提示：

  1. 字符都是英文字母。
  2. 字符串长度在[1, 9]之间。

class Solution {
public:
    vector<string> res;
    void dfs(string& s, int startidx) {
        if (startidx == s.size()-1) {	// 终止条件
            res.push_back(s);	//加入答案并返回
            return;
        }
        for (int i = startidx; i < s.size(); i++) {	//由startidx开始循环
            swap(s[startidx], s[i]);	//修改
            dfs(s, startidx+1);			//dfs
            swap(s[startidx], s[i]);	//复原
        }
    }

    vector<string> permutation(string s) {
        dfs(s, 0);
        return res;
    }
};

面试题 08.08. 有重复字符串的排列组合

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例 1：

 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]

示例 2：

 输入：S = "ab"
 输出：["ab", "ba"]

提示:

  1. 字符都是英文字母。
  2. 字符串长度在[1, 9]之间。

class Solution {
public:
    vector<string> res;
    void dfs(string& s, int startidx) {
        if (startidx == s.size() - 1) {
            res.push_back(s);
            return;
        }
        set<char> dic;		//对于每一个dfs(s, startidx)，即每一个startidx位置上，交换的元素不该重复
        for (int i = startidx; i < s.size(); i++) {
            if (dic.find(s[i]) == dic.end()) {		//如果是不重复的才执行
                dic.insert(s[i]);
                swap(s[startidx], s[i]);
                dfs(s, startidx + 1);
                swap(s[startidx], s[i]);
            }
        }
    }

    vector<string> permutation(string s) {
        dfs(s, 0);
        return res;
    }
};

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

  • 1 <= n <= 20
  • 1 <= k <= n

class Solution {
public:
    vector<vector<int>> result;
    vector<int> res;
    void dfs(int n, int k, int startidx) {
        if (res.size() == k) {
            result.push_back(res);
            return;
        }
	  	// 
        for (int i = startidx; i <= n - (k - res.size()) + 1; i++) {	//剪枝操作
            res.push_back(i);
            dfs(n, k, i + 1);		//这里和排列不太一样
            res.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        dfs(n, k, 1);
        return result;
    }
};

容易知道：搜索起点和当前还需要选几个数有关，而当前还需要选几个数与已经选了几个数有关，即与 res 的长度相关。我们举几个例子分析：

例如：n = 6 ，k = 4。

res.size() == 1 的时候，接下来要选择 3 个数，搜索起点最大是 4，最后一个被选的组合是 [4, 5, 6]；

res.size() == 2 的时候，接下来要选择 2 个数，搜索起点最大是 5，最后一个被选的组合是 [5, 6]；

再如：n = 15 ，k = 4。

res.size() == 1 的时候，接下来要选择 3 个数，搜索起点最大是 13，最后一个被选的是 [13, 14, 15]；

res.size() == 2 的时候，接下来要选择 2 个数，搜索起点最大是 14，最后一个被选的是 [14, 15]；

可以归纳出：

搜索起点的上界 + 接下来要选择的元素个数 - 1 = n

其中，接下来要选择的元素个数 = k - res.size()，整理得到：

搜索起点的上界 = n - (k - res.size()) + 1

所以，我们的剪枝过程就是：把 i <= n 改成 i <= n - (k - res.size()) + 1

作者：liweiwei1419

链接：https://leetcode.cn/problems/combinations/solutions/13436/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成

class Solution {
public:
    vector<vector<string>> result;
    vector<string> res;
    bool ishw(const string& s) { // 判断给定s是不是回文
        int n = s.size();
        for (int i = 0; i < n / 2; i++) {
            if (s[i] != s[n - 1 - i]) {
                return false;
            }
        }
        return true;
    }
    void dfs(const string& s, int startidx) {
        if (startidx == s.size()) {
            result.push_back(res);
            return;
        }
        for (int i = startidx; i < s.size(); i++) {
            string subs = s.substr(startidx, i - startidx + 1);
            if (ishw(subs)) {
                res.push_back(subs);
                dfs(s, i + 1);
                res.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        dfs(s, 0);
        return result;
    }
};

全部评论

相关推荐

05-08 10:34
武汉科技大学 活动执行
昨天问转正，今天我的实习岗位就被挂上了
25应届，实习干了五个多个月了，小心翼翼的组织了措辞问mt是否有hc，回答是可能有一个名额，但内部流程很慢，两三月后才能确定，如果我继续实习，有名额就给我。但今天来上班就看到mt已经在看下一批实习牛马的简历了，我的真的有点绷不住了这份工作是我喜欢，工作强度也不大，组里的大家也好相处，我能进来实习是因为急招，属实走狗屎运了。让我放弃有点舍不得，而且临近毕业忙到飞起，再投简历一轮轮走面试也属实没这精力了。。。现在不知道怎么办了，有点迷茫😭😭😭😭
不找到java后端实习不改名：他在外面看简历，你也往外面投简历呗，你都看到他在准备后手了还愿意赌他的善良吗
点赞 评论 收藏
分享
05-07 16:17
深信服_Java研发工程师(准入职员工)
深信服内推-深信服内推码
🎉最近已经入职深信服啦，感觉时间过得超快！&nbsp;之前经常有朋友来问我做B端的售前产品经理/客户经理未来发展到底怎么样，适合刚毕业无经验的应届生吗？我的专业与市场不搭边，能往市场岗位发展吗？这回借着来深信服长沙培训的契机，也是亲身体验了下深信服的新人培训，以上问题，可以给大家统统分享一下啦！&nbsp;🌷深信服的市场岗位为什么值得选择？&nbsp;深信服，网安云计算领军者，融AI技术，服务多领域。市场岗位邀你共谋数字化转型，策划战略，定制方案，远离内卷，拓宽视野，实现价值转身。&nbsp;🤟深信服市场新人培养体验究竟如何？&nbsp;👅个人背景&nbsp;本硕化学专业，ENFJ。喜爱健身，吉他，唱歌，读书等。&nbsp;🤛跨界的我，从化学实验室转战...
深信服公司福利 409人发布
点赞 评论 收藏
分享
04-05 18:26
蚌埠坦克学院 golang
有点难绷
遂发牛牛空间
喜欢疯狂星期四的猫头鹰在研究求职打法：短作业优先
点赞 评论 收藏
分享
05-08 16:16
苏州大学 前端工程师
人生第一次面试！
大家好！&nbsp;我叫扯蛋蛋&nbsp;，前几天我带着玩玩的心态着投了些简历，结果还有一个比较大点的公司，通过我的简历约到啦面试，听着我的前端领路人讲述面试官的过程，面试前我内心十分害怕，紧张万分。说实话，面试是很遥远的事情，但是不知不觉的中，感觉一切都始料未及。我的的八股文还没有背完，只背啦ccs部分，js八股文还没开始背，这个让我这次面试直接寄的原因之一。接下来讲讲面试的过程。介绍项目和项目的难点我的第一次面试，我以为是视频面试，结果是电话面试。当我接到电话，面试官第一句话就是说：‘看你的简历没有项目，你有做什么项目嘛’。我说：‘有啊’&nbsp;面试官：‘介绍一下你的项目’。我的内心想不是第一个问题来自我介绍吗。为...
查看7道真题和解析 大家都开始春招面试了吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# 面试问题记录 #
21596次浏览 357人参与
# 面试经验谈 #
13937次浏览 211人参与
# 京东TGT #
29270次浏览 151人参与
# 职场新人生存指南 #
333744次浏览 7153人参与
# 面试吐槽bot #
2715次浏览 35人参与
# 异地恋该为对方跳槽吗 #
24220次浏览 120人参与
# 硬件人更看重稳定还是高薪 #
39373次浏览 204人参与
# 机械求职避坑tips #
41468次浏览 355人参与
# 租房找室友 #
28179次浏览 147人参与
# 硬件人秋招的第一个offer #
66019次浏览 1082人参与
# 滴滴工作体验 #
23742次浏览 123人参与
# 上班苦还是上学苦呢？ #
214050次浏览 1288人参与
# 不考虑转正，实习多久合适 #
24590次浏览 118人参与
# 学历or实习经历，哪个更重要 #
114438次浏览 753人参与
# 硬件人你反向读研了吗 #
40254次浏览 608人参与
# 深信服求职进展汇总 #
188992次浏览 1694人参与
# 得物求职进展汇总 #
92741次浏览 792人参与
# 你遇到过哪些神仙同事 #
69818次浏览 623人参与
# 材料进Fab厂真的劝退吗？ #
36503次浏览 158人参与
# 机械只有转码才有出路吗？ #
125908次浏览 1590人参与
# 非技术岗投递进展 #
137597次浏览 1222人参与
牛客网
牛客企业服务