61、[中等] 旋转链表链表class Solution { public: ListNode* rotateRight(ListNode* head, int k) { if (k 0 || head nullptr || head-next nullptr) { return head; } int n 1; ListNode* iter head; while (iter-next) { iter iter-next; n; } int add n - k % n; if (add n) { return head; } iter-next head; while (add--) { iter iter-next; } ListNode* ret iter-next; iter-next nullptr; return ret; } };62、[中等] 不同路径数学动态规划动态规划class Solution { public: int uniquePaths(int m, int n) { // 初始化 F(0, j) F(i, 0) 1; vectorvectorint dp(m, vector(n, 1)); for (int i 1; i m; i) { for (int j 1; j n; j) { dp[i][j] dp[i - 1][j] dp[i][j - 1]; } } return dp[m - 1][n - 1]; } };备忘录class Solution { public: int uniquePaths(int m, int n) { vectorvectorint memo(m 1, vectorint(n 1)); return dfs(m, n, memo); } int dfs(int i, int j, vectorvectorint memo) { if (memo[i][j] ! 0) { return memo[i][j]; } if (i 0 || j 0) { return 0; } if (i 1 j 1) { memo[i][j] 1; return memo[i][j]; } memo[i][j] dfs(i - 1, j, memo) dfs(i, j - 1, memo); return memo[i][j]; } };63、[中等] 不同路径 Ⅱ数学动态规划矩阵动态规划class Solution { public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int row obstacleGrid.size(); int col obstacleGrid[0].size(); vectorvectorint dp(row 1, vector(col 1, 0)); dp[0][1] 1; for (int i 1; i row; i) { for (int j 1; j col; j) { if (obstacleGrid[i - 1][j - 1] ! 1) { dp[i][j] dp[i - 1][j] dp[i][j - 1]; } else { dp[i][j] 0; } } } return dp[row][col]; } };class Solution { public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int row obstacleGrid.size(); int col obstacleGrid[0].size(); vectorvectorint pathNum(row, vector(col, 1)); for (int i 0; i row; i) { for (int j 0; j col; j) { if (obstacleGrid[i][j] 1) { pathNum[i][j] 0; } else { if (i 0 j 0) { pathNum[i][j] 1; } else if (i 0) { pathNum[i][j] pathNum[i][j - 1]; } else if (j 0) { pathNum[i][j] pathNum[i - 1][j]; } else { pathNum[i][j] pathNum[i - 1][j] pathNum[i][j - 1]; } } } } return pathNum[row - 1][col - 1]; } };class Solution { public: int uniquePathsWithObstacles(vectorvectorint obstacleGrid) { int row obstacleGrid.size(); int col obstacleGrid[0].size(); vectorint dp(col); dp[0] (obstacleGrid[0][0] 0); for (int i 0; i row; i) { for (int j 0; j col; j) { if (obstacleGrid[i][j] 1) { dp[j] 0; continue; } if (j - 1 0 obstacleGrid[i][j - 1] 0) { dp[j] dp[j - 1]; } } } return dp[col - 1]; } };64、[中等] 最小路径和数组动态规划矩阵class Solution { public: int minPathSum(vectorvectorint grid) { int row grid.size(); int col grid[0].size(); vectorvectorint dp(row, vectorint(col)); dp[0][0] grid[0][0]; for (int i 1; i row; i) { dp[i][0] dp[i - 1][0] grid[i][0]; } for (int j 1; j col; j) { dp[0][j] dp[0][j - 1] grid[0][j]; } for (int i 1; i row; i) { for (int j 1; j col; j) { dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j]; } } return dp[row - 1][col - 1]; } };65、[困难] 有效数字字符串确定有限状态自动机class Solution { private: enum State { STATE_INITIAL, STATE_INT_SIGN, STATE_INTEGER, STATE_POINT, STATE_POINT_WITHOUT_INT, STATE_FRACTION, STATE_EXP, STATE_EXP_SIGN, STATE_EXP_NUMBER, STATE_END }; enum CharType { CHAR_NUMBER, CHAR_EXP, CHAR_POINT, CHAR_SIGN, CHAR_ILLEGAL }; CharType toCharType(char ch) { if (ch 0 ch 9) { return CHAR_NUMBER; } else if (ch e || ch E) { return CHAR_EXP; } else if (ch .) { return CHAR_POINT; } else if (ch || ch -) { return CHAR_SIGN; } else { return CHAR_ILLEGAL; } } public: bool isNumber(string s) { unordered_mapState, unordered_mapCharType, State transfer{ {STATE_INITIAL, {{CHAR_NUMBER, STATE_INTEGER}, {CHAR_POINT, STATE_POINT_WITHOUT_INT}, {CHAR_SIGN, STATE_INT_SIGN}}}, {STATE_INT_SIGN, {{CHAR_NUMBER, STATE_INTEGER}, {CHAR_POINT, STATE_POINT_WITHOUT_INT}}}, {STATE_INTEGER, {{CHAR_NUMBER, STATE_INTEGER}, {CHAR_EXP, STATE_EXP}, {CHAR_POINT, STATE_POINT}}}, {STATE_POINT, {{CHAR_NUMBER, STATE_FRACTION}, {CHAR_EXP, STATE_EXP}}}, {STATE_POINT_WITHOUT_INT, {{CHAR_NUMBER, STATE_FRACTION}}}, {STATE_FRACTION, {{CHAR_NUMBER, STATE_FRACTION}, {CHAR_EXP, STATE_EXP}}}, {STATE_EXP, {{CHAR_NUMBER, STATE_EXP_NUMBER}, {CHAR_SIGN, STATE_EXP_SIGN}}}, {STATE_EXP_SIGN, {{CHAR_NUMBER, STATE_EXP_NUMBER}}}, {STATE_EXP_NUMBER, {{CHAR_NUMBER, STATE_EXP_NUMBER}}}}; int len s.length(); State st STATE_INITIAL; for (int i 0; i len; i) { CharType typ toCharType(s[i]); if (transfer[st].find(typ) transfer[st].end()) { return false; } else { st transfer[st][typ]; } } return st STATE_INTEGER || st STATE_POINT || st STATE_FRACTION || st STATE_EXP_NUMBER || st STATE_END; } };66、[简单] 加一数组class Solution { public: vectorint plusOne(vectorint digits) { int n digits.size(); int add digits[n - 1] 1; vectorint ret; ret.push_back(add % 10); add / 10; for (int i n - 2; i 0; i--) { add digits[i]; ret.push_back(add % 10); add / 10; } if (add) { ret.push_back(add); } reverse(ret.begin(), ret.end()); return ret; } };class Solution { public: vectorint plusOne(vectorint digits) { int n digits.size(); for (int i n - 1; i 0; i--) { if (digits[i] ! 9) { digits[i]; for (int j i 1; j n; j) { digits[j] 0; } return digits; } } // digits 中所有的元素均为 9 vectorint ret(n 1); ret[0] 1; return ret; } };67、[简单] 二进制求和位运算class Solution { public: string addBinary(string a, string b) { string ret; int cur1 a.size() - 1; int cur2 b.size() - 1; int add 0; while (cur1 0 || cur2 0 || add) { if (cur1 0) { add a[cur1--] - 0; } if (cur2 0) { add b[cur2--] - 0; } ret add % 2 0; add / 2; } reverse(ret.begin(), ret.end()); return ret; } };68、[困难] 文本左右对齐数组字符串class Solution { private: // blank 返回长度为 n 的由空格组成的字符串 string blank(int n) { return string(n, ); } // join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串 string join(vectorstring words, int left, int right, string sep) { string s words[left]; for (int i left 1; i right; i) { s sep words[i]; } return s; } public: vectorstring fullJustify(vectorstring words, int maxWidth) { vectorstring ret; int right 0, n words.size(); while (true) { int left right; // 当前行的第一个单词在 words 的位置 int sumLen 0; // 循环确定当前行可以放多少单词注意单词之间应至少有一个空格 while (right n sumLen words[right].length() right - left maxWidth) { sumLen words[right].length(); } // 当前行是最后一行单词左对齐且单词之间应只有一个空格在行末填充剩余空格 if (right n) { string s join(words, left, n, ); ret.emplace_back(s blank(maxWidth - s.length())); return ret; } int numWords right - left; int numSpaces maxWidth - sumLen; // 当前行只有一个单词该单词左对齐在行末填充剩余空格 if (numWords 1) { ret.emplace_back(words[left] blank(numSpaces)); continue; } // 当前行不只一个单词 int avgSpaces numSpaces / (numWords - 1); int extraSpaces numSpaces % (numWords - 1); string s1 join(words, left, left extraSpaces 1, blank(avgSpaces 1)); // 拼接额外加一个空格的单词 string s2 join(words, left extraSpaces 1, right, blank(avgSpaces)); // 拼接其余单词 ret.emplace_back(s1 blank(avgSpaces) s2); } } };69、[简单] x 的平方根数学二分查找class Solution { public: int mySqrt(int x) { if (x 1) { return 0; } int left 1, right x; while (left right) { long long mid left (right - left 1) / 2; if (mid * mid x) { left mid; } else { right mid - 1; } } return left; } };70、[简单] 爬楼梯数学动态规划动态规划class Solution { public: int climbStairs(int n) { int p 0, q 0, r 1; for (int i 1; i n; i) { p q; q r; r p q; } return r; } };class Solution { public: int climbStairs(int n) { vectorint dp(n 1); dp[0] dp[1] 1; for (int i 2; i n; i) { dp[i] dp[i - 1] dp[i - 2]; } return dp[n]; } };