28. Find the Index of the First Occurrence in a String E ！！！需要动手写

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

 

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.

 

Constraints:

• 1 <= haystack.length, needle.length <= 104
• haystack and needle consist of only lowercase English characters.

A:

就是Rabin-Karp string matching algorithm 来过滤。 有个KMP 算法，太难了，不考虑

我靠，还是出了好多处错误。

class Solution {
public:
    int strStr(string haystack, string needle) {
        int m = needle.size(), n = haystack.size();
        if(m > n){
            return -1;
        }
        // find a prime number to speed up , 797 is another good choice
        int prime = 3319;
        int vN = 0, vM = 0, rm = 1;// remainder of first letter position
        for(int i =0; i<m;i++){
            vN = (vN * 26 + (needle[i] - 'a')) % prime;
            vM = (vM * 26 + (haystack[i] - 'a')) % prime;
            if(i<m-1){
                rm = (rm*26) % prime;
            }
        }
        if(vN == vM && haystack.substr(0,m) == needle){
            return 0;
        }
        for(int i = m; i<n;i++){
            vM = (( vM - (haystack[i-m] -'a') * rm) * 26 + (haystack[i]-'a') )% prime;
            vM = (vM % prime + prime) % prime; // this is NEEDED, since VM can be negative. fuck
            if(vN == vM && haystack.substr(i-m+1, m) == needle){
                return i-m+1;
            }
        }
        return -1;
    }
};

最经典，也是下次还是容易犯错的：

就是 

            if(i<m-1){
                rm = (rm*26) % prime;
            }

这个一开始没想到。 确实是水平不行 阿。 

234. Palindrome Linked List E

Given the head of a singly linked list, return true if it is a 

palindrome

 or false otherwise.

 

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

 

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

 

Follow up: Could you do it in O(n) time and O(1) space?

A:

就是简单的读2遍，然后一个从后往前，一个从前往后。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> v;
        ListNode* runner = head;
        while(runner){
            v.push_back(runner->val);
            runner = runner->next;
        }
        runner = head;
        while(runner){
            int val = v.back();
            v.pop_back();
            if(val != runner->val){
                return false;
            }
            runner = runner->next;
        }
        return true;
    }
};

Follow up:

Could you do it in O(n) time and O(1) space?

1：  reverse后半段。

2： 利用 recursive  的call stack,来对比

227. Basic Calculator II M

 Q:

Given a string s which represents an expression, evaluate this expression and return its value. 

The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

 

Example 1:

Input: s = "3+2*2"
Output: 7

Example 2:

Input: s = " 3/2 "
Output: 1

Example 3:

Input: s = " 3+5 / 2 "
Output: 5

 

Constraints:

• 1 <= s.length <= 3 * 105
• s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
• s represents a valid expression.
• All the integers in the expression are non-negative integers in the range [0, 231 - 1].
• The answer is guaranteed to fit in a 32-bit integer.

A:

走3遍， 第一遍， 都分割， 成为list 形式的string

第二遍。  做 / * 运算

第三遍， 做 + - 运算

class Solution {
public:
    int calculate(string s) {
        // first convert s to list of symbols
        vector<string> V;
        int start = 0;
        while(start < s.length()){
            if(s[start]==' '){
                start++;
            }else if(s[start]=='/' || s[start]=='+' || s[start]=='-' || s[start]=='*'){
                V.push_back(s.substr(start,1));
                start++;
            }else{
                int end = start+1;
                while(end < s.length() && isdigit(s[end])){
                    end++;
                }
                V.push_back(s.substr(start,end-start)); //substr (expect the 2nd as length)
                start = end;
            }
        }
        vector<string> V2;
        // calcualte / * first
        for(int i =0; i<V.size(); ++i){
            if(V[i] == "*" || V[i] == "/" ){
                int tmp = 0;
                if(V[i] == "*"){
                    tmp = stoi(V2.back()) * stoi( V[i+1]);
                }else{
                    tmp = stoi(V2.back()) / stoi( V[i+1]);
                }
                V2.pop_back();
                ++i;
                V2.push_back(to_string(tmp));
            }else{
                V2.push_back(V[i]);
            }
        }

        for(int i =0; i<V2.size(); ++i){
            cout << i<< ":" << V2[i] <<endl;
        }
        int res = stoi(V2[0]);
        // calcualte + - 
        for(int i =1; i<V2.size(); ++i){
            if(V2[i] == "+" || V2[i] == "-" ){
                if (V2[i] == "+" ){
                    res += stoi(V2[i+1]);
                }else{
                    res -= stoi(V2[i+1]);
                }
                ++i;
            }
        }
        return res;
    }
};