Longest Word in Dictionary through DeletingLongest Word in DictionaryMaximum Length of Repeated SubarrayLargest Number At Least Twice of OthersReverse Linked ListFirst Missing PositiveLZH007 Longest Word in Dictionary Maximum Length of Repeated Subarray Largest Number At Least Twice of Others Reverse Linked List First Missing Positive

比较字符的大小时,若字符串a的首字符大于b的首字符则a比较大,不对后续字符进行判断。

class Solution {
public:
    string findLongestWord(string s, vector<string>& d) {
            string ans;
            for (int i = 0; i < d.size(); i++) {
                int pi = 0, pj = 0;
                for (; pi < s.size() && pj < d[i].size(); pi++) {
                    pj += s[pi] == d[i][pj];
                }
                if (pj == d[i].size() && (ans.size() < d[i].size() || (ans.size() == d[i].size() && ans > d[i])))
                    ans = d[i];
            }
            return ans;
        }
};

2018/1/22
posted in 
leetcode

Longest Word in Dictionary

class Solution {
public:
    string longestWord(vector<string>& words) {
        sort(words.begin(), words.end());  //对字符串排好序,按照字符的ascll编码,匹配字典的排序
        unordered_set<string> set;
        string res = "";
        for (int i = 0 ; i<words.size(); i++) {
            if (words[i].size()==1||set.count(words[i].substr(0,words[i].size()-1))) {
                res = words[i].size()>res.size() ? words[i]:res;
                set.insert(words[i]);
            }
        }

        return res;
    }
};

2018/1/22
posted in 
leetcode

Maximum Length of Repeated Subarray

运用了动态规划,从A的尾部,来遍历B。

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int m = A.size(), n = B.size();
        if (!m||!n) {
            return 0;
        }
        vector<int> dp(n+1); //要比B的长度多一位,在下面j=为n-1时需要获取dp[j+1]的值
        int res = 0;
        for (int i = m-1; i>=0; i--) {
            for (int j = 0; j<n; j++) {
                dp[j] = A[i]==B[j] ? dp[j+1]+1 : 0;
                res = max(res, dp[j]);
            }
        }
        return res;
    }
};

2018/1/20
posted in 
leetcode

Largest Number At Least Twice of Others

class Solution {
public:
    int dominantIndex(vector<int>& nums) {
        int max = 0, tmp = 0,index = 0;
        for (int i = 0; i<nums.size(); i++) {
            if(nums[i]>=max) {
                tmp = max;
                max = nums[i];
                index = i;
            }else if (nums[i]>tmp){
                tmp = nums[i];
            }
            if (i==nums.size()-1 && tmp*2<=max) return index;
        }
        return -1;
    }
};

2018/1/20
posted in 
leetcode

Reverse Linked List

迭代法:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        while (head) {
            ListNode* next = head -> next;
            head -> next = pre;
            pre = head;
            head = next;
        } 
        return pre;
    }
};

递归法:

class Solution {
public:   
    ListNode* reverseList(ListNode* head) {
        if (!head || !(head -> next)) return head;
        ListNode* node = reverseList(head -> next);
        head -> next -> next = head;
        head -> next = NULL;
        return node; 
    }
}; 

2018/1/19
posted in 
leetcode

First Missing Positive

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_map<int, int> map;
        int min = INT_MAX, max = 0, res = 1;
        for (int i = 0; i<nums.size(); i++) {
            if (nums[i]<=min&&nums[i]>=0) {
                min = nums[i];
            }else if (nums[i]<0) min = 0;
            if (nums[i]>=max) max = nums[i];
            map[nums[i]]++;
        }
        for (int j=min; j<=max; j++) {
            if (j==0) continue;
            if (min>=2) {
                return 1;
            }
            if (map[j]==0) {
                res = j;
                break;
            }
            if (j==max) {
                res = max+1;
            }
        }
        return res;
    }
};

2018/1/18
posted in 
leetcode