leetcode 560. Subarray Sum Equals K

题目

https://leetcode.com/problems/subarray-sum-equals-k/
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Constraints:

The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

思路

记录向前累计和,而后向前查找距离目标k的差值出现多少次,区间问题尽量转换为向前累计和的操作,而不是区间和的问题

源码

class Solution {
public:
    unordered_map<int,int> m;
    int sum[20005];
    int res = 0;
    int subarraySum(vector<int>& nums, int k) {
        sum[0] = 0;
        m[0] = 1;
        for(int i = 1;i <= nums.size();++i){
            int s = sum[i-1]+nums[i-1];
            sum[i] = s;
            int re = s-k;
            if(m.find(re)!=m.end()){
                res+=m[re];
            }
            if(m.find(s)==m.end()){
                m[s]=1;
            }else{
                m[s]++;
            }
        }
        return res;
    }
};

leetcode28 KMP模板

思路

KMP 模板
https://www.zhihu.com/question/21923021
– 首先理解 PMT,以及根据 PMT 如何进行回溯;其与 next 不同
– next 数组指的是 pattern 当前位匹配不上时,应该回溯到哪一位继续匹配
– p[j] == t[k] 时更新 next[j+1]==k+1,思路时 j+1 匹配不上时回溯要考虑前一位的匹配情况

源码

//
//  leetcode28.cpp
//  test
//
//  Created by sgxm on 2020/8/5.
//  Copyright © 2020 sgxm. All rights reserved.
//

#include <stdio.h>
#include <string>
#include <iostream>
#include <vector>
using namespace std;

vector<int> calNext(string p){
    vector<int> next(p.length());
    next[0] = -1;
    int j = 0,k = -1;
    while(j<p.length()-1){
        if(k==-1||p[j]==p[k]){
            j++;k++;
            next[j]=k;
        }else{
            k = next[k];
        }
    }
    return next;
}
int main(){
    string p =      "ababca";
    string target = "abcababca";
    vector<int> next = calNext(p);
    int j = 0,i = 0;
    while((j<(int)p.length())&&(i<(int)target.length())){
        if(j==-1||p[j]==target[i]){
            i++;j++;
        }else{
            j = next[j];
        }
//        if((j<p.length())&&(i<target.length()))
//            cout <<i<<" < "<<target.length()<<","<<j<<" < "<<p.length()<<endl;
    }
   // cout << j;
    if(j == p.length()){
        cout <<i-j<<endl;
    }else{
        cout <<-1<<endl;
    }
    return 0;
}

Scala 学习笔记

文章丑一定有他的原因,这是我的学习笔记,Markdown 源码直接来源于 Typora,由于 CSS 样式及 md 解析差异,造就了这篇文章,这里只是做一份副本,不具有使用价值
———— 我自己说的

声明

val 声明必须初始化

import java.lang._ //导入lang中所有
val myStr2:String = HelloWorld!//Scala中的字符串类直接来自于java
println(myStr2)

如何输入多行代码:没输入完时可以敲回车

字面量

val i = 123
val i = true//布尔字面量

操作符

a 方法 b 等价于 a.方法(b)

递增

i += 1

富包装类

Int 对应 RichInt

String 对应 RichString, 这些类位于 scala.runtime 中

Range

1 to 5 
1.to(5)//1,2,3,4,5
1 until 5//1,2,3,4
0.5f to 5.9f by 0.8f//步长0.8f

输入输出

readInt, readShort //import scala.io.StdIn._

val str = readLine("enter your name")
val f = readFolot()
>3.5e1
println("hello");println("world!")
printf("i = %.1f",i);//print(),println(),printf()默认所有scala程序都可以使用

写入文件

import java.io.PrintWriter
val out = new PrintWriter("out.txt")
for(i <- 1 to 5) out.println(i)
out.close()

读入文件

import scala.io.Source
val in = Source.fromFile("in.txt")
val lines = in.getLines//返回迭代器
for(line <- lines) println(line)

继续阅读

日常学习笔记

SHA256


哈希是一种能将不同的输入映射为独一无二的定长字符串的算法,如果对于不同的输入,映射为同一字符串,则称之为哈希碰撞(collision).
对于哈希碰撞,我们可以记住这样一个公式

50%概率发生哈希碰撞的计算次数

    \[m =\sqrt{(\frac{\pi }{2}N)}\]

N为哈希值的二进制位数,对于 SHA256 来说,它会生成32字节,64长度的16进制字符串,256位(每个字符取值范围为[0-9a-z])

对于生日来说可以计算出它50%概率发生碰撞所需要的计算次数为23.9
同时也要记住另一个公式

哈希碰撞概率公式

    \[p(n,d)\approx 1 - e^{\frac{-n(n-1)}{2d}}\]

n为计算次数,d为取值空间,该公式推导过程中用到了泰勒公式e^x \approx 1+x

继续阅读

指针和数组

指针也就是地址,他存储的是一个变量在内存中所在的位置,当它存储变量i的地址时,我们就说这个指针指向i

在32位编译器中,指针变量的大小都是4字节,也就是是说int* 和char* 类型的变量都是四个字节

int m;
char n;
int *i;
char *j;
printf("m在内存中占%d个字节\n n在内存中占%d个字节\n",sizeof(m),sizeof(n));
printf("i在内存中占%d个字节\n j在内存中占%d个字节\n",sizeof(i),sizeof(j));
m在内存中占4个字节
n在内存中占1个字节
i在内存中占4个字节
j在内存中占4个字节

 

指针之间的加法乘法除法都是没有意义的,但是指针之间的减法可以表示地址的偏移,比如你的门牌号是123我的门牌号是456,123+456 123*456 123/456都没有任何意义

但是123-456或者456-123的差就可以表示地址的偏移,我们如果知道了这个差值那么我们就可以通过过我的门牌号找到你的门牌号,从而找到你家

我们都知道数组名就是一个指针常量,它存储的是数组第一个元素在内存中的地址

//
int a[3] = {1,2,3};
printf("a = %#X\n",a);//a是一个指针常量,指向第一个元素
printf("*a = %d\n",*a);
printf("a[0] = %d\n",a[0]);

//输出
/*
a = 0X69FF04
*a = 1
a[0] = 1
*/

我们发现*a和a[0]实际上是一样的,都代表了数组中的第一个元素,当一个指针p指向一个变量时,*p就代表它指向的这个变量,其实a[0]就等价于 *(a + 0)

//
int a[3] = {1,2,3};
printf("a[0]的地址为%p\n",&a[0]);
printf("a[1]的地址为%p\n",&a[1]);
printf("a[2]的地址为%p\n",&a[2]);

//输出
/*
a[0]的地址为0069FF04
a[1]的地址为0069FF08
a[2]的地址为0069FF0C
*/

我们发现数组中每个元素的地址之间都相差4,这正是因为int变量占4个字节,而我们规定对于一个变量我们用它第一个字节在内存中的编号作为它的地址。也就是说,虽然对a[0]取地址输出的是0069FF04,但0069FF05 0069FF06 0069FF07也都是a[0]

现在就用到我们上面讲的地址偏移了,我们知道了数组中每个元素的地址之间相差4,那么我们就可以通过第一个元素的地址来找到第二个元素

//
int a[3] = {1,2,3};
printf("%p\n",a);
printf("%p\n",a+4);
printf("%p\n",a+1);
printf("%d\n",*(a+1));
/*
0069FF04
0069FF14
0069FF08
2
*/

a+4的结果和a差了16根本不是我们想要的a[1]的地址,而a+1刚好和a相差4,我们输出     a+1指向的变量,刚好也是第二个元素2,这是因为指针变量的加号运算符被重载了它的+1实际上加的是对应变量的长度,例如字符指针加一就是加一,而整形指针加一就是加四,所以无论是什么类型的数组,a[5]和*(a+5)都是完全等价的

总结:

1.(32位)所有类型的指针变量都占4个字节,我们用第一个字节的在内存中的编号来作为它的地址

2. 如果指针p指向i,那么*p完全等价于i

3. 数组在内存中是连续的的,每个元素都是相邻的,是一种连续的线性存储结构

4. a[i]完全等价于*(a + i)

加一道据说是去年的c++考试的题

//
using namespace std;
int x[4] = {10,20,30,40};
int *p = x;
cout << *++p << endl;//等价于++p; cout<<*p;
cout << *p++ << endl;//等价于cout<<*p; p++;
cout << ++*p << endl;//等价于int i = *p; ++i; cout<<i;
cout << (*p)++ << endl;
cout << *p << endl;

/*输出
20
20
31
31
32
*/

来简单看一下为什么

*++p   *和前自增优先级相同但是结合性是从左到右也就是先执行++在执行*                      *p++   后加加优先级高于*,他会先执行后自增结合的是p,但因为是自增,所以虽然它先执行,但是依然要等到*之后才加一                                                                             ++*p   优先级相同,从右向左,先* 再++  可以和第一个对比

有问题欢迎大家提问哦0。0 可以直接评论😂 也可以QQ🤣