发表更新LeetCode / 算法30 分钟读完 (大约4477个字)

LeetCode-位运算

位运算常见技巧

  • 位运算计算
a op b res
x xor 0x00 x
x xor 0xff ~x
x xor x 0
x and 0x00 0
x and 0xff x
x and x x
x or 0x00 x
x or 0xff 0xff
x or x x
x and x-1 去掉最低位
x and -x 得到最低位
  • 状态压缩

用二进制位表示状态

268. 丢失的数字

阅读更多
发表更新LeetCode / 算法26 分钟读完 (大约3825个字)

LeetCode-27

[Medium] 29. 两数相除

分析

  • 只能用加减法，最朴素的方法是循环相减/加，直到小于0/大于0，计算加/减的次数
  • 这样算法是o(n)，考虑到i+=i或者i<<=1相当于i*=2,i>>=1相当于i/=2
  • 只考虑divisor, divident都大于0的情况，先找到整数p，使得 divisor∗2p<=dividentdivisor*2^p <= divident，divident−=divisor∗2p,ratio+=2pdivident-=divisor*2^p, ratio+=2^p若divident为0，则商为ratio，否则重复上面的过程，直到divident为0。
  • 考虑divisor, divident到可能正，可能负，而负数的范围大于正数，直接将所有整数变成负数，并记录符号
  • 注意取相反数的时候要用位运算~x+1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend < divisor && dividend > 0) return 0;
        if(dividend > divisor && dividend < 0) return 0;
        if((dividend == INT_MIN) && (divisor == -1)) return INT_MAX;
        if((dividend == INT_MIN) && (divisor == 1)) return INT_MIN;
        if(dividend == divisor) return 1;
        if(dividend < 0 && divisor > 0 && dividend == ~divisor+1) return -1;
        if(dividend > 0 && divisor < 0 && ~dividend+1 == divisor) return -1;
        bool sign = false;
        if(dividend < 0) {
            sign = !sign;
        } else {
            dividend = ~dividend+1;
        }
        if(divisor < 0) {
            sign = !sign;
        } else {
            divisor = ~divisor+1;
        }
        int res = 0;
        int i = -1;
        while(dividend < divisor && divisor >= (INT_MIN >> 1)) {
            divisor += divisor;
            i+=i;
        }
        while(true) {
            while(dividend > divisor) {
                if(i == -1) {
                    return sign ? (res) : (~res+1);
                }
                divisor >>= 1;
                i>>=1;
            }
            dividend -= divisor;
            res+=i;
        }
    }
};

275. H 指数 II

阅读更多
发表更新misc12 分钟读完 (大约1765个字)

c语言函数绘图

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
#define _XOPEN_SOURCE 500
#define _C99_SOURCE
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <float.h>
//#define LOG_LEVEL DEBUG_LOG
#define DEBUG_LOG 7
#define INFO_LOG 5
#define ERR_LOG 4
#ifndef LOG_LEVEL
#define LOG_LEVEL INFO_LOG
#endif
#ifndef GREATER_CHAR
#define GREATER_CHAR ' '
#endif
#ifndef SMALLER_CHAR
#define SMALLER_CHAR '+'
#endif
void logger(int level, const char *format, ...) {
    if(level > LOG_LEVEL) return;
    va_list args;
    va_start(args, format);
    int len = vsnprintf(NULL, 0, format, args)+1;
    va_end(args);
    va_start(args, format);
    char *str = malloc(len);
    vsprintf(str, format, args);
    va_end(args);
    fprintf(stderr, "%s\n", str);
    free(str);
}
double x1, x2, _y1, _y2, s1, s2;

#define PUSH(s, n) (s[s##_ptr++] = (n))
#define POP(s, n) (n = s[--s##_ptr])
#define TOP(s, n) (n = s[s##_ptr-1])
#define EMPTY(s) (s##_ptr == 0)
enum {
    op_acos     = 48,
    op_asin         ,
    op_atan         ,
    op_cos          ,
    op_cosh         ,
    op_sin          ,
    op_sinh         ,
    op_tan          ,
    op_tanh         ,
    op_exp          ,
    op_log          ,
    op_floor        ,
    op_sqrt         ,
    op_fabs         ,
    op_ceil
};
const static int op_min = op_acos;
const static int op_max = op_ceil;

static double stack[1024];
static char op_stack[1024];
static int priv[128] = {
        [0 ... 39] = 0,
        ['('] = 1,
        [')'] = 2,
        ['*'] = 3,
        ['+'] = 2,
        [44] = 0,
        ['-'] = 2,
        [46] = 0,
        ['/'] = 3,
        [48 ... 93] = 0,
        ['^'] = 4,
        [95 ... 127] = 0
};
static int stack_ptr = 0;
static int op_stack_ptr = 0;
void logStack() {
    logger(DEBUG_LOG, "op_stack: ");
    for(int cnt = 0; cnt < op_stack_ptr; cnt++) {
        logger(DEBUG_LOG, "%c ", op_stack[cnt]);
    }
    logger(DEBUG_LOG, "stack: ");
    for(int cnt = 0; cnt < stack_ptr; cnt++) {
        logger(DEBUG_LOG, "%lf ", stack[cnt]);
    }
    logger(DEBUG_LOG, "");
}
void biCheck() {
    if(EMPTY(stack)) {
        logger(ERR_LOG, "empty stack!");
        exit(1);
    }
}
void pushOP(char cur_op) {
    double n1, n2;
    char op;
    while(!EMPTY(op_stack) && priv[TOP(op_stack, op)] >= priv[cur_op]) {
        POP(op_stack, op);
        double res = 0;
        POP(stack, n2);
        if(!EMPTY(stack))POP(stack, n1);
        else n1 = 0;
        switch(op) {
            case '+':
                res = n1 + n2;
                break;
            case '-':
                res = n1 - n2;
                break;
            case '*':
                res = n1 * n2;
                break;
            case '/':
                if(n2 == 0) {
                    logger(ERR_LOG, "divisor is zeor!");
//                    exit(1);
                }
                res = n1 / n2;
                break;
            case '^':
                res = pow(n1, n2);
                break;
            default:
                break;
        }
        PUSH(stack, res);
    }
}
int len_strncmp(const char *a, const char *b) {
    return strncmp(a, b, strlen(b));
}
double eval(double y, double x, const char *expr) {
    int len = strlen(expr);
    int i = 0;
    stack_ptr = 0;
    op_stack_ptr = 0;
    while(i < len) {
        switch(expr[i]) {
            case '^':
                biCheck();
                pushOP(expr[i]);
                // if(EMPTY(stack)) PUSH(stack, 0);
                PUSH(op_stack, expr[i]);
                break;
            case 'x': case 'X':
                PUSH(stack, x);
                break;
            case 'y': case 'Y':
                PUSH(stack, y);
                break;
            case '(':
                PUSH(op_stack, '(');
                break;
            case ')': {
                double n1, n2;
                char op;
                if(EMPTY(op_stack)) {
                    logger(ERR_LOG, "no match ')'");
                    exit(1);
                }
                pushOP(')');
                POP(op_stack, op);
                if(TOP(op_stack, op) >= op_min && TOP(op_stack, op) <= op_max) {
                    POP(op_stack, op);
                    double n;
                    if(!EMPTY(stack)) {
                        POP(stack, n);
                    } else {
                        logger(ERR_LOG, "Error : no opvalue");
                        exit(1);
                    }
                    double (*op_func)(double);
                    switch(op) {
                        case op_acos:
                            if(n > 1 || n < -1) return DBL_MAX;
                            op_func = acos;
                            break;
                        case op_asin:
                            if(n > 1 || n < -1) return DBL_MAX;
                            op_func = asin;
                            break;
                        case op_atan:
                            op_func = atan;
                            break;
                        case op_cos:
                            op_func = cos;
                            break;
                        case op_cosh:
                            op_func = cosh;
                            break;
                        case op_sin:
                            op_func = sin;
                            break;
                        case op_sinh:
                            op_func = sinh;
                            break;
                        case op_tan:
                            op_func = tan;
                            break;
                        case op_tanh:
                            op_func = tanh;
                            break;
                        case op_exp:
                            op_func = exp;
                            break;
                        case op_log:
                            if(n < 0) return DBL_MAX;
                            op_func = log;
                            break;
                        case op_sqrt:
                            if(n < 0) return DBL_MAX;
                            op_func = sqrt;
                            break;
                        case op_fabs:
                            op_func = fabs;
                            break;
                        case op_ceil:
                            op_func = ceil;
                            break;
                        case op_floor:
                            op_func = floor;
                            break;
                    }
                    PUSH(stack, op_func(n));
                }
            }
                break;
            case '+':case '-': {
                if((i > 0 && expr[i-1] != '(')) { // fix： a-(-b)
                    // if stack is empty or last op is '(', ‘-’ is an Unary operator
                    // else it's a Binary operator
                    biCheck();
                    pushOP(expr[i]);
                } else {
                    PUSH(stack, 0);
                }
                PUSH(op_stack, expr[i]);
            }
                break;
            case '*':
            case '/':
                biCheck();
                pushOP(expr[i]);
                // if(EMPTY(stack)) PUSH(stack, 0);
                PUSH(op_stack, expr[i]);
                break;
            case 'p': // p1 = 3.14
                if(i + 1 < len && expr[i + 1] == 'i') {
                    PUSH(stack, M_PI);
                    i++;
                } else {
                    logger(ERR_LOG, "Error 'pi': unknown char(%c)", expr[i]);
                    exit(1);
                }
                break;
            case 'e': // e = 2.7
                PUSH(stack, M_E);
                break;
            case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':case '.':
            {
                double n = 0;
                double n1 = 1;
                while(i < len) {
                    if(expr[i] < '0' || expr[i] > '9') {
                        break;
                    }
                    n *= 10;
                    n += expr[i] - '0';
                    i++;
                }
                if(expr[i] == '.') {
                    i++;
                    while(i < len && expr[i] != '.') {
                        if(expr[i] < '0' || expr[i] > '9') {
                            break;
                        }
                        n1 /= 10.0;
                        n += n1 * (expr[i] - '0');
                        i++;
                    }
                }if(expr[i] == '.') {
                    logger(ERR_LOG, "error : two '.' in one number");
                    exit(1);
                }
                PUSH(stack, n);
                i--;
            }
                break;
            default:
                if(!len_strncmp(expr + i, "ACOS")) {
                    PUSH(op_stack, op_acos);
                    i+=3;
                } else if(!len_strncmp(expr + i, "ASIN")) {
                    PUSH(op_stack, op_asin);
                    i+=3;
                } else if(!len_strncmp(expr + i, "ATAN")) {
                    PUSH(op_stack, op_atan);
                    i+=3;
                } else if(!len_strncmp(expr + i, "COS")) {
                    if(expr[i+3] == 'H') {
                        PUSH(op_stack, op_cosh);
                        i+=3;
                    } else {
                        PUSH(op_stack, op_cos);
                        i+=2;
                    }
                } else if(!len_strncmp(expr + i, "SIN")) {
                    if(expr[i+3] == 'H') {
                        PUSH(op_stack, op_sinh);
                        i+=3;
                    } else {
                        PUSH(op_stack, op_sin);
                        i+=2;
                    }
                } else if(!len_strncmp(expr + i, "TAN")) {
                    if(expr[i+3] == 'H') {
                        PUSH(op_stack, op_tanh);
                        i+=3;
                    } else {
                        PUSH(op_stack, op_tan);
                        i+=2;
                    }
                } else if(!len_strncmp(expr + i, "EXP")) {
                    PUSH(op_stack, op_exp);
                    i+=2;
                } else if(!len_strncmp(expr + i, "LOG")) {
                    PUSH(op_stack, op_log);
                    i+=2;
                } else if(!len_strncmp(expr + i, "SQRT")) {
                    PUSH(op_stack, op_sqrt);
                    i+=3;
                } else if(!len_strncmp(expr + i, "FABS")) {
                    PUSH(op_stack, op_fabs);
                    i+=3;
                } else if(!len_strncmp(expr + i, "CEIL")) {
                    PUSH(op_stack, op_ceil);
                    i+=3;
                } else if(!len_strncmp(expr + i, "FLOOR")) {
                    PUSH(op_stack, op_floor);
                    i+=4;
                } else {
                    logger(ERR_LOG, "Error: unknown char(%c)", expr[i]);
                    exit(1);
                }
                break;
        }
        i++;
        logStack();
    }
    biCheck();
    pushOP(0);
    logStack();
    return stack[0];
}
void INIT(char **argv) {
    int i = 0;
    _y1 = eval(0, 0, argv[i++]);
    _y2 = eval(0, 0, argv[i++]);
    s1 = eval(0, 0, argv[i++]);
    x1 = eval(0, 0, argv[i++]);
    x2 = eval(0, 0, argv[i++]);
    s2 = eval(0, 0, argv[i++]);
    logger(DEBUG_LOG, "%lf, %lf, %lf, %lf, %lf, %lf\n", _y1, _y2, s1, x1, x2, s2);

}
int main(int argc, char **argv) {
    if(argc < 8) {
        logger(INFO_LOG, "Usage: %s y1 y2 sy x1 x2 sy expression", argv[0]);
        logger(INFO_LOG, "example: %s -1 1 0.125 -1 1 0.0625 \"x*x+y*y-1\" 2>errs.log", argv[0]);
        logger(INFO_LOG, "example: %s \"-pi/2\" \"pi/2\" 0.25 \"-3*pi\" \"2*pi\" 0.125 \"y^2-SIN(x+y)^2\" 2>errs.log", argv[0]);
        logger(INFO_LOG, "example: %s \"-pi/2\" \"pi/2\" 0.25 \"-3*pi\" \"2*pi\" 0.125 \"y^2-SIN(x)^2\" 2>errs.log", argv[0]);
        logger(INFO_LOG, "example: %s \"-2\" \"ACOS(1/2)-pi/4\" 0.125 \"-pi/2\" \"pi/2\" 0.0625 \"y*y+x*x+y-SQRT(y*y+x*x)\" 2>errs.log", argv[0]);
        logger(INFO_LOG, "example: %s \"-pi\" \"1\" 0.125 \"-2\" \"2\" 0.0625 \"(ACOS(1-FABS(x))-pi)-y\" \"y-SQRT(1-(FABS(x)-1)^2)\" 2>errs.log", argv[0]);
        logger(INFO_LOG, "example: %s \"-1\" \"pi/2\" 0.125 \"-1\" \"1\" 0.0625 \"x*x+(y-FABS(x)^(2.0/3.0))^2-1\" 2>errs.log", argv[0]);

        exit(0);
    }
    INIT(argv + 1);
    for(double i = _y2; i >= _y1; ) {
        for(double j = x1; j <= x2; ) {
            logger(DEBUG_LOG, "x = %lf, y = %lf", j, i);
            bool ok = true;
            for(char **expr = argv + 7; *expr; expr++) {
                if(eval(i, j, *expr) >= 0) {
                    ok = false;
                    break;
                }
            }
            if(ok) {
                printf("%c", SMALLER_CHAR);
            } else {
                printf("%c", GREATER_CHAR);
            }
            j+=s2;
        }
        printf("\n");
        i-=s1;
    }
}

example

圆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
.................................
.........+++++++++++++++.........
......+++++++++++++++++++++......
....+++++++++++++++++++++++++....
...+++++++++++++++++++++++++++...
..+++++++++++++++++++++++++++++..
.+++++++++++++++++++++++++++++++.
.+++++++++++++++++++++++++++++++.
.+++++++++++++++++++++++++++++++.
.+++++++++++++++++++++++++++++++.
.+++++++++++++++++++++++++++++++.
..+++++++++++++++++++++++++++++..
...+++++++++++++++++++++++++++...
....+++++++++++++++++++++++++....
......+++++++++++++++++++++......
.........+++++++++++++++.........
.................................
阅读更多
发表更新Android8 分钟读完 (大约1208个字)

06-OKHTTP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
final Dispatcher dispatcher; // 线程控制
final @Nullable Proxy proxy; // 代理服务器，java.net
final List<Protocol> protocols;
final List<ConnectionSpec> connectionSpecs;
final List<Interceptor> interceptors;
final List<Interceptor> networkInterceptors;
final EventListener.Factory eventListenerFactory;
final ProxySelector proxySelector;
final CookieJar cookieJar;
final @Nullable Cache cache;
final @Nullable InternalCache internalCache;
final SocketFactory socketFactory;
final SSLSocketFactory sslSocketFactory;
final CertificateChainCleaner certificateChainCleaner;
final HostnameVerifier hostnameVerifier;
final CertificatePinner certificatePinner;
final Authenticator proxyAuthenticator;
final Authenticator authenticator;
final ConnectionPool connectionPool;
final Dns dns;
final boolean followSslRedirects;
final boolean followRedirects;
final boolean retryOnConnectionFailure;
final int callTimeout;
final int connectTimeout;
final int readTimeout;
final int writeTimeout;
final int pingInterval;

websocket

wikipedia:

  • 利用tcp提供全双工通信 WebSocket is a computer communications protocol, providing full-duplex communication channels over a single TCP connection.
  • 运行在80/443端口上 WebSocket is designed to work over HTTP ports 443 and 80 as well as to support HTTP proxies and intermediaries

Dispatcher - 线程控制

使用Deque控制任务

阅读更多
发表更新Android6 分钟读完 (大约858个字)

05-Retrofit

HOST验证

在上节https的ca证书验证时，如果某个恶意网站直接获取整个ca证书，发给其他用户骗取信任怎么办。这个时候就需要host验证，即证书的host主机与发送证书的主机host是否是同一个域名。

fiddler如何抓包

fiddler是一个中间人，通过系统代理，浏览器/应用将请求发送至fiddler，fiddler自签一个证书与浏览器/应用使用，且需要用户向操作系统安装根证书。fiddler拿到数据包后再与服务器交互。

retrofit源码阅读

retrofit的使用

阅读更多
发表更新Android4 分钟读完 (大约672个字)

04-登录授权 Https TCP/IP

登录授权

Basic

在header中
Authorization: Basic username:password(Base64ed, encrypted)

Bearer

在header中
Authorization: Bearer bearer_token

这里的bearer_token就类似于github的Personal access tokens，在请求中持有token的请求，可以根据token的权限对第三方账号中的数据进行获取、修改

阅读更多
发表更新Android6 分钟读完 (大约826个字)

02-http

格式

  • 报文格式(Request)
    • 请求行 eg: GET /users?id=xxxx HTTP/1.1
      • method
      • path(包括参数部分)
      • Http version
    • headers (Host在这里)
    • body
  • 报文格式(Response)
    • 状态行 eg: HTTP/1.1 200 OK
      • Http Version
      • status code
      • status message
    • headers
    • body

Request

method

  • GET
    • 获取资源
    • 没有body
  • POST
    • 增加/修改资源
    • 有body
  • PUT
    • 修改资源
    • 有body
  • DELETE
    • 删除资源
    • 没有body
  • HEAD
    • 获取资源
    • 没有body
    • 响应无body
    • 用于下载时，确定文件大小，有无断点续传等信息

幂等性：指重复的请求多次向服务器传送，对服务器的没有影响。如GET和PUT,DELETE。

阅读更多
发表更新Android6 分钟读完 (大约862个字)

01-多线程

java thread

synchronized

  • 类锁

    • 修饰static函数和synchronized(ClassName.class)都是获取类锁

  • 对象锁

    • 修饰成员函数和synchronized(this|object)都是对象锁
    • 其中修饰成员函数和synchronized(this)获取的都是当前类对象的锁

  • 优点

    • 简单，易用
    • 开销少

  • 缺点

    • 可重入性差
    • 大量使用可能导致性能下降

  • 推荐用法

    • 单例模式使用
    • 用于计数器的自增或类似场景

Object.wait, Object.notify, Object.notifyAll

函数作用顾名思义

wait: 先释放对象锁，等待notify/notifyAll后释放
也就是说，可以基于他们实现条件变量, pv操作

阅读更多
关注我

链接

分类

最新文章

归档

标签

6.8242
Android1
Android FrameWork1
Android 高级开发瓶颈突破系列课11
Android-官方文档1
Android-官方源码5
Android面试查漏补缺2
C/C++1
Flutter1
Java基础1
Kotlin-Android21
Kotlin-Android 实习25
LeetCode45
LeetCode 1013
LeetCode周赛1
Linux/UNIX系统编程手册38
OI KIWI2
OS4
PAT-(Advanced-Level)-Practice2
PAT-(Basic-Level)-Practice44
blockchain1
fedfab13
gallery1
geth1
git1
gradle1
hexo2
linux2
misc1
projects1
shell2
刷题2
动态规划1
多线程1
排序1
数据库2
牛客2
算法43
×