\chapter{String}

\section{Reverse String} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Write a function that takes a string as input and returns the string reversed.

\textbf{Example:}

Given s = \code{"hello"}, return \code{"olleh"}.

\subsubsection{Solution}

\begin{Code}

public String reverseString(String s) {

return new StringBuilder(s).reverse().toString();

}

\end{Code}

\section{Reverse String II} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.

\textbf{Example:}

\textbf{Input:} s = \code{"abcdefg"}, k = 2

\textbf{Output:} \code{"bacdfeg"}

\textbf{Restrictions:}

The string consists of lower English letters only.

Length of the given string and k will in the range \code{[1, 10000]}

\subsubsection{Solution}

\begin{Code}

public String reverseStr(String s, int k) {

if (s.length() <= k) {

return new StringBuilder(s).reverse().toString();

}

if (s.length() <= 2 * k) {

return reverseStr(s.substring(0, k), k) + s.substring(k);

}

return reverseStr(s.substring(0, 2 * k), k) + reverseStr(s.substring(2 * k), k);

}

\end{Code}

\section{Reverse Words in a String} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given an input string, reverse the string word by word.

For example,

Given s = "the sky is blue",

return "blue is sky the".

Clarification:

1. What constitutes a word?

A sequence of non-space characters constitutes a word.

2. Could the input string contain leading or trailing spaces?

Yes. However, your reversed string should not contain leading or trailing spaces.

3. How about multiple spaces between two words?

Reduce them to a single space in the reversed string.

\subsubsection{Solution I}

\begin{Code}

// 耗时10ms

public String reverseWords(String s) {

StringBuilder sb = new StringBuilder();

boolean inWord = false;

char[] cc = s.toCharArray();

for (int i = cc.length - 1, idx = 0; i >= 0; i--) {

if (cc[i] != ' ') {

if (!inWord && sb.length() > 0) {

sb.append(' ');

}

inWord = true;

sb.insert(idx, cc[i]);

} else if (inWord) {

idx = sb.length() + 1;

inWord = false;

}

}

return sb.toString();

}

\end{Code}

\subsubsection{Solution II}

\begin{Code}

// 耗时18ms

public String reverseWords2(String s) {

StringBuilder sb = new StringBuilder();

for (int i = 0, j = 0; i < s.length(); ) {

if (s.charAt(i) == ' ') {

i++;

j = i;

} else if (j >= s.length() || s.charAt(j) == ' ') {

sb.insert(0, s.substring(i, j) + " ");

i = j;

} else {

j++;

}

}

if (sb.length() > 0) {

sb.setLength(sb.length() - 1);

}

return sb.toString();

}

\end{Code}

\section{Reverse Words in a String II} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,

Given s = \code{"the sky is blue"},

return \code{"blue is sky the"}.

Could you do it in-place without allocating extra space?

\subsubsection{Solution}

\begin{Code}

public void reverseWords(char[] s) {

for (int i = 0, j = i; i < s.length; ) {

if (j >= s.length || s[j] == ' ') {

reverse(s, i, j - 1);

for (i = j; j < s.length && s[j] == ' '; j++, i = j) ;

} else {

j++;

}

}

reverse(s, 0, s.length - 1);

}

private void reverse(char[] s, int start, int end) {

for (int i = start, j = end; i < j; i++, j--) {

char t = s[i];

s[i] = s[j];

s[j] = t;

}

}

\end{Code}

\section{Reverse Words in a String III} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

\textbf{Example 1:}

\textbf{Input:} \code{"Let's take LeetCode contest"}

\textbf{Output:} \code{"s'teL ekat edoCteeL tsetnoc"}

\textbf{Note:} In the string, each word is separated by single space and there will not be any extra space in the string.

\subsubsection{Solution}

\begin{Code}

public String reverseWords(String s) {

String[] texts = s.split(" ");

StringBuilder sb = new StringBuilder();

for (String text : texts) {

if (text.length() > 0) {

sb.append(new StringBuilder(text).reverse().toString()).append(" ");

}

}

return sb.toString().trim();

}

\end{Code}

\section{Reverse Vowels of a String} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Write a function that takes a string as input and reverse only the vowels of a string.

\textbf{Example 1:}

Given s = \code{"hello"}, return \code{"holle"}.

\textbf{Example 2:}

Given s = \code{"leetcode"}, return \code{"leotcede"}.

\textbf{Note:}

The vowels does not include the letter \code{"y"}.

\subsubsection{Solution}

\begin{Code}

public String reverseVowels(String s) {

boolean[] flag = new boolean[256];

for (char c : "aeiouAEIOU".toCharArray()) {

flag[c] = true;

}

StringBuilder sb = new StringBuilder(s);

for (int i = 0, j = sb.length() - 1; i < j; ) {

if (!flag[sb.charAt(i)]) {

i++;

} else if (!flag[sb.charAt(j)]) {

j--;

} else {

char c = sb.charAt(i);

sb.setCharAt(i, sb.charAt(j));

sb.setCharAt(j, c);

i++;

j--;

}

}

return sb.toString();

}

\end{Code}

\section{Longest Substring Without Repeating Characters} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a string, find the length of the longest substring without repeating characters.

\textbf{Examples:}

Given \code{"abcabcbb"}, the answer is \code{"abc"}, which the length is 3.

Given \code{"bbbbb"}, the answer is \code{"b"}, with the length of 1.

Given \code{"pwwkew"}, the answer is \code{"wke"}, with the length of 3. Note that the answer must be a substring, \code{"pwke"} is a subsequence and not a substring.

\subsubsection{Solution}

\begin{Code}

// 耗时39ms，性能挺好

public int lengthOfLongestSubstring(String s) {

int[] count = new int[256];

int maxLen = 0;

for (int i = 0, j = 0; j < s.length(); ) {

if (count[s.charAt(j)] == 0) {

count[s.charAt(j)]++;

maxLen = Math.max(maxLen, j - i + 1);

j++;

} else {

--count[s.charAt(i++)];

}

}

return maxLen;

}

\end{Code}

\section{Longest Substring with At Most Two Distinct Characters} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = \code{“eceba”},

T is \code{"ece"} which its length is 3.

\subsubsection{Solution}

\begin{Code}

// 7ms

public int lengthOfLongestSubstringTwoDistinct2(String s) {

int[] count = new int[256];

int distinct = 0, longest = 0;

for (int i = 0, j = 0; j < s.length(); j++) {

if (count[s.charAt(j)]++ == 0) {

distinct++;

}

for ( ; i < j && distinct > 2; ) {

if (--count[s.charAt(i++)] == 0) {

--distinct;

}

}

longest = Math.max(longest, j - i + 1);

}

return longest;

}

\end{Code}

\section{Longest Substring with At Most K Distinct Characters} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = \code{“eceba”} and k = 2,

T is \code{"ece"} which its length is 3.

\subsubsection{Solution}

\begin{Code}

/**

* 思路跟Longest Substring With At Most Two Distinct Characters一样，只是给2改成k，

* 要注意k等于0时返回0

*/

// 耗时9ms

public int lengthOfLongestSubstringKDistinct(String s, int k) {

if (k == 0) {

return 0;

}

int[] count = new int[256];

int distinct = 0, longest = 0;

for (int i = 0, j = 0; j < s.length(); j++) {

if (count[s.charAt(j)]++ == 0) {

distinct++;

}

for ( ; i < j && distinct > k; ) {

if (--count[s.charAt(i++)] == 0) {

--distinct;

}

}

longest = Math.max(longest, j - i + 1);

}

return longest;

}

\end{Code}

\section{Minimum Window Substring} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,

S = \code{"ADOBECODEBANC"}

T = \code{"ABC"}

Minimum window is \code{"BANC"}.

\textbf{Note:}

If there is no such window in S that covers all characters in T, return the empty string \code{""}.

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

\subsubsection{Solution}

\begin{Code}

// 耗时8ms，时间复杂度O(n)

public String minWindow(String s, String t) {

int[] sc = new int[256], tc = new int[256];

for (char c : t.toCharArray()) {

tc[c]++;

}

int minStart = 0, minLen = Integer.MAX_VALUE;

for (int i = 0, j = 0, k = 0; j < s.length(); j++) {

char c = s.charAt(j);

if (++sc[c] <= tc[c]) {

++k;

}

if (k == t.length()) {

for (; i < j; i++) {

char cc = s.charAt(i);

if (tc[cc] == 0) {

continue;

}

if (sc[cc] <= tc[cc]) {

break;

}

sc[cc]--;

}

if (j - i + 1 < minLen) {

minLen = j - i + 1;

minStart = i;

}

}

}

return minLen != Integer.MAX_VALUE ? s.substring(minStart, minStart + minLen) : "";

}

\end{Code}

\section{Sliding Window Maximum} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,

Given nums = \code{[1,3,-1,-3,5,3,6,7]}, and k = 3.

\begin{Code}

Window position Max

--------------- -----

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

\end{Code}

Therefore, return the max sliding window as \code{[3,3,5,5,6,7]}.

\textbf{Note:}

You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.

\textbf{Follow up:}

Could you solve it in linear time?

\subsubsection{Solution I}

\begin{Code}

// 注意PriorityQueue的remove复杂度是O(k)，所以本题复杂度是O(n*k)

// 可以将PriorityQueue转成TreeMap，复杂度为O(n*lgk), 耗时58ms

public int[] maxSlidingWindow(int[] nums, int k) {

if (nums.length == 0) {

return new int[0];

}

Queue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {

@Override

public int compare(Integer i1, Integer i2) {

return i2 - i1;

}

});

for (int i = 0; i < k; i++) {

queue.offer(nums[i]);

}

int[] result = new int[nums.length - k + 1];

result[0] = queue.peek();

for (int i = 1; i < result.length; i++) {

queue.remove(nums[i - 1]);

queue.offer(nums[i + k - 1]);

result[i] = queue.peek();

}

return result;

}

\end{Code}

\subsubsection{Solution II}

\begin{Code}

// 耗时23ms

// queue中存的是索引

public int[] maxSlidingWindow2(int[] nums, int k) {

if (nums.length == 0) {

return new int[0];

}

Deque<Integer> queue = new LinkedList<Integer>();

int[] result = new int[nums.length - k + 1];

for (int i = 0; i < nums.length; i++) {

if (!queue.isEmpty() && queue.peek() <= i - k) {

queue.removeFirst();

}

while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {

queue.pollLast();

}

queue.offerLast(i);

if (i >= k - 1) {

result[i - k + 1] = nums[queue.peek()];

}

}

return result;

}

\end{Code}

\section{Sliding Window Median} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

\textbf{Examples:}

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example,

Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

\begin{Code}

Window position Median

--------------- -----

[1 3 -1] -3 5 3 6 7 1

1 [3 -1 -3] 5 3 6 7 -1

1 3 [-1 -3 5] 3 6 7 -1

1 3 -1 [-3 5 3] 6 7 3

1 3 -1 -3 [5 3 6] 7 5

1 3 -1 -3 5 [3 6 7] 6

\end{Code}

Therefore, return the median sliding window as \code{[1,-1,-1,3,5,6]}.

\textbf{Note:}

You may assume k is always valid, ie: k is always smaller than input array's size for non-empty array.

\subsubsection{Solution}

\begin{Code}

public double[] medianSlidingWindow(int[] nums, int k) {

double[] res = new double[nums.length - k + 1];

TreeMap<Integer, Integer> minHeap = new TreeMap<Integer, Integer>();

TreeMap<Integer, Integer> maxHeap = new TreeMap<Integer, Integer>(Collections.reverseOrder());

int minHeapCap = k / 2; //smaller heap when k is odd.

int maxHeapCap = k - minHeapCap;

for (int i = 0; i < k; i++) {

maxHeap.put(nums[i], maxHeap.getOrDefault(nums[i], 0) + 1);

}

int[] minHeapSize = new int[]{0};

int[] maxHeapSize = new int[]{k};

for (int i = 0; i < minHeapCap; i++) {

move1Over(maxHeap, minHeap, maxHeapSize, minHeapSize);

}

res[0] = getMedian(maxHeap, minHeap, maxHeapSize, minHeapSize);

int resIdx = 1;

for (int i = 0; i < nums.length - k; i++) {

int addee = nums[i + k];

if (addee <= maxHeap.keySet().iterator().next()) {

add(addee, maxHeap, maxHeapSize);

} else {

add(addee, minHeap, minHeapSize);

}

int removee = nums[i];

if (removee <= maxHeap.keySet().iterator().next()) {

remove(removee, maxHeap, maxHeapSize);

} else {

remove(removee, minHeap, minHeapSize);

}

//rebalance

if (minHeapSize[0] > minHeapCap) {

move1Over(minHeap, maxHeap, minHeapSize, maxHeapSize);

} else if (minHeapSize[0] < minHeapCap) {

move1Over(maxHeap, minHeap, maxHeapSize, minHeapSize);

}

res[resIdx] = getMedian(maxHeap, minHeap, maxHeapSize, minHeapSize);

resIdx++;

}

return res;

}

public double getMedian(TreeMap<Integer, Integer> bigHeap, TreeMap<Integer, Integer> smallHeap, int[] bigHeapSize, int[] smallHeapSize) {

return bigHeapSize[0] > smallHeapSize[0] ? (double) bigHeap.keySet().iterator().next() : ((double) bigHeap.keySet().iterator().next() + (double) smallHeap.keySet().iterator().next()) / 2.0;

}

//move the top element of heap1 to heap2

public void move1Over(TreeMap<Integer, Integer> heap1, TreeMap<Integer, Integer> heap2, int[] heap1Size, int[] heap2Size) {

int peek = heap1.keySet().iterator().next();

add(peek, heap2, heap2Size);

remove(peek, heap1, heap1Size);

}

public void add(int val, TreeMap<Integer, Integer> heap, int[] heapSize) {

heap.put(val, heap.getOrDefault(val, 0) + 1);

heapSize[0]++;

}

public void remove(int val, TreeMap<Integer, Integer> heap, int[] heapSize) {

if (heap.put(val, heap.get(val) - 1) == 1) heap.remove(val);

heapSize[0]--;

}

\end{Code}

\section{Longest Palindromic Substring} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

\textbf{Example:}

\textbf{Input:} \code{"babad"}

\textbf{Output:} \code{"bab"}

\textbf{Note:} \code{"aba"} is also a valid answer.

\textbf{Example:}

\textbf{Input:} \code{"cbbd"}

\textbf{Output:} \code{"bb"}

\subsubsection{Solution I}

\begin{Code}

private int begin, maxLen;

// 耗时14ms，平均复杂度O(n)

public String longestPalindrome(String s) {

for (int i = 0; i < s.length(); i++) {

helper(s, i, i);

helper(s, i, i + 1);

}

return s.substring(begin, begin + maxLen);

}

private void helper(String s, int i, int j) {

for (; i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j); i--, j++) ;

int len = j - i - 1;

if (len > maxLen) {

maxLen = len;

begin = i + 1;

}

}

\end{Code}

\subsubsection{Solution II}

\begin{Code}

// 动态规划，耗时73ms，复杂度O(n^2)

public String longestPalindrome2(String s) {

int len = s.length();

if (len == 0) {

return s;

}

boolean[][] f = new boolean[len][len];

int index = 0;

int max = 1;

for (int i = 0; i < len; i++) {

for (int j = 0; j <= i; j++) {

if (s.charAt(j) == s.charAt(i) && (i - j < 2 || f[j + 1][i - 1])) {

f[j][i] = true;

if (i - j + 1 > max) {

max = i - j + 1;

index = j;

}

}

}

}

return s.substring(index, index + max);

}

\end{Code}

\section{Shortest Palindrome} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given \code{"aacecaaa"}, return \code{"aaacecaaa"}.

Given \code{"abcd"}, return \code{"dcbabcd"}.

\subsubsection{Solution}

\begin{Code}

/**

* 其实只要将s与s的逆序串拼接在一起，求最长公共子串，逆序串中刨除这个最长公共子串，

* 就是要加到s前面的

*/

public String shortestPalindrome(String s) {

StringBuilder builder = new StringBuilder(s);

return builder.reverse().substring(0, s.length() - getCommonLength(s)) + s;

}

private int getCommonLength(String str) {

StringBuilder builder = new StringBuilder(str);

String rev = new StringBuilder(str).reverse().toString();

builder.append("#").append(rev);

int[] p = new int[builder.length()];

for (int i = 1; i < p.length; i++) {

int j = p[i - 1];

while (j > 0 && builder.charAt(i) != builder.charAt(j)) j = p[j - 1];

p[i] = j == 0 ? (builder.charAt(i) == builder.charAt(0) ? 1 : 0) : j + 1;

}

return p[p.length - 1];

}

/**

* 更直观的写法

*/

private int getCommonLength2(String str) {

String rev = new StringBuilder(str).reverse().toString();

return getCommonLength(str + rev, str.length());

}

private int getCommonLength(String s, int max) {

for (int i = s.length() - max; i < s.length(); i++) {

if (s.startsWith(s.substring(i))) {

return s.length() - i;

}

}

return 0;

}

\end{Code}

\section{Count and Say} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

The count-and-say sequence is the sequence of integers with the first five terms as following:

\begin{Code}

1. 1

2. 11

3. 21

4. 1211

5. 111221

\end{Code}

1 is read off as \code{"one 1"} or 11.

11 is read off as \code{"two 1s"} or 21.

21 is read off as \code{"one 2, then one 1"} or 1211.

Given an integer n, generate the nth term of the count-and-say sequence.

\textbf{Note:} Each term of the sequence of integers will be represented as a string.

\subsubsection{Solution}

\begin{Code}

public String countAndSay(int n) {

String s = "1";

for (int i = 2; i <= n; i++) {

s = next(s);

}

return s;

}

private String next(String s) {

StringBuilder sb = new StringBuilder();

char cur = 0;

int times = 0;

for (int i = 0; i < s.length(); i++) {

if (times == 0) {

cur = s.charAt(i);

times = 1;

} else if (s.charAt(i) == cur) {

times++;

} else {

sb.append(String.format("%d%c", times, cur));

cur = s.charAt(i);

times = 1;

}

}

// 这一句千万别掉了

if (times != 0) {

sb.append(String.format("%d%c", times, cur));

}

return sb.toString();

}

\end{Code}

\section{Valid Parentheses} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given a string containing just the characters \code{'(', ')', '{', '}', '[' and ']'}, determine if the input string is valid.

The brackets must close in the correct order, \code{"()"} and \code{"()[]{}"} are all valid but \code{"(]"} and \code{"([)]"} are not.

\subsubsection{Solution}

\begin{Code}

// 耗时5ms

public boolean isValid(String s) {

char[] stack = new char[s.length()];

int top = -1;

for (char c : s.toCharArray()) {

switch (c) {

case ')':

if (top >= 0 && stack[top] == '(') {

top--;

} else {

return false;

}

break;

case '}':

if (top >= 0 && stack[top] == '{') {

top--;

} else {

return false;

}

break;

case ']':

if (top >= 0 && stack[top] == '[') {

top--;

} else {

return false;

}

break;

default:

stack[++top] = c;

break;

}

}

return top < 0;

}

\end{Code}

\section{Group Anagrams} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given an array of strings, group anagrams together.

For example, given: \code{["eat", "tea", "tan", "ate", "nat", "bat"]},

Return:

\begin{Code}

[

["ate", "eat","tea"],

["nat","tan"],

["bat"]

]

\end{Code}

\textbf{Note:} All inputs will be in lower-case.

\subsubsection{Solution}

\begin{Code}

public List<List<String>> groupAnagrams(String[] strs) {

HashMap<String, List<String>> map = new HashMap<>();

for (String s : strs) {

char[] cc = s.toCharArray();

Arrays.sort(cc);

String t = new String(cc);

List<String> list = map.get(t);

if (list == null) {

list = new LinkedList<>();

map.put(t, list);

}

list.add(s);

}

return new LinkedList<>(map.values());

}

\end{Code}

\section{Add Binary} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Given two binary strings, return their sum (also a binary string).

For example,

a = \code{"11"}

b = \code{"1"}

Return \code{"100"}.

\subsubsection{Solution}

\begin{Code}

public String addBinary(String a, String b) {

StringBuilder sb = new StringBuilder();

int i = a.length() - 1, j = b.length() - 1, k = 0;

for ( ; i >= 0 || j >= 0 || k > 0; i--, j--) {

int i0 = i >= 0 ? a.charAt(i) - '0' : 0;

int j0 = j >= 0 ? b.charAt(j) - '0' : 0;

int s = i0 + j0 + k;

sb.insert(0, s & 1);

k = s >> 1;

}

return sb.toString();

}

\end{Code}

\section{String to Integer (atoi)} %%%%%%%%%%%%%%%%%%%%%%



\subsubsection{Description}

Implement atoi to convert a string to an integer.

\textbf{Hint:} Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

\textbf{Notes:} It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

\subsubsection{Analysis}

1. 过滤掉前面的空格

2. 考虑正负号

3. 如果溢出则返回上限或下限

4. 解析时遇到非法字符则停止，返回当前结果

5，防御空串

\subsubsection{Solution}

\begin{Code}

public int myAtoi(String str) {

long n = 0, sign = 1;

str = str.trim();

// 这里要防御空串

if (str.length() == 0) { return 0; }

switch (str.charAt(0)) {

case '-':

sign = -1;

case '+':

str = str.substring(1);

break;

}