Python 在线笔试题9/30

迷南。 2023-06-18 06:56 35阅读 0赞

### 在线笔试9 ###

*   *   *  1.杨辉三角
         *  8.被围绕的区域
         *  9.分割回文串
         *  10.分发糖果

### 1.杨辉三角 ###

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

> 示例  
> 输入: 5  
> 输出:  
> \[  
> \[1\],  
> \[1,1\],  
> \[1,2,1\],  
> \[1,3,3,1\],  
> \[1,4,6,4,1\]  
> \]

class Solution { 
    public:
        vector<vector<int>> generate(int numRows) { 
            vector<vector<int>>ans;
            vector<int>res = { 1};
            while(numRows--){ 
                ans.push_back(res);
                for(int i = res.size()-1;i>=1;--i){ 
                    res[i] += (i-1 >=0?res[i-1]:0);
                }
                res.push_back(1);
            }
            return ans;
        }
    };

进阶

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

> 示例  
> 输入: 3  
> 输出: \[1,3,3,1\]

可以直接使用题 1 的代码，返回第 k 行

也可以直接进行更新，保存一行数组就行了

class Solution { 
    public:
        vector<int> getRow(int rowIndex) { 
            vector<int>ans = { 1};
            for(int i = 2;i<rowIndex+1;++i){ 
                ans.push_back(1);
                for(int j = i-2;j>0;--j){ 
                    ans[j] += ans[j-1];
                }
            }
            return ans;
        }
    };

### 8.被围绕的区域 ###

给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。

找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

> 示例  
> 输入  
> X X X X  
> X O O X  
> X X O X  
> X O X X  
> 输出  
> X X X X  
> X X X X  
> X X X X  
> X O X X  
> 解释:  
> 被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

解题思路:搜索矩阵边缘上的‘O’，然后以’O’为起点进行广度优先搜索遍历，只要遇到O，就重新换一个值覆盖

最后进行判断，如果是区域是O赋值为X，也要把重新边缘上的自定义字符重新赋值回O

思路想通之后代码比较简单，好久不用C++写了，都快忘记了！

void isdulpa(vector<vector<char>>& board,int row,int col,int rows,int cols){ 
            if(row<rows && row>=0 && col>=0 && col<cols && board[row][col]=='O'){ 
                board[row][col]='T';
                isdulpa(board,row+1,col,rows,cols);
                isdulpa(board,row-1,col,rows,cols);
                isdulpa(board,row,col+1,rows,cols);
                isdulpa(board,row,col-1,rows,cols);
            }
        }
        void solve(vector<vector<char>>& board) { 
            int rows = board.size();
            if (rows<=0){ 
                return;
            }
            int cols = board[0].size();
            
            // 判断字符
            for(int row = 0;row<rows;++row){ 
                for(int col = 0;col<cols;++col){ 
                    if ((row==0 || row==rows-1 || col==0 || col==cols-1) 
                        && board[row][col]=='O'){ 
                            isdulpa(board,row,col,rows,cols);
                    }
                }
            }
            // 修改字符
            for(int row = 0;row<rows;++row){ 
                for(int col = 0;col<cols;++col){ 
                    if (board[row][col]=='T'){ 
                        board[row][col]='O';
                    }else{ 
                        board[row][col]='X';
                    } 
                }
            }
        }

### 9.分割回文串 ###

> 输入: “aab”  
> 输出: \[ \[“aa”,“b”\],\[“a”,“a”,“b”\]\]

思路：回溯法，其实这题我特别不熟，思想也不是很了解，所以每次都要借助案列走一遍代码，才能理解！

自己写，真的写不出来…

案例：s = ‘ababca’

首先是一个一个的被加到 path 中，字符串 s 的变化是这样的，‘ababca’ > ‘babca’ > ‘abca’ > ‘bca’ > ‘ca’ > ‘a’ 当 s 变为 a的时候，已经循环了很多次，每一次的循环只执行一次， 当再一次以 s\[i:\]进行函数调用的时候，s 变为 ‘ ’ ， 这时候 path = \[‘a’,‘b’,‘a’,‘b’,‘c’,‘a’\]

然后进行回溯，回溯的意思就是执行循环从里往外走，因为套了很多次循环，所以还是要走出去的。

当第一次执行 return 返回后， s =‘a’,但是循环结束，调到倒数第二个循环，s 变为 ‘ca’,然后 i ++,但是发现并不是回文串，循环结束（因为循环结束的条件时 i == len(s)由于i 第一次就等于 1，++后等于2，而这时候 字符串长度就是 2，所以会循环结束）再调到倒数第三个循环中，s = 'bca’由于没有回文串，所以会继续往外跳，知道 s = ‘babca’，这时候 i = a,在循环内 i ++,当走到 i 走到 第二个b 的时候，发现一个 回文串就是 ‘bab’会把它加入到 path中，这时候path 中还有一个字符 ‘a’;然后在调用一次函数，当 s =’'的时候，path = \[‘a’,‘bab’,‘c’,‘a’\],然后在跳出循环，往外层循环走…【可能写的有点乱！】

def partition(self, s: str) -> List[List[str]]:
            res = []
            def dfs(s,path):
                if not s:
                    res.append(path)
                    return
                for i in range(1,len(s)+1):
                    if s[:i]==s[:i][::-1]:
                        dfs(s[i:],path+[s[:i]])
            dfs(s,[])
            return res

### 10.分发糖果 ###

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。  
相邻的孩子中，评分高的孩子必须获得更多的糖果。  
那么这样下来，老师至少需要准备多少颗糖果呢？

> 示例1  
> 输入: \[1,0,2\]  
> 输出: 5  
> 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

> 示例2  
> 输入: \[1,2,2\]  
> 输出: 4  
> 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。  
> 第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

**思路**：

(1)为了满足第一个条件（每个孩子至少分配到 1 个糖果），可以先给每个人发一个糖果

(2)评分高的孩子获得的糖果比左右相邻的孩子要多，可以这样考虑：先保证所有评分更高的孩子比左邻孩子糖果多，再实现所有评分更高的孩子比右邻孩子糖果多

def candy(self, ratings: List[int]) -> int:
            cantiny = [1]*len(ratings)
            # 从左到右
            for i in range(1,len(ratings)):
                if ratings[i]>ratings[i-1]:
                    cantiny[i] = cantiny[i-1]+1
            
            # 从右到左
            for i in range(len(ratings)-2,-1,-1):
                if ratings[i]>ratings[i+1] and cantiny[i]<=cantiny[i+1]:
                    cantiny[i] = cantiny[i+1]+1
            return sum(cantiny)