发表于

8. String to Integer (atoi)

Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

Only the space character ‘ ‘ is considered as whitespace character.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example 1:

Input: “42”
Output: 42

Example 2:

Input: “ -42”
Output: -42
Explanation: The first non-whitespace character is ‘-‘, which is the minus sign.
Then take as many numerical digits as possible, which gets 42.

Example 3:

Input: “4193 with words”
Output: 4193
Explanation: Conversion stops at digit ‘3’ as the next character is not a numerical digit.

Example 4:

Input: “words and 987”
Output: 0
Explanation: The first non-whitespace character is ‘w’, which is not a numerical
digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:

Input: “-91283472332”
Output: -2147483648
Explanation: The number “-91283472332” is out of the range of a 32-bit signed integer.
Thefore INT_MIN (−231) is returned.

Solution:

思路:

  • 1, 除去' ', 之前是使用whil循环判断, 可直接用str.find_first_not_of(' ')找到第一个非空字符位置
  • 2, 用一个flag标记正负, 如果没有+-号, flag缺省为1
  • 3, ans等于扩大10倍+当前位, 如果溢出就要返回INT_MIN或者INT_MAX

错误的几个case

/*
// case1
Input:
"+-2"
Output:
2
Expected:
0
*/


/*
// case2
Input:
"2147483648"
Output:
-2147483648
Expected:
2147483647
*/

/*
// case3
Input:
"-91283472332"
Output:
-1089159116
Expected:
-2147483648
*/

最后的代码:

// Time:O(n), Space:O(1)
class Solution {
 public:
  int myAtoi(string str) {
    long long int ans = 0;                        // case3
    int flag = 1;
    int i = str.find_first_not_of(' ');
    if (str[i] == '-' || str[i] == '+') {         // case1
      flag = (str[i++] == '-') ? -1 : 1;
    }
    while ('0' <= str[i] && str[i] <= '9') {
      ans = ans*10 + (str[i++] - '0');
      if (ans * flag >= INT_MAX) return INT_MAX;  // case2
      if (ans * flag <= INT_MIN) return INT_MIN;
    }
    return ans * flag;
  }
};

发表于

125. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: “A man, a plan, a canal: Panama”
Output: true

Example 2:

Input: “race a car”
Output: false

Solution1:

过滤成回文串去计算, 需要O(n)的空间复杂度

// Time:O(n), Space:O(n)
class Solution {
 public:
  bool isPalindrome(string s) {
    if (s.length() == 0) return true;
    string t;
    for (char c : s) {
      if (isdigit(c) || isalpha(c)) {
        t += tolower(c);
      }
    }
    int n = t.length();
    for (int i = 0; i <= n/2; i++) {
      if (t[i] != t[n-1-i]) return false;
    }
    return true;
  }
};

Solution2:

用two pointers的方法, 在原地进行判断,

注意点:

  • 数字和字母, 可以用isalnum()这个函数..
  • 注意还要ignore case, 因此使用tolower在判断前。
// Time:O(n), Space:O(1)
// two pointers, in-place
class Solution {
 public:
  bool  isPalindrome(string s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
      while (isalnum(s[i]) == false && i < j) i++;
      while (isalnum(s[j]) == false && i < j) j--;
      if (tolower(s[i]) != tolower(s[j])) return false;
      i++;
      j--;
    }
    return true;
  }
};

发表于

242. Valid Anagram

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = “anagram”, t = “nagaram”
Output: true

Example 2:

Input: s = “rat”, t = “car”
Output: false

Note:

You may assume the string contains only lowercase alphabets.

Follow up:

What if the inputs contain unicode characters? How would you adapt your solution to such case?

Solution1:

使用sort

class Solution {
 public:
  bool isAnagram(string s, string t) {
    if (s.length() != t.length()) {
      return false;
    }
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());

    for (int i = 0; i < s.length(); i++) {
      if (s[i] != t[i]) return false;
    }
    return true;
  }
};

简化版本

class Solution {
 public:
  bool isAnagram(string s, string t) {
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    if (s == t) return true;
    return false;
  }
};

Solution2:

建立Hash表, key是char, 对应该字符出现的次数. 一个字符串加一个字符串减。
这里使用散列表实现的unodered_map

class Solution {
 public:
  bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false;
    unordered_map<char, int> counts;
    for (int i = 0; i < s.length(); i++) {
      counts[s[i]]++;
      counts[t[i]]--;
    }
    for (auto count : counts) {
      if (count.second) return false;
    }
    return true;
  }
};

Solution3

用ascii码作为key值, 不用map容器用数组

class Solution {
 public:
  bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false;
    int counts[26];
    memset(counts, 0, sizeof(counts));
    for (int i = 0; i < s.length(); i++) {
      counts[s[i] - 'a']++;
      counts[t[i] - 'a']--;
    }
    for (int i = 0; i < 26; i++) {
      if (counts[i]) return false;
    }
    return true;
  }
};

发表于

387. First Unique Character in a String

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = “leetcode”
return 0.

s = “loveleetcode”,
return 2.

Note: You may assume the string contain only lowercase letters.

Solution:

因为不到最后无法得知出现是否重复, 于是建立一个Hash表,大小为26个lower字母, 存放每个字符出现的次数.

// Time:O(n), Space:O(1)
class Solution {
 public:
  int firstUniqChar(string s) {
    int cnt[30];
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < s.length(); i++) {
      cnt[s[i] - 'a']++;
    }
    for (int i = 0; i < s.length(); i++) {
      if (cnt[s[i] - 'a'] == 1) return i;
    }
    return -1;
  }
};

发表于

7. Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note:

Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Solution:

不需要重新写大整数类

  • 1, 位数*10代表着升位。
  • 2, 可通过乘10再除以10是否相等来判断是否溢出

AC的解法:

class Solution {
 public:
  int reverse(int x) {
    int result = 0, judge = 0;
    while (x) {
      judge = result * 10;
      if (judge / 10 != result) {
        return 0;
      }
      result = judge;
      result += x % 10;
      x /= 10;
    }
    return result;
  }
};

之前错误百出的解法:

class Solution {
 public:
  int reverse(int x) {
    if (x < pow(-2, 31) || x > pow(2, 31) - 1) return 0;
    vector<int> nums;
    while (x) {
      nums.push_back(x % 10);
      x /= 10;
    }
    int ans = 0, n = nums.size();
    for (int i = n-1; i >= 0; i--) {
      int d = pow(10, i) * nums[n-1-i];
      printf("d = %d\n", d);
      if (d % 10 == 0 || d == 1 || d == -1) {
        if ((ans > pow(2, 31) - 1 - d) || (ans < pow(-2, 31) - d))
          return 0;
        ans += d;
      } else {
        return 0;
      }
      // if (ans < pow(-2, 31) || ans > pow(2, 31) - 1) return 0;
    }
    return ans;
  }
};

发表于

1079 延迟的回文数(20)

非回文数也可以通过一系列操作变出回文数。首先将该数字逆转，再将逆转数与该数相加，如果和还不是一个回文数，就重复这个逆转再相加的操作，直到一个回文数出现。如果一个非回文数可以变出回文数，就称这个数为延迟的回文数。（定义翻译自 https://en.wikipedia.org/wiki/Palindromic_number ）

给定任意一个正整数，本题要求你找到其变出的那个回文数。

输入格式：

输入在一行中给出一个不超过1000位的正整数。

输出格式：

对给定的整数，一行一行输出其变出回文数的过程。每行格式如下

A + B = C
其中 A 是原始的数字，B 是 A 的逆转数，C 是它们的和。A 从输入的整数开始。重复操作直到 C 在 10 步以内变成回文数，这时在一行中输出 C is a palindromic number.；或者如果 10 步都没能得到回文数，最后就在一行中输出 Not found in 10 iterations.。

输入样例 1：

97152

输出样例 1：

97152 + 25179 = 122331
122331 + 133221 = 255552
255552 is a palindromic number.

输入样例 2：

196

输出样例 2：

196 + 691 = 887
887 + 788 = 1675
1675 + 5761 = 7436
7436 + 6347 = 13783
13783 + 38731 = 52514
52514 + 41525 = 94039
94039 + 93049 = 187088
187088 + 880781 = 1067869
1067869 + 9687601 = 10755470
10755470 + 07455701 = 18211171
Not found in 10 iterations.

Solution:

case6需要实现大整数, 构造, 转换(change), 相加(add), 转成字符串(bignToString)

#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

struct Bign {
  int d[1005];
  int len;
  Bign() {
    memset(d, 0, sizeof(d));
    len = 0;
  }
};

Bign change(string str) {
  Bign a;
  a.len = str.length();
  for (int i = 0; i < a.len; i++) {
    a.d[i] = str[a.len-1-i] - '0';
  }
  return a;
}

Bign add(Bign a, Bign b) {
  Bign c;
  int carry = 0;
  for (int i = 0; i < a.len || i < b.len; i++) {
    int temp = a.d[i] + b.d[i] + carry;
    c.d[c.len++] = temp % 10;
    carry = temp / 10;
  }
  if (carry) {
    c.d[c.len++] = carry;
  }
  return c;
}

string bignToString(Bign a) {
  string s;
  for (int i = a.len-1; i >= 0; i--) {
    s += (a.d[i] + '0');
  }
  return s;
}

int is_p(string s) {
  if (s.length() == 1) return 1;
  int i = 0, j = s.length() - 1;
  while (i <= j) {
    if (s[i] != s[j]) return 0;
    i++; j--;
  }
  return 1;
}

int main() {
  string A, B, C;
  cin >> A;
  if (is_p(A)) {
    cout << A << " is a palindromic number." << endl;
    return 0;
  }
  int find = 0, cnt = 0;
  while (cnt < 10) {
    string tmp_s = A;
    reverse(tmp_s.begin(), tmp_s.end());
    B.clear(); B = tmp_s;

    Bign intc = add(change(A), change(B));

    // int tmp_c = stoi(A) + stoi(B);        // case6, need to convert to bign
    // C.clear(); C = to_string(tmp_c);
    C.clear(); C = bignToString(intc);       // debug case6

    cout << A << " + " << B << " = " << C << endl;

    if (is_p(C)) {
      cout << C << " is a palindromic number." << endl;
      find = 1;
      break;
    }
    A.clear(); A = C;
    cnt++;
  }
  if (!find) {
    cout << "Not found in 10 iterations." << endl;
  }
  return 0;
}

发表于

1070 结绳(25)

给定一段一段的绳子，你需要把它们串成一条绳。每次串连的时候，是把两段绳子对折，再如下图所示套接在一起。这样得到的绳子又被当成是另一段绳子，可以再次对折去跟另一段绳子串连。每次串连后，原来两段绳子的长度就会减半。

rope.jpg

给定 N 段绳子的长度，你需要找出它们能串成的绳子的最大长度。

输入格式：

每个输入包含 1 个测试用例。每个测试用例第 1 行给出正整数 N (2≤N≤10^4)；第 2 行给出 N 个正整数，即原始绳段的长度，数字间以空格分隔。所有整数都不超过10^4。

输出格式：

在一行中输出能够串成的绳子的最大长度。结果向下取整，即取为不超过最大长度的最近整数。

输入样例：

8
10 15 12 3 4 13 1 15

输出样例：

14

Solution:

主要要弄明白一个问题, 绳子怎么拼能够获得最大长度。

使得长度越长的绳子, 被折叠的次数越少; 尽可能让长度短的绳子折叠的更多(既然一定需要折叠的话).

由于不会在数学上进行证明, 就先写完算法, 然后跟案例数据去匹配验证。

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 10050;
int a[MAXN];

int main() {
  int N, tmp; scanf("%d", &N);

  for (int i = 0; i < N; i++) {
    scanf("%d", &tmp);
    a[i] = tmp;
  }
  sort(a, a+N);
  double sum = a[0];
  for (int i = 1; i < N; i++) {
    sum = (sum + a[i]) / 2;
  }
  printf("%d\n", (int)floor(sum));
  // printf("sum = %lf", sum);
  return 0;
}

发表于

1069 微博转发抽奖(20)

  1. 微博转发抽奖(20)
    小明 PAT 考了满分，高兴之余决定发起微博转发抽奖活动，从转发的网友中按顺序每隔 N 个人就发出一个红包。请你编写程序帮助他确定中奖名单。

输入格式：

输入第一行给出三个正整数 M（≤ 1000）、N 和 S，分别是转发的总量、小明决定的中奖间隔、以及第一位中奖者的序号（编号从 1 开始）。随后 M 行，顺序给出转发微博的网友的昵称（不超过 20 个字符、不包含空格回车的非空字符串）。

注意：可能有人转发多次，但不能中奖多次。所以如果处于当前中奖位置的网友已经中过奖，则跳过他顺次取下一位。

输出格式：

按照输入的顺序输出中奖名单，每个昵称占一行。如果没有人中奖，则输出 Keep going…。

输入样例 1：

9 3 2
Imgonnawin!
PickMe
PickMeMeMeee
LookHere
Imgonnawin!
TryAgainAgain
TryAgainAgain
Imgonnawin!
TryAgainAgain

输出样例 1：

PickMe
Imgonnawin!
TryAgainAgain

输入样例 2：

2 3 5
Imgonnawin!
PickMe

输出样例 2：

Keep going…

Solution:

注意需要先进行一次统一读入, 不能跳着读。
重复用map来判断, 用一个keep变量01来判断是否有中奖的同学.

#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;

map<string, int> mp;
vector<string> v;
int main() {
  int M, N, S; cin >> M >> N >> S;
  int keep = 1;
  getchar();
  // debug, 读入问题
  for (int i = 0; i < M; i++) {
    string tmp_s; getline(cin, tmp_s);
    v.push_back(tmp_s);
  }
  for (int i = 0; i < M; i++) {
    if (i == S-1) {
      keep = 0;
      cout << v[i] << endl;
      mp[v[i]] = 1;
      int j = i + N;
      while (j <= M-1) {
        auto it = mp.find(v[j]);
        if (it != mp.end()) {
          j = j+1;
        } else {
          cout << v[j] << endl;
          mp[v[j]] = 1;
          j = j+N;
        }
      }
      break;
    }
  }
  if (keep) {
    cout << "Keep going..." << endl;
  }
  return 0;
}

发表于

1040 有几个PAT(25)

字符串 APPAPT 中包含了两个单词 PAT，其中第一个 PAT 是第 2 位(P)，第 4 位(A)，第 6 位(T)；第二个 PAT 是第 3 位(P)，第 4 位(A)，第 6 位(T)。

现给定字符串，问一共可以形成多少个 PAT？

输入格式：

输入只有一行，包含一个字符串，长度不超过10^5 ，只包含 P、A、T 三种字母。

输出格式：

在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大，只输出对 1000000007 取余数的结果。

输入样例：

APPAPT

输出样例：

2

Solution:

先用最暴力的方法求解， 1,2AC, 后三个超时, 15分, 如何解决3sum问题?

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;

int main() {
  string s; cin >> s;
  int n = s.length(), cnt = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'P') {
      for (int j = i+1; j < n; j++) {
        if (s[j] == 'A') {
          for (int k = j+1; k < n; k++) {
            if (s[k] == 'T') {
              cnt++;
            }
          }
        }
      }
    }
  }
  printf("%d\n", cnt ? cnt % 1000000007 : 0);
  return 0;
}

其实这道题目跟3sum问题还是有区别, 是属于观察特性, 总结规律的题目.

对于每一个A来说, 可以跟它组合个数是, 前面P的个数*后面T的个数.

给出一种新的解法。

// 计算每个A左边有几个P, 右边有几个T, 相乘
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;

int main() {
  string s; cin >> s;
  int sum = 0, n = s.length();
  for (int i = 0; i < n; i++) {
    if (s[i] == 'A') {
      int left_P = 0, right_T = 0;
      int p = i-1, q = i+1;
      while (p >= 0) {
        if (s[p] == 'P') left_P++;
        p--;
      }
      while (q < n) {
        if (s[q] == 'T') right_T++;
        q++;
      }
      sum += left_P * right_T;
    }
  }
  printf("%d\n", sum);
  return 0;
}
// case3, 4, wrong

但这个复杂度, 仍然后很高, 因为找过的p又重新找了。

我在外公家用他的麻将牌模拟了一遍, 找出一种新解法。
既然是需要左边的P, 右边的T, 如果从左往右扫描的话, 先用一次扫描记录字符串所有T的个数right_t, 只要在下次扫描过程中, 用left_p记录从左边到A所有P的个数, 碰到T之后, right_t减1, 碰到A就左右相乘

坑点, 每次相加就需要取余数, 这里有点理不清楚, 但是先这样理解着吧。

// 优化递推的做法,
// Time: O(n), Space:O(1)

#include <iostream>
#include <string>
using namespace std;

int main() {
  string s; getline(cin, s);
  int sum = 0, cnt_p = 0, cnt_t = 0;
  int n = s.length();
  for (int i = 0; i < n; i++) {
    if (s[i] == 'T') cnt_t++;
  }
  for (int i = 0; i < n; i++) {
    if (s[i] == 'P') {
      cnt_p++;
    } else if (s[i] == 'T') {
      cnt_t--;
    } else if (s[i] == 'A') {
      sum = (sum + cnt_p * cnt_t) % 1000000007;
    }
  }
  cout << sum << endl;
  return 0;
}

发表于

1044. 火星数字(20)

火星人是以 13 进制计数的：

地球人的 0 被火星人称为 tret。
地球人数字 1 到 12 的火星文分别为：jan, feb, mar, apr, may, jun, jly, aug, sep, oct, nov, dec。
火星人将进位以后的 12 个高位数字分别称为：tam, hel, maa, huh, tou, kes, hei, elo, syy, lok, mer, jou。
例如地球人的数字 29 翻译成火星文就是 hel mar；而火星文 elo nov 对应地球数字 115。为了方便交流，请你编写程序实现地球和火星数字之间的互译。

输入格式：

输入第一行给出一个正整数 N（<100），随后 N 行，每行给出一个 [0, 169) 区间内的数字 —— 或者是地球文，或者是火星文。

输出格式：

对应输入的每一行，在一行中输出翻译后的另一种语言的数字。

输入样例：

4
29
5
elo nov
tam

输出样例：

hel mar
may
115
13

Solution:

先判断读入的string字符串, 首位是否为数字, 来决定是哪种转译方法.

low, high建立成数组, 用数组建立map散列, 可用于英文和数字之间的转换.
对于有两个英文的火星文, 需要用find在string找到” “字符串, 然后分别转译, 按照进制进行转换.

坑点:

  • 1, 01问题, 低位tret的是可以作为0的, 高位0是tam, 实际上是1, 相应需要减1
  • 2, 如果是13的话, 低位是0, 转译后不被翻译。case2, 4
  • 3, 逻辑一定会有疏漏, 要学着自己写测试案例, 如下:
    写测试函数的技巧
    /*
    8
    0
    12
    13
    26
    27
    tret
    jan
    hel jan
    */

    /*
    tret
    dec
    tam
    hel
    hel jan
    0
    1
    27
    */

    /*
    tret
    dec
    tam tret
    hel tret
    hel jan
    0
    1
    27
    */

实际代码如下:

#include <iostream>
#include <string>
#include <map>
using namespace std;


map<string, int> mp_low;
map<string, int> mp_high;

int main() {
  int N; cin >> N;
  string low[] = {"tret", "jan", "feb", "mar", "apr", "may",
                  "jun", "jly", "aug", "sep", "oct", "nov", "dec"};
  string high[] = {"tam", "hel", "maa", "huh", "tou", "kes",
                   "hei", "elo", "syy", "lok", "mer", "jou"};  // a-1
  for (int i = 0; i < 13; i++) {
    mp_low[low[i]] = i;
  }
  for (int i = 1; i < 13; i++) {
    mp_high[high[i-1]] = i;
  }

  string s;
  getchar();
  while (N--) {
    getline(cin, s);
    if (isdigit(s[0])) {
      int a = stoi(s) / 13, b = stoi(s) % 13;
      if (a == 0) {
        cout << low[b] << endl;
      } else {
        cout << high[a-1];
        if (b != 0) {             // case2, 4
          cout << " " << low[b];
        }
        cout << endl;
      }
    } else {
      int pos = s.find(" ");
      int ans;
      if (pos != string::npos) {
        string s1 = s.substr(0, 3), s2 = s.substr(pos+1, 3);
        ans = mp_high[s1] * 13 + mp_low[s2];
      } else {
        // ans = mp_low[s];    // eror
        auto it_low = mp_low.find(s);
        if (it_low != mp_low.end()) {
          ans = mp_low[s];
        } else {
          ans = mp_high[s] * 13;
        }
      }
      cout << ans << endl;
    }
  }
  return 0;
}

// case 2, 4 wrong answer;