ITeye博客

2016 年文章归档

共 209 篇文章

Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s. For example, s = "anagram", t = "nagaram", return true. s = "rat", t = "car", return false. Note: You may assume the string contains only lowercase alphabets. 判断两个词是否为异位构词,我们可以借助计数排序算法的思想来解决,代码如下: public class Solutio…

2016-02-24 05:48 · Leetcode

Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom. For example, Consider the following matrix: , , ,…

2016-02-24 05:38 · Leetcode

Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. For example, Given nums = , and k = 3. Window position Max -3 5 3 6 7 3…

2016-02-24 05:22 · Leetcode

Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output* is equal to the product of all the elements of nums except nums*. Solve it without division and in O(n). For example, given , return . 我们创建一个长度和原数组num长度一样的数组result,先从左边开始,让result = 1; result = 1 * num, result =…

2016-02-24 02:43 · Leetcode

Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a de…

2016-02-23 04:01 · Leetcode

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome. Follow up: Could you do it in O(n) time and O(1) space? 判断一个单向链表是否为回文链表,要求时间复杂度为O(n),空间复杂度为O(1)。我们可以先用快慢指针找到中间的节点,然后将后半部分链表反转,然后以前半部分的链表进行比较,如果相同就返回true,如果不同就返回false。代码如下: /** * Definition for singly-linked list. * public class ListNode {…

2016-02-23 03:34 · Leetcode

Implement Queue using Stacks

Implement the following operations of a queue using stacks. push(x) -- Push element x to the back of queue. pop() -- Removes the element from in front of queue. peek() -- Get the front element. empty() -- Return whether the queue is empty. Notes: You must use only standard operations of a stack -- …

2016-02-23 03:16 · Leetcode

Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You may assume k is always valid, 1 ≤ k ≤ BST's total elements. 给定一个二叉搜索树,从中找到第k小的元素。根据二叉搜索树的性质中序遍历正好是二叉搜索树的升序排列,当我们遍历到第k个元素是返回就可以了。代码如下: /** * Definition for a binary tree node. * public class Tr…

2016-02-23 02:59 · Leetcode

Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space. 这道题目是 Majority Element 的变形,这里要求找出出现次数多余n/3次。我们通过分析可以知道这样的元素可能有两个,我们同样可以采用Moore算法,与上一题目不同的的是三个元素一组,这样在线性的时间复杂度下可以解决。代码如下: public class Solution { public…

2016-02-23 02:14 · Leetcode

Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges. For example, given , return . 从第一个元素开始,每次保留开始的元素的值,依次扫描后面的元素,如果有连续的就一直往后查找,直到遇到不连续的,然后记录这段范围。直到遍历完所有的元素。代码如下: public class Solution { public List<String> summaryRanges(int[] nums) { List<String> list = new ArrayList<…

2016-02-22 04:10 · Leetcode

Invert Binary Tree

Invert a binary tree. 4 / 2 7 / \ / 1 3 6 9 to 4 / 7 2 / \ / 9 6 3 1 给定一个二叉树,交换它的左右子树。我们用递归完成,从根节点开始,递归交换root的左子树,然后递归交换root的右子树。代码如下: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class …

2016-02-22 03:30 · Leetcode

Implement Stack using Queues

Implement the following operations of a stack using queues. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. empty() -- Return whether the stack is empty. Notes: You must use only standard operations of a queue -- which means only…

2016-02-22 03:21 · Leetcode

Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane. Each rectangle is defined by its bottom left corner and top right corner as shown in the figure. Assume that the total area is never beyond the maximum possible value of int. 首先计算出两个长方形的面积,然后计算出它们重叠的面积,最后返回两个面积的差就可以了。代码如下: pub…

2016-02-22 02:51 · Leetcode

Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes. Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclus…

2016-02-22 02:22 · Leetcode

Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area. For example, given the following matrix: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Return 4. 典型的二维动态规划的问题。我们构造一个二维的dp数组,dp 代表到点(i , j)时由1构成的正方形的最大长度。当char 为0时,dp 在当前点只能为0;如果char 为1时,dp* =…

2016-02-21 03:37 · Leetcode

Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums* and nums is at most t and the difference between i and j is at most k. 题目中给定一个数组,判断数组中是否存在两个数nums*和nums,它们之间的差最大为t, 两个下标i和j之间的差最大为k。我们用TreeSet来解决,我们维护一个大小为k的treese…

2016-02-21 03:17 · Leetcode

Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums* = nums and the difference between i and j is at most k. 给定一个数组判断数组中是否存在两个相同的数,它们之间的差最大为k。我们借助HashMap, key中存放数组的元素nums*,value中存放对应的下标i。如果遇到相同的key,就对比当前元素的下标i与key中value的值与…

2016-02-21 02:36 · Leetcode

Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Ensure that numbers within the set are sorted in ascending order. Example 1: Input: k = 3, n = 7 Output: ] Example 2: Input:…

2016-02-21 02:19 · Leetcode

House Robber II

Note: This is an extension of House Robber. After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the…

2016-02-21 01:21 · Leetcode

Add and Search Word - Data structure design

Design a data structure that supports the following two operations: void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter. For example: addWord("bad") addWord("dad") addW…

2016-02-20 08:29 · Leetcode