挺简单的,和 group anagram 异曲同工。
唯一需要注意的就是 "az" 和 "ba" 同组,说明字母表是环形的。两个字母之间的差如果为负数,就把 diff 加上 26. "az" diff = -25 + 26 = 1; "ba" diff = 1;
Copy 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 剪枝不到位。
用个 hashset 存一下已经访问过的 sum 值,避免重复;
以上两招都可以很简便的减少内存和计算时间开销。
Copy 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 ;
}
}
再仔细观察一下这题:
能选的元素是固定数量的 perfect square (有的会超)
这就是背包啊!
Copy 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 + 1 后面的区间翻转,over.
1: 右往左,找下落;
2:左往右,找 threshold (换过来的数,怎么说也得比 nums[start] 大)
3:交换,反转。
Copy 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 .
Copy 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% ~
Copy 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 的代码~ 太粗糙,得改改。
Copy 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) 计算一下就好,也能处理直线的情况。
Copy 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;
}
}