No.1
题目链接：Gray Code
- 题目描述：
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:00 - 0 01 - 1 11 - 3 10 - 2Note: For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
(1)思路：该问题给我们一个数字n，要求生成n位的格雷码。考虑到格雷码相邻两个二进制数只能在一位上有差异，所以我们可以用一种从最低为开始，逐位加一的方法去解决这个问题。
我们以n=3为例。我们可以令一开始的数为000，然后在最低位加一，得到：
000
001
然后我们在上述已知的格雷码中，从下往上在次低位加一：
000
001
011
010
这里要注意加一的顺序，必须要从下往上加，因为新增加的数字如果是从上往下产生的，那么就相当于是同时在多个位上发生改变，而从下往上加可以确保只有一位发生了改变，又因为原先有的相邻格雷码之间只有一位有区别，如果在同一个位置上都加一，相邻两个之间的差异仍然只有一，因此性质还是成立的。 最后我们在最高位上加一，注意还是要从下往上：
000
001
011
010
110
111
101
100
(2)代码：
#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res(1, 0);
for (int i = 0; i < n; ++i) {
int size = res.size();
while (size--) {
int curNum = res[size];
curNum += (1 << i);
res.push_back(curNum);
}
}
return res;
}
};
int main(){
int n;
cout<<"请输入位数n：";
cin>>n;
Solution solution;
vector<int> result=solution.grayCode(n) ;
for(int i=0;i<result.size();i++){
cout<<result[i]<<" ";
}
cout<<endl;
}
No.2
题目链接：Insertion Sort List
- 题目描述：
Sort a linked list using insertion sort.
(1)思路：该问题比较简单，要求我们用插入排序的方法实现链表的排序。插入排序即遍历链表，然后将其插入到适当的为值即可，我们可以将链表分为两部分，前半部分为已经排序好的，后半部分是还未排序的，用指针指向未排序的头结点，然后遍历排序号的部分，找到第一个大于该值的节点，然后将其插入到该节点之前一个位置即可。然后未排序部分的头结点向后移一个节点即可，直至遍历完整个链表。
(2)代码：
#include<iostream>
#include<stdlib.h>
#include<string>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode *newhead = new ListNode(-1);
while(head != NULL){
ListNode *temp = head->next;
ListNode *cur = newhead;
while(cur->next != NULL &&cur->next->val < head->val){
cur = cur->next;
}
head->next = cur->next;
cur->next = head;
head = temp;
}
return newhead->next;
}
};
int main(){
cout<<"请输入链表长度 N ：";
int n;
cin>>n;
ListNode *head = NULL;
ListNode *p;
int a;
cout<<"请输入链表元素：";
while(n--){
cin>>a;
if(head == NULL){
head = (ListNode *)malloc(sizeof(ListNode));
head->val = a;
p = head;
}
else{
p->next = (ListNode *)malloc(sizeof(ListNode));
p = p->next;
p->val = a;
}
}
p->next = NULL;
Solution solution;
ListNode* result = solution.insertionSortList(head);
while(result != NULL){
if(result->next == NULL){
cout<<result->val<<endl;
}
else{
cout<<result->val<<" -> ";
}
result = result->next;
}
cout<<endl;
return 0;
}
No.3
题目链接：Word Break
- 题目描述：
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words. For example, given
s = “leetcode”, dict = [“leet”, “code”].
Return true because “leetcode” can be segmented as “leet code”.
(1)思路：该问题给了我们一个字符串s和一个字典dict，要求我们根据字典判断字符串s能否全部根据字典中的单词进行分割。我们可以这样思考：字符串s可以被全部分割，即组成字符串s的子字符串全部都在字典dict中，而判断子字符串是否在dict中，我们可以一个一个字符的判断，用一个bool类型的数组或者向量，向量或数组的长度为字符串s的长度加1，然后每一位初始设为false，第一位设为true。然后遍历没一个字符，如果该字符在dict中就将对应位置的数组设为true，每一位的判断先要满足前一位为true的条件，然后再进行判断，最后得出的字符串s长度的位置为真即代表可以完全分割。
(2)代码：
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int size = s.size();
vector<bool> dp(size + 1, false);
dp[0] = true;
for(int i = 1; i <= size; i++){
for(int j = 0; j < i; j++){
if(dp[j]){
vector<string>::iterator re = find( wordDict.begin(), wordDict.end(), s.substr(j, i - j));
if (re != wordDict.end())
dp[i] = true;
}
}
}
return dp[size];
}
};
int main(){
string s;
cout<<"请输入原始字符串s：";
cin>>s;
cout<<"请输入字典向量的额元素个数n：";
vector<string> wordDict;
int n;
string a;
cin>>n;
while(n--){
cin>>a;
wordDict.push_back(a);
}
Solution solution;
bool result=solution.wordBreak(s, wordDict);
if(result == true) cout<<"True"<<endl;
else cout<<"False"<<endl;
return 0;
}
No.4
题目链接：Combination Sum III
- 题目描述：
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
(1)思路：该问题给出我们两个参数，k和n，要求我们列出k个数和为n的所有组合，可以用的数字为1~9。我们可以采用递归循环调用的方法：我们可以用一个向量num存现有的数字的集合，n是k个数字之和，如果n小于0，则直接返回；如果n正好等于0，而且此num中数字的个数正好为k，说明此时是一个正确解，将其存入结果result中。
(2)代码：
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
class Solution {
public:
vector<vector<int> > combinationSum3(int k, int n) {
vector<vector<int> > result;
vector<int> num;
help(k, n, 1, num, result);
return result;
}
void help(int k, int n, int level, vector<int> &num, vector<vector<int> > &result){
if(n < 0) return;
if(n == 0 && num.size() == k) result.push_back(num);
for(int i=level;i<=9;++i){
num.push_back(i);
help(k, n-i, i+1, num, result);
num.pop_back();
}
}
};
int main(){
int k, n;
cout<<"请输入 k 和 n ：";
cin>>k>>n;
Solution solution;
vector<vector<int> > result = solution.combinationSum3(k, n);
int size = result.size();
for(int i=0;i<size;i++){
int size1=result[i].size();
cout<<"[";
int j;
for(j=0;j<size1-1;j++){
cout<<result[i][j]<<", ";
}
cout<<result[i][j]<<"]"<<endl;
}
return 0;
}
