daniellee

3.1万

daniellee
2019-04-16 16:27

### 算法1

#### C++ 代码

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void dfs(vector<int>& v,int k,TreeNode* root){
if (v.size() == k){
res = v[v.size()-1];
return;
}
if (!root) return;
if(root){
dfs(v,k,root->left);
// cout<<root->val<<endl;
v.push_back(root->val);
dfs(v,k,root->right);
}
}
int res = 0;
TreeNode* kthNode(TreeNode* root, int k) {

vector<int> v;
dfs(v,k,root);
// res = v[v.size()-1];
TreeNode *p = new TreeNode(res);
return p;
}
};


daniellee
2019-04-16 16:09

#### C++ 代码

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
map<ListNode*,int> record;
int cnt = 0;
while(h!=NULL){
record[h] = 1;
h = h->next;
}
while(h!=NULL){
if (record[h]) return h;
h = h->next;
}
return NULL;
}
};


daniellee
2019-04-16 16:07

#### C++ 代码

class Solution {
public:
int getNumberOfK(vector<int>& nums , int k) {
int half = (nums.size()-1)/2;
int r = nums.size()-1;
int l = 0;
if (nums.empty()) return 0;

while(l<=r){
half = (l+r)/2;
if (nums[half]<k){
l = half + 1;
}
else if (nums[half] >= k){
r = half-1;
}
}
int cnt = 0;
int a = half+1;
int b = half;
//   cout<<nums[half]<<endl;
//   cout<<half<<endl;
while(k == nums[a] && a<nums.size() ) {
a++;
cnt++;
// cout<<cnt<<endl;
}
while(k == nums[b] && b>=0){
b--;
cnt++;
}
return cnt;
}
};


daniellee
2019-04-16 14:29

### 算法2

#### C++ 代码

class Solution {
public:
int judge(int x,int y,int z){
int min = (x<y)?x:y;
min = (min < z)? min:z;
return min;
}
int getUglyNumber(int n) {
vector<int> v(n+1,0);
v[1] = 1;
int next = 1;
int idx2 = 1;
int idx3 = 1;
int idx5 = 1;

while(next < n){
next += 1;
int x = v[idx2] * 2;
int y = v[idx3] * 3;
int z = v[idx5] * 5;
v[next] = judge(x,y,z);
// cout<<v[next]<<endl;
while(v[idx2] * 2 <= v[next])
idx2++;
while(v[idx3] * 3 <= v[next])
idx3++;
while(v[idx5] * 5 <= v[next])
idx5++;
}
return v[n];
}
};


daniellee
2019-04-16 12:39

### 算法1

##### (动态规划) $O(n^2)$

dp[i][j] 代表走到（i，j）这个位置的最大价值

#### C++ 代码

class Solution {
public:
int getMaxValue(vector<vector<int>>& grid) {
if (grid.empty()) return 0;
int m = grid.size();
int n  = grid[0].size();
int dp[m+1][n+1];
memset(dp,0,sizeof(dp));
dp[0][0] = grid[0][0];
for(int i=1;i<n;i++){
dp[0][i] = dp[0][i-1] + grid[0][i];
}
for(int i=1;i<m;i++){
dp[i][0] = dp[i-1][0] + grid[i][0];
}

for (int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = (dp[i-1][j] > dp[i][j-1]?dp[i-1][j]:dp[i][j-1]) + grid[i][j];

}
}
// cout<<dp[1][0]<<dp[2][0];
return dp[m-1][n-1];
}
};


daniellee
2019-04-16 12:09

### 算法1

#### C++ 代码

class Solution {
public:
int getTranslationCount(string s) {
if(s.empty()) return 0;
int len = s.size();
int dp[len+1];
memset(dp,0,sizeof(dp));
dp[0] = 1;
dp[1] = 1;
for (int i=2;i<=len;i++){
dp[i] = dp[i-1];
int  k = s[i-1] - '0';
int k1 = s[i-2] - '0';
if (k1 * 10 + k <= 25 && k1 != 0){
dp[i]  += dp[i-2];
}
}
return dp[len];
}
};


daniellee
2019-04-10 13:49

#### C++ 代码

class Solution {
public:
int getMissingNumber(vector<int>& nums) {
if (nums.size()==0) return 0;
int i;
for( i=0;i<nums.size();i++){
if (i==nums[i]){
continue;
}
else{
return i;
}
}
if (i==nums.size()) return i;
}
};


daniellee
2019-04-10 13:48

#### C++ 代码

class Solution {
public:
int getNumberSameAsIndex(vector<int>& nums) {
if (nums.size()==0) return -1;
bool flag= false;
int res = -1;
for(int i=0;i<nums.size();i++){
if (nums[i] < 0) continue;
else if(nums[i] == i) {
flag = true;
res = i;
}
}
if(flag) return res;
else{
return -1;
}
}
};


daniellee
2019-04-10 13:22

### 算法1

#### C++ 代码

class Solution {
public:
string convert(int x){
string s ="";
while(x>0){
int m  = x%10;
x/=10;
s.push_back(m+'0');
}
reverse(s.begin(),s.end());
return s;
}
string compare(string s1,string s2){
string a = s1+s2; //mn
string b = s2+s1; //nm
for (int i=0;i<a.size();i++){
if(a[i]-'0' > b[i]-'0'){
return s2;
}
else if(a[i]-0<b[i]-0){
return s1;
}
else{
continue;
}
}
return s1;
}
string printMinNumber(vector<int>& nums) {
vector<string> sw;
//vector<vector<int>> sw;

for(auto x:nums){
string s = convert(x);
sw.push_back(s);
}
string res = "";
string s2,s1,p;
for(int i=0;i<sw.size();i++){

for (int j = 0;j<sw.size()-1-i;j++){
s2 = sw[j];
s1 = sw[j+1];
p = compare(s1,s2);

if (p == s1){
sw[j+1] = sw[j];
sw[j] = p;
}

}
}
for(int i=0;i<sw.size();i++){
res+=sw[i];
}
return res;

}
};


daniellee
2019-04-10 13:19

#### C++ 代码

class Solution {
public:

int n;
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
n = input.size();
vector<int> res;
for(int i=0;i<n;i++){
if(i<k) insert(res, input[i]);
else{
if(input[i]<res[0]){
res[0]=input[i];
push_down(res, k-1, 0);
}
}
}
sort(res.begin(), res.end());
return res;
}

void push_down(vector<int> &a, int size, int u){
int t=u, l=u*2+1, r=u*2+2;
if(l<=size && a[l]>a[t]) t=l;
if(r<=size && a[r]>a[t]) t=r;
if(t!=u){
swap(a[u], a[t]);
push_down(a, size, t);
}
}

void push_up(vector<int> &a, int u){
if(!u) return;
while((u-1)/2>=0 && a[u]>a[(u-1)/2]){
swap(a[u], a[(u-1)/2]);
u=(u-1)/2;
}
}

void insert(vector<int> &a, int x){
a.push_back(x);
push_up(a, a.size()-1);
}

};