leetcode难度一的习题小结

LeetCode ：Remove Duplicates from Sorted Array 

题目

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

 本来我是按照常规思路，遍历A的每一个节点，遇到与前驱节点相同的节点，即删除掉

public int removeDuplicates(int[] A){
		if(A == null || A.length == 0){
			return 0;
		}
		int length = A.length;
		int count = 1;
		for(int i = 1 ; i < length; i++){
			if(A[i] == A[i - 1]){
				delete(A, i--);
				length--;
			}else{
				count++;
			}
		}
		return count;	
	}
	
	public void delete(int[] a ,int index){
		if(a == null || index >= a.length){
			return;//throw exception
		}
		for(int i = index + 1; i < a.length; i++){
			a[i - 1] = a[i];
		}
	}

好无意外的错了，意外的是是超时，看了一眼题中给的case，给跪了

挂掉的case

有一个case从-999 到9999，每个数都出现了两次，一共有11000个数左右，n*n复杂度肯定是过不去的

那么答案只能是O(NlogN)甚至是O(n)，看了一眼 http://huntfor.iteye.com/admin/blogs/2038023中给的算法提示：two pointer！

因此有了下面的算法： 

 public int removeDuplicates(int[] A){
		if(A == null || A.length == 0){
			return 0;
		}
		int start = 1;		
		for(int i = 1; i < A.length;i++){
			if(A[i] == A[i - 1]){
				continue;
			}else{
				A[start++] = A[i];
			}
		}
		return start;
	}

 不能不说，双指针真是好用的不得了。

 

LeetCode：Remove Element

 

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

 同样是two pointer！

不多说了，依葫芦画瓢吧

public int removeElement(int[] A, int elem) {
        int start = 0;
//two pointer: 
//one is used to traverse the array
//the other is to record the new array base on the old one
		for(int i = 0; i < A.length ; i++){
			if(A[i]!= elem){
				A[start++] = A[i];
			}
		}
		return start;
  }

 涨姿势了。

 

LeetCode：Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.

偷懒的做法，不涉及技术含量

    public int lengthOfLastWord(String s) {
		if(s == null || s.isEmpty()){
			return 0;
		}
		String[] words = s.split(" ");
		int length = words.length ;
		String record = "";
		if(length > 0){
			 record = words[words.length - 1];
			 return record.length();
		}else{
			return 0;
		}
    }

  看到有大神这样做的，不偷懒，好算法：

public class Solution {
    public int lengthOfLastWord(String s) {
		int len = 0;
		boolean flag = true;
		for(char c :s.toCharArray()){
			if(Character.isLetter(c)){
				if(flag){
					len++;
					continue;
				}else {
					len=1;
					flag=true;
				}
			}else 
				flag=false;
		}
		return len;    
    }
}

 

LeetCode Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

题目大意是，一个非负数用数组表示，对这个数+1，返回+1后的数组结果

第一反应肯定是把数组的数转换成自然数，但是肯定是不对的（我们只见过数位太多，用数组表示大数，逆向显然不对的，虽然我没试过，其实就是一个加法的模拟，不多说）

    public int[] plusOne(int[] digits) {
       		if(digits == null || digits.length == 0){
			return null;
		}
		int length = digits.length;
		int[] result = new int[1+length];//放结果，可能进位，因此多开一位
		for(int i = length - 1; i >= 0; i--){
			result[i + 1] = digits[i];
		}
		result[0] = 0;
		digits[length - 1] = digits[length - 1] + 1;
		if(digits[length - 1] < 10){
			return digits;
		}else{
			result[length] = digits[length - 1];
			for(int i = length - 1; i >= 0; i--){
				result[i] += 1;
				result[i + 1] -= 10;
				if(result[i] < 10){
					break;
				}
			}
		}
		if(result[0]!=0){
			return result;
		}else{
			int[] tem = Arrays.copyOfRange(result, 1, result.length );
			return tem;
		}
    }

 感觉自己空间开的太多。。。。

 

LeetCode：Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

 判断两棵树相同，只需比较其  中序遍历 && （前序 | | 后序），最简单的递归，没啥好讲的

  public boolean isSameTree(TreeNode p, TreeNode q) {
		if (p == null && q == null) {
			return true;
		}
		String pPre = preOrder(p, new StringBuilder()).toString();
		String pIn = inOrder(p, new StringBuilder()).toString();
		String qPre = preOrder(q, new StringBuilder()).toString();
		String qIn = inOrder(q, new StringBuilder()).toString();
		if (pPre.equals(qPre) && pIn.equals(qIn)) {
			return true;
		}
		return false;
	}

	public StringBuilder preOrder(TreeNode root, StringBuilder sb) {
		if (root != null) {
			sb.append(root.val + "");
			preOrder(root.left, sb);
			preOrder(root.right, sb);
		} else {
			sb.append("#");
		}
		return sb;
	}

	public StringBuilder inOrder(TreeNode root, StringBuilder sb) {
		if (root != null) {
			inOrder(root.left, sb);
			sb.append(root.val + "");
			inOrder(root.right, sb);
		} else {
			sb.append("#");
		}
		return sb;
	}

 

LeetCode ：Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

 遇到后继节点自己相同，就删掉，若不同，就将尾指针后移

public ListNode deleteDuplicates(ListNode head) {
		if(head == null){
			return null;
		}
		if(head.next == null){
			return head;
		}
		ListNode tail = head;
		while(tail.next != null){
			if(tail.next.val == tail.val){
				tail.next = tail.next.next;
			}else{
				tail = tail.next;
			}
		}
		return head;
    }

 LeetCode : Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

 求二叉树的高，递归，层次遍历都可，还是用递归吧，简单。不罗嗦

    public int maxDepth(TreeNode root) {
		if(root == null){
			return 0;
		}
		int leftDep = 0,rightDep = 0;
		if(root.left != null){
			leftDep = maxDepth(root.left);
		}
		if(root.right != null){
			rightDep = maxDepth(root.right);
		}
		return leftDep > rightDep ? leftDep + 1: rightDep + 1;
    }

 

剩下的几道明后天会补上。