`
huntfor
  • 浏览: 201088 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

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;
    }

 

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

分享到:
评论

相关推荐

    leetcode安卓-leetcode:leetcode练习题收集,渐渐锻炼自己的算法思维能力

    练习题收集 回顾: 曾经自己是一名PHPer,一度认为PHP是世界上最好的语言,直到大学写了个Android项目,才知道原来java才是世界上最好的语言,毕业找实习是抱着自己是PHPer的身份去的,然结果都不是很满意,直到面试...

    leetcode第一题代码

    第一题的四种方法,包括暴力破解和字典、列表。我也是刚开始练习

    leetcode:leetcode练习题代码

    LeetCode 是一个在线平台,提供各种编程练习题,旨在帮助程序员提升算法技能和解决实际问题的能力。本压缩包“leetcode-master”很可能包含了某用户在解决LeetCode题目时编写的Java代码仓库。以下将针对LeetCode平台...

    leetcode book 习题集

    leetcode 习题集, leetcode 官网出品,包含基本的算法

    微软面试leetcode难度-leetcode:微软面试习题练习

    首先,LeetCode上的题目按照难度级别分为简单、中等和困难,微软面试通常会涉及中等和困难级别的问题,因此选择“中等”难度的习题是相当明智的。这些题目旨在测试你的逻辑思维、问题解决能力和编码技巧,这些都是在...

    acm和leetcode难度-ACM:leetcode-数据结构与算法刷题

    acm和leetcode难度 ACM 数据结构与算法 目录按照LeetCode题目编写,* 代表简单, ** 代表中等, *** 代表困难 两数之和 时间复杂度为O(n) 使用了字典 方便得到序列号 两数相加 循环节点相加,大于十进位,要考虑两数...

    leetcode分类-leetcode:leetcode刷题(中等难度分类)

    《LeetCode刷题指南:中等难度篇》 在编程领域,LeetCode 是一个非常知名的在线平台,它提供了丰富的算法题目,旨在帮助开发者提升编程技能、理解和解决实际问题。本篇将聚焦于LeetCode中的中等难度题目,通过深入...

    leetcode每日一题总结.zip

    LeetCode的每日一题是平台上的一个特色功能,每天会发布一个新的编程题目,涵盖各种难度级别,从基础到进阶,涉及语言包括Java、Python、C++等。这些题目涵盖了数据结构(如数组、链表、栈、队列、树、图等)和算法...

    leetcode双人赛-leetcode:LeetCode练习题的解决方案

    练习题的解决方案。 # 问题标题 / LeetCode 链接 解决方案 困难 标签 1 简单的 array hash table 2 中等的 linked list math 3 中等的 hash table 5 中等的 two pointers 6 中等的 string 7 简单的 math 8 中等的 ...

    leetcode全套解答python版本

    LeetCode是一个广受欢迎的在线编程挑战平台,致力于帮助程序员提升技能,特别是面试准备。这个压缩包“lc-all-solutions-master”包含了使用Python语言解决LeetCode所有问题的代码,覆盖了从基础算法到复杂数据结构...

    leetcode-习题集资源-源代码

    leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源leetcode-习题集资源

    leetcode添加元素使和等于-js-algorithm-leetcode:Leetcode练习题与JavaScript实现数据结构与算法

    leetcode添加元素使和等于 js-algorithm JavaScript 实现数据结构与算法 Leetcode 算法练习 难度简单68收藏分享切换为英文接收动态反馈 写一个 RecentCounter 类来计算特定时间范围内最近的请求。 请你实现 ...

    leetcode周赛难度-leetcode:leetcode

    周赛难度LeetCode 题解 一题目列表 细绳 # 标题 标签 困难 解决方案 描述 1 细绳 中等的 2 细绳 中等的 3 细绳 中等的 4 细绳 中等的 DP # 标题 标签 困难 解决方案 描述 1 DP 中等的 2 DP 中等的 3 DP 中等的 4 DP ...

    leetcode-习题集资源源代码

    leetcode-习题集资源源代码leetcode-习题集资源源代码leetcode-习题集资源源代码leetcode-习题集资源源代码leetcode-习题集资源源代码

    leetcode腾讯精选练习(50题)C++版

    leetcode腾讯精选练习(50题)C++版

    leetcode-习题集资源

    leetcode

    leetcode答案-leetcode:leetcode习题答案

    本资源包“leetcode答案-leetcode:leetcode习题答案”是针对LeetCode平台上的习题所整理的一系列解决方案,主要涵盖C++, Java, Python等多种编程语言。这些答案和解析是开源的,为学习者提供了宝贵的参考。 ...

    acm和leetcode难度-leetcode:leetcode算法分析和代码实现

    acm和leetcode难度 leetcode 解题列表 俗话说: 熟读唐诗三百首, 不会作诗也会吟. 要想掌握好算法和数据结构, 老王觉得至少需要两样东西: 体系化的学习 一定量的练习 最近老王听说很多人喜欢去leetcode上刷题, 就去看...

    leetcode2sumc-leetcode:leetcode的所有练习题

    leetcode 2 和 c LEETCODE - leetcode 问题的终极指南 创建存储库是为了解决基本的面试问题,重点是数据结构和算法。 该文件维护每个程序的详细信息以及相关的源/其他信息。 当前使用 C# 编写的存储库(VS 2019 - ...

    leetcode感觉难度大-LeetChill:隐藏难度的WebExtension显示在LeetCode上

    leetcode 难度大利特寒 创建时间:2017 年 2 月 上可用。 LeetChill 是一个 WebExtension,它隐藏了 LeetCode 上的难度级别和接受率。 这样做的目的是为了避免被评级困难的问题吓倒。 我瞄准无缝与页面整合的变化,...

Global site tag (gtag.js) - Google Analytics