2016 年文章归档
共 209 篇文章
Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array. 从数组中找到出现次数多于一般的元素。题目中有两个限定条件,一个是非空,另一个是肯定有一个元素出现次数多余一半。这种情况下我们可以用Moore voting…
2016-02-16 04:29 · Leetcode
Compare Version Numbers
Compare two version numbers version1 and version2. If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0. You may assume that the version strings are non-empty and contain only digits and the . character. The . character does not represent a decimal point and is used…
2016-02-16 04:17 · Leetcode
Find Peak Element
A peak element is an element that is greater than its neighbors. Given an input array where num* ≠ num, find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that num = num = -∞. For example, in…
2016-02-16 03:11 · Leetcode
Intersection of Two Linked Lists
Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3 begin to intersect at node c1. Notes: If the two linked lists have no intersection at all, return null. The linked l…
2016-02-16 02:31 · Leetcode
Sort List
Sort a linked list in O(n log n) time using constant space complexity. 在O(nlogn)的时间复杂度下对一个链表进行排序,通过时间复杂度很容易想到用快排和分治。链表的快排实现比较复杂,这里我们用分治法来实现。代码如下: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solutio…
2016-02-15 04:40 · Leetcode
Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getMin() -- Retrieve the minimum element in the stack. 实现一个可以返回最小值的堆栈,因为题目要求我们在O(1)…
2016-02-15 04:06 · Leetcode
Find Minimum in Rotated Sorted Array II
Follow up for "Find Minimum in Rotated Sorted Array": What if duplicates are allowed? Would this affect the run-time complexity? How and why? Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Find the minimum element. The ar…
2016-02-15 03:51 · Leetcode
Find Minimum in Rotated Sorted Array
Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). Find the minimum element. You may assume no duplicate exists in the array. 给定一个有序的数组,不过数组通过一个支点进行了旋转,让我们从中找到最下的元素。我们如果直接找时间复杂度为O(n), 因为这是有序数组进行了旋转,我们可以考虑二分查找法,这样时间复杂度为O(logn)…
2016-02-15 03:42 · Leetcode
Reverse Words in a String
Given an input string, reverse the string word by word. For example, Given s = "the sky is blue", return "blue is sky the". 给定一个字符串,将里面包含的单词倒叙排列。我们可以将字符串通过空格分割成一个字符串数组,然后从后面开始组成一个新的字符串。这里要注意的是分割字符串我们用到了String的split()方法,split的参数类型是个正则表达式,不是简单的字符串,我们要用转义字符来写,例如用空格来分的话最好写成“\s” 或者“\s+”,代表通过一个空格或多个空格来分割…
2016-02-15 03:13 · Leetcode
Insertion Sort List
Sort a linked list using insertion sort. 题目的要求很简单,用插入排序来排序一个链表,不清楚插入排序的可以参考 几种常见的排序算法 。对于链表来说,每次都将当前待插入的节点与之前的有序序列进行比较,对于数组来讲,我们是将当前元素从后往前与有序数列比较的,这样可以保证排序是稳定的。因为链表只能从头节点开始,我们只能从头节点开始比较,因此链表的插入排序是不稳定的排序。代码如下: /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode n…
2016-02-14 07:05 · Leetcode
Reorder List
Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→… You must do this in-place without altering the nodes' values. For example, Given {1,2,3,4}, reorder it to {1,4,2,3}. 给定一个链表让我们重新排列它,例如以前的顺序为0-1-2-3-4,排列后的顺序为0-4-1-3-2。我们首先要找到中间的节点,用快慢指针,这个比较简单,不过值得注意的是节点是奇数和偶数的不同情…
2016-02-14 04:17 · Leetcode
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 . 输出一颗树的后序遍历序列。我们可以用递归和迭代两种方法。用迭代时我们借助堆栈,因为是后序遍历,顺序为左-右-根,因此我们只需要通过根-右-左的顺序进行遍历,然后将序列翻转就可以了。代码如下: 递归: /** * Definition for a binary tree node. * public class TreeNode {…
2016-02-14 03:23 · Leetcode
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 . 前序遍历一棵树,我们可以用递归,也可以借助堆栈用迭代来解决,因为前序遍历的顺序是根-左-右,因此我们压栈的时候顺序为根-右-左。下面是两个方法的代码: 递归: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNod…
2016-02-14 03:10 · Leetcode
Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Note: Do not modify the linked list. Follow up: Can you solve it without using extra space? 判断一个链表中是否有环存在,并且输出环的起始点。我们用快慢指针fast,slow来判断是否有环存在,如果它们可以相遇就说明有环存在,如果不能相遇说明没有环存在。它们相遇之后,图中的meet点是它们的相遇点,假设join为环…
2016-02-14 02:41 · Leetcode
Linked List Cycle
Given a linked list, determine if it has a cycle in it. Follow up: Can you solve it without using extra space? 判断一个链表中是否有环存在,用快慢指针来解决,设定两个指针fast和slow都指向head,我们让fast = fast.next.next,slow = slow.next,如果存在环,fast和slow就会相遇,因此当fast == slow时我们就返回true, 否则返回false。代码如下: /** * Definition for singly-linked li…
2016-02-13 03:11 · Leetcode
Word Break
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, given s = "leetcode", dict = . Return true because "leetcode" can be segmented as "leet code". 开始想用递归来解决,时间复杂度太高,于是想到用动态规划,创建一个boolean数组dp, …
2016-02-13 03:05 · Leetcode
Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. 题目中给定了一个链表,链表中的节点类有三个成员,label,next,random,其中label和next和普通链表中的一样,多了一个random,random指针指向链表中的任意一个元素或者指向空,要求我们复制这个链表。这道题目和 Clone Graph 很类似。我…
2016-02-13 02:00 · Leetcode
Single Number II
Given an array of integers, every element appears three times except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 给定一个数组,每个元素都出现了三次,只有一个元素出现一次,要求时间复杂度为O(n),空间复杂度为O(1),找到这个元素,我们采取位运算来解决。每个整型的数都有32位,我们记…
2016-02-13 01:39 · Leetcode
Single Number
Given an array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 给定一个数组,每个元素都出现了两次,只有一个元素出现一次,要求时间复杂度为O(n),空间复杂度为O(1),找到这个元素。我们可以采取位运算,两个相同的数异或结果为0,任何数异或0都为它…
2016-02-13 01:32 · Leetcode
Gas Station
There are N gas stations along a circular route, where the amount of gas at station i is gas*. You have a car with an unlimited gas tank and it costs cost* of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the star…
2016-02-12 06:19 · Leetcode