首页 > 代码库 > leetCode题解(1)
leetCode题解(1)
Single Number
public int singleNumber(int[] A) {
int result = 0;
for(int i = 0;i < A.length;i++){
result = result^ A[i];
}
return result;
}利用异或的性质：a^b = b^a;
a^0 = a;
a^a = 0;
Maximum Depth of Binary Tree
求树的最大深度，递归求解，很简单public int max(int x,int y){
return x>y?x:y;
}
public int maxDepth(TreeNode root) {
if(root!=null)
return 1+max(maxDepth(root.left),maxDepth(root.right));
else
return 0;
}
Same Tree
判断两颗树是否相同，递归求解
public int max(int x,int y){
return x>y?x:y;
}
public int maxDepth(TreeNode root) {
if(root!=null)
return 1+max(maxDepth(root.left),maxDepth(root.right));
else
return 0;
}public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null&&q == null)
return true;
else if(p!=null&&q!=null){
if(p.val!=q.val)
return false;
else
return (isSameTree(p.left,q.left)&&isSameTree(p.right,q.right));
}else
return false;
}Unique Binary Search Trees
输出n个节点的二叉树有几种不同形态 简单的动态规划
public int numTrees(int n) {
if (n <= 1)
return 1;
else {
n--;
int sum = 0;
for (int i = 0; i <= n; i++) {
sum += numTrees(i) * numTrees(n-i);
}
return sum;
}
}
Reverse Integer
反转整数
public int reverse(int x) {
long result = 0;
while (x != 0) {
int n = x % 10;
x /= 10;
result = result * 10 + n;
if(result >2147483647||result < -2147483648)
return 0;
}
return (int)result;
}
Linked List Cycle
判断一个链表是否有环，设置两个指针 一个一次移动一位，一个移动两位 如果有环，移动快的迟早会追上移动慢的
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null)
return false;
ListNode headSlow = head;
ListNode headFast = head;
while (headFast != null && headFast.next != null
&& headFast.next.next != null) {
headFast = headFast.next.next;
headSlow = headSlow.next;
if (headFast == headSlow)
return true;
}
return false;
}
Binary Tree Preorder Traversal
二叉树非递归前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> s = new Stack<TreeNode>();
List<Integer> l = new ArrayList<Integer>();
if(root!= null)
s.push(root);
while(!s.isEmpty()){
TreeNode t = s.pop();
int p = t.val;
l.add(p);
if(t.right!=null)
s.push(t.right);
if(t.left!= null)
s.push(t.left);
}
return l;
}Binary Tree Inorder Traversal
二叉树非递归中序遍历
public List<Integer> inorderTraversal(TreeNode p) {
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> l = new ArrayList<Integer>();
while (p != null || !stack.empty()) {
// 和递归一样的思路，很好想
if (p!= null) {
stack.push(p);
p = p.left;
} else {
p = stack.pop();
l.add(p.val);
p = p.right;
}
}
return l;
}Populating Next Right Pointers in Each Node
见图： 1
/ 2 3
/ \ / 4 5 6 7
1 -> NULL
/ 2 -> 3 -> NULL
/ \ / 4->5->6->7 -> NULL给其添加next指针，递归求解
private void connect1(TreeLinkNode root1, TreeLinkNode root2) {
if (root1 != null && root2 != null) {
root1.next = root2;
root2.next = null;
if (root1.left != null) {
root1.left.next = root1.right.next;
root1.right.next = root2.left;
root2.left.next = root2.right.next;
root2.right.next = null;
connect1(root1.left, root1.right);
connect1(root1.right, root2.left);
connect1(root2.left, root2.right);
}
}
}
public void connect(TreeLinkNode root) {
if (root != null) {
root.next = null;
connect1(root.left, root.right);
}
return;
}
Search Insert Position
给一个数组和一个值，找出该值的位置，不在的话返回应该插入的位置，简单的二分查找
找不到时 left为大于x的最小值，right为小于x的最大值，所以应该返回left的值
public int binarySearch(int[] a, int left, int right, int x) {
while (left <= right) {
int mid = (left + right) / 2;
if (a[mid] == x)
return mid;
else if(a[mid] > x)
right = mid - 1;
else
left = mid + 1;
}
return left;
}
Remove Duplicates from Sorted List
删除一个排好序的链表里重复的值 注意指针变化就行
public ListNode deleteDuplicates(ListNode head) {
if (head == null||head.next == null)
return head;
ListNode headA = head;
while(head!=null&&head.next!=null){
if(head.val == head.next.val)
head.next = head.next.next;
else
head = head.next;
}
return headA;
}Remove Duplicates from Sorted Array
删除一个排好序的数组里的重复的值
public int removeDuplicates(int[] A) {
int count = 0;
if (A.length != 0) {
int temp = A[0];
A[count++] = A[0];
for (int i = 1; i < A.length; i++) {
if (A[i] != temp) {
A[count++] = A[i];
temp = A[i];
}
}
}
return count;
}
Remove Element
删除数组里的某个元素
public int removeElement(int[] A, int elem) {
int count = 0;
for(int i = 0;i < A.length;i++){
if(A[i]!=elem){
A[count++] = A[i];
}
}
return count;
}
Plus One
大数加1
public int[] plusOne(int[] digits) {
int[] result = new int[digits.length + 1];
int k = 1;
for(int i = digits.length -1;i >= 0;i--){
digits[i] += k;
if(digits[i]==10){
digits[i] = 0;
k = 1;
if(i==0){
result[0] = 1;
for(int j = 0;j < digits.length;j++)
result[j+1] = digits[j];
digits = result;
}
}else
k = 0;
}
return digits;
}
Symmetric Tree
判断一棵树是否对称，递归求解
public boolean isEqure(TreeNode root1,TreeNode root2){
if(root1!=null &&root2!=null)
if(root1.val!=root2.val)
return false;
else{
return isEqure(root1.left,root2.right)&&isEqure(root1.right,root2.left);
}else if(root1==null&&root2==null)
return true;
else
return false;
}
public boolean isSymmetric(TreeNode root) {
if(root!=null)
return isEqure(root.left,root.right);
else
return true;
} Pascal‘s Triangle
For example, given numRows = 5,
Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]public List<List<Integer>> generate(int numRows) {
List<List<Integer>> a = new ArrayList<List<Integer>>();
for (int i = 0; i < numRows; i++) {
ArrayList<Integer> array = new ArrayList<Integer>();
if (i == 0)
array.add(1);
else {
List<Integer> temp = (ArrayList<Integer>) a.get(i - 1);
for (int j = 0; j <= temp.size(); j++) {
if (j == 0 || j == temp.size())
array.add(1);
else {
array.add(temp.get(j - 1) + temp.get(j));
}
}
}
a.add(array);
}
return a;
}Palindrome Number
判断一个数是否是回文数，不用额外空间
public boolean isPalindrome(int x) {
if( x < 0)
return false;
int n = 0;
int k = x;
int m = x;
while(k > 0 ){
n++;
k/=10;
}
for(int i = n;i >= 1;i--){
int e = (int) Math.pow(10,i-1);
int mBit = m % 10;
int xBit = x/e;
if(mBit!=xBit)
return false;
m/=10;
x%=e;
}
return true;
}
Intersection of Two Linked Lists
O(n)求两个链表的交集中的第一个指针 找出哪个多，然后移动到两个链表元素数量相同，在比较public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode head1 = headA;
ListNode head2 = headB;
if(headA == null || headB == null)
return null;
int count1 = 0;
int count2 = 0;
while (head1 != null) {
count1++;
head1 = head1.next;
}
while (head2 != null) {
count2++;
head2 = head2.next;
}
int count = Math.abs(count2 - count1);
for (int i = 1; i <= count; i++) {
if (count2 >= count1)
headB = headB.next;
else
headA = headA.next;
}
while (headA != null && headB != null) {
if (headA == headB)
return headA;
headA = headA.next;
headB = headB.next;
}
return null;
}
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
Count and Say
题意是 先给一个1 读作一个1 即11
接着读作两个1 即21
在接着读一个2一个1 即1211
返回第n个
public String countAndSay(int n) {
String s = "11";
if (n == 1)
return "1";
n-=2;
StringBuffer sb = new StringBuffer();
while (n-- != 0) {
int count = 1;
for (int i = 0; i < s.length() - 1; i++) {
if (s.charAt(i) != s.charAt(i + 1)) {
sb.append(count + ""+s.charAt(i));
count = 1;
} else {
count++;
}
if (i + 1 == s.length() - 1)
sb.append(count +""+ s.charAt(i+1));
}
s = new String(sb);
sb = new StringBuffer();
}
return s;
}
String to Integer (atoi)
字符串转整型，各种奇葩的输入
挺麻烦
public int atoi(String str) {
String s = new String();
int count = 0;
while (count < str.length()&&str.charAt(count) == ' ')
count++;
for (int i = count; i < str.length(); i++)
s += str.charAt(i) + "";
count = 0;
boolean flag = true;
while (count < s.length()&&(s.charAt(count) < '0' || s.charAt(count) > '9'))
count++;
;
String s2 = new String();
if (count == 1) {
if (s.charAt(0) == '-')
flag = false;
else if (s.charAt(0) == '+')
flag = true;
else
return 0;
for (int i = 1; i < s.length(); i++)
s2 += s.charAt(i) + "";
s = s2;
}
if (count > 1)
return 0;
long result = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
result = result * 10 + (s.charAt(i) - '0');
if (result > 2147483647)
if (flag)
return 2147483647;
else
return -2147483648;
} else
break;
}
if (!flag)
result = -result;
return (int) result;
}
leetCode题解(1)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。