#每日一题合集#牛客JZ13-JZ22

为了督促自己每天练一练编程
时间：2022年8月11日-2022年8月20日
网站：https://www.nowcoder.com/exam/oj/ta?tpId=13

8.11-JZ13.机器人的运动范围

        递归需要考虑的：
        1.边界：首先，由于坐标是从[0,0]到[rows-1,cols-1]的，因此最基础的就是不合法的数据(x < 0 || y < 0 || x >= rows || y >= cols)；然后，就是题目的条件，“不能进入行坐标和列坐标的数位之和大于 threshold 的格子”，所以需要分解行列的位数再相加，这个就比较基础(getsum(x) + getsum(y) > threshold)；最后，由于我们是统计格子数，因此需要判断，这个格子走没走过，没走过的才进入下一轮判断
        2.递归条件：这个就比较简单，就是这个格子，加上往上下左右四个方向的格子数，然后不断递归就可以啦。

class Solution {
public:
    bool visit[101][101];
    // 求和函数
    int getsum(int n){
        int sum = 0;
        while(n != 0){
            sum += n % 10;
            n = n / 10;
        }
        return sum;
    }
    //递归判断走路函数
    int Judge(int threshold, int rows, int cols, int x, int y){
        if(x < 0 || y < 0 || x >= rows || y >= cols || getsum(x) + getsum(y) > threshold || visit[x][y])
            return 0;
        visit[x][y] = 1;
        return Judge(threshold, rows, cols, x, y+1) +
            Judge(threshold, rows, cols, x, y-1) +
            Judge(threshold, rows, cols, x-1, y) +
            Judge(threshold, rows, cols, x+1, y) +1;
    }
    
    int movingCount(int threshold, int rows, int cols) {
        if(rows <= 0 || cols <= 0 || threshold < 0)
            return 0;
        int cnt = Judge(threshold, rows, cols, 0, 0);
        return cnt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

8.12-JZ14.剪绳子

动态规划思路：一根绳子其中一段不可分的为j，那么如果另一段为n−j最大乘积已知，我们可以遍历所有j找到这个最大乘积。因此用dp[i]表示长度为i的绳子可以被剪出来的最大乘积，那么后续遍历每个j的时候，我们取dp[i]和j∗dp[i−j]的最大值就好了。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int cutRope(int n) {
        // write code here
        if(n <= 3)
            return n - 1;
        vector<int> dp(n + 1, 0);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
        for(int i = 5; i <= n; i++){
            for(int j = 1; j < i; j++){
                dp[i] = max(dp[i], j * dp[i-j]);
            }
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

8.13-JZ15.二进制中1的个数

基础位与操作

class Solution {
public:
     int  NumberOf1(int n) {
         int res = 0;
         for(int i = 0; i < 32; i++){
             if(n & 1 != 0){
                 res++;
             }
             n = n >> 1;
         } 
         return res;
     }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

8.14-JZ16.数值的整数次方

基础计算，就是多了负数的，转换一下即可

class Solution {
public:
    double Power(double base, int exponent) {
        double res = 1.0;
        if(exponent < 0){
            base = 1 / base;
            exponent = -exponent;
        }
        for(int i = 0; i < exponent; i++)
            res *= base;
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

8.15-JZ17.打印从1到最大的n位数

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 最大位数
     * @return int整型vector
     */
    vector<int> printNumbers(int n) {
        // write code here
        vector<int> res;
        for(int i = 1; i < pow(10,n); i++)
            res.push_back(i);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

8.16-JZ18.删除链表的节点

比较基础的链表操作

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param val int整型 
     * @return ListNode类
     */
    ListNode* deleteNode(ListNode* head, int val) {
        // write code here
        ListNode* res = new ListNode(0);
        res->next = head;
        
        ListNode* pre = res;
        ListNode* cur = head;
        
        while(cur != NULL){
            if(cur->val == val){
                pre->next = cur->next;
                break;
            }
            pre = cur;
            cur = cur->next;
        }
        
        return res->next;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

8.17-JZ19.正则表达式匹配

这个参考了官方解析：
    首先，两个空串是直接匹配，因此dp[0][0]=true。然后利用*字符出现0次的特性，遍历pattern字符串，如果遇到*意味着它前面的字符可以出现0次，要想匹配空串也只能出现0，那就相当于考虑再前一个字符是否能匹配，因此dp[0][i]=dp[0][i−2]。
     然后分别遍历str与pattern的每个长度，开始寻找状态转移。首先考虑字符不为*的简单情况，只要遍历到的两个字符相等，或是pattern串中为.即可匹配。因此只需要二者各自前一位能完成匹配，就有dp[i][j]=dp[i−1][j−1]。然后考虑*出现的情况：
        1.pattern前一位能够多匹配一位(pattern[j - 2] == '.' || pattern[j - 2] == str[i - 1])，匹配成功则转移dp[i][j]=dp[i−1][j]∣∣dp[i][j−2]
        2.不满足上述条件，即不匹配，让前一个字符出现0次，dp[i][j]=dp[i][j−2]。

class Solution {
public:
    bool match(string str, string pattern) {
        int n1 = str.length();
        int n2 = pattern.length();
        //dp[i][j]表示str前i个字符和pattern前j个字符是否匹配
        vector<vector<bool> > dp(n1 + 1, vector<bool>(n2 + 1, false)); 
        //两个都为空串自然匹配
        dp[0][0] = true; 
        
        //初始化str为空的情况，字符串下标从1开始
        for(int i = 2; i <= n2; i++){ 
            if(pattern[i - 1] == '*') 
                dp[0][i] = dp[0][i - 2]; 
        }

        
        for(int i = 1; i <= n1; i++){ 
            for(int j = 1; j <= n2; j++){ 
                //当前字符不为*，用.去匹配或者字符直接相同
                if(pattern[j - 1] != '*' && (pattern[j - 1] == '.' || pattern[j - 1] == str[i - 1])){ 
                      dp[i][j] = dp[i - 1][j - 1];
                //当前的字符为*
                }else if(j >= 2 && pattern[j - 1] == '*'){ 
                    //若是前一位为.或者前一位可以与这个数字匹配
                    if(pattern[j - 2] == '.' || pattern[j - 2] == str[i - 1]) 
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2];  
                    else
                        dp[i][j] = dp[i][j - 2]; 
                }
            }
        }
        return dp[n1][n2];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

8.18-JZ20.表示数值的字符串

一道纯纯思路题，注意各个条件，具体见代码注释

class Solution {
public:
    //设计下标为全局变量，让下标一位位检查，检查通过后后移
    int index = 0;
  
    bool judge_integer(string& s){
        //空格后的符号可能是小数或者整数的一个符号('+'或'-')
        if(index < s.length() && (s[index] == '-' || s[index] == '+'))
            //如果有的话，一个是合法的，下标后移
            index++;
        return judge_un_integer(s);
    }
    
    bool judge_un_integer(string& s){
        int tmp = index;
        //数字有多少位都是合法的，因此不断判断后移
        while(index < s.length() && (s[index] >= '0' && s[index] <= '9'))
            index++;
        //如果下标没变化，说明没有数字
        return index > tmp;
        
    }
 
    bool isNumeric(string str) {
        //空串肯定不是数值
        if(str.length() == 0)
            return false;
        
        //由于数值前后都有若干空格，所以要先去空格
        //去前面的空格
        while(index < str.length() && str[index] == ' ')
            index++;
        //去后面的空格
        int n = str.length() - 1;
        while(n >= 0 && str[n] == ' ')
            n--;
        //这样最后就一个空格，以便最后检查遍历是否结束
        n++;
        //若是长度小于下标，说明全是空格，也不是数值
        if(index > n)
            return false;
        
        //判断是否是有符号数
        bool flag = judge_integer(str);
        //这时候index已经到了下一个非数字上了
        //如果有小数点
        if(index < n && str[index] == '.'){
            index++;
            //根据要求，小数点前面或者后面至少一个数字
            //前面已经判断完了，结果是flag，后面的再判断一次即可
            flag = judge_un_integer(str) || flag;//注意这里一定是后面的判断在前，因为或运算第一个为真时第二个条件是不计算的
        }
        //如果是e
        if(index < n && (str[index] == 'e' || str[index] == 'E')){
            index++;
            //e后面要跟着一个整数
            flag = flag && judge_integer(str);

        }
        //确认遍历结束
        flag = flag && (index == n);
        
        return flag;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

8.19-JZ21.调整数组顺序使奇数位于偶数前面(一)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArray(vector<int>& array) {
        // write code here
        int n = array.size();
        vector<int> res(n);
        int odd = 0;
        for(int i = 0 ; i < n; i++){
            if(array[i] % 2)
                odd++;
        }
        int x = 0, y = odd;
        for(int i = 0; i < n; i++){
            if(array[i] % 2){
                res[x] = array[i];
                x++;
            }
            else{
                res[y] = array[i];
                y++;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

8.20-JZ22.链表中倒数最后k个结点

经典快慢指针问题

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* FindKthToTail(ListNode* pHead, int k) {
        // write code here
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        
        for(int i = 0; i < k; i++){
            if(fast != NULL)
                fast = fast->next;
            else 
                return NULL;
        }
        
        while(fast != NULL){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29