算法练习4

ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3), should return "PAHNAPLSIIGYIR" 。

解题思路

题目大意：将一个字符串以之字形方式重排列之后输出。

看到这道题很容易就想到了构建nRows个字符串，将原字符串按照之字形顺序添加在相应的字符串末尾。观察题目给出的例子，容易得出字符一个之字形周期是2 * nRows - 2，设index = i % (2 * nRows - 2)，则当index大于nRows时，index=2*nRwos-index-2，index是字符串数组的下标。最后将字符串数组按顺序拼接得到解。

代码

public class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        int li = numRows + (numRows - 2);
        StringBuilder[] builders = new StringBuilder[numRows];
        for (int i = 0; i < numRows; i++) {
            builders[i] = new StringBuilder();
        }
        for (int i = 0; i < s.length(); i++) {
            int index = i % li;
            if (index >= numRows) {
                index = 2 * numRows - index - 2;
            }
            builders[index].append(s.charAt(i));
        }
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < numRows; i++) {
            res.append(builders[i].toString());
        }

        return res.toString();
    }
}

---

Reverse Integer

Reverse digits of an integer.The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

Example1: x = 123, return 321
Example2: x = -123, return -321

解题思路

题目大意：反转整数，溢出返回0

对输入x每次取最后一位，然后向右移一位，然后将结果result向左移一位后加取到的最后一位。直到x为0。每次移位之后判断移位前后result是否相等，若不相等则溢出，返回0。

代码

public class Solution {
    public int reverse(int x) {
        int result = 0;
    while (x != 0) {
        int tail = x % 10;
        int newResult = result * 10 + tail;
        if ((newResult - tail) / 10 != result) return 0;
        result = newResult;
        x = x / 10;
    }
    return result;
    }
}