点击小箭头阅读更舒适 如果觉得卡顿,请点击小眼睛关闭蜘蛛网特效

LeetCode刷题总结(1):658,1,2,7,14,56,3,69,67,501

步入研究生,又重新拾起了算法这个老伙计。在空闲之余练习一下算法,顺便复习一下C++,也是一举两得的事情。

在此总结一下第1阶段做的题目,再定个小目标,坚持每十道题做一次记录。


658. Find K Closest Elements:

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Example 2:

Input:[1,2,3,4,5], k=4, x=-1
Output:[1,2,3,4]

Note:

  1. The value k is positive and will always be smaller than the length of the sorted array.
  2. Length of the given array is positive and will not exceed 104
  3. Absolute value of elements in the array and x will not exceed 104

UPDATE (2017/9/19):
The arr parameter had been changed to an array of integers (instead of a list of integers). Please reload the code definition to get the latest changes.

solution(滑动窗口,二分搜索)

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int left = 0;
        int right = arr.size()-k;
        while(left<right){
            int mid = left+(right-left)/2;
            if(x-arr[mid]>arr[mid+k]-x){
                left = mid+1;
            }else{
                right = mid;
            }
        }
        vector<int> result(arr.begin()+left, arr.begin()+left+k);

        return result;
    }
};

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[<b>0</b>] + nums[<b>1</b>] = 2 + 7 = 9,
return [<b>0</b>, <b>1</b>].
 solution(创建map对象,逐一比较放入vector中)
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> array;
        vector<int> result;

        for(int i = 0;i < nums.size(); i ++)
        {
            array[nums[i]] = i;
        }
        for(int i = 0;i < nums.size(); i ++)
        {
            result.push_back(i);
            int dif = target - nums[i];
            if(array.find(dif) != array.end() && i != array[dif])
            {
                result.push_back(array[dif]);
                return result;
            }   
            else
                result.pop_back();

        }
    }
};

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

 solution:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            ListNode* dummyHead = new ListNode(0);
    ListNode* p = l1;
    ListNode* q = l2;
    ListNode* curr = dummyHead;
    int carry = 0;

    while(p != NULL || q != NULL)
    {
        int x = (p != NULL)? p->val:0;
        int y = (q != NULL)? q->val:0;
        int sum = carry + x + y;
        carry = sum/10;
        curr->next = new ListNode(sum%10);
        curr = curr->next;
        if(q != NULL) q = q->next;
        if(p != NULL) p = p->next;
    }

    if(carry > 0)
    {
        curr->next = new ListNode(carry);
    }
    return dummyHead->next;
        
    }
};

7. Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output:  321

Example 2:

Input: -123
Output:-321

Example 3:

Input: 120
Output:21

Note:
Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

solution:

class Solution {
public:
    int reverse(int x) {
        int begin_number = 0;
        if(x < 0)
            begin_number = -x;
        else
            begin_number = x;
        int tmp = begin_number;
        int number_length = 0;
        int64_t return_number = 0;
        vector<int> num(10);
        for(int i = 0;i < 10; i++)
        {
            num[i] = tmp%10;
            number_length ++;
            if((tmp = tmp/10) == 0)
                break;

        }
        for(int i = 0;i < 10; i++)
        {
            return_number += num[i]*pow(10,number_length-1);
            number_length --;
            if(number_length < 0)
                break;
        }

        if((int64_t)((int32_t)return_number) != return_number)
        {
            return 0;
        }

        if(x < 0)
            return -(int32_t)return_number;
        else
            return (int32_t)return_number;
    }
};

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

class Solution {
public:
    uint32_t mymin(const uint32_t x, const uint32_t y)
    {
    return x<y? x: y;
    }
    bool isCommonPrefix(vector<string>& strs, int len)
    {
        string str1 = strs[0].substr(0, len);
        for(int i = 1; i < strs.size(); i++)
            if(strs[i].compare(0,len,str1) != 0)
                return false;
        return true;
    }

    string longestCommonPrefix(vector<string>& strs)
    {
        if(strs.empty())
            return "";
        uint32_t minlen = INT_MAX;
        for(uint32_t i = 0; i < strs.size(); i ++)
        {
            minlen = mymin(minlen, (uint32_t)strs[i].length());
        }
        uint32_t low = 1;
        uint32_t high = minlen;
        while (low <= high)
        {
            uint32_t middle = (low + high) / 2;
            if(isCommonPrefix(strs, middle))
                low = middle + 1;
            else
                high = middle - 1;
        }
        return strs[0].substr(0, (low + high) / 2);
    }
};

56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        auto length = intervals.size();
        Interval temp;
        for(int i = 0; i < length; i ++)
        {
            if(intervals[i].end < intervals[i+1].start)
                temp.start = intervals[i].start;
                temp.end = intervals[i+1].end;
                
        }
            
    }
};

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring"pwke" is a subsequenceand not a substring.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        set<char> char_container;
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            if (char_container.find(s.at(j)) == char_container.end()){
                char_container.insert(s.at(j++));
                ans = max(ans, j - i);
            }
            else {
                char_container.erase(s.at(i++));
            }
        }
        return ans;
    }
};

69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Input: 4
Output: 2

Example 2:

Input:8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.
public int sqrt(int x) {
    if (x == 0)
        return 0;
    int left = 1, right = Integer.MAX_VALUE;
    while (true) {
        int mid = left + (right - left)/2;
        if (mid > x/mid) {
            right = mid - 1;
        } else {
            if (mid + 1 > x/(mid + 1))
                return mid;
            left = mid + 1;
        }
    }
}

67. Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

class Solution {
public:
    string addBinary(string a, string b)
    {
   string s = "";

    int c = 0, i = a.size() - 1, j = b.size() - 1;
    while(i >= 0 || j >= 0 || c == 1)
    {
        c += i >= 0 ? a[i --] - '0' : 0;
        c += j >= 0 ? b[j --] - '0' : 0;
        s = char(c % 2 + '0') + s;
        c /= 2;
    }

    return s;
        
    }
};

501. Find Mode in Binary Search Tree

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
  • Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

   1
    \
     2
    /
   2

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

/**
 * 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:
    vector<int> modes;
    void getMaxFre(TreeNode* r, int& max_fre, int& last_value, int& cur_fre)
    {
        if(!r) return;
        getMaxFre(r->left, max_fre, last_value, cur_fre);
        getMaxFre(r->right, max_fre=max(max_fre,cur_fre), last_value=r->val, ++(cur_fre*=(r->val==last_value)));
    }
    void getMode(TreeNode* r,const int max_fre, int& last_value,int& cur_fre)
    {
        if(!r) return;
        getMode(r->left, max_fre, last_value, cur_fre);
        if(max_fre == ++(cur_fre*=(r->val==last_value))) modes.push_back(r->val);
        getMode(r->right, max_fre, last_value=r->val, cur_fre);
    }
    vector<int> findMode(TreeNode* root) 
    {
        int maxfrequent = 0;
        int curfrequent = 0;
        int last_value = 0;
        getMaxFre(root, maxfrequent=0, last_value, curfrequent=0);  
        getMode(root, maxfrequent, last_value, curfrequent=0);      
        return modes;
    }
    
};

 

 

  点赞
本篇文章采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
转载请务必注明来源: https://oldpan.me/archives/leetcode-sum1

   欢迎关注Oldpan博客微信公众号,同步更新博客深度学习文章。


发表评论

电子邮件地址不会被公开。 必填项已用*标注

评论审核已启用。您的评论可能需要一段时间后才能被显示。