ITeye博客

2016 年文章归档

共 209 篇文章

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. 在一个有序的链表中删除重复的元素,使每个元素只能出现一次。做链表删除节点的问题,我们一般采用一个辅助节点helper来记录头结点,用于返回。对于这道题目,头结点肯定不会删除,因此我们直接将helper节点指向头结点即可。如果head.val = head.ne…

2016-02-04 01:47 · Leetcode

java中类的加载与实例化顺序

首先来看一段程序,通过它的输出来分析类的加载以及实例化的机制。 public class T implements Cloneable { public static int k = 0; public static T t1 = new T("t1"); public static T t2 = new T("t2"); public static int i = print("i"); public static int n = 99; public int j = print("j"); { print("构造块"); } static { print("静态块"); } public…

2016-02-03 06:34 · CS基础

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed? Would this affect the run-time complexity? How and why? Write a function to determine if a given target is in the array. 这道题目是 Search in Rotated Sorted Array 的变形。在上一题中数组中没有重复元素,我们用二分法,通过对比每次都可以删掉一般的元素,那样搜索的时间复杂度为O(logn)…

2016-02-03 05:44 · Leetcode

Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates": What if duplicates are allowed at most twice? For example, Given sorted array nums = , Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length. 这道题目是 Remove Duplica…

2016-02-03 04:38 · Leetcode

Word Search

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. For example, Given board = , , ] wo…

2016-02-03 02:50 · Leetcode

Subsets

Given a set of distinct integers, nums, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example, If nums = , a solution is: , , , , , , , ] 求子集问题,最直接的办法是用回溯法,假设一共有n个元素,子集的个数为2^n个,找出长度length从0到n的所有的可能的组…

2016-02-03 01:56 · Leetcode

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n. For example, If n = 4 and k = 2, a solution is: , , , , , , ] 有关组合的问题,给定了一个限定条件,长度为k的组合。同样用回溯法,回溯的条件就是每个结果的长度为k。往前搜索的时候,每次都加1,知道遍历完所有的可能。代码如下: public class Solution { public List<List<Integer>> combine(int n, …

2016-02-02 05:17 · Leetcode

Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not suppose to use…

2016-02-02 04:26 · Leetcode

Search a 2D Matrix

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 from left to right. The first integer of each row is greater than the last integer of the previous row. For example, Consider the following matrix: , …

2016-02-02 04:04 · Leetcode

Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. 给定一个m * n的矩阵,如果一个元素为0,那么把这个元素所在的行和列都设置为0。我们可以借助两个boolean数组,一个代表行row,一个代表列col。遍历数组,如果遇到元素matrix 为0,就把相应的行row 设置为true; 相应的列col设置为true。最后遍历这两个boolean数组,当遇到true时(row* == true || col == true)就把当前元素设置为0。空间复杂度为O(…

2016-02-02 03:37 · Leetcode

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? 爬楼梯的问题,思路和 Unique Paths 问题类似。我们假设到了第i个台阶,因为每次只能走一步和两步,因此到第i个台阶的方式等于到第i-1个台阶的方式和到第i-2个台阶的方式的和,这时i > 1; 递推式为dp* = dp + dp;实现代码如下: publi…

2016-02-02 02:13 · Leetcode

Sqrt(x)

Implement int sqrt(int x). Compute and return the square root of x. 一道设计题,实现sqrt方法,也就是开平方根。我们可以用二分法来做,设定left 为1, right为x, 用x / mid 和mid来进行比较(之所以用x / mid与mid比较,而不用x与mid mid比较是因为mid mid可能溢出,用x / mid可以防止溢出),如果x /mid 等于mid,就返回mid; 如果x /mid 小于mid,就让right = mid - 1; 如果x /mid 大于mid,就让left = mid + 1;直到left…

2016-02-01 07:08 · 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. 这道题目和 Add Binary 这道题,还有 Add Two Numbers 这道题目属于同一类型的题目。主要的问题要维护一个进位carry,根据题目的要求,不管是二进制还是十进制,如果有进位,carry就为1。最后要检查最后一位是否有进位,如果有…

2016-02-01 06:45 · Leetcode

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. 最小路径求和的问题,用动态规划来解决。每经过一个点都记录从开始到这个点的最小带权路径。当i = 0 或者j = 0的时候,因为只有一个方向可以走,这时的递推式为gr…

2016-02-01 06:15 · Leetcode

Unique Paths II

Follow up for "Unique Paths": Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example, There is one obstacle in the middle of a 3x3 grid as illustrated below. , , ] The total …

2016-02-01 05:57 · Leetcode

Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths…

2016-02-01 05:25 · Leetcode

Add Binary

Given two binary strings, return their sum (also a binary string). For example, a = "11" b = "1" Return "100". 这道题目与 Add Two Numbers 这道题目类似。不同的是这道题符合我们从低位到高位的进位方式,也就是从右往左,add two numbers那道题目是从左往右,一个是十进制,一个是二进制。思路是一样的,维护一个进位carry,对于这道题目,如果当前的值大于1的时候就需要进位,此时我们就把carry设置为1。在我们扫描完字符串之后,不要忘记检测carry的值,如果为…

2016-01-31 13:26 · Leetcode

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative. For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL. 旋转一个链表,首先我们计算出链表的长度len,如果k % len == 0, 我们可以直接返回head,如果不为0,我们就让head移动 len - 1 - (k % len)次,将链表分为两部分,这样剩下的右边部分就是长度为k的一个链表,然后将后面长度为k的链表连接到左边部分的…

2016-01-31 06:57 · Leetcode

Permutation Sequence

The set contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): "123" "132" "213" "231" "312" "321" Given n and k, return the kth permutation sequence. Note: Given n will be between 1 and 9 inclusive. 题目中给定…

2016-01-31 06:27 · 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…

2016-01-31 05:46 · Leetcode