螺旋矩陣2

給你一個正整數 n ，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的 n x n 正方形矩陣 matrix。

示例 1：
輸入：n = 3 輸出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
輸入：n = 1 輸出：[[1]]

解題思路：里面元素是1 - n*n，并且數組是順序螺旋排列。

public int[][] generateMatrix(int n) {int maxNum = n * n;int curNum = 1;int[][] matrix = new int[n][n];int row = 0;int column = 0;int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int directionIndex = 0;while(curNum <= maxNum) {matrix[row][column] = curNum;curNum++;int nextRow = row + directions[directionIndex][0];int nextColumn = column + directions[directionIndex][1];if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n || matrix[nextRow][nextColumn] != 0) {directionIndex = (directionIndex + 1) % 4; // 順時針旋轉至下一個方向}row = row + directions[directionIndex][0];column = column + directions[directionIndex][1];}return matrix;}

排列序列

給出集合 [1,2,3,…,n]，其所有元素共有 n! 種排列。按大小順序列出所有排列情況，并一一標記，當 n = 3 時, 所有排列如下：
“123”
“132”
“213”
“231”
“312”
“321”
給定 n 和 k，返回第 k 個排列。

示例 1：
輸入：n = 3, k = 3 輸出：“213”
示例 2：
輸入：n = 4, k = 9 輸出：“2314”
示例 3：
輸入：n = 3, k = 1 輸出：“123”

解題思路：DFS

 public String getPermutation(int n, int k) {int[] factorial = new int[n];factorial[0] = 1;for (int i = 1; i < n; ++i) {factorial[i] = factorial[i - 1] * i;}--k;StringBuffer ans = new StringBuffer();int[] valid = new int[n + 1];Arrays.fill(valid, 1);for (int i = 1; i <= n; ++i) {int order = k / factorial[n - i] + 1;for (int j = 1; j <= n; ++j) {order -= valid[j];if (order == 0) {ans.append(j);valid[j] = 0;break;}}k %= factorial[n - i];}return ans.toString();}

旋轉鏈表

給你一個鏈表的頭節點 head ，旋轉鏈表，將鏈表每個節點向右移動 k 個位置。

示例 1：
輸入：head = [1,2,3,4,5], k = 2 輸出：[4,5,1,2,3]
示例 2：
輸入：head = [0,1,2], k = 4 輸出：[2,0,1]

public ListNode rotateRight(ListNode head, int k) {if (k == 0 || head == null || head.next == null) {return head;}int n = 1;ListNode iter = head;while (iter.next != null) {iter = iter.next;n++;}int add = n - k % n;if (add == n) {return head;}iter.next = head;while (add-- > 0) {iter = iter.next;}ListNode ret = iter.next;iter.next = null;return ret;}

不同路徑

一個機器人位于一個 m * n 網格的左上角 。機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角，問總共有多少條不同的路徑？

示例 1：
輸入：m = 3, n = 7 輸出：28
示例 2：
輸入：m = 3, n = 2 輸出：3
示例 3：
輸入：m = 7, n = 3 輸出：28
示例 4：
輸入：m = 3, n = 3 輸出：6

解題思路：動態規劃

public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for (int i = 0; i < n; i++) {dp[0][i] = 1;}for (int i = 0; i < m; i++) {dp[i][0] = 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];  }

不同路徑2

一個機器人位于一個 m x n 網格的左上角 。機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角。現在考慮網格中有障礙物。那么從左上角到右下角將會有多少條不同的路徑？
網格中的障礙物和空位置分別用 1 和 0 來表示。

示例 1：
輸入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
輸出：2
示例 2：
輸入：obstacleGrid = [[0,1],[0,0]]
輸出：1

public int uniquePathsWithObstacles(int[][] obstacleGrid) {int len = obstacleGrid.length;int m = obstacleGrid[0].length;int[] f = new int[m];f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;for (int i = 0; i < len; ++i) {for (int j = 0; j < m; ++j) {if (obstacleGrid[i][j] == 1) {f[j] = 0;continue;}if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {f[j] += f[j - 1];}}}return f[m - 1];}