LeetCode 77. 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:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

题目大意:给两个整数n和k,返回所有的k个数字组合,这些数字只能从1…n中选择~

分析:从cur == 0,cnt == 0开始,每次将cur + 1 ~ n之间的数字放入row中,并将cnt + 1,然后继续深度优先搜索直到cnt == k为止将row放入result中作为结果之一,不要忘记dfs遍历后还要将当前元素pop_back()出来,最后返回result~

 

LeetCode 386. Lexicographical Numbers

386. Lexicographical Numbers
Given an integer n, return 1 – n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

题目大意:给一个整数n,将1-n所有数按照字典序排序~
分析:从1~9分别深度优先遍历,对于每一次遍历,继续深度优先它的10 * cur + i(i从1~9),只要符合范围的就将该数字cur放入result数组中~最后返回result即可~

 

LeetCode 82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

题目大意:给一个已经排序的链表,删除所有元素值出现过2次或者以上的结点,只保留元素值仅仅出现过一次的结点~

分析:p为head的next,如果p的值和head的值不同,则将head->next置为deleteDuplicates(p),返回head,否则直到找到第一个p不等于head的地方,返回deleteDuplicates(p)~

 

LeetCode 222. 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 inclusive at the last level h.

题目大意:给一个完全二叉树,计算结点的个数~

分析:完全二叉树满足当最左结点和最右结点等高(h)的时候,结点数为2的h次方-1;否则等于左子树的结点数 + 右子树的结点数 + 1。且完全二叉树的左子树和右子树也是一个完全二叉树~