songlj的博客
songlj · 共 27 篇文章
Binary Tree Postorder Traversal
题目描述:Given a binary tree, return the postorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3} , 1 \ 2 / 3 return [3,2,1] . Note: Recursive solution is trivial, could you do it iteratively? 解题思路:采用左右根的形式后续遍历二叉树 Java代码实现: /** * Definition for a binary tree node. * public …
2015-09-08 12:59 · 评论(0)
Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3} , 1 \ 2 / 3 return [1,2,3] . Note: Recursive solution is trivial, could you do it iteratively? 解题思路:根左右的形式前序遍历,遍历的元素加入list,左分支遍历结束,继续右分支。 java实现: /** * Definition for a binary tree n…
2015-09-08 12:55 · 评论(0)
Basic Calculator
题目描述:Implement a basic calculator to evaluate a simple expression string. The expression string may contain open ( and closing parentheses ) , the plus + or minus sign - , non-negative integers and empty spaces . You may assume that the given expression is always valid. Some examples: "1 + 1" = …
2015-09-08 12:50 · 评论(0)
Implement Stack using Queues
题目描述:Implement the following operations of a stack using queues. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. empty() -- Return whether the stack is empty. Notes: You must use only standard operations of a queue -- which me…
2015-09-08 12:42 · 评论(0)
Reverse Bits
**解题思路:**该题与上题类似,如果是负数首先转化成正数(+ 2147483647+1),再处理,然后变成2进制数(如果是负数最高位是1),翻转2进制数,变成十进制数,翻转后如果最后位是1,在十进制数基础上加上2147483647+1。 Java代码实现: public class Solution { // you need treat n as an unsigned value public int reverseBits(int n) { String str=""; if(n==0) return 0; if(n==-2147483648) return 1; System…
2015-09-08 11:18 · 评论(0)
Number of 1 Bits
**解题思路:**32位有符号整数的表示范围:-2147483648—2147483647。32位无符号整数的表示范围:0—2147483647+2147483648。如果输入的无符号数大于2147483647,则会显示成负数,所以当输入数字小于0时,只需加上2147483647+1,之后按照整数求1的个数,此时需要将1的个数加1. Java代码实现: public class Solution { // you need to treat n as an unsigned value public int hammingWeight(int n) { int count=0; if(n==…
2015-09-08 11:16 · 评论(0)
Invert Binary Tree
**解题思路:**利用中序遍历的方式,依次交换所遍历节点的左右子树。 Java 代码实现: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode invertTree(TreeNode root) { if(root==null) return root; Stack …
2015-09-08 11:13 · 评论(0)
Kth Smallest Element in a BST
**解题思路:**按树的中序遍历的方式,利用栈实现,第k个出栈的节点即是所求的。 Java 代码实现: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int kthSmallest(TreeNode root, int k) { TreeNode p=new TreeNode(0…
2015-09-08 11:10 · 评论(0)
Power of Two
**解题思路:**如果一个数是否是2的次方,即如果其对应的二进制数1的个数如果超过1,不是的2的次方,反之才是。 Java代码实现: public class Solution { public boolean isPowerOfTwo(int n) { int count=0; if(n==1) return true; if(n<=0) return false; while(n>0){ int mod=n%2; if(mod==1) count++; if(count>1) return false; n=n/2; } return true; } } 原题题目: https://le…
2015-09-08 11:07 · 评论(0)
Implement Queue using Stacks
**解题思路:**采用两个栈,实现队列,一个用于进栈S1,一个用于出栈和取头元素S2。进栈时必须将S2中元素全部加入S1中,出栈时必须将S1中的元素加入S2中,才可以保证先进先出。判断为空时,S1,S2均为空。 Java代码实现: class MyQueue { private Stack stack1; private Stack stack2; MyQueue(){ stack1=new Stack(); stack2=new Stack(); } // Push element x to the back of queue. public void push(int x) { if(s…
2015-09-08 11:05 · 评论(0)
Number of Digit One
**解题思路:**0-9中1的个数为1个,而X99..9的1的个数可以通过公式计算:即Math.pow(10, digit-1)+(10-(9-highestDigit))*Math.pow(10,digit-2)*(digit-1);比如8999:10^3+9*10^2*3。由此可以将输入数字分解,比如9548=9000+548=9000+500+48=9000+500+40+8,如此分布计算即可 Java代码: public class Solution { public int countDigitOne(int n) { int count=0; while(n>0){ if(n/1…
2015-09-08 11:02 · 评论(0)
Delete Node in a Linked List
**解题思路:**指定删除任一节点,因无头节点指针,实际删除节点即是删除节点的值,所以可以将要删除节点和后继节点的值替换,删除后继节点即可。 Java代码实现: /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ void deleteNode(struct ListNode* node) { struct ListNode *p,*q; p=q=node; q=p->next; p->val=q->val; p->next=q->ne…
2015-09-08 10:58 · 评论(0)
Valid Anagram
**解题思路:**该题意思即是两个字符串是否具有相同的字符组成的串,首先记录第一个字符串出现的字符及其个数,然后与第二个字符串想比较。(另一个思路:将两个字符串分别排序,不过耗时。) Java****代码实现 : public class Solution { public boolean isAnagram(String s, String t) { if(s.length()!=t.length()) return false; Map<String,Integer> map =new HashMap<String,Integer>(); for(int i=0;i<s.length()…
2015-09-08 10:54 · 评论(0)
Add Digits
**解题思路:**传统方法,按位相加,循环,直至只有一位为止。 Java代码实现: public class Solution { public int addDigits(int num) { int sum=0; //System.out.println(num); while(num/10>0){ String strNum=String.valueOf(num); //System.out.println(strNum.length()); for(int i=0;i<strNum.length();i++){ sum+=Integer.valueOf(strNum.charAt(i…
2015-09-08 10:51 · 评论(0)
Single Number III
**解题思路:**该题利用一个集合存储遍历的数字,如何初始该集合中没有则加入,有的话则删除,最后集合里面的数字,即是所要求的。 Java****代码实现 : public class Solution { public int[] singleNumber(int[] nums) { Set set=new HashSet(); for(int i=0;i<nums.length;i++){ if(!set.contains(nums[i])) set.add(nums[i]); else set.remove(nums[i]); } int [] re=new int[set.size()…
2015-09-08 10:45 · 评论(0)