剑指office算法（二）

发表于 分类于 阅读次数：
本文字数： 6.3k 阅读时长 ≈ 6 分钟

剑指office算法（二）

机器人的运动范围

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
/**
地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。
一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 k 的格子。
请问该机器人能够达到多少个格子？
样例1
输入：k=7, m=4, n=5
输出：20
样例2
输入：k=18, m=40, n=40
输出：1484
解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
      但是，它不能进入方格（35,38），因为3+5+3+8 = 19。
*/

class Solution {
public:
    
    int get_single_sum(int x){
        int s = 0;
        while(x) s += x %10, x /= 10;
        return s;
    }
    int get_sum(pair<int,int> p){
        return get_single_sum(p.first) + get_single_sum(p.second);
    }
 	int movingCount(int threshold, int rows, int cols){
    	int res = 0;
    	if(!rows || !cols) return 0;
        vector<vector<bool>> st(rows, vector<bool>(cols));
        queue<pair<int,int>> q;
        q.push({0,0});
        
        int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};
        
        while(q.size()){
            auto t = q.front();
            q.pop();
            if(get_sum(t) > threshold || st[t.first][t.second]) continue;
            
            res++;
            st[t.first][t.second] = true;
            
            for(int i = 0 ; i < 4; i++){
                int x = t.first + dx[i], y = t.second + dy[i];
                if(x >=0 && x < rows && y >=0 && y < cols)
                q.push({x,y});
            }
            
        }
            return res;
    }

};

##

剪绳子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
给你一根长度为 n 绳子，请把绳子剪成 m 段（m、n 都是整数，2≤n≤58 并且 m≥2）。
每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少？
例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。
样例
输入：8

输出：18
**/
class Solution {
public:
    int maxProductAfterCutting(int length) {
        int n =  length;
        if( n <= 3) return 1 * (n -1);
       int res = 1; 
        if(n % 3 == 1) res = 4, n -=4;
        else if(n % 3 == 2) res = 2, n -=2;
        while(n) res *= 3, n -=3;
        return res;
    }
};

二进制中1的个数

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
/**
输入一个32位整数，输出该数二进制表示中1的个数。

注意：

负数在计算机中用其绝对值的补码来表示。
样例1
输入：9
输出：2
解释：9的二进制表示是1001，一共有2个1。
样例2
输入：-2
输出：31
解释：-2在计算机里会被表示成11111111111111111111111111111110，
      一共有31个1。
*/

class Solution {
public:
    int NumberOf1(int n) {
        int res = 0;
        unsigned int un = n;
        while(un) res += un & 1, un >>= 1;
    }
};

数值的整数次方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
实现函数double Power(double base, int exponent)，求base的 exponent次方。
不得使用库函数，同时不需要考虑大数问题。
注意：
不会出现底数和指数同为0的情况
样例1
输入：10 ，2
输出：100
样例2
输入：10 ，-2  
输出：0.01
*/
class Solution {
public:
    double Power(double base, int exponent) {
        bool flag = true;
        if(exponent < 0) flag = false, exponent = -exponent; 
        
        double res = 1;
        while(exponent--) res *= base;
        if(!flag) res = 1 / res;
        return flag;
    }
};

在O(1)时间删除链表结点

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
/**
给定单向链表的一个节点指针，定义一个函数在O(1)时间删除该结点。
假设链表一定存在，并且该节点一定不是尾节点。
样例
输入：链表 1->4->6->8
      删掉节点：第2个节点即6（头节点为第0个节点）
输出：新链表 1->4->8
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        
        auto p = node -> next;
        node -> val = p -> val;
        node -> next = p -> next;
        
        delete p;
    }
};

删除链表中重复的节点

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
/**
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留。
样例1
输入：1->2->3->3->4->4->5
输出：1->2->5
样例2
输入：1->1->1->2->3
输出：2->3
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        auto dummy = new ListNode(-1);
        dummy -> next = head;
        
        auto q = dummy -> next;
        while(q -> next){
            
            auto p = q -> next;
            while(p && q ->next -> val == p ->val) p = p-> next; // 查看要跨几步 p步
            
            if(q->next && q -> next -> next == p) q = q ->next; // 跨一步
            else q -> next = p; //跨一大步
        }
        return dummy-> 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
39
40
41
42
/**
假设有排成一行的N个位置，记为1~N，开始时机器人在M位置，机器人可以往左或者往右走，如果机器人在1位置，那么下一步机器人只能走到2位置，如果机器人在N位置，那么下一步机器人只能走到N-1位置。规定机器人只能走k步，最终能来到P位置的方法有多少种。由于方案数可能比较大，所以答案需要对1e9+7取模。
输出包括一行四个正整数N（2<=N<=5000）、M(1<=M<=N)、K(1<=K<=5000)、P(1<=P<=N)。
输出一个整数，代表最终走到P的方法数对10^9+7取模后的值。
输入
5 2 3 3
输出
3
说明
1).2->1,1->2,2->3
2).2->3,3->2,2->3
3).2->3,3->4,4->3
*/
class Solution {
public:
int mod = 1e9+7;
    //     N个位置 当前位置 还剩几步 终点
int walk2(int N, int cur, int rest, int P){
 
    //总长度 当前 剩余步数 终点 
    vector<vector<int>> dp(cur+1, vector<int>(N+1,0));
    dp[0][P] = 0;
    
    for(int i = 1; i <= cur; i++){
        for(int k = 1; k <= N ; k++){
            if(k == 1) dp[i][k] = dp[i-1][2];
            else if(k == N) dp[i][k] = dp[i-1][N-1];
            else dp[i][j] = dp[i-1][j-1] +dp[i-1][j+1];
        }
    }
    return dp[cur][N];
}
    
    int main(){
    int N, M, K, P;
    cin >> N >> M >> K >> P;
    if(N<2 || K<1 || M>N || M<1|| P>N || P<1)
        return 0;
    cout << walk2(N, M, K, P) << endl;
    return 0;
}
}

###

正则表达式匹配

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
/**
请实现一个函数用来匹配包括'.'和'*'的正则表达式。
模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。
输入：
s="aa"
p="a*"
输出:true
*/
class Solution {
public:
    bool isMatch(string s, string p) {
        int sn = s.size(), pn = p.size();
        vector<vector<int>> dp(sn+10, vector<int>(pn+10,0));
        dp[0][0] = 1;
        for(int i = 0; i < sn; i++){
            for(int j=1; j < pn; j++){
                //如果是 。
                if( i > 0 && p[j-1] == '.'){
                    dp[i][j] = dp[i-1][j-1];
                }
                else if( i > 0 && p[j-1] == s[i-1] && p[j-1] != '*'){
                    dp[i][j] = dp[i-1][j-1];
                }
                else if(j > 1 && p[j-1] == "*")
                {
                    if()
                }
            }
        }
    }
};
相关文章
0%