LeetCode【剑指offer】系列（图和其他篇）

图

剑指offer12.矩阵中的路径

题目链接

题目：字母迷宫游戏初始界面记作m x n二维字符串数组grid，请判断玩家是否能在grid中找到目标单词target。
注意：寻找单词时必须按照字母顺序，通过水平或垂直方向相邻的单元格内的字母构成，同时，同一个单元格内的字母 不允许被重复使用 。

思路：深搜。以迷宫中每个位置为起点深搜一遍即可，遇到不符合的情况提前返回false即可。

通过代码：

class Solution {
public:vector<vector<char>> grid;string target;int dx[4] = {0, 0, -1, 1};int dy[4] = {-1, 1, 0, 0};bool dfs(int x, int y, int idx, vector<vector<bool>> &vis) {if(grid[x][y] != target[idx])return false;if(idx == target.size() - 1)return true;for(int i = 0; i < 4; i++){int nx = x + dx[i];int ny = y + dy[i];if(nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && !vis[nx][ny]){vis[nx][ny] = true;if(dfs(nx, ny, idx + 1, vis))return true;vis[nx][ny] = false;}}return false;}bool wordPuzzle(vector<vector<char>>& grid, string target) {this -> grid = grid;this -> target = target;int n = grid.size(), m = grid[0].size();for(int i = 0; i < n; i++)for(int j = 0; j < m; j++){vector<vector<bool>> vis(n, vector<bool> (m, false));vis[i][j] = true;if(dfs(i, j, 0, vis))return true;}return false;}
};

剑指offer13.机器人的运动范围

题目链接

题目：家居整理师将待整理衣橱划分为m x n的二维矩阵grid，其中grid[i][j]代表一个需要整理的格子。整理师自grid[0][0] 开始逐行逐列地整理每个格子。

整理规则为：在整理过程中，可以选择向右移动一格或向下移动一格，但不能移动到衣柜之外。同时，不需要整理digit(i) + digit(j) > cnt的格子，其中digit(x)表示数字x的各数位之和。

请返回整理师 总共需要整理多少个格子。

思路：深搜。dfs(i,j)返回从i, j出发到终点所需要清理的格子数。从起点开始，有向下或向右两条路径，再加上当前格子，所以返回1+dfs(i +1, j) + dfs(i, j + 1)。

通过代码：

class Solution {
public:int digit(int x) {int res = 0;while(x > 0){res += x % 10;x /= 10;}return res;}int dfs(int i, int j, int cnt, vector<vector<bool>> &vis) {if(i >= vis.size() || j >= vis[0].size() || vis[i][j] || digit(i) + digit(j) > cnt)return 0;vis[i][j] = true;return 1 + dfs(i + 1, j, cnt, vis) + dfs(i, j + 1, cnt, vis);}int wardrobeFinishing(int m, int n, int cnt) {vector<vector<bool>> vis(m, vector<bool> (n));return dfs(0, 0, cnt, vis);}
};

剑指offer29.顺时针打印矩阵

题目链接

题目：给定一个二维数组 array，请返回「螺旋遍历」该数组的结果。

螺旋遍历：从左上角开始，按照 向右、向下、向左、向上 的顺序 依次 提取元素，然后再进入内部一层重复相同的步骤，直到提取完所有元素。

思路：可以将二维数组看成若干层，首先打印最外层的元素，其次打印次外层的元素，直到打印最内层的元素。对于每层，从左上方开始以顺时针的顺序遍历所有元素。用四个变量作为每一层的定界，假设当前层的左上角位于 (top,left)，右下角位于 (bottom,right)。由于不一定是正方形，所以最下和最左的两条边需要判断是否需要遍历。

通过代码：

class Solution {
public:vector<int> spiralArray(vector<vector<int>>& array) {vector<int> res;if(array.size() == 0)return res;int left = 0, top = 0, bottom = array.size() - 1, right = array[0].size() - 1;while(left <= right && top <= bottom){for(int i = left; i <= right; i++)res.push_back(array[top][i]);for(int i = top + 1; i <= bottom; i++)res.push_back(array[i][right]);if(left < right && top < bottom){for(int i = right - 1; i >= left; i--)res.push_back(array[bottom][i]);for(int i = bottom - 1; i > top; i--)res.push_back(array[i][left]);}left++;top++;right--;bottom--;}return res;}
};

贪心算法

剑指offer63.股票中的最大利润

题目链接

题目：数组 prices记录了某芯片近期的交易价格，其中prices[i] 表示的 i 天该芯片的价格。你只能选择 某一天 买入芯片，并选择在 未来的某一个不同的日子 卖出该芯片。请设计一个算法计算并返回你从这笔交易中能获取的最大利润。

如果你不能获取任何利润，返回 0。

思路一：贪心。在一趟遍历中，同时记录到目前为止的最小价格，并更新最大利润。最大利润一定是减去目前最小价格得到的。

通过代码：

class Solution {
public:int bestTiming(vector<int>& prices) {if(prices.size() < 2)return 0;int min_price = prices[0];int max_profit = 0;for(int i = 1; i < prices.size(); i++){max_profit = max(max_profit, prices[i] - min_price);min_price = min(min_price, prices[i]);}return max_profit;}
};

思路二：动态规划。dp[i]表示前i天的最大利润。当从第i-1天转移到第i天时，需要选择第i天卖出所获得的最大利润和前i天的最大利润中的较大值，即dp[i] = max(dp[i - 1], prices[i] - min_price);。因此，遍历的时候也需要维护到目前为止的最低价格。

class Solution {
public:int bestTiming(vector<int>& prices) {if(prices.size() < 2)return 0;vector<int> dp(prices.size());int min_price = prices[0];for(int i = 1; i < prices.size(); i++){dp[i] = max(dp[i - 1], prices[i] - min_price);min_price = min(min_price, prices[i]);}return dp[prices.size() - 1];}
};

找规律

剑指offer43.1~n整数中1出现的次数

题目链接

题目：给定一个整数 num，计算所有小于等于 num 的非负整数中数字 1 出现的个数。

通过代码：

class Solution {
public:int digitOneInNumber(int num) {long digit = 1;int high = num / 10, cur = num % 10, low = 0, res = 0;while(high != 0 || cur != 0){if(cur == 0)res += high * digit;else if(cur == 1)res += high * digit + low + 1;elseres += (high + 1) * digit;low += cur * digit;cur = high % 10;high /= 10;digit *= 10;}return res;}
};

剑指offer44.数字序列中某一位的数字

题目链接

题目：某班级学号记录系统发生错乱，原整数学号序列 [1,2,3,4,...] 分隔符丢失后变为 1234... 的字符序列。请实现一个函数返回该字符序列中的第 k 位数字。

思路：

通过代码：

class Solution {
public:int findKthNumber(int k) {int digit = 1;long start = 1;long count = 9;while(k > count){k -= count;digit++;start *= 10;count = 9 * start * digit;}long num = start + (k - 1) / digit;string s = to_string(num);int res = s[(k - 1) % digit] - '0';return res;}
};