joyonline

joyonline
5个月前
class Solution {
public int treeDepth(TreeNode root) {
if(root == null){
return 0;
}
LinkedList<TreeNode> list = new LinkedList();
list.add(root);
int count = 0;
while(root != null && !list.isEmpty()){
int len = list.size();
count++;
while(len > 0){
TreeNode tmp = list.pop();
if(tmp.left != null) {
list.add(tmp.left);
root = tmp.left;
}
if(tmp.right != null){
list.add(tmp.right);
root = tmp.right;
}
len--;
}
}
return count;
}

}


joyonline
5个月前

递归。满足条件跳出递归

class Solution {
public TreeNode kthNode(TreeNode root, int k) {
Solution s = new Solution();
List<TreeNode> list = new ArrayList();
return s.zx(root,k,list).get(k-1);
}

public List<TreeNode> zx(TreeNode root,int k,List<TreeNode> list){
if(root.left != null){
zx(root.left,k,list);
}
if(root != null){
list.add(root);
if(list.size() == k) {
new RuntimeException();
}
}
if(root.right != null){
zx(root.right,k,list);
}
return list;
}

}


非递归中序

class Solution {
public TreeNode kthNode(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack();
stack.push(root);
int count = 0;
while(root!=null || !stack.isEmpty()){
while(root!=null){
stack.push(root);
root = root.left;
}
if(!stack.isEmpty()){
TreeNode t = stack.pop();//弹出根节点
count++;
if(count == k){
return t;
}
root = t.right;
}

}
return root;
}
}


joyonline
5个月前

go代码

func getMissingNumber(nums []int) int {

if len(nums) == 0 || len(nums) == 1 ||
nums[len(nums) - 1] == len(nums) - 1{
return len(nums)
}
if nums[0] !=0 {
return 0
}
start,end :=0,len(nums)-1
for ;end - start > 1 ; {
mid := (start + end) >> 1
if nums[mid] <= mid {
start = mid
}else {
end = mid
}

}
return nums[end]-1

}


joyonline
5个月前

java 代码

class Solution {
public ListNode findFirstCommonNode(ListNode headA, ListNode headB) {
Stack<ListNode> a = new Stack();
Stack<ListNode> b = new Stack();
while(headA!=null || headB!=null){
if(headA!=null) {
a.push(headA);
headA = headA.next;
}
if(headB!=null){
b.push(headB);
headB = headB.next;
}
}
ListNode tmp = null;
while(!a.isEmpty() && !b.isEmpty()){
ListNode f = a.pop();
ListNode s = b.pop();
if(f==s){
tmp = f;
}else{
break;
}
}
return tmp;
}
}


a+c+b b+c+a

class Solution {
public ListNode findFirstCommonNode(ListNode headA, ListNode headB) {
ListNode p = headA;
ListNode q = headB;
while(p != q){
if(p!=null) p = p.next;
else p = headB;
if(q!=null) q = q.next;
else q = headA;
}
return p;
}
}


joyonline
5个月前

java 代码

class Solution {
public char firstNotRepeatingChar(String s) {
int len = s.length();
if(len == 0) return '#';
int[] array = new int[126 - 32];//采用数组来存放位置。如果已存放，则职位-1
for(int i=0;i<array.length;i++)
array[i] = -1;
for (int i = 0; i < len; i++) {
int index = s.charAt(i) - 32;
if (array[index] == -1) {
array[index] = i;
}else{
array[index] = -1;
}
}
int min = array.length;
for (int i = 0; i < array.length; i++) {
if(array[i] !=-1) {
if(array[i] < min) min = array[i];
}
}
;
return min==array.length?'#':s.charAt(min);
}
}


joyonline
5个月前

java 代码

class Solution {
public int longestSubstringWithoutDuplication(String s) {
int len = s.length();
if(len == 0 || len == 1) return len;
//定义一个数组，长度位26。用于存储a-z最后一次出现的位置
int[] array = new int[]{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
int frist = 0;
int second = 1;
int max = 1;
while(frist < len){
int fristchar = s.charAt(frist)-97;
array[fristchar] = frist;
while(second < len){
int secondchar = s.charAt(second)-97;
if(array[secondchar] != -1){
frist = frist<=array[secondchar]? array[secondchar]+ 1:frist;
}
array[secondchar] = second;
if((second-frist + 1) > max) max = second-frist + 1;
second++;
}
frist++;
}
return max;
}

}


joyonline
5个月前

java 代码

class Solution {
public int maxSubArray(int[] nums) {
int sum = 0;
int max = nums[0];
for (int i = 0; i < nums.length; i++) {
if ((nums[i] + sum) > nums[i]) { //判断前面的值+当前位置值 后的大小
sum = nums[i] + sum;//如果比当前位置大，则前面的留着
} else {
sum =nums[i];//否则舍弃前面的
}
if(sum>max) max = sum;
}
return max;
}
}


joyonline
5个月前

java 代码

class Solution {
public List<Integer> printFromTopToBottom(TreeNode root) {
List<Integer> result = new ArrayList();
if(root==null){
return result;
}
LinkedList<TreeNode> list = new LinkedList();//先进先出
list.add(root);
while(list.size()>0){
TreeNode tmp = list.get(0);
result.add(tmp.val);
if(tmp.left !=null) list.add(tmp.left);
if(tmp.right !=null) list.add(tmp.right);
list.pop();
}
return result;
}

}


joyonline
5个月前

java 代码

class MinStack {

public Stack<Integer> a;
public Stack<Integer> c;

/** initialize your data structure here. */
public MinStack() {
a = new Stack();
c = new Stack();
}

public void push(int x) {
a.push(x);
if(c.isEmpty()){
c.push(x);
return;
}
c.push(Math.min(x,c.peek()));
}

//删除第一个元素
public void pop() {
int x = a.pop();
while(!c.isEmpty() && x == c.peek()){
c.pop();
}

}

//返回第一个元素
public int top() {
return  a.peek();
}

public int getMin() {
return c.peek();
}

}


joyonline
5个月前

java代码

class Solution {
public boolean isPopOrder(int [] pushV,int [] popV) {
int pul = pushV.length;
int pol = popV.length;
if(pul != pol) return false;
if(pul == 0 && pol == 0) return true;
Stack stack = new Stack();
int k = 0;
int flag = 0;
while(k < pul){
if(pushV[k] == popV[flag]){
k++;
flag++;
}else{
if(stack.isEmpty() || !stack.peek().equals(popV[flag])){
stack.push(pushV[k]);
k++;
}else{
stack.pop();
flag++;
}
}

}
if(stack.isEmpty()){
return true;
}
// for(int i=flag;i<pol;i++){
//     // System.out.print(popV[i]);
//     System.out.print(stack.pop());
// }
while(flag < pol){
if(!stack.pop().equals(popV[flag])){
return false;
}
flag++;
}
return true;
}
}