7月4日的五题

58. 最后一个单词的长度

59. 螺旋矩阵 II

60. 第k个排列

61. 旋转链表

62. 不同路径

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

58. 最后一个单词的长度

Difficulty: 简单

给定一个仅包含大小写字母和空格 ' ' 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。

如果不存在最后一个单词，请返回 0 。

**说明：**一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。

示例:

输入: "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

Difficulty: 中等

给定一个正整数 n，生成一个包含 1 到 n² 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 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个排列

Difficulty: 中等

给出集合 [1,2,3,…,_n_]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123""132""213""231""312""321"

给定 n 和 k，返回第 k 个排列。

说明：

给定 n 的范围是 [1, 9]。给定 _k _的范围是[1, n!]。

示例 1:

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

示例 2:

输入: 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); } //计算n的阶乘 public int jieCheng(int n){ int res = 1; for(int i=2; i<=n; i++){ res *= i; } return res; } }

61. 旋转链表

Difficulty: 中等

给定一个链表，旋转链表，将链表每个节点向右移动 _k _个位置，其中 _k _是非负数。

示例 1:

输入: 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

示例 2:

输入: 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. 不同路径

Difficulty: 中等

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

示例 1:

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

示例 2:

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

提示：

1 <= m, n <= 100题目数据保证答案小于等于 2 * 10 ^ 9

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]; } }