ITeye博客

2016 年文章归档

共 209 篇文章

Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity. Example: Given 1…

2016-02-28 05:03 · Leetcode

Power of Three

Given an integer, write a function to determine if it is a power of three. Follow up: Could you do it without using any loop / recursion? 判断一个整数是否为3的幂。如果一个整数是3的幂,那么就可以表示为 3 ^ x = n => log(3^x) = log(n) => xlog(3) = log(n) => x = log(n) / log(3)。我们只需要判断x是否为整数就可以了,代码如下: public class Solution { public…

2016-02-28 04:58 · Leetcode

Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given , The longest increasing subsequence is , therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm sho…

2016-02-28 04:22 · Leetcode

Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and positi…

2016-02-28 03:30 · Leetcode

Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize …

2016-02-27 05:11 · Leetcode

Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones. Both of you are very clever and have op…

2016-02-27 03:37 · Leetcode

Word Pattern

Given a pattern and a string str, find if str follows the same pattern. Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str. Examples: pattern = "abba", str = "dog cat cat dog" should return true. pattern = "abba", str = "dog cat ca…

2016-02-27 03:29 · Leetcode

Game of Life

According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970." Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neig…

2016-02-27 03:15 · Leetcode

Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. Note: You must not modify the array (assume the array is read only). You must…

2016-02-27 02:26 · Leetcode

Peeking Iterator

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next(). Here is an example. Assume that the iterator is initialized to the…

2016-02-26 05:08 · Leetcode

Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements. For example, given nums = , after calling your function, nums should be . Note: You must do this in-place without making a copy of the array. Minimize the total numb…

2016-02-26 04:38 · Leetcode

First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions a…

2016-02-26 03:07 · Leetcode

H-Index II

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm? 这道题目是H-Index的follow up。题目的意思让我们在O(log n)的时间复杂度下解决。我们用二分法,这道题目比较trick, 代码如下: public class Solution { public int hIndex(int[] citations) { if(citations == null || citations.length == 0)…

2016-02-26 02:56 · Leetcode

H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index. According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h pap…

2016-02-26 02:25 · Leetcode

Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array. For example, Given nums = return 2. 通过位运算,将数组里面的元素与对应的下标进行异或运算,得到一个结果result, 然后将result与数组的长度进行异或运算,得到的结果就是缺少的数字。代码如下: public class Solution { public int missingNumber(int[] nums) { …

2016-02-25 03:46 · Leetcode

Ugly Number II

Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers. Note that 1 is typically treated as an ugly number. 找到第n个ugly number, 第一我们维护ugly number…

2016-02-25 03:36 · Leetcode

Ugly Number

Write a program to check whether a given number is an ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7. Note that 1 is typically treated as an ugly number. 分别于2,3,5取余,然后取…

2016-02-25 02:45 · Leetcode

Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. For example: Given nums = , return . Note: The order of the result is not important. So in the above example, is also correct.…

2016-02-25 02:20 · Leetcode

Binary Tree Paths

Given a binary tree, return all root-to-leaf paths. For example, given the following binary tree: 1 / 2 3 5 All root-to-leaf paths are: 给定一个二叉树,输出从根到叶子节点的路径。用递归来完成,代码如下: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x…

2016-02-25 01:40 · Leetcode

Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *. Example 1 Input: "2-1-1". ((2-1)-1) = 0 (2-(1-1)) = 2 Output: Example 2 Input: "2 3-4 5" (2*(3-(4 5))) = -34 ((2 3)…

2016-02-24 10:03 · Leetcode