8/10, Google Tag
挺简单的，和 group anagram 异曲同工。
唯一需要注意的就是 "az" 和 "ba" 同组，说明字母表是环形的。两个字母之间的差如果为负数，就把 diff 加上 26. "az" diff = -25 + 26 = 1; "ba" diff = 1;
public class Solution {
public List<List<String>> groupStrings(String[] strings) {
List<List<String>> rst = new ArrayList<>();
// Key : diff1,diff2... single character is ""
// Value : list of strings grouped together
HashMap<String, List<String>> map = new HashMap<>();
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < strings.length; i++){
String str = strings[i];
sb.setLength(0);
for(int j = 0; j < str.length() - 1; j++){
int diff = str.charAt(j) - str.charAt(j + 1);
if(diff < 0) diff += 26;
sb.append(diff);
sb.append(',');
}
String key = sb.toString();
if(!map.containsKey(key)) map.put(key, new ArrayList<String>());
map.get(key).add(str);
}
Iterator<String> iter = map.keySet().iterator();
while(iter.hasNext()){
rst.add(map.get(iter.next()));
}
return rst;
}
}一开始看错了，以为是相乘，搞了一堆因式分解数因数的。。还往数论上想了半天。
后来发现 BFS 就能 AC.
前两次提交都在大数上 MLE，说明 BFS 剪枝不到位。
扫合理 moves 的时候，先从大的扫；
用个 hashset 存一下已经访问过的 sum 值，避免重复；
以上两招都可以很简便的减少内存和计算时间开销。
public class Solution {
public int numSquares(int n) {
// All perfect squares less than n
List<Integer> moves = new ArrayList<>();
for(int i = 1; i <= n; i++){
if(i * i <= n) moves.add(i * i);
else break;
}
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
int lvl = 0;
queue.offer(0);
while(!queue.isEmpty()){
int size = queue.size();
lvl ++;
for(int i = 0; i < size; i++){
int sum = queue.poll();
for(int j = moves.size() - 1; j >= 0; j--){
int next = moves.get(j);
if(sum + next > n || visited.contains(sum + next)){
continue;
} else if(sum + next == n){
return lvl;
} else {
visited.add(sum + next);
queue.offer(sum + next);
}
}
}
}
return -1;
}
}再仔细观察一下这题:
我们要凑出来一个和正好是 n 的选择组合；
能选的元素是固定数量的 perfect square (有的会超)
一个元素可以选多次；
这就是背包啊！
public class Solution {
public int numSquares(int n) {
// All perfect squares less than n
int[] dp = new int[n + 1];
Arrays.fill(dp, n + 1);
dp[0] = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j * j <= n; j++){
if(i - j * j >= 0) dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}流程：
start 从倒数第二个数起，往左扫，寻找到第一个 nums[start] < nums[start + 1] 的位置；
从 start 往后找，找到第一个比 nums[start] 小的前一个数 (也就是最小的大于等于 nums[start] 的数)
交换 start , end
把 start + 1 后面的区间翻转，over.
1: 右往左，找下落；
2：左往右，找 threshold (换过来的数，怎么说也得比 nums[start] 大)
3：交换，反转。
public class Solution {
public void nextPermutation(int[] nums) {
if(nums == null || nums.length <= 1) return;
int start = nums.length - 2;
while(start >= 0 && nums[start] >= nums[start + 1]) start--;
if(start >= 0){
int end = start + 1;
while(end < nums.length && nums[start] < nums[end]) end++;
end--;
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
}
reverse(nums, start + 1);
}
private void reverse(int[] nums, int index){
int end = nums.length - 1;
while(index < end){
int temp = nums[index];
nums[index] = nums[end];
nums[end] = temp;
index++;
end--;
}
}
}为什么一个这么简单的 DFS 能超过 89% ..
注意：index == 0 并且 i == 0 的时候要跳过，免得在起始位置填上 0 .
public class Solution {
public List<String> findStrobogrammatic(int n) {
List<String> list = new ArrayList<>();
char[] num1 = {'0','1','8','6','9'};
char[] num2 = {'0','1','8','9','6'};
char[] number = new char[n];
dfs(list, number, num1, num2, 0);
return list;
}
private void dfs(List<String> list, char[] number, char[] num1, char[] num2, int index){
int left = index;
int right = number.length - index - 1;
if(left > right){
list.add(new String(number));
return;
}
// We can fill in 0,1,8 only
if(left == right){
for(int i = 0; i < 3; i++){
number[left] = num1[i];
dfs(list, number, num1, num2, index + 1);
}
} else {
for(int i = 0; i < num1.length; i++){
if(index == 0 && i == 0) continue;
number[left] = num1[i];
number[right] = num2[i];
dfs(list, number, num1, num2, index + 1);
}
}
}
}Google 面经里的 follow-up 是，给定一个上限 n ，输出所有上限范围内的数。
办法土了点，遍历所有 lowLen ~ highLen 区间的长度，生成所有可能的结果，考虑到区间可能是大数，我们就改一下，自己写一个 String compare 函数好了。
后来发现有点多余，可以直接用内置的 str1.compareTo(str2).
超过 81.92% ~
public class Solution {
int count = 0;
public int strobogrammaticInRange(String low, String high) {
int lowLen = low.length();
int highLen = high.length();
char[] num1 = {'0','1','8','6','9'};
char[] num2 = {'0','1','8','9','6'};
for(int i = lowLen; i <= highLen; i++){
char[] number = new char[i];
dfs(number, num1, num2, 0, low, high);
}
return count;
}
private void dfs(char[] number, char[] num1, char[] num2, int index, String low, String high){
int left = index;
int right = number.length - index - 1;
if(left > right){
String num = new String(number);
if(compare(low, num) <= 0 && compare(num, high) <= 0) count++;
return;
} else if(left == right){
for(int i = 0; i < 3; i++){
number[left] = num1[i];
dfs(number, num1, num2, index + 1, low, high);
}
} else {
for(int i = 0; i < 5; i++){
if(index == 0 && i == 0) continue;
number[left] = num1[i];
number[right] = num2[i];
dfs(number, num1, num2, index + 1, low, high);
}
}
}
// -1 : str1 is bigger
// 1 : str 2 is bigger
// 0 : equal
private int compare(String str1, String str2){
if(str1.length() > str2.length()) return 1;
else if(str1.length() < str2.length()) return -1;
else {
for(int i = 0; i < str1.length(); i++){
int digit1 = str1.charAt(i) - '0';
int digit2 = str2.charAt(i) - '0';
if(digit1 != digit2) return (digit1 > digit2) ? 1: -1;
}
}
// Equal
return 0;
}
}我很喜欢这题，挺有创意~
注意点 1 : a = 0 的时候是直线，不能无脑按照抛物线的方式处理；
注意点 2 : 对称轴 -b / 2 * a 的时候括号顺序是 (double) -b / (2 * a)
第一次 AC 的代码~ 太粗糙，得改改。
public class Solution {
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
int[] rst = new int[nums.length];
// Is a straight line
if(a == 0){
if(b > 0){
for(int i = 0; i < nums.length; i++){
rst[i] = a * nums[i] * nums[i] + b * nums[i] + c;
}
} else {
for(int i = 0; i < nums.length; i++){
rst[nums.length - i - 1] = a * nums[i] * nums[i] + b * nums[i] + c;
}
}
return rst;
}
double symmetricAxis = -((double) b / (2*a));
int left = 0;
int right = nums.length - 1;
int index = (a < 0) ? 0: nums.length - 1;
int step = (a < 0) ? 1: -1;
while(left <= right){
double leftDis = Math.abs(nums[left] - symmetricAxis);
double rightDis = Math.abs(nums[right] - symmetricAxis);
if(leftDis > rightDis){
rst[index] = a * nums[left] * nums[left] + b * nums[left] + c;
left ++;
} else {
rst[index] = a * nums[right] * nums[right] + b * nums[right] + c;
right --;
}
index += step;
}
return rst;
}
}这题比较简洁的写法如下，明天学习一个。
这种写法的核心是只看 a 的 “正负”，无所谓 0.
If a > 0; the smallest number must be at two ends of orgin array;
If a < 0; the largest number must be at two ends of orgin array;
换句话说，a 的符号可以直接确定 two pointer 两端一定有一个 “最大/最小” 的值，每次 O(1) 计算一下就好，也能处理直线的情况。
public class Solution {
public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
int n = nums.length;
int[] sorted = new int[n];
int i = 0, j = n - 1;
int index = a >= 0 ? n - 1 : 0;
while (i <= j) {
if (a >= 0) {
sorted[index--] = quad(nums[i], a, b, c) >= quad(nums[j], a, b, c)
? quad(nums[i++], a, b, c)
: quad(nums[j--], a, b, c);
} else {
sorted[index++] = quad(nums[i], a, b, c) >= quad(nums[j], a, b, c)
? quad(nums[j--], a, b, c)
: quad(nums[i++], a, b, c);
}
}
return sorted;
}
private int quad(int x, int a, int b, int c) {
return a * x * x + b * x + c;
}
}Last updated
Was this helpful?