0%

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

img
In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

1
2
3
4
5
6
7
8
9
Input: 5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
阅读全文 »

Given a non-empty array of digits representing a non-negative integer, increment one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

1
2
3
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

1
2
3
Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
阅读全文 »

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

1
2
Input: [1,3,5,6], 5
Output: 2

Example 2:

1
2
Input: [1,3,5,6], 2
Output: 1

Example 3:

1
2
Input: [1,3,5,6], 7
Output: 4

Example 4:

1
2
Input: [1,3,5,6], 0
Output: 0
阅读全文 »

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

1
2
3
4
5
Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5
6
7
Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.
阅读全文 »

Given a sorted array nums, 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 by modifying the input array in-place with O(1) extra memory.

Example 1:

1
2
3
4
5
Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5
Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

注意,要判断nums的长度,如果是0则会报错

阅读全文 »

如下为类型CMyString的声明, 请为该类型添加赋值运算符函数.

1
2
3
4
5
6
7
8
9
10
class CMyString
{
public:
CMyString(char* pData = nullptr);
CMyString(const CMyString& str);
~CMyString(void);

private:
char* m_pData;
}
阅读全文 »

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1:

输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3

限制:

2 <= n <= 100000

阅读全文 »

设计一个类, 我们只能生成该类的一个实例

1. 饿汉式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Hungry {
//饿汉式浪费空间, 一上来就把对象加载到内存中
private AtomicLong atomicLong = new AtomicLong(); //假设单例模式中的资源
private Hungry(){

}
private final static Hungry HUNGRY = new Hungry();
public static Hungry getInstance(){
return HUNGRY;
}
public long getId(){
return atomicLong.incrementAndGet();
}
}

能防住多线程, 不能防住反射.

2. 懒汉式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Lazy{
//单线程下没问题, 多线程不行
private AtomicLong atomicLong = new AtomicLong();
private Lazy(){
System.out.println("one lazy singleton has been created");
}
private static Lazy LAZY;

public static Lazy getInstance(){
if(LAZY == null){
LAZY = new Lazy();
}
return LAZY;
}
public long getId(){
return atomicLong.incrementAndGet();
}

不能防住多线程, 不能防住反射.

3. 加锁懒汉式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//加锁之后的懒汉式单例模式, DCL
class LockLazy{
private AtomicLong atomicLong = new AtomicLong();
private LockLazy(){
System.out.println("one locklazy singleton has been created");
}
private static LockLazy LOCKLAZY;
//双重检查, 如果单例已经创建了, 就不加锁. 单例未创建才加锁.
public static LockLazy getInstance(){
if(LOCKLAZY == null){
synchronized (LockLazy.class){
if(LOCKLAZY == null){
LOCKLAZY = new LockLazy();
}
}
}
return LOCKLAZY;
}
public long getId(){
return atomicLong.incrementAndGet();
}
}
//但是这样也还是不安全, 如果一个线程进行new LockLazy();操作,这个操作不是原子性的, 会被jvm大体分为3个阶段.
//1. 分配内存空间 2. 初始化对象, 进行属性赋值. 3. 将对象指向这个空间
//如果没有发生指令重排, 是安全的. 如果指令重排为 132这样的顺序, 当一个线程执行完第3步, 还没有执行第2步, 这时时间片用尽, 切换到另一个线程, 另外一个线程执行getInstance()方法, 一看LOCKLAZY非空, 就直接返回了这个对象了, 但是这个对象内还没有初始化. 自然就会报错, 所以为了安全一定要将单例的引用加volatile

4. 加锁加volatile懒汉式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class SafeLazy{
private AtomicLong atomicLong = new AtomicLong();
private volatile static SafeLazy SAFELAZY;
private SafeLazy(){

}

public static SafeLazy getInstance(){
if(SAFELAZY == null)
{
synchronized (SafeLazy.class)
{
if(SAFELAZY == null)
{
SAFELAZY = new SafeLazy();
}
return SAFELAZY;
}
}
return SAFELAZY;
}

public long getId(){
return atomicLong.incrementAndGet();
}
}

多线程足够安全, 仍然防不住反射

5. 静态内部类实现单例模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Holder {
private Holder(){

}
private AtomicLong atomicLong = new AtomicLong();
private static class InnerClass
{
private static final Holder HOLDER = new Holder();
}
public static Holder getInstance(){
return InnerClass.HOLDER;
}
public long getId(){
return atomicLong.incrementAndGet();
}
}
//静态内部类单例模式也称单例持有者模式,实例由内部类创建,由于 JVM 在加载外部类的过程中,
// 是不会加载静态内部类的, 只有内部类的属性/方法被调用时才会被加载, 并初始化其静态属性

就是把饿汉式的new 单例模式的过程private final static Hungry HUNGRY = new Hungry();放到个静态内部类中, 通过静态内部类的加载机制实现懒惰加载. 仍然防不住反射

6. 枚举类实现单例模式

1
2
3
4
5
6
7
8
9
10
11
12
enum Singleton
{
SINGLETON;
private AtomicLong atomicLong = new AtomicLong();
public long getId(){
return atomicLong.incrementAndGet();
}
public static Singleton getInstance()
{
return SINGLETON;
}
}

这个最安全, 多线程和反射都破坏不了, 反序列化的方法也破解不了. 也最简洁, 核心代码只需要3行. 加载模式和饿汉式一样, 都是提前加载. 怪不得都推荐使用这种方法

这个题等价于leetcode 287.

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one duplicate number in nums, return this duplicate number.

Follow-ups:

  1. How can we prove that at least one duplicate number must exist in nums?
  2. Can you solve the problem without modifying the array nums?
  3. Can you solve the problem using only constant, O(1) extra space?
  4. Can you solve the problem with runtime complexity less than O(n2)?

Example 1:

1
2
Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

1
2
Input: nums = [3,1,3,4,2]
Output: 3

Example 3:

1
2
Input: nums = [1,1]
Output: 1

Example 4:

1
2
Input: nums = [1,1,2]
Output: 1

Constraints:

  • 2 <= n <= 3 * 104
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • All the integers in nums appear only once except for precisely one integer which appears two or more times.
阅读全文 »

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

限制:

0 <= 节点个数 <= 5000

阅读全文 »