回复：leetcode刷题贴

第十一题：169. Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
找出给定数组中重复出现多次的元素。出现多次的元素出现次数超过了半数。
假定数组中一定存在这样的元素，且数组不为空。
函数格式：
int majorityElement(int* nums, int numsSize) {
}
抱歉，翻译的时候看错了，所以翻译错了。

这个是答案。这个是由Robert S.Boyer 和J Strother Moore于1980年发明的一种算法。

第十二题：206. Reverse Linked List
Reverse a singly linked list。
反转一个单链表。
希望用迭代和递归两种方法实现。
这个很简单，我就写一种了。
函数格式：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head) {
}

第十三题:13. Roman to Integer
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
将给定的罗马数字转化为整形十进制数字。
假定给出的罗马数字的范围是1到3999.
函数格式：
int romanToInt(char* s) {
}

好像比较难。代码还是很简单的。wiki上面有具体算法解释。

第十四题：235. Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
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 descendant of itself).”
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4_ 7 9
/ \
3 5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
在一个二叉树中找到给定两个节点的公共祖先。公共祖先是距离两个节点最近的公共的父节点。例子中2,8的公共组件是6,然而2和4的公共祖先是4。
函数格式：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
}
好像题目越来越难了。二叉树基本是递归和迭代。今天就这样吧，明天我解这个题。

这个题相比之前比较难。首先要明白什么是BST树。
BST树是指二叉查找树（Binary Sort Tree），是一种有一定顺序的额二叉树。特点就是二叉树中序遍历的结果是严格递增的。通俗的说法就是左节点小于根节点，小于右节点。
左<中<右。
解法如下：

第十五题：191. Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.
计算一个无符号整形数转化为二进制之后包含的1的个数。
例子：32位整形数11中的二进制位00000000000000000000000000001011，返回结果为3.
(又称之为：the Hamming weight).
函数格式：
int hammingWeight(uint32_t n) {
}
/*************
没有人看，一点动力都没有。大概再有60个题目左右，简单的就刷完了。
如果超不过1000楼，中等题目就不更了。也证明贴吧多是 小白。没有 意义留下去了。
**************/

第十六题：83. 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.
删除一个有序链表中重复出现的节点。
例子：
1->1->2，结果为1->2
函数格式：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteDuplicates(struct ListNode* head) {
}

找到重复，指向下一个。指针基础操作。

第十七题：70. 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?
上n阶楼梯，每次可以上1节或者两节，求有多少种上楼梯的方法。
函数格式：
int climbStairs(int n) {
}
/**************
最基础的动态规划算法。基本上教算法一定会做到的题。
***************/