头像

daniellee




离线



daniellee
2019-04-16 16:27

算法1

(中序遍历) $O(n)$

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
(哈希表) $O(n+m)$

用一个哈希表记下访问过的指针

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        map<ListNode*,int> record;
        int cnt = 0;
        ListNode* h = headA; 
        while(h!=NULL){
            record[h] = 1;
            h = h->next;
        }
        h = headB;
        while(h!=NULL){
            if (record[h]) return h;
            h = h->next;
        }
        return NULL;
    }
};



daniellee
2019-04-16 16:07
(二分查找) $O(log(n))$

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

(暴力枚举) $O(n)$

保存中间结果,累乘

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)这个位置的最大价值
由于只能向下向右走,所以(i,j)这个位置只能从左边和上边过来,所以dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + grid[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

(动态规划) $O(n)$

类比爬楼梯,dp[n] = dp[n-1]+dp[n-2],dp[n]代表走到最后一个字符,能有多少多少中翻译方法
对于访问到当前的字符dp[n],能有多少中翻译?(1)当前字符翻译为1个字符这是一种方法,dp[n] = dp[n-1] (2) 当前字符呵前一个字符共同翻译为一种方法 dp[n]+=dp[n-2],此时的条件为前后两个字符可以翻译为同一个字符。还有 04,05,06,这种只能翻译为1中,其组合不能作为一种翻译。
时间复杂度分析:blablabla

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

(暴力枚举) $O(n^2)$

这题其实是定义一种比较方法,然后排序,排序的速度决定了时间复杂度
这里用的冒泡排序,可以尝试其他排序算法

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);
    }


};