精华内容
下载资源
问答
  • C++双指针示例

    2017-11-11 14:57:09
    C++双指针的展示,想进阶C++的可以看一下,如果看懂了对指针的理解会有一个新的高度
  • } // 也可以做一个字典, 字典只需要遍历一遍即可, 不需要排序, 而双指针需要排序, 相当于遍历两遍 void solution2(vector<int> numbers, int target){ map,int> personnel; for(int i=0; i(); i++){ int sum = ...

    一. 归并有序序列

    LeetCode 88题

    input: 	nums1 = {2,2,3,0,0,0}; m=3;  nums2 = {1,5,6}; n=3
    output: nums1 = {1,2,2,3,5,6}
    require: 时间O(n) 内存O(1)
    

    1.1 总结:

    在这里插入图片描述

    1.2 代码

    #include <iostream>
    #include <stdio.h>
    #include <vector>
    #include <map>
    
    using namespace std;
    
    // 归并两个有序数组
    // 加上&参数传递的是地址, 这样就可以改变参数的值, 因为题目要求是在数组nums1上进行排序
    void solution(vector<int>& nums1, int m, std::vector<int> nums2, int n){
    	for(auto i: nums1)cout<<i<<" "; cout<<endl;
    	int pos=nums1.size()-1;// 这里也可以是m+n-1
    	m--;
    	n--;
    	while(m>=0 && n>=0){
    		nums1[pos--] = nums1[m] <= nums2[n] ? nums2[n--]:nums1[m--];
    	}
    	while(n>=0){ 
    	//这里是因为如果num1还有剩余, 那么num1前面的因为已经排好序那自然是没毛病了, 
    	// 但是num2还有剩余, 就需要转移到num1中
    		nums1[pos--] = nums2[n--];
    	}
    }
    
    
    
    int main(int argc, char const *argv[])
    {
    	std::vector<int> nums1 = {2,2,3,0,0,0};
    	std::vector<int> nums2 = {1,5,6};
    
    	solution(nums1, 3, nums2, 3);
    	for(auto i: nums1)cout<<i<<" "; cout<<endl;
    	printf("%s\n", "hello");
    	return 0;
    }
    

    二. 两数之和

    LeetCode 167题

    input: 	nums1 = {1,2,3,4,5,7}; target=9
    

    2.1 总结:

    在这里插入图片描述

    2.2 代码

    #include<iostream>
    #include<algorithm>
    #include<vector>
    #include<stdio.h>
    #include <map>
    
    using namespace std;
    void print_vector(vector<int> numbers){
        for(auto c : numbers) cout<< c <<" ";cout<<endl;
    }
    
    // 使用&, 指的是函数参数传递进来的可以被改变,引用传递,  int a, func(a) func(int &a){a=100}
    // 使用*, 指的是参数即为指针, int a, func(&a) func(int *a){*a=100}
    int solution1(vector<int> numbers, int target){
        print_vector(numbers);
        sort(numbers.begin(), numbers.end());
        int sum, i=0,j=numbers.size()-1;
        while (i<j){
            sum= numbers[i]+numbers[j];
            if (sum>target) {j--; }
            else if(sum==target) {break; }
            else {i++;}
        }
        print_vector(numbers);
        printf("%d = %d+%d\n", target, numbers[i], numbers[j]);
    }
    
    // 也可以做一个字典, 字典只需要遍历一遍即可, 不需要排序, 而双指针需要排序, 相当于遍历两遍
    void solution2(vector<int> numbers, int target){
        map<int,int> personnel;
        for(int i=0; i<numbers.size(); i++){
            int sum = target-numbers[i];
            if (personnel.find(sum) == personnel.end()){
                personnel.insert(pair<int, int>(numbers[i],i));
            }else{
                printf("%d = %d+%d\n", target, numbers[i], personnel.find(sum)->first);
            }
        }
    }
    // python解法
    // numbers = [1,2,4,5,7]
    // target = 9
    
    // map1 = {}
    // for i,numb in enumerate(numbers):
    //     if map1.get(target-numb)==None:
    //     	map1[numb] = i
    //     else:
    //     	print(numb, target-numb)
    
    
    int main(int argc, char const *argv[])
    {
        vector<int>numbers = {2,7,11,15,1,2};
    
        solution1(numbers, 9);
        solution2(numbers, 9);
        cout<<"hello" <<endl;
        return 0;
    }
    

    三. Floyd算法

    LeetCode 142题

    • 给定一个链表, 判断是否存在环路, 存在则返回环路入口节点
      在这里插入图片描述
      找到2的所属节点

    总结: 这题太重要了, 一个Floyd算法的数学证明和单链表的各种基础操作

    3.1 总结

    在这里插入图片描述

    3.2 代码

    注意: 这里包含单链表的基础操作

    #include <stdio.h>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    struct ListNode {
    	int val;
    	ListNode *next;
    	ListNode(int x) : val(x), next(nullptr) {} // 这里默认Node的next是nullptr
    };
    
    
    // Floyd算法, 找到环路起点
    ListNode *detectCycle(ListNode *head){
    	ListNode *slow=head;
    	ListNode *fast=head;
    	int i=20;
    	// fast:slow=2:1的速度前进, 如果fast到达终点, 则没有环路, 
    	// 否则等二者相遇, fast回归起点, 1:1速度进行,二次相遇后, 为起始点
    	while(fast && fast->next){
    		fast = fast->next->next; //因为while入口已经确定fast->next存在, 那么fast->next的next至少至少也是nullptr格式, 因为结构体定义部分定义的, 所以这里fast->next->next;不会越界
    		slow = slow->next;
    		if(fast == slow){ //第一次相遇
    			fast = head;
    			while(fast!=slow){
    				slow = slow->next;
    				fast = fast->next;
    			}
    			cout<<"\n带环最终结果是"<<fast->val<<endl;
    			return fast; //第二次相遇
    		}
    	}
    	cout<<"没有环"<<endl;
    	return nullptr;
    }
    
    int main(int argc, char const *argv[])
    {
    	ListNode *head, *end; //创建两个节点
    	head=(ListNode*)malloc(sizeof(ListNode)); //给头节点先开辟个空间
    
    	// 创建节点,并赋值
    	ListNode *normal=(ListNode*)malloc(sizeof(ListNode)); //创建临时节点
    	normal->val = 28; //给临时节点赋值
    	head->next = normal; //临时节点链接到头节点
    	end = head->next;  
    	for(int i=0; i<11; i++){ //链表的插入
    		ListNode *a=(ListNode*)malloc(sizeof(ListNode));
    		a->val = i;
    		end->next = a;
    		end = end->next;
    		// cout<<end->val<< endl;
    	}
    	
    
    	cout<<"打印当前链表内容: 0 28 0 1 2 3 4 5 6 7 8 9"<<endl;
    	detectCycle(head);
    
    	end->next = normal; // 加上一个圆环
    
    	ListNode *a = head;
    	cout<<"打印一下带环链表内容,"<<endl;
    	for(int i=0; i<20; i++){
    		cout<<a->val<<" ";
    		a = a->next;
    	}
    
    	detectCycle(head);
    	cout<<"hello" <<endl;
    	return 0;
    }
    

    四. 最长不重复子串(滑动窗口)

    LeetCode 3题

    input  = 'acbva'
    output = "acbv"或者"cbva"
    output = 4
    
    最长不重复子串解题技巧: 
    设定左右两指针, 指向窗口找最大
    如若窗口有重复, 集合删左左在进
    

    4.1 总结

    在这里插入图片描述

    4.2 代码

    注意这里使用一个字典, 集合, 列表其实都可以, 只要能判定元素是否在列表中, 能删除列表的第一位即可

    #include <vector>
    #include <iostream>
    #include <stdio.h>
    #include <algorithm>
    #include <set>
    using namespace std;
    
    // 问题描述: 
    // 不重复最长子串
    // 输入 'acbva'
    // 找到这串里面最长的不重复的子串, 如果是acbva, 这是子序列, 
    // 只有不重复的才是子串, 则acbv是子串, acbv或者cbva是不重复最长子串
    
    // -----------解题关键: 就是创建一个数组, 集合, 字典, 用来装窗口内是否有重复, 
    // -------------如果有重复就左指针右移, 没有就右右移
    
    // 最长不重复子串解题技巧: 
    // 设定左右两指针, 指向窗口找最大
    // 如若窗口有重复, 集合删左左在进
    string solution_set(string s){ //acbva
    	cout << "\n需要找的最长子串是"<<s<<endl;
    	set<char> set_swap;
    	int max_len = 0;
    	int left=0, right=0;
    	while(right<s.size()){
    		// set_swap保存的是s[left, right]不重复的数据呀
    		if(0 == set_swap.count(s[right])){ // 确定没s[right], 就是加入s[right]依然没有重复的, 则将s[right]加入到字典, 
    			set_swap.insert(s[right++]);
    			if(max_len < right-left){
    				for(set<char>::iterator iter = set_swap.begin(); iter!=set_swap.end(); iter++){
    					cout<<*iter<<"  ";
    				}cout<<endl;				
    			}
    			max_len = max(max_len, right-left);
    		}
    		else{ // 如果有重复的, 那就删除
    			set_swap.erase(s[left++]);
    		}
    	}
    	printf("最长子串是: %d\n", max_len);
    	string res = "";
    	return res;
    }
    
    string solution_vector(string s){
    	string res = "";
    	std::vector<char> v_swap;
    	std::vector<string> v_res;
    	int left=0, right=0, max_len=0;
    	while(right < s.size()){
    		if (0 == std::count(v_swap.begin(), v_swap.end(), s[right])){
    			v_swap.push_back(s[right++]);
    			if (max_len<right-left){ // 打印结果
    				for(auto i:v_swap){
    					cout<<i<<" ";
    				}cout<<endl;
    			}
    			max_len = max(max_len, right-left);
    		}
    		else{
    			v_swap.erase(v_swap.begin(),v_swap.begin()+1); // 删除列表中的第一个
    			left++;
    		}
    	}
    	cout<<"输入"<<s<<" 结果是:"<<max_len<<endl;
    	return res;
    }
    
    int main(int argc, char const *argv[])
    {
    	string s = "11334566";
    	string res = solution_set(s);
    	// string res = solution_vector(s);
    	cout<< "hello world" <<endl;
    	return 0;
    }
    

    五. 最短覆盖子串(滑动窗口)

    LeetCode 76题

    input:   S = "ADOBECODEBANC";  T = "ABC";
    output:  res = BANC
    

    5.1 总结

    这里需要注意的是:
    创建一个能够统计目标字符的字典, 这样就可以在每次判断每一个字符是否是多余的, 对窗口去冗余极其重要
    在这里插入图片描述

    5.2 代码

    a. python实现

    import sys,os
    # 核心思路:  找到目标窗口, 然后去除冗余, 完成
    # 右指针向右, 直到遇到全部T,
    # 左指针向右, 直到最短子串S1出现, 给临时最优
    # 左指针在向右, 此时窗口没有目标子串, 此时右指针向右,右指针 
    # 
    # 最短目标子串解题技巧: 
    # 设定左右两指针, 指向窗口找目标
    # 窗有冗余左进右, 无余左进等右尽
    # 
    # 注意滑动窗口就是目标值
    def solution(S, T):
        # print(S, T)
        if len(S)<len(T):
            return ""
        window = "" 
        result = ""
        need = {}
        for _ in T:need[_] = 1 if _ not in need else need[_]+1
        needCnt = len(T)
        for c in S:
            if c in need:
                if need[c]>0:
                    needCnt-=1
                need[c]-=1
            window+=c
            if needCnt == 0: # 窗口已经满足, 可以去冗余, 这个时候, need里面的值, 有可能是-2, 如AAABC
                while True:
                    if window[0] in T: # 窗口最左是目标字符
                        if need[window[0]] <0: # 字符没用, 左指针右移
                            need[window[0]] += 1
                            window = window[1:]
                        elif need[window[0]] == 0: # 关键 表示正好, 此时左右没有冗余, 此时左指针向右移动一个后, 整个窗口就不完整了, 进行下一轮
                            if result:
                                if len(window)<len(result):
                                    result = window 
                            else:
                                result = window
                            need[window[0]] += 1
                            window = window[1:]
                            needCnt += 1
                            break
                    else: # 这里是最左的字符是垃圾, 直接去掉即可
                        window = window[1:]
        print("结果是: ",result)
        return result
    
    if __name__ == '__main__':
        solution("ADOBECODEBANC", "ABC")
    # // Input: S = "ADOBECODEBANC", T = "ABC"
    # // Output: "BANC"
    

    b. C++实现

    #include <iostream>
    #include <algorithm>
    #include <stdio.h>
    #include <vector>
    #include <sstream> // 为了使用stringsteam
    using namespace std;
    
    
    // 题目描述: 给定字符串S,T, 求S中包含T所有字符的最短连续子字符串的长度, 时间复杂度不能超过O(n)
    // 输入样例: 
    // Input: S = "ADOBECODEBANC", T = "ABC"
    // Output: "BANC"
    
    
    // 解题思路: 双指针(前后指针)指向开始, 如果没有遇到T中的字符串, 
    // 双指针同时向后移动, 遇到一个以后, 后指针继续, 知道遇到全部T, 
    // 将当前前后指针指向子串给临时最优, 
    // 核心: 当窗口不满足要求的时候, 就向右拓宽边界
    string solution(string S, string T){
    	cout<<S<<"里面找"<<T<<endl;
    	vector<int> chars(128, 0);     //计数需要查找的字符个数, 比如AABBA 则需要找到三个A两个B
    	vector<bool> flag(128, false); //标记都有哪几个字符需要查找
    	// 先统计T中的字符情况
    	for(int i = 0; i < T.size(); ++i) {
    		flag[T[i]] = true;
    		++chars[T[i]];
    	}
    
    	// 移动滑动窗口,不断更改统计数据
    	int cnt = 0, left = 0, min_l = 0, min_size = S.size() + 1;
    	for (int right = 0; right < S.size(); ++right) {
    		if (flag[S[right]]) { // 如果当前right所指字符是待查找字符
    			if (--chars[S[right]] >= 0) { // 且当前该字符还没查完, 那就计数加
    				++cnt;
    			}
    			// 若目前滑动窗口已包含T中全部字符,
    			// 则尝试将l右移,在不影响结果的情况下获得最短子字符串
    			while (cnt == T.size()) {
    				if (right - left + 1 < min_size) { // 缩短长度
    					min_l = left;
    					min_size = right - left + 1;
    				}
    				if (flag[S[left]] && ++chars[S[left]] > 0) {
    					--cnt;
    				}
    				++left;
    			}
    		}
    	}
    	return min_size > S.size()? "": S.substr(min_l, min_size);
    }
    int main(int argc, char const *argv[])
    {
    	string S = "ADOBECODEBANC";
    	string T = "ABC";
    	string res = solution(S,T);
    	cout << res << endl;
    	return 0;
    }
    
    展开全文
  • C++双指针技巧

    千次阅读 2019-08-06 16:38:36
    通常,我们只使用从第一个元素开始并在最后一个元素结束的一个指针来进行迭代。 但是,有时候,我们可能需要同时使用两个指针来进行迭代。 典型例子 反转数组中的元素。 其思想是将第一个元素与末尾进行交换,再...

    来源:https://leetcode-cn.com/explore/learn/card/array-and-string/201/two-pointer-technique/782/
    通常,我们只使用从第一个元素开始并在最后一个元素结束的一个指针来进行迭代。 但是,有时候,我们可能需要同时使用两个指针来进行迭代。

    场景一

    一、同步指针:从两端向中间迭代数组。

    典型例子 反转数组中的元素

    其思想是将第一个元素与末尾进行交换,再向前移动到下一个元素,并不断地交换,直到它到达中间位置。

    我们可以同时使用两个指针来完成迭代:一个从第一个元素开始,另一个从最后一个元素开始。持续交换它们所指向的元素,直到这两个指针相遇。

    void reverse(int *v, int N) {
        int i = 0;
        int j = N - 1;
        while (i < j) {
            swap(v[i], v[j]);
            i++;
            j--;
        }
    }
    

    场景一总结

    这时你可以使用双指针技巧:
    一个指针从始端开始,而另一个指针从末端开始。
    值得注意的是,这种技巧经常在排序数组中使用。

    场景二

    有时,我们可以使用两个不同步的指针来解决问题。

    示例

    让我们从另一个经典问题开始:

    给定一个数组和一个值,原地删除该值的所有实例并返回新的长度。
    

    如果我们没有空间复杂度上的限制,那就更容易了。我们可以初始化一个新的数组来存储答案。如果元素不等于给定的目标值,则迭代原始数组并将元素添加到新的数组中。

    实际上,它相当于使用了两个指针,一个用于原始数组的迭代,另一个总是指向新数组的最后一个位置。

    重新考虑空间限制

    现在让我们重新考虑空间受到限制的情况。

    我们可以采用类似的策略,我们继续使用两个指针:一个仍然用于迭代,而第二个指针总是指向下一次添加的位置。

    以下代码可以供你参考:

    int removeElement(vector<int>& nums, int val) {
        int k = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != val) {
                nums[k] = nums[i];
                ++k;
            }
        }
        return k;
    }
    

    在上面的例子中,我们使用两个指针,一个快指针 i 和一个慢指针 k 。i 每次移动一步,而 k 只在添加新的被需要的值时才移动一步。

    场景二总结

    这是你需要使用双指针技巧的一种非常常见的情况:

    同时有一个慢指针和一个快指针。
    解决这类问题的关键是

    确定两个指针的移动策略
    与前一个场景类似,你有时可能需要在使用双指针技巧之前对数组进行排序,也可能需要运用贪心想法来决定你的运动策略。

    场景一例题

    反转字符串

    Write a function that reverses a string. The input string is given as an array of characters char[].

    Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

    You may assume all the characters consist of printable ascii characters.
    Example 1:

    Input: [“h”,“e”,“l”,“l”,“o”]
    Output: [“o”,“l”,“l”,“e”,“h”]
    Example 2:

    Input: [“H”,“a”,“n”,“n”,“a”,“h”]
    Output: [“h”,“a”,“n”,“n”,“a”,“H”]

    思路一 内置函数法

    class Solution {
    public:
    	void reverseString(vector<char>& s) {
    		reverse(s.begin(), s.end());
    	}
    };
    

    思路二

    定义 swap函数,加快运算速度 和省内存。
    class Solution {
    public:
    	void reverseString(vector<char>& s) {
    		int M = 0;
    		int N = s.size()-1;
    		char tmp;
    		while (M < N)
    		{
    			swap(s[M], s[N]);
    			M++;
    			N--;
    		}
    	}
    	void swap(char& a, char& b) { char tmp = a; a = b; b = tmp; }
    };
    

    数组拆分 I
    Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

    Example 1:
    Input: [1,4,3,2]

    Output: 4
    Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
    Note:
    n is a positive integer, which is in the range of [1, 10000].
    All the integers in the array will be in the range of [-10000, 10000].

    排序后,相邻的两数之间组合。

    class Solution {
    public:
    	int arrayPairSum(vector<int>& nums) {
    		sort(nums.begin(), nums.end());
    		for (int i = 1; i < nums.size(); i += 2)
    			nums[i] = 0;
    		return accumulate(nums.begin(),nums.end(),0);
    	}
    };
    

    场景二例题

    移除元素

    Given an array nums and a value val, remove all instances of that value in-place and return the new length.

    Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

    The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

    Example 1:
    
    Given nums = [3,2,2,3], val = 3,
    
    Your function should return length = 2, with the first two elements of nums being 2.
    
    It doesn't matter what you leave beyond the returned length.
    
    Example 2:
    
    Given nums = [0,1,2,2,3,0,4,2], val = 2,
    
    Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
    
    Note that the order of those five elements can be arbitrary.
    
    It doesn't matter what values are set beyond the returned length.
    
    Clarification:
    
    Confused why the returned value is an integer but your answer is an array?
    
    Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
    
    Internally you can think of this:
    
    // nums is passed in by reference. (i.e., without making a copy)
    int len = removeElement(nums, val);
    
    // any modification to nums in your function would be known by the caller.
    // using the length returned by your function, it prints the first len elements.
    for (int i = 0; i < len; i++) {
        print(nums[i]);
    }
    

    思路:双指针,一指针遍历数组,一指针从尾部往前移动与删除数字交换。

    class Solution {
    public:
    	int removeElement(vector<int>& nums, int val) {
    		int k=0;
    		if (nums.size() < 1)
    			return 0;
    
    		int m = nums.size() - 1;
    		for (int i = 0; i <=m;)
    			if (nums[i] != val)
    			{
    				k++;
    				i++;
    			}
    			else
    			{
    				nums[i] = nums[m];
    				m--;
    			}
    		return k;
    	}
    };
    

    最大连续1的个数

    给定一个二进制数组, 计算其中最大连续1的个数。

    示例 1:

    输入: [1,1,0,1,1,1]
    输出: 3
    解释: 开头的两位和最后的三位都是连续1,所以最大连续1的个数是 3.
    注意:

    输入的数组只包含 0 和1。
    输入数组的长度是正整数,且不超过 10,000。

    class Solution {
    public:
    	int findMaxConsecutiveOnes(vector<int>& nums) {
    		int max = 0;
    		int k = 0;
    		for (int i = 0; i < nums.size(); i++)
    			if (nums[i] == 1)
    			{
    				k++;
    				if (k > max)
    					max = k;
    			}
    			else
    				k = 0;		
    		return max;
    	}
    };
    

    长度最小的子数组

    给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。

    示例:

    输入: s = 7, nums = [2,3,1,2,4,3]
    输出: 2
    解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
    进阶:

    如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

    思路一(双指针)
    一个指针子数组起始位置循环遍历,一个指针嵌套寻找子数组结尾位置,得到每个位置的最短子数组,记录最短长度实现>s的子数组.首先通过求和判断是否存在符合<s的子数组,复杂度为O(n^2) 408ms。

    class Solution
    {
    public:
    	int minSubArrayLen(int s, vector<int>& nums)
    	{
    		if (accumulate(nums.begin(), nums.end(),0)<s)
    			return 0;
    			
    		int minlen = nums.size();
    		for (int i = 0; i < nums.size(); i++)
    		{
    			int sum = 0;
    			for (int j = i; j < nums.size(); j++)
    			{	
    				sum += nums[j];
    				if (sum >= s)
    				{
    					if (j - i + 1 < minlen)
    						minlen = j - i + 1;
    					break;
    				}
    			}
    			if (minlen <= 1)
    				break;			
    		}
    		return minlen;
    	}
    };
    

    改进思路一
    对当前minlen来说,后续的任何检索的字串长度都小于minlen,长于minlen的不考虑。提升较小,仍未O(n^2) 420 ms

    class Solution
    {
    public:
    	int minSubArrayLen(int s, vector<int>& nums)
    	{
    		if (accumulate(nums.begin(), nums.end(), 0) < s)
    			return 0;
    
    		int minlen = nums.size();
    		for (int i = 0; i < nums.size(); i++)
    		{
    			int sum = 0;
    			for (int j = i; j-i < minlen&&j<nums.size(); j++)
    			{
    				sum += nums[j];
    				if (sum >= s)
    				{
    					if (j - i + 1 < minlen)
    						minlen = j - i + 1;
    					break;
    				}
    			}
    			if (minlen <= 1)
    				break;
    		}
    		return minlen;
    	}
    };
    

    改进思路二(滑动窗口)
    思想:贪心算法,它可以帮助我们设计指针的移动策略,尽量不进行重复的加法,以一定的准则去移动指针。
    实现方法:根据sum<s是否成立决定移动哪个指针。过程中记录minlen.
    不移动重复的指针,因此复杂度O(n) 结果 8 ms。

    指针移动方法(不包含minlen更新和判断):
    while(true)
    {
    if sum>=s
    移动左指针
    更新sum
    if sum < s
    移动右指针,更新sum,至满足sum>s,若不能移了,则break;
    }

    class Solution
    {
    public:
    	int minSubArrayLen(int s, vector<int>& nums)
    	{
    		if (accumulate(nums.begin(), nums.end(), 0) < s)
    			return 0;
    
    		int minlen = nums.size();
    		int b=0, e;
    		int sum = 0;
    		for (int i = 0; i < nums.size(); i++)
    		{
    			sum += nums[i];
    			if (sum >= s)
    			{
    				e = i;				
    				break;
    			}
    		}
    		minlen = e - b + 1;
    		while (b!=nums.size()-1)
    		{	
    			sum -= nums[b++];
    			if (sum >= s && e - b + 1 < minlen)
    				minlen = e - b + 1;
    			else if (sum < s)
    			{
    				if (++e > nums.size() - 1)
    					break;
    				sum += nums[e];
    			}
    				
    		}
    
    		return minlen;
    	}
    };
    

    改进思路三
    O(n log n) 时间复杂度,用二分。因为问题是找到合适的长度的子数组长度,因此只需对子数组的长度是否符合要求使用二分法。使用后若满足则缩小窗口,否则扩大窗口。判断长度是否符合要求的函数的复杂度为O(n),二分法复杂度为O(logn);

    展开全文
  • c++双指针的初始化

    千次阅读 2018-07-23 10:27:15
    双指针初始化: 字符串双指针初始化: char **text = new char*[512]; for (int i = 0; i &lt; 512; i++) { text[i] = new char[1024]; } 整型双指针初始化: int **temp; int i = 0; //初始化 temp ...

    双指针初始化:
    字符串双指针初始化:

    char **text = new char*[512];
        for (int i = 0; i < 512; i++)
        {
            text[i] = new char[1024];
        }

    整型双指针初始化:

    int **temp;
    
    int i = 0;
    
    //初始化
    
    temp = new int*[100];
    
    for(i = 0; i < 100; i++)
    
      temp[i] = new int[200];
    
    //释放
    
    for(i = 0; i < 100; i++)
    
      delete []temp[i];
    
    delete []temp;

    可以理解为temp[100][200];

    展开全文
  • c++双重指针数组

    2018-11-25 22:29:36
    c++指针数组在使用的时候更加体现其“指针”的特性。 #include &lt;iostream&gt; using namespace std; int main (int argc, const char* argv[]) { int** arrp; int arr[4][5]; arrp = new int* [4]; ...

    c++指针数组在使用的时候更加体现其“指针”的特性。

    #include <iostream>
    using namespace std;
    int main (int argc, const char* argv[]) {
        int** arrp;
        int arr[4][5];
        arrp = new int* [4];
        for (int i = 0; i != 4; ++i) {
            arrp[i] = new int[5];
        }
        cout << sizeof(*arrp) << endl;	//8
        cout << sizeof(int*) << endl;	//8
        cout << sizeof(*arr) << endl;	//20
        for (int i = 0; i != 4; ++i) {
            delete[] arrp[i];
        }
        delete[] arrp;
        return 0;
    }
    }
    
    展开全文
  • C++双指针与指针引用详解例程

    千次阅读 2013-04-15 13:14:31
    // Class01.cpp : Defines the entry point for the console application...*并在主函数中用一个指针来指向 *注意必须是传地址,否则一旦函数结束则将被释放 */ #include "stdafx.h" #include #include //#defi
  • 1、题目描述 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 2、代码详解 class Solution(object): def longestPalindrome(self, s): res = "" for i in range(len(s)): ...
  • 通过二级指针对二叉树进行创建,不使用二级指针对树进行创建。
  • 引用博文:...当指针作为函数参数传递时,在函数内部重新申请了一个新指针,与传入指针指向相同地址。在函数内部的操作只能针对指针指向的值。#include &lt;iostream&gt; using namespace st...
  • C++双指针法

    2020-11-19 18:57:28
    使用双指针思路可以大大降低算法时间复杂度。 实例 题目描述 求一个有序数组中和=8的下标。 解题思路 设置两个不同的指针 ,或者头,或者尾。在一个递增的序列中,根据结果分类,判断指针的下一步应该怎么移动。 ...
  • 详细的讨论了指针,解引用,取地址,引用,二级指针
  •     #include using namespace std;... // 将子类地址传入指针数组,直接调用子类方法 A *ptr[3] = {&a,&b,&c}; for(int i=0; i; i++) { ptr[i]->abc(); } return 0; }  
  • 我用java调用c++的函数,函数中用到了一个双指针作为参数,我应该怎么样传入一个双指针的变量,java中没有指针的概念
  • 双指针”法解决链表问题

    千次阅读 2018-04-02 22:14:51
     “双指针”就是用一个快指针一个慢指针同时进行单链表的顺序扫描。如此就可以使用快指针的时间差给慢指针提供更多的操作信息。下面是两个LeetCode下的习题。(1)给定一个链表,删除链表的倒数第 n 个节点并返回...
  • C++探索指针,双重指针,引用

    千次阅读 2017-09-16 23:00:23
    当我们的函数的参数有指针时: void change(int *_a,int &b){ _a=&b; } void main(){ int a=10,b=20; int *p_a=&a; change(p_a,b); printf("%d",*p_a); } 输出为:10 其实系统有一个隐含的操作,...
  • C++指针的作用

    2020-09-08 17:13:38
    1.指针允许你以更简洁的方式引用大的数据结构 程序的数据结构从原子级别的数据结构:整型、浮点型、字符型、枚举型,到分子级别的数组、结构体(又称为“记录”),再到数据结构中的队列、栈、链表、树等,无论如何...
  • C++双重指针的区别

    2019-09-03 20:55:09
    #include <iostream> using namespace std; struct ListNode { int m_nValue; ListNode* m_pNext; }; void AddToTail(ListNode** pHead, int val) { ListNode* pNew = new ListNode...m_pNext ...
  • C++指针的使用艺术

    2016-01-26 14:18:47
    C++指针的使用艺术 所谓成也指针,败也指针,指针是把刃剑.
  • 双指针空间分配及释放

    千次阅读 2018-03-20 20:23:00
    需要一个3*3的数组,使用双指针的方法。Float **__K;__K = new float*[3]; for(int i = 0; i &lt; 3; i++) { __K[i]= new float[3]; memset(__K[i],0, sizeof(float) * 3); }for (int i ...
  • 初探c++内存 指针越界检测机制_CrtMemBlockHeader c++的new和delete操作,可以让我们在程序运行中动态的开辟内存空间,但是我们知道,一旦处理不好就会造成内存泄漏。一直有一个疑问,c++为防止(或者说检测)指针...
  • 双指针题算是数组类型题目的一个子模块了。 373. Partition Array by Odd and Even 把一个数组划分为奇数在前偶数在后的状态,要求in place。很简单,就用双指针法,让两个指针从两头往中间扫描,当左边是偶数右边...
  • 使用双重指针作为函数形参的例子,该例子中的实参是动态创建的双重指针形式,可以直接作为实参进行传递,如果实参只是普通的二维数组,则在做为实参的时候需要做相应地类型转换 。 #include using namespace ...
  • 而在侯捷的深入浅出MFC中第二章C++重要性质中: 1、如果你以一个"基类之指针"指向一个"派生类之对象",那么经由该指针你只能调用该基类所定义的函数 2、如果你以一个“派生类之指针”指向一个“基类之对象”,你...
  • C++双指针的作用(int**)

    千次阅读 2009-12-29 15:33:00
    为了叙述方便,下面所有的指针类型都为int * ,int ** 简单的指针的例子: int a=10; int *p=&a; //平时使用的最多的指针,是... //双指针,它的值是p的内存的地址 ---------------------------------------------
  • 双向链表也叫链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表...
  • C++使用指针的优点

    千次阅读 2018-07-05 20:03:20
    使用指针可以带来如下的好处:(1)可以提高程序的编译效率和执行速度,使程序更加简洁。(2)通过指针被调用函数可以向调用函数处返回除正常的返回值之外的其他数据,从而实现两者间的双向通信。(3)利用指针可以...
  • C++-指针与void*指针

    2016-11-15 00:04:08
    指针简单理解,指针代表了两个变量:一个是指针变量本身,另一个是它所指向的变量。对于int *p;这句话可以认为定义了两个变量p和*p,p是一个地址变量,只能存放整型变量在内存中的地址;*p是一个整形变量,只能存放...
  • C++ - 指针总结

    万次阅读 多人点赞 2019-02-26 20:09:04
    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!... 指针是什么? ...在C++中,指针变量只有有了明确的指向才有意义。 指针类型 int* ptr; // ...
  • 数学基础离散数学中的异或运算 a⊕b,具有以下性质a⊕b = b⊕a a⊕a = 0 a⊕0 = a a⊕(a⊕b) = (a⊕a)⊕b = b ...其中每个节点的后半部分表示指针域,存储了它的前驱节点的指针与后继借点的指针的异或

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 87,445
精华内容 34,978
关键字:

c++双指针

c++ 订阅