CodeTop100 Day20

58、翻转字符串中的数字

class Solution {public String reverseWords(String s) {s = s.trim();                                   int j = s.length() - 1, i = j;StringBuilder res = new StringBuilder();while (i >= 0) {while (i >= 0 && s.charAt(i) != ' ') i--;     res.append(s.substring(i + 1, j + 1) + " "); while (i >= 0 && s.charAt(i) == ' ') i--;     j = i;                                      }return res.toString().trim();                    }
}

尽量避免用库函数，这里采用双指针做法，先去掉头尾部空格，左指针从最右边向左移动，然后将i,j+1加入字符串，然后移动i指针到下一个单词，j指针跟随i进入下一轮循环，最后减去最后个空格输出即可

59、最小栈

class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;public MinStack() {stack=new Stack<>();minStack=new Stack<>();}public void push(int val) {stack.push(val);if(minStack.isEmpty()||val<=minStack.peek()){minStack.push(val);}}public void pop() {if(stack.pop().equals(minStack.peek())){minStack.pop();}}public int top() {return stack.peek();}public int getMin() {//每次进栈时候额外增加个当前位置最小值//返回top.min就行了return minStack.peek();}
}

当然这里可以用数组代替，空间可以更小

具体思路就是维护一个最小栈存放当前最小值

60、求根结点到叶子节点之和

class Solution {public int ans = 0;public int sumNumbers(TreeNode root) {dfs(root,0);return ans;}public void dfs(TreeNode r,int val) {if (r == null) {// ans += val;return ;}val = val * 10 + r.val;if (r.left == null && r.right == null) {ans += val;return;}if (r.left != null ) dfs(r.left,val);if (r.right != null) dfs(r.right,val);}
}

模拟题，遍历一下路径，将结果放入ans，val值是当前节点的上一层，递归还是很清晰的