61. 旋转链表

https://leetcode.cn/problems/rotate-list/

做法:

注意:k的值可能大于链表长度n, 每个节点右移n个单位,相当于原链表没有改变! 所以k%=n才是真实要右移的位置

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head || k<0) return head;
        //1.找尾节点,顺便统计长度
        ListNode* cur = head;
        int n = 1;
        while(cur->next)
        {
            n++;
            cur = cur->next;
        }
        //2.首尾链接成环
        cur->next = head;
        //3.成环后,从原来尾节点位置cur往后走n-k步找到分段点   
        k%=n;//每移动n个位置恢复原状 
        for(int i = 0;i<n-k;i++)
        {
            cur = cur->next;
        }
        //4.更换头节点位置 + 分段点前后断开
        head = cur->next;
        cur->next = nullptr;
        //5.返回旋转后的结果
        return head;
    }
};

1. 两数之和

https://leetcode.cn/problems/two-sum/

方法1:暴力 -O(N^2)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i = 0;
        int j = 0;
        vector<int> ans;
        for(int i = 0;i<nums.size();i++)
        {
            //j从i+1位置开始找
            for(int j = i+1;j<nums.size();j++)
            {
                //寻找目标值target
                if(nums[i]+nums[j] == target)
                {
                    ans.push_back(i);
                    ans.push_back(j);
                    break;
                }
            }
        }
        return ans;
    }
};

方法2:使用map,key-value为:元素值-下标
遍历到i下标位置的元素x,先查找map中是否含target-x这个元素

• 如果有:那么x + target-x = target, 返回此时i位置和此时map中该元素的第二个成员
• 如果没有:就把当前{i,x}新插入到map中,为后序寻找做准备

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        map<int,int> m;//值nums[i]- 下标i
        vector<int> v;//存放结果
        for(int i = 0;i<nums.size();i++)
        {
            //当前元素nums[i]
            //在map中查找是否有target-nums[i]这个值
            auto it = m.find(target-nums[i]);
            if(it != m.end()) 
            {
                //如果找到了,返回当前i位置和map中此元素第二个成员的下标
               v.push_back(it->second);
               v.push_back(i);
               break;
            }
            //没有找到,在map中插入键值对:当前元素值 - 当前元素下标
            m.insert(make_pair(nums[i],i));   //没有找到 -> 插入当前元素
        }
        return v;//返回空容器
    }
};