58. 最后一个单词的长度

59. 螺旋矩阵 II

60. 第k个排列

61. 旋转链表

62. 不同路径

----------------------------------分割线-----------------------------------------

58. 最后一个单词的长度

输入: "Hello World"
输出: 5

Solution：注意这种情况 "a "

​class Solution {public int lengthOfLastWord(String s) {if(s == null || s.length()<=0) return 0;int res = 0, len = s.length();boolean flag = false;for(int i=len-1; i>=0; i--){if(s.charAt(i) == ' '){if(flag) return res;else continue;}else{res++;if(!flag) flag = true;}} return res;}
}

59. 螺旋矩阵 II

输入: 3
输出:
[[ 1, 2, 3 ],[ 8, 9, 4 ],[ 7, 6, 5 ]
]

Solution：固定四个，一层层的遍历，注意（上和下）、（左和右）重复的情况

​class Solution {public int[][] generateMatrix(int n) {int[][] res = new int[n][n];if(n == 0) return res;else if(n == 1){res[0][0] = 1;return res;}int low, high;low = 0;high = n-1;int x = 1;while(x <= n*n){for(int j=low; j<=high; j++){res[low][j] = x;x++;}for(int j=low+1; j<high; j++){res[j][high] = x;x++;}if(low != high){   //（上和下）、（左和右）重复的情况for(int j=high; j>low; j--){res[high][j] = x;x++;}for(int j=high; j>low; j--){res[j][low] = x;x++;}}low ++;high--;}return res;}
}

60. 第k个排列

输入: n = 3, k = 3
输出: "213"

输入: n = 4, k = 9
输出: "2314"

Solution：（递归）——把所有的情况写成二叉树的形式，依次确定每个值属于哪支树杈

​class Solution {public String getPermutation(int n, int k) {StringBuilder builder = new StringBuilder();int[] used = new int[n+1];  help(n, n, k, builder, used);return builder.toString();}public void help(int n, int m, int k, StringBuilder builder, int[] used){if(m <= 0 || k < 0) return ;int jc = jieCheng(m-1);  //有多少树杈int x = (k-1) / jc; // x就是位于第几个树杈int count  = -1;for(int i=1; i<=n; i++){if(used[i] == 0){count++;if(count == x){builder.append(i);used[i] = 1;break;}}}help(n, m-1, k-x*jc, builder, used);}public int jieCheng(int n){int res = 1;for(int i=2; i<=n; i++){res *= i;}return res;}
}

61. 旋转链表

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

Solution ：就是把倒数第（k%len）个结点当做头结点

​/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode rotateRight(ListNode head, int k) {int len = 0;ListNode node = head;//找链表的长度while(node != null){len++;node = node.next;} if(len <= 0) return head;k = k%len;   //避免循环重复的情况if(k == 0) return head;//寻找倒数第k+1个结点node = head;for(int i=0; i<len-k-1; i++){node = node.next;}//res就是头结点ListNode res = node.next;node.next = null;node = res;while(node.next != null){node = node.next;}node.next = head;return res;}
}

62. 不同路径

输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1\. 向右 -> 向右 -> 向下
2\. 向右 -> 向下 -> 向右
3\. 向下 -> 向右 -> 向右

输入: m = 7, n = 3
输出: 28

Solution：动态规划

​class Solution {int count = 0;public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for(int i=0; i<m; i++){for(int j=0; j<n; j++){if(i==0 || j==0) dp[i][j] = 1;else dp[i][j] = dp[i][j-1] + dp[i-1][j];}}return dp[m-1][n-1];}
}