问题描述

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.

要求

• 不能修改数组（数组只读）
• 空间复杂度\(\Theta(1)\)
• 时间复杂度小于\(\Theta(n^2)\)

问题描述

The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

1
2
3
4
5
6
7
8
9
10

//3位gray code
格雷码     二进制码
0 0 0       0 0 0
0 0 1       0 0 1
0 1 1       0 1 0
0 1 0       0 1 1
1 1 0       1 0 0
1 1 1       1 0 1
1 0 1       1 1 0
1 0 0       1 1 1

前言

最近把leetcode的linked list专题刷完了，我感觉收获很多，也看了很多他人的代码，对单链表的理解又更深了一步，所以写篇博文来总结一下，同时也方便自己以后复习。

leetcode上的链表节点定义如下：

1
2
3
4
5

struct ListNode{
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};

问题描述

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character

前言

Fast Inverse Square Root 即平方根倒数速算法，是一种快速计算\(x^{\frac{1}{2}}\) 的方法。在公布的《雷神之锤3》里被发现，写的很强大，原作者不详，但是与卡神相关。 遇到这种神级代码，就想记录下来。_(:зゝ∠)_

Code

先来看看这段代码，其中的注释也是原汁原味的。

问题描述

Implement int sqrt(int x).
Compute and return the square root of x.

思路

本题应该是采用一种快速的收敛方法来接近最终解。一般的做法是采用 二分法，但是我今天要说的是另一种，Newton\’s method。