1 public class Solution { 2 /** 3 * @param str: A string 4 * @return An integer 5 */ 6 public int atoi(String str) { 7 if (str == null || str.length() == 0) { 8 return 0; 9 } 10 int index = 0; 11 int sign = 1; 12 int sum = 0; 13 // remove the previous space 14 while (index < str.length() && str.charAt(index) == ' ') { 15 index++; 16 } 17 //if the input string has more than one sign, then the input is invalid. 18 //judge the sign 19 if (index < str.length() && str.charAt(index) == '+' || str.charAt(index) == '-') { 20 sign = str.charAt(index) == '+' ? 1 : -1; 21 index++; 22 } 23 //judge the number 24 while (index < str.length() && str.charAt(index) >= '0' && str.charAt(index) <= '9' && str.charAt(index) != '.'){ 25 int num = str.charAt(index) - '0'; 26 if (sum > Integer.MAX_VALUE / 10 || (sum == Integer.MAX_VALUE / 10 && num > Integer.MAX_VALUE % 10)) { 27 return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE; 28 } 29 sum = sum * 10 + num; 30 index++; 31 } 32 return sum * sign; 33 } 34 }
(42)Binary Tree Level Order Traversal
1 /** 2 * Definition of TreeNode: 3 * public class TreeNode { 4 * public int val; 5 * public TreeNode left, right; 6 * public TreeNode(int val) { 7 * this.val = val; 8 * this.left = this.right = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 /** 14 * @param root: The root of binary tree. 15 * @return: Level order a list of lists of integer 16 */ 17 public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) { 18 //1.边界判断 19 ArrayList<ArrayList<Integer>> arrList = new ArrayList<>(); 20 if (root == null) { 21 return arrList; 22 } 23 //2.Queue是个接口，能通过LinkedList实现不能通过ArrayList实现 24 Queue<TreeNode> queue = new LinkedList<TreeNode>(); 25 queue.offer(root); 26 //3.循环体 27 while (!queue.isEmpty()) { 28 ArrayList<Integer> level = new ArrayList<>(); 29 int qSize = queue.size(); //注意，不能直接写入for循环 i < queue.size()，否则会因为后期的offer操作改变 30 for (int i = 0; i < qSize; i++) { 31 TreeNode head = queue.poll(); //poll()获取头部，并从队列中移除头部 32 level.add(head.val); 33 if (head.left != null) { 34 queue.offer(head.left); 35 } 36 if (head.right != null) { 37 queue.offer(head.right); 38 } 39 } 40 arrList.add(level); 41 } 42 return arrList; 43 } 44 }
(43)Remove Duplicates from Sorted List
1 /** 2 * Definition for ListNode 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { 7 * val = x; 8 * next = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 /** 14 * @param ListNode head is the head of the linked list 15 * @return: ListNode head of linked list 16 */ 17 public static ListNode deleteDuplicates(ListNode head) { 18 if (head == null) { 19 return head; 20 } 21 ListNode cur = head; 22 while (cur.next != null) { 23 if (cur.val == cur.next.val) { 24 cur.next = cur.next.next; 25 } else { 26 cur = cur.next; 27 } 28 } 29 return head; 30 } 31 }
1 /** 2 * Definition of TreeNode: 3 * public class TreeNode { 4 * public int val; 5 * public TreeNode left, right; 6 * public TreeNode(int val) { 7 * this.val = val; 8 * this.left = this.right = null; 9 * } 10 * } 11 */ 12 class Solution { 13 /** 14 * This method will be invoked first, you should design your own algorithm 15 * to serialize a binary tree which denote by a root node to a string which 16 * can be easily deserialized by your own "deserialize" method later. 17 */ 18 public String serialize(TreeNode root) { 19 StringBuilder sb = new StringBuilder(); 20 buildString(root, sb); 21 return sb.toString(); 22 } 23 private void buildString(TreeNode root, StringBuilder sb) { 24 if (root == null) { 25 sb.append("$,"); 26 } else { 27 sb.append(root.val).append(","); 28 buildString(root.left, sb); 29 buildString(root.right, sb); 30 } 31 } 32 /** 33 * This method will be invoked second, the argument data is what exactly 34 * you serialized at method "serialize", that means the data is not given by 35 * system, it's given by your own serialize method. So the format of data is 36 * designed by yourself, and deserialize it here as you serialize it in 37 * "serialize" method. 38 */ 39 public TreeNode deserialize(String data) { 40 Deque<String> nodes = new LinkedList<>(); 41 nodes.addAll(Arrays.asList(data.split(","))); 42 return buildTree(nodes); 43 } 44 private TreeNode buildTree(Deque<String> nodes) { 45 // we need the deque class to get the method of remove(); 46 String val = nodes.remove(); 47 if (val.equals("$")) { 48 return null; 49 } else { 50 TreeNode root = new TreeNode(Integer.valueOf(val)); 51 root.left = buildTree(nodes); 52 root.right = buildTree(nodes); 53 return root; 54 } 55 } 56 }
(45)Binary Tree Zigzag Level Order Traversal
1 /** 2 * Definition of TreeNode: 3 * public class TreeNode { 4 * public int val; 5 * public TreeNode left, right; 6 * public TreeNode(int val) { 7 * this.val = val; 8 * this.left = this.right = null; 9 * } 10 * } 11 */ 12 13 14 public class Solution { 15 /** 16 * @param root: The root of binary tree. 17 * @return: A list of lists of integer include 18 * the zigzag level order traversal of its nodes' values 19 */ 20 public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { 21 ArrayList<ArrayList<Integer>> result = new ArrayList<>(); 22 if (root == null) { 23 return result; 24 } 25 Stack<TreeNode> curLevel = new Stack<>(); 26 Stack<TreeNode> nextLevel = new Stack<>(); 27 Stack<TreeNode> temp = new Stack<>(); 28 29 curLevel.push(root); 30 boolean oddOrEven = true; 31 32 while (!curLevel.isEmpty()) { 33 ArrayList<Integer> curResult = new ArrayList<>(); 34 while (!curLevel.isEmpty()) { 35 TreeNode node = curLevel.pop(); 36 curResult.add(node.val); 37 if (oddOrEven) { 38 if (node.left != null) { 39 nextLevel.push(node.left); 40 } 41 if (node.right != null) { 42 nextLevel.push(node.right); 43 } 44 } else { 45 if (node.right != null) { 46 nextLevel.push(node.right); 47 } 48 if (node.left != null) { 49 nextLevel.push(node.left); 50 } 51 } 52 } 53 temp = curLevel; 54 curLevel = nextLevel; 55 nextLevel = temp; 56 oddOrEven = !oddOrEven; 57 result.add(curResult); 58 } 59 return result; 60 } 61 }
(46)Product of Array Exclude Itself
1 public class Solution { 2 /** 3 * @param A: Given an integers array A 4 * @return: A Long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1] 5 */ 6 public ArrayList<Long> productExcludeItself(ArrayList<Integer> a) { 7 ArrayList<Long> arrList = new ArrayList<>(); 8 if (a == null || a.size() == 0) { 9 return arrList; 10 } 11 int len = a.size(); 12 long[] array = new long[len]; 13 long[] array1 = new long[len]; 14 for (int i = 0; i < len; i++) { 15 array[i] = a.get(i); 16 } 17 array1 = multiply(array, array1); 18 for (int i = 0; i < len; i++) { 19 arrList.add(array1[i]); 20 } 21 return arrList; 22 } 23 public long[] multiply(long[] array, long[] array1) { 24 //divid two parts to multiply 25 int len = array.length; 26 array1[0] = 1; 27 for (int i = 1; i < len; i++) { 28 array1[i] = array1[i - 1] * array[i - 1]; 29 } 30 long temp = 1; 31 for (int i = len - 2; i >= 0; i--) { 32 temp = temp * array[i + 1]; 33 array1[i] = array1[i] * temp; 34 } 35 return array1; 36 } 37 }