写于2019年5月26日
文章目录
[48. 旋转图像](https://leetcode.com/problems/rotate-image/)① 题目描述② 非原地旋转③ 顺时针旋转90
[49. 字母异位词分组](https://leetcode.com/problems/group-anagrams/)① 题目描述② 字母异位词的排序字符串相同③ 字母异位词的每个字母的个数一致。
[53. 最大子序和](https://leetcode.com/problems/maximum-subarray/)① 题目描述② 暴力解法③ 动态规划
48. 旋转图像
① 题目描述
给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。说明： 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。示例 1:
给定 matrix = [ [1,2,3], [4,5,6], [7,8,9] ], 原地旋转输入矩阵，使其变为: [ [7,4,1], [8,5,2], [9,6,3] ]
② 非原地旋转
通过观察发现，原始矩阵的第一行通过旋转后，变为新矩阵的最后一列，即第i行变n-i-1列。使用新的矩阵存储变形后的矩阵，再将新矩阵赋值给原始矩阵。代码如下：
public void rotate(int[][] matrix
) {
int n
= matrix
.length
;
int[][] temp
= new int[n
][n
];
for (int i
= 0; i
< n
; i
++) {
for (int j
= 0; j
< n
; j
++) {
temp
[j
][n
- i
- 1] = matrix
[i
][j
];
}
}
for (int i
= 0; i
< n
; i
++) {
for (int j
= 0; j
< n
; j
++) {
matrix
[i
][j
] = temp
[i
][j
];
}
}
}
③ 顺时针旋转90
相当于先转置（第i列变第i行），再水平对称翻转。
[
1
2
3
4
5
6
7
8
9
]
⇒
[
1
4
7
2
5
8
3
6
9
]
⇒
[
7
4
1
8
5
2
9
6
3
]
\begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{bmatrix}\Rightarrow \begin{bmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \\ \end{bmatrix}\Rightarrow \begin{bmatrix} 7& 4 & 1 \\ 8 & 5 & 2 \\ 9 & 6 & 3 \\ \end{bmatrix}
⎣⎡147258369⎦⎤⇒⎣⎡123456789⎦⎤⇒⎣⎡789456123⎦⎤代码如下，注意： 转置时，内层循环j <= i：
public void rotate(int[][] matrix
) {
int n
= matrix
.length
;
for (int i
= 0; i
< n
; i
++) {
for (int j
= 0; j
<= i
; j
++) {
if (i
== j
) {
continue;
}
int temp
= matrix
[i
][j
];
matrix
[i
][j
] = matrix
[j
][i
];
matrix
[j
][i
] = temp
;
}
}
for (int i
= 0; i
< n
; i
++) {
int start
= 0;
int end
= n
- 1;
while (start
< end
) {
int temp
= matrix
[i
][start
];
matrix
[i
][start
] = matrix
[i
][end
];
matrix
[i
][end
] = temp
;
start
++;
end
--;
}
}
}
49. 字母异位词分组
① 题目描述
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。示例:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”], 输出: [ [“ate”,“eat”,“tea”], [“nat”,“tan”], [“bat”] ]
说明： 所有输入均为小写字母；不考虑答案输出的顺序。
② 字母异位词的排序字符串相同
字母异位词的排序字符串相同，可以通过hashmap将按字符顺序排序相同的目标词放在同一个key下。每一个value采用List<String>类型，既可以存储个数不确定的目标词，又能在map.values()返回Collection<List<String>>类型的结果。巧用Java API，比如对目标词进行排序，通过API将其转化为char[]，再使用Arrays.sort(arr)进行排序。没有必要自己写排序函数！整体思想示意图： 代码如下：
public List
<List
<String>> groupAnagrams(String
[] strs
) {
Map
<String
, List
<String>> map
= new HashMap<>();
for (int i
= 0; i
< strs
.length
; i
++) {
char[] arr
= strs
[i
].toCharArray();
Arrays
.sort(arr
);
String key
= String
.valueOf(arr
);
if (map
.containsKey(key
)) {
map
.get(key
).add(strs
[i
]);
} else {
List
<String> item
= new ArrayList<>();
item
.add(strs
[i
]);
map
.put(key
, item
);
}
}
return new ArrayList<List
<String>>(map
.values());
}
③ 字母异位词的每个字母的个数一致。
自己的想法： 灵感来自于将排序后的目标词作为hashmap的key，计算目标词中每一个字母出现的次数，然后使用#2#1#0#0...的形式（以aba为例）将其转化为key，将相同key的字符串存到到value中。运行结果花了38ms，代码如下：
public List
<List
<String>> groupAnagrams(String
[] strs
) {
Map
<String
, List
<String>> map
= new HashMap<>();
for (int i
= 0; i
< strs
.length
; i
++) {
int[] count
= new int[26];
for (int j
= 0; j
< strs
[i
].length(); j
++) {
int index
= strs
[i
].charAt(j
)- 'a';
count
[index
]++;
}
String key
= "";
for (int k
= 0; k
< 26; k
++) {
key
+= "#" + count
[k
];
}
if (map
.containsKey(key
)) {
map
.get(key
).add(strs
[i
]);
} else {
List
<String> item
= new ArrayList<>();
item
.add(strs
[i
]);
map
.put(key
, item
);
}
}
return new ArrayList<List
<String>>(map
.values());
}
别人的想法： ① 比较当前目标词和之后的目标词的字母个数是否一致，如果一致添加到同一List中，并将之后的目标词置为null，表示已经有相应的分组。 ② 需要编写helper方法，比较两个字符串的字母个数是否一致，也是采用hashmap。第一个字符串的字母个数计入hashmap，第二个字符串，遇到相同字母，让个数-1，字母不存在返回false；最后遍历hashmap，如果每个字母的个数均为0，表示两个字符串是异位词。 ③ 已经分组的字符串要置为null，因此使用前，一定要判断其是否为null。竟然Time Limit Exceeded！代码如下：
public List
<List
<String>> groupAnagrams(String
[] strs
) {
List
<List
<String>> result
= new ArrayList<>();
for (int i
= 0; i
< strs
.length
; i
++) {
if (strs
[i
] != null
) {
List
<String> item
= new ArrayList<>();
item
.add(strs
[i
]);
for (int j
= i
+ 1; j
< strs
.length
; j
++) {
if (strs
[j
] != null
&& helper(strs
[i
], strs
[j
])) {
item
.add(strs
[j
]);
strs
[j
] = null
;
}
}
result
.add(item
);
}
}
return result
;
}
public boolean helper(String s1
, String s2
) {
Map
<Character, Integer> map
= new HashMap<>();
for (int i
= 0; i
< s1
.length(); i
++) {
if (map
.containsKey(s1
.charAt(i
))) {
map
.put(s1
.charAt(i
), map
.get(s1
.charAt(i
)) + 1);
} else {
map
.put(s1
.charAt(i
), 1);
}
}
for (int j
= 0; j
< s2
.length(); j
++) {
if (map
.containsKey(s2
.charAt(j
))) {
map
.put(s2
.charAt(j
), map
.get(s2
.charAt(j
)) - 1);
} else {
return false;
}
}
for (Character key
: map
.keySet()) {
if (map
.get(key
) != 0) {
return false;
}
}
return true;
}
53. 最大子序和
① 题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
② 暴力解法
从下标i开始，遍历nums，对其进行求和，如果max_sum < sum，则更新max_sum。时间复杂度:
n
(
n
−
1
)
2
\dfrac{n(n-1)}{2}
2n(n−1)，即
O
(
n
2
)
O(n^2)
O(n2)。代码如下：
public int maxSubArray(int[] nums
) {
int max_sum
= Integer
.MIN_VALUE
;
for (int i
= 0; i
< nums
.length
; i
++) {
int sum
= 0;
for (int j
= i
; j
< nums
.length
; j
++) {
sum
+= nums
[j
];
if (max_sum
< sum
) {
max_sum
= sum
;
}
}
}
return max_sum
;
}
③ 动态规划
用一个一维数组 dp [ i ] 表示以下标 i 结尾的子数组的元素的最大的和，有两种情况： 如果 dp [ i - 1 ] < 0，那么dp [ i ] = nums [ i ]，因为一个数加上负数，一定会变小！ 如果 dp [ i - 1 ] >= 0，那么 dp [ i ] = dp [ i - 1 ] + nums [ i ]。初始化条件：dp[0] = nums[0]且max_sum = nums[0]。时间复杂度：
O
(
n
)
O(n)
O(n)，一次遍历即可。空间复杂度：
O
(
n
)
O(n)
O(n)，需要开辟额外的空间作为dp[]。代码如下：
public int maxSubArray(int[] nums
) {
int[] dp
= new int[nums
.length
];
dp
[0] = nums
[0];
int max_sum
= nums
[0];
for (int i
= 1; i
< nums
.length
; i
++) {
if (dp
[i
- 1] < 0) {
dp
[i
] = nums
[i
];
} else {
dp
[i
] = dp
[i
- 1] + nums
[i
];
}
if (max_sum
< dp
[i
]) {
max_sum
= dp
[i
];
}
}
return max_sum
;
}
