算法笔记

admin管理员组

文章数量:1794759

算法笔记

不同进制数的表示形式

二进制：0b

八进制：0

十六进制：0x

int a = 0b001; int b = 07; int c = 0xa; cout << a << endl; // 1 cout << b << endl; // 7 cout << c << endl; // 10 计算机中对数字的表示方法 相关概念

原码：数值绝对值二进制表示+1位符号位（即最高位正数为0，负数为1）

补码：正数补码=原码；

负数补码=原码除符号位外的所有位取反后加1

+5-5

原码	0101	1101
补码	0101	1011

注意：0的原码，补码都是0；

**计算机存储的都是补码** 移位操作

逻辑移位：移位不考虑符号位，即不论左移还是右移，都补0

算术移位：移位考虑符号位，即带符号位的移位

正数：无论左移还是右移都是补0； 负数：左移在右边补0，右移需要在左边补1

补充：如果要对负数做逻辑移位，可以****int转unsigned int

#include <limits.h> int a = -1; unsigned int b = a; cout << (b >> 1) << endl; // 2147483647 cout << ((b >> 1) == INT_MAX); // 1 (true)

参考：zhuanlan.zhihu/p/97749860

右移一位和除2的差异

正数：无差异

负数：偶数无差异；奇数有差异

int x = -1; int a1 = 5; int a2 = -5; int b1 = 4; int b2 = -4; cout << x / 2 << " " << (x >> 1) << endl; // 0 -1 cout << a1 / 2 << " " << (a1 >> 1) << endl; // 2 2 cout << a2 / 2 << " " << (a2 >> 1) << endl; // -2 -3 cout << b1 / 2 << " " << (b1 >> 1) << endl; // 2 2 cout << b2 / 2 << " " << (b2 >> 1) << endl; // -2 -2 leetcode405 数字转换成16进制 class Solution { public:     string toHex(int num) {         if (num == 0) return "0"; // 技巧：将数值与字符联系起来         string str = "0123456789abcdef"; // 使用逻辑移位         unsigned int n = num;         string res = ""; // 判断有效位移完         while (n > 0) { // 只取低4位             int idx = n & 0xf;             res = str[idx] + res;             n = n >> 4;         }         return res;     } }; ip地址转数字及前缀匹配 bool MatchDestIP(int m, string s, const string &dest) { if (s == "0.0.0.0") return true; int ip = GetIntValue(s); int target = GetIntValue(dest); // 前缀匹配：前m个字符相同 return ip >> (32 - m) == target >> (32 - m); } // ip地址字符串（s）转int int GetIntValue(string s) { long long res = 0; for (int i = 0; i < 4; ++i) { int pos = s.find_first_of("."); int num = stoi(s.substr(0, pos)); res += num << ((3 - i) * 8); s = s.substr(pos + 1); } return res; } 计算器系列 基本计算器【±( )’’】 class Solution { public: int calculate(string s) { stack<int> ops; ops.push(1); int sign = ops.top(); int res = 0; int i = 0; while (i < s.size()) { if (s[i] == ' ') { i++; } else if (s[i] == '+') { sign = ops.top(); i++; } else if (s[i] == '-') { sign = -ops.top(); i++; } else if (s[i] == '(') { ops.push(sign); i++; } else if (s[i] == ')') { ops.pop(); i++; } else { long num = 0; while (i < s.size() && s[i] >= '0' && s[i] <= '9') { num = num * 10 + s[i] - '0'; i++; } res += sign * num; } } return res; } }； 基本计算器II 【±*/】 class Solution { public: int calculate(string s) { vector<long long> numStack; char op = '+'; long long num = 0; for (int i = 0; i < s.size(); ++i) { if (IsNum(s[i])) { num = num * 10 + (s[i] - '0'); } if (IsOP(s[i]) || i == s.size() -1) { switch (op) { case '+': numStack.push_back(num); break; case '-': numStack.push_back(-num); break; case '*': numStack.back() *= num; break; case '/': numStack.back() /= num; break; } op = s[i]; num = 0; } } return accumulate(numStack.begin(), numStack.end(), 0); } bool IsNum(char ch) { return ch >= '0' && ch <= '9'; } bool IsOP(char ch) { return ch == '+' || ch == '-' || ch == '*' || ch == '/'; } int GetNum(char ch, int& i, string s) { int num = 0; for (; i < s.size() && IsNum(s[i]); ++i) { num = num * 10 + (s[i] - '0'); } return num; } };

本文标签： 算法笔记