即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

算法结构和设计初步入门基础知识作业第八周

编程语言 qianggezuishuai 7℃ 0评论

303.Range Sum Query-Immutabe

Description:

Given an integer array nums, find the sum of the elements between indices
i and j (ij), inclusive

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

  1. You may assume that the array does not change.
  2. There are many calls to sumRange function.

分析:

       题意很简单,求出一个数组第i位到第j位的和。


My C++ code:

class NumArray { 
    public:     
    NumArray(vector nums) {         
        nSum.push_back(0);         
        for(auto e: nums)         
        {             
            nSum.push_back(e+nSum.back());         
            
        }     
    }      
    int sumRange(int i, int j) {         
        return nSum[j+1] - nSum[i];     
    } 
    private:     
    vector nSum; 
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */


19.Remove Nth Node From End Of List

Description:

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:


Given n will always be valid.


Try to do this in one pass.

分析:

      题目的意思是删除掉一个列表的倒数第n个数字。

My C++ code:

/** * Definition for singly-linked list.  
    * struct ListNode {  
    *     int val;  
    *     ListNode *next;  
    *     ListNode(int x) : val(x), next(NULL) {}  * };  
    */
    class Solution { 
        public:     
        ListNode* removeNthFromEnd(ListNode* head, int n) {         
            count = 0;         
            ListNode *dup_head = new ListNode(0);         
            dup_head->next = head;         
            recursive_helper(dup_head, n);         
            return dup_head->next;     }          
            void recursive_helper(ListNode* head, int n)     
            {         
                if(nullptr == head)         
                {             
                    //printf("from tail return\n");             
                    return;         
                }         
                else         
                {             
                    recursive_helper(head->next, n);             
                    if(count == n)             
                    {                 
                    //printf("deleteing, %d\n", head->next->val);                 
                    ListNode *toBeDel = head->next;                 
                    head->next = head->next->next;                 
                    delete toBeDel;             
                    }            
                    ++count;             
                    //printf("recursive return , head val %d, count %d\n", head->val, count);         
                }
            }     
        int count; 
    };



转载请注明:CodingBlog » 算法结构和设计初步入门基础知识作业第八周

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情