[关闭]
@dyk 2015-11-04T00:45:25.000000Z 字数 4382 阅读 442

Problem Solutions

Algorithm Workspace

Two Sum

LeetCode

大意：给定一个整数array，给定一个target，要求找出两个array中的数a，b，要a+b=target
解法：rbtree，hash map

  1. class Solution {
  2. public:
  3.     // 其实二分查找也可以，使用RB树也可以，另外题目的对于output的要求并不是十分明确
  4.     vector<int> twoSum(vector<int>& nums, int target) {
  5.         int query,count;
  6.         vector<int> v(2);
  7.         map<int,int> mymap;
  8.         vector<int>::iterator it;
  9.         map<int,int>::iterator fit;
  10.         it = nums.begin();
  11.         for(count = 1; it != nums.end(); it++, count++){
  12.             mymap.insert(pair<int,int>(*it,count));
  13.         }
  14.         for(count = 1, it = nums.begin() ; it != nums.end(); it++, count++){
  15.             //cout<<"Now query "<<*it<<endl;
  16.             query = target - *it;
  17.             fit = mymap.find(query);
  18.             if(fit != mymap.end()){
  19.                 //cout<<"in"<<endl;
  20.                 if(count < fit->second){
  21.                     v[0] = count;
  22.                     v[1] = fit->second;
  23.                     break;
  24.                 }else if(count > fit->second){
  25.                     v[1] = count;
  26.                     v[0] = fit->second;
  27.                     break;
  28.                 }
  29.             }
  30.         }
  31.         return v;
  32.     }
  33. };

Lisp Expression Explainer

hinocoder ， 2015-09-16年网易游戏开发第三题

建立操作符栈，以及操作数栈，并且记录每个括号内的操作数个数。

Input Examples:
5
(+ 1 (* 2 3)))
(2 3)
(- 3 2 1)
(+ (+ 1 2) (* 2 3) (- 2 1))
(- 2)

Output Examples:
invalid expression
invalid expression
invalid expression
10
-2

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <stack>
  4. #include <fstream>
  5. using namespace std;
  7. int main()
  8. {
  9.     int casenm;
  10.     stack<char> op_stack;
  11.     stack<int> opd_stack;
  12.     stack<int> opdn_stack;
  13.     char op;
  14.     int opd , opdn, ans;
  15.     char exp[1000001];
  16.     int flag = 1;
  17.     ifstream ifs;
  18.     ifs.open("./input.txt");
  19.     if(!ifs){
  20.         return 0;
  21.     }
  22.     ifs>>casenm;
  23.     ifs.getline(exp,1000000);
  24.   //cin>>casenm;
  25.   //cin.getline(exp,1000000);
  26.     for(int k = 0; k < casenm  ; k++){
  27.      // cin.getline(exp,1000000);
  28.         ifs.getline(exp,1000000);
  29.         flag = 1;
  30.         opd = -1;
  31.         opdn = 0;
  32.         while(!op_stack.empty()){
  33.             op_stack.pop();
  34.         }
  35.         while(!opd_stack.empty()){
  36.             opd_stack.pop();
  37.         }
  38.         while(!opdn_stack.empty()){
  39.             opdn_stack.pop();
  40.         }
  41.         for(int i = 0; exp[i] != '\0' ; i++){
  42.             if( exp[i] == '(' || exp[i] == '+' || exp[i] == '-' || exp[i] == '*' ){
  43.                 op_stack.push(exp[i]);
  44.                 if(exp[i] == '('){
  45.                     opdn_stack.push(opdn);
  46.                     opdn = 0;
  47.                     if(opd != -1){
  48.                     // 操作数连着左括号的情况
  49.                         opd_stack.push(opd);
  50.                         opdn++;
  51.                         opd = -1;
  52.                     }
  53.                 }
  54.             }else if(exp[i] == ')'){
  55.                 //开始退站计算， 减号只能有2以下个参数 ，加号至少有 1个参数 ， 乘号至少有 2 个
  56.                 if(op_stack.empty()){
  57.                     // 如果符号栈空则错误
  58.                     flag = 0;
  59.                     break;
  60.                 }else{
  61.                     op = op_stack.top();
  62.                     op_stack.pop();
  63.                 }
  65.                 //如果存在操作数先将操作数进栈
  66.                 if(opd != -1){
  67.                     opd_stack.push(opd);
  68.                     opd = -1;
  69.                     opdn++;
  70.                 }
  71.                 if(op == '-'){
  72.                         //
  73.                     if(opdn == 2){
  74.                         ans = opd_stack.top();
  75.                         opd_stack.pop();
  76.                         ans = opd_stack.top() - ans;
  77.                         opd_stack.pop();
  78.                     }else if(opdn == 1){
  79.                         ans = -1 * opd_stack.top();
  80.                         opd_stack.pop();
  81.                     }else if(opdn > 2){
  82.                         flag = 0;
  83.                         break;
  84.                     }
  85.                 }else if(op == '+'){
  86.                     ans = 0;
  87.                     for(int i = 0; i < opdn ; i++){
  88.                         ans = ans + opd_stack.top();
  89.                         opd_stack.pop();
  90.                     }
  91.                 }else if(op == '*'){
  92.                     if(opdn < 2){
  93.                         flag = 0;
  94.                         break;
  95.                     }else{
  96.                         ans = 1;
  97.                         for(int i = 0; i < opdn ; i++){
  98.                             ans = ans * opd_stack.top();
  99.                             opd_stack.pop();
  100.                         }
  101.                     }
  102.                 }else if(op == '('){
  103.                     //没有操作符的情况
  104.                     flag = 0;
  105.                     break;
  106.                 }
  109.                 if( !op_stack.empty() && op_stack.top() == '('){
  110.                     op_stack.pop();
  111.                 }else if(!op_stack.empty() && op_stack.top() != '('){
  112.                     // 反向括号不对应的情况 对应了其他符号
  113.                     flag = 0;
  114.                     break;
  115.                 }else if(op_stack.empty()){
  116.                     // 反向括号不对应的情况 没有对应了其他符号
  117.                     flag = 0;
  118.                     break;
  119.                 }
  121.                 // 一个括号的运算结果入栈，这个结果可能被上一层的括号使用
  122.                 opd_stack.push(ans);
  123.                 if(!opdn_stack.empty()){
  124.                     // 将上一层opdn的数量弹出
  125.                     opdn = opdn_stack.top();
  126.                     opdn_stack.pop();
  127.                 }else{
  128.                     flag = 0;
  129.                     break;
  130.                 }
  131.                 opdn++;  // 上一层的opd数量+ 1
  132.                 opd = -1;
  133.             }else if(exp[i] >= '0' && exp[i] <= '9'){
  134.                 if(opd == -1){
  135.                     // opd 开始情况
  136.                     opd = 0;
  137.                 }
  138.                 opd = opd * 10 + exp[i] - '0';
  139.             }else if(exp[i] == ' '){
  140.                 if(opd != -1){
  141.                     // 空格情况，如果存在opd则将其入栈
  142.                     opd_stack.push(opd);
  143.                     opdn++;
  144.                     opd = -1;
  145.                 }
  146.             }
  147.            // else if(exp[i] == '\0' || 0){
  148.            //     if(opd != -1){
  149.            //         opd_stack.push(opd);
  150.            //         opdn++;
  151.            //         opd = -1;
  152.            //   }
  153.            // }
  154.         }
  155.         if(op_stack.empty()){
  156.             if( opdn == 1 && flag != 0){
  157.                 printf("%d\n", opd_stack.top() );
  158.             }else{
  159.                 printf("invalid expression\n");
  160.             }
  161.         }else{
  162.             printf("invalid expression\n");
  163.         }
  164.     }
  165.     return 0;
  166. }

ZigZag Conversion

给一个字符串，以及row数（行数）。摆出N行的，之后在一行一行的输入。
根据N型的特点计算每一个位置的字符。

  1. class Solution {
  2. public:
  3.     string convert(string s, int numRows) {
  4.         int len = s.length();
  5.         int tmp, dis;
  6.         dis = 2 * numRows - 2;
  7.         if(dis == 0)
  8.             // 处理字符长度为1的情况
  9.             dis = 1;
  10.         char ans[len+1];
  11.         ans[len] = '\0';
  12.         for(int i = 0, cnt = 0 ; i < numRows ; i++){
  13.             if( i == 0 ){
  14.                 tmp = 0;
  15.                 while(tmp < len){
  16.                     ans[cnt++] = s[tmp];
  17.                     tmp = tmp + dis;
  18.                 }
  19.             }else if(i == numRows - 1){
  20.                 tmp = numRows - 1;
  21.                 while(tmp < len){
  22.                     ans[cnt++] = s[tmp];
  23.                     tmp = tmp + dis;
  24.                 }
  25.             }else{
  26.                 tmp = 0;
  27.                 while(tmp - i < len){
  28.                     if(tmp - i > 0){
  29.                         ans[cnt++] = s[tmp-i];
  30.                     }
  31.                     if(tmp + i < len){
  32.                         ans[cnt++] = s[tmp+i];
  33.                     }
  34.                     tmp = tmp + dis;
  35.                 }
  36.             }
  37.         }
  38.         return ans;
  39.     }
  40. };

Reverse Integer

将给定的int反转后输出，例如123输出321。符号相同。
唯一需要注意的一点就是反转之后数字可能会溢出int。
判断两个int溢出的方法可以反向验证，例如
A=B+C，是否溢出只需要验证A-B=C？。其他计算式同理。

  1. class Solution {
  2. public:
  3.     int reverse(int x) {
  4.         int ans, flag;
  5.         ans = 0;
  6.         if(x < 0){
  7.             flag = -1;
  8.             x = x * flag;
  9.         }
  10.         else flag = 1;
  11.         while(x){
  12.             ans = ans*10 + x%10;
  13.             if(ans - x%10 != (ans/10)*10)
  14.                 return 0;
  15.             x = x/10;
  16.         }
  17.         return flag*ans;
  18.     }
  19. };

判断计算是否越界

可以在计算之前先试用INT_MAX或者INT_MIN对计算进行判断。
例如

  1.  if(flag == 1){
  2.                 if(ans > INT_MAX / 10){
  3.                     return INT_MAX;
  4.                 }else if(ans > (INT_MAX - (str[k] - '0') * flag )/10 )
  5.                     return INT_MAX;
  7.             }else if(flag == -1){
  8.                 if(ans < INT_MIN / 10){
  9.                     return INT_MIN;
  10.                 }else if(ans < (INT_MIN - (str[k] - '0') * flag)/10)

水仙花问题

水仙花字符串，可以采用遍历所有的可能字串进行判断，当然字串需要划分是偶数串还是奇数串进行判断。

水仙花数，在没有额外空间的情况下判断一个数是不是水仙花数。

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注