LeetCode 06Z字形變換&07整數反轉
Z字形變換
題意
題目描述
將一個給定字串根據給定的行數，以從上往下、從左到右進行 Z 字形排列。
比如輸入字串爲 「LEETCODEISHIRING」 行數爲 3 時，排列如下：
L C I R
E T O E S I I G
E D H N
之後，你的輸出需要從左往右逐行讀取，產生出一個新的字串，比如：「LCIRETOESIIGEDHN」。
請你實現這個將字串進行指定行數變換的函數：
string convert(string s, int numRows);
範例 1:
輸入: s = 「LEETCODEISHIRING」, numRows = 3
輸出: 「LCIRETOESIIGEDHN」
範例 2:
輸入: s = 「LEETCODEISHIRING」, numRows = 4
輸出: 「LDREOEIIECIHNTSG」
解釋:
L D R
E O E I I
E C I H N
T S G
分析
對於這題該如何處理呢？首先要理解題意，它就是本來給一個字串，然後要按照Z字形排列等到一個形狀，根據這個形狀按照從左往右的順序取值得到一個新的字串。
法一模擬法：
既然這個字串是固定的，那麼我們是否可以模擬這個過程？
- of course you can 模擬。你可以定義一個二位陣列，根據Z字形的這個排列規律，先向下(同時橫座標不變)，再向上(同時考慮橫座標增加)一直到最後，然後對二維陣列進行遍歷取值(不空的值。)
這樣當然可以，但是模擬真的有必要這麼搞嘛？當然沒必要。二維陣列佔據太多無用的空間浪費記憶體。我們其實可以對記憶體進行優化考慮：
這樣只需要考慮上下兩個方嚮往集閤中新增元素，最終就可以實現啦。不過在字串疊加時候儘量不要使用String直接加，會很慢。這種方法只能幹掉40%的人，一般般。
ac程式碼爲：
public String convert(String s, int numRows) {
List<Character> list[]=new ArrayList[numRows];
for(int i=0;i<numRows;i++)
{
list[i]=new ArrayList<Character>();
}
int index=0;
boolean up=false;//方向 初始向下
for(int i=0;i<s.length();i++)
{
list[index].add(s.charAt(i));
if(numRows==1) {continue;}
if(up)//向上
{
if(index==0)
{
index++;up=false;
}
else {
index--;
}
}
else {
if(index==numRows-1)
{
index--;up=true;
}
else {
index++;
}
}
}
StringBuilder builder=new StringBuilder();
for(int i=0;i<numRows;i++)
{
for(int j=0;j<list[i].size();j++)
{
builder.append(list[i].get(j));
}
}
return builder.toString();
}
法二數學分析
上面的一種方法爲模擬Z字形操作的整個流程，需要往裏新增，取值也需要遍歷取值。我們能不能用另一種角度去思考問題呢？
因爲每次只加一個字元，我們如果按照以下的思路看待這個問題(原字串彎曲)，從每一層看，能不能找到每一層有什麼規律呢？
- 第一層是
0 6 12也就是0 0+(n-1)*2 0+(n-1)*3 - 第二層兩個求位置關係，可不可以看成第一層每個位置-1和+1兩個位置(越界不考慮)？
- 第三層和第二層同理，看成第一層的-2和+2不越界的位置。
- 最後一層單獨考慮
這樣整個邏輯分析就完成了，可以根據位置新增元素進去再取值。ac的程式碼如下：
public String convert(String s, int numRows) {
if(numRows==1)return s;
List<Character> list[]=new ArrayList[numRows];
for(int i=0;i<numRows;i++)
{
list[i]=new ArrayList<Character>();
}
//處理第一行最後一行
for(int i=0;i<s.length();i+=(numRows-1)*2)
{
list[0].add(s.charAt(i));
if(i+numRows-1<s.length())
{
list[numRows-1].add(s.charAt(i+numRows-1));
}
}
for(int i=0;i<s.length()+numRows;i+=(numRows-1)*2)
{
for(int j=1;j<numRows-1;j++)//中間所有行
{
int index1=i-j;
int index2=i+j;
if(index1>=0&&index1<s.length())
list[j].add(s.charAt(index1));
if(index2>=0&&index2<s.length())
list[j].add(s.charAt(index2));
}
}
StringBuilder builder=new StringBuilder();
for(int i=0;i<numRows;i++)
{
for(int j=0;j<list[i].size();j++)
{
builder.append(list[i].get(j));
}
}
return builder.toString();
}
但這種方法也只能幹掉40%+的人，該如何優化呢?
- 首先，該方法先存到List[]再取，其實是遍歷兩次，其實大可不必這樣，我們可以在進行計算每一層的同時加入到結果中。
- 其次，由於邊界的問題我們需要考慮太多的邊界問題，我們對此對中間層的考慮優化，兩個節點位置通過計算這樣組合，可以優化邊界的if else判斷。
注意一些細節情況，最終ac的程式碼爲：
public static String convert2(String s, int numRows) {
if(numRows==1)return s;
//處理第一行
StringBuilder builder=new StringBuilder();
for(int i=0;i<s.length();i+=(numRows-1)*2)
{
builder.append(s.charAt(i));
}
for(int i=1;i<numRows-1;i++)
{
for(int j=0;j<s.length()+numRows;j+=(numRows-1)*2)//中間所有行
{
int index1=j+i;
int index2=j+(numRows-1)*2-i;
if(index1<s.length())
builder.append(s.charAt(index1));
if(index2<s.length())
builder.append(s.charAt(index2));
}
}
for(int i=numRows-1;i<s.length();i+=(numRows-1)*2)
{
builder.append(s.charAt(i));
}
return builder.toString();
}
最終的效果還行(偶爾三毫秒)：
整數反轉
這題的話注意以下陣列越界問題，可以用long型別處理最終再用整形處理。
主要有兩種處理方法，一個就是轉成字串處理，第二個就是用數值處理。但是一般儘量不要用字串處理比較慢。
ac程式碼爲：
public int reverse(int x) {
if(x==0)return 0;
String value=x+"";
if(value.charAt(0)=='-')
value=value.substring(1);
StringBuilder sb=new StringBuilder();
for(int i=value.length()-1;i>=0;i--)
{
sb.append(value.charAt(i));
}
long num=Long.parseLong(sb.toString());
if(x<0)num=-num;
if(num<Integer.MIN_VALUE||num>Integer.MAX_VALUE)
{
return 0;
}
return (int)num;
}
數值型別處理方式爲：
public int reverse(int x) {
if(x==0)return 0;
long num=0;
while (x%10==0) {
x/=10;
}
int t;
while (x!=0) {
t=x%10;//各位
num=num*10+t;
x/=10;
if(num>Integer.MAX_VALUE||num<Integer.MIN_VALUE)
return 0;
}
return (int)num;
}
結語
本次兩題稍容易一些，再接再厲，注意方法的優化。
歡迎關注公衆號：bigsai,回覆 回復進羣，一起打卡LeetCode！
