发表于

1063 计算谱半径(20)

在数学中，矩阵的“谱半径”是指其特征值的模集合的上确界。换言之，对于给定的 n 个复数空间的特征值 它们的模为实部与虚部的平方和的开方，而“谱半径”就是最大模。
现在给定一些复数空间的特征值，请你计算并输出这些特征值的谱半径。

输入格式：

输入第一行给出正整数 N（≤ 10 000）是输入的特征值的个数。随后 N 行，每行给出 1 个特征值的实部和虚部，其间以空格分隔。注意：题目保证实部和虚部均为绝对值不超过 1000 的整数。

输出格式：

在一行中输出谱半径，四舍五入保留小数点后 2 位。

输入样例：

5
0 1
2 0
-1 0
3 3
0 -3

输出样例：

4.24

Solution:

注意, 开方是平方的逆过程.

对小数位后四舍五入的做法, 先将double扩大100倍(小数点后2位), 进位后, 缩小100倍.
其实就是进小数点后2位。

#include <cmath>
#include <cstdio>

int main() {
  int N, a, b; scanf("%d", &N);
  double max = 0, tmp;

  while (N--) {
    scanf("%d %d", &a, &b);
    tmp = sqrt(a*a+b*b);
    if (tmp > max) max = tmp;
  }
  printf("%.2lf", floor(max * 100 + 0.5)/100);

  return 0;
}

发表于

1062 最简分数(20)

一个分数一般写成两个整数相除的形式：N/M，其中 M 不为0。最简分数是指分子和分母没有公约数的分数表示形式。

现给定两个不相等的正分数 N1/M1 和 N2/M2，要求你按从小到大的顺序列出它们之间分母为 K 的最简分数。

输入格式：

输入在一行中按 N/M 的格式给出两个正分数，随后是一个正整数分母 K，其间以空格分隔。题目保证给出的所有整数都不超过 1000。

输出格式：

在一行中按 N/M 的格式列出两个给定分数之间分母为 K 的所有最简分数，按从小到大的顺序，其间以 1 个空格分隔。行首尾不得有多余空格。题目保证至少有 1 个输出。

输入样例：

7/18 13/20 12

输出样例：

5/12 7/12

Solution:

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
int limit[1000];
int mp[2500];

int main() {
  char s1[15], s2[15]; int K;
  scanf("%s %s %d", s1, s2, &K);
  getchar();     // print
  int limit_n = 0;

  for (int i = 2; i <= K; i++) {   // bug01, i != 0
    if (K % i == 0) {
      limit[limit_n++] = i;
    }
  }
  // 仍旧可以优化

  int N1, M1, N2, M2;
  sscanf(s1, "%d/%d", &N1, &M1);
  sscanf(s2, "%d/%d", &N2, &M2);
  memset(mp, 0, sizeof(mp));

  double da =  N1/((double)M1/K), db =  N2/( (double) M2/K);
  if (da > db) {double tmp = da; da = db; db = tmp;}
  int a = ceil(da), b = floor(db);

  if (K == 1) {                         // case1
    for (int i = a; i < b; i++) {
      if (-0.00005 < i - da && i - da < 0.000005) continue;
      if (i != a) printf(" ");
      printf("%d/%d", i, K);
    }
    return 0;
  }

  int scale = 1, over = 0;
  while (!over) {
    over = 1;
    for (int i = 0; i < limit_n; i++) {
      int tmp = limit[i] * scale;
      if (tmp <= b) {
        over = 0;
        if (a <= tmp) {
          mp[tmp] = 1;
        }
      }
    }
    scale++;
    if (over) break;
  }

  int first = 0;
  for (int i = a; i < db; i++) {
    if (-0.00005 < i - da && i - da < 0.000005) continue;   // case2
    if (!mp[i]) {
      if (first) printf(" ");
      printf("%d/%d", i, K);
      first = 1;
    }
  }
  printf("\n");
  return 0;
}

发表于

283. Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

Solution:

因为需要原地排序, 选择用交换.
让交换的次数尽可能的少, 从尾部向前找, 找到的第一个数交换到尾部, 然后让尾部”缩短”.

// 从右向左找到0, 用j标记位置, i交换到尾部, 找到下一个0, 交换到尾部之前的位置.
// Time:O(n^2), Space:O(1)
class Solution {
 public:
  void moveZeroes(vector<int>& nums) {
    
    int n = nums.size();
    int i = n-1, j;
    while (i >= 0) {
      if (nums[i] == 0) {
        while (i < n-1) {
          swap(nums[i], nums[i+1]); i++;
        }
        n--;
        i = j;
      }
      i--;
    }
  }
};

但应该还能考虑一种, 直接将0交换到尾部对应的位置, 而不是一步步交换;

这种交换的难点在于对, 要保持除0外的元素的顺序不变.

发表于

66. One Plus

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Solution:

先后两遍扫描,
从右开始向左计算, 当前位置满10修改成0, 左位置+1.
若首位10, vector尾部添加0, 首位修改成0, 中间添0.

class Solution {
 public:
  vector<int> plusOne(vector<int> &digits) {
    int n = digits.size();
    int i = n; digits[--i]++;
    while (digits[i] == 10 && i > 0) {
      digits[i] = 0;
      digits[--i]++;
    }
    if (digits[0] == 10) {
      digits.push_back(0);
      digits[0] = 1;
      for (int j = 1; j < n; j++) digits[j] = 0;
    }

    return digits;
  }
};

发表于

350. Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:

Each element in the result should appear as many times as it shows in both arrays.

The result can be in any order.

Solution:

nums1找到num2中的存在的元素, nums2共同存在的元素删除, nums1不存在元素删除.

class Solution {
 public:
  vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    if (nums1.size() == 0 || nums2.size() == 0) return {};
    int i = 0;
    while (i < nums1.size()) {
      int exist = 0;
      for (int j = 0; j < nums2.size(); j++) {
        if (nums1[i] == nums2[j]) {
          nums2.erase(nums2.begin() + j);
          exist = 1;
          break;
        }
      }
      if (!exist) {
        nums1.erase(nums1.begin() + i);
      } else {
        i++;
      }
    }
    return nums1;
  }
};

Follow up:

1, What if the given array is already sorted? How would you optimize your algorithm?

// 两个有序数组求交
class Solution {
 public:
  vector<int> intersect(vector<int> &nums1, vector<int> &nums2) {
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());
    vector<int> ans_v;
    int i = 0, j = 0;
    while (i < nums1.size() && j < nums2.size()) {
      if (nums1[i] == nums2[j]) {
        ans_v.push_back(nums1[i]); i++; j++;
      } else {
        nums1[i] < nums2[j] ? i++ : j++;
      }
    }
    return ans_v;
  }
};

发表于

136. Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

Solution:

两遍遍历的方法:

// Time:O(n^2), Space:O(1);
class Solution {
 public:
  int singleNumber(vector<int> &nums) {
    if (nums.size() == 1) return nums[0];
    int n = nums.size();
    for (int i = 0; i < n; i++) {
      int ok = 0;
      for (int j = 0; j < n; j++) {
        if (i == j) continue;
        if (nums[i] == nums[j]) {ok = 1; break;}
      }
      if (!ok) return nums[i];
    }
    return 0;
  }
};

异或操作的做法,

// ^异或操作, 两次异或同一数, 结果相同
// Time:O(n), Space:O(1);
class Solution {
 public:
  int singleNumber(vector<int> &nums) {
    int ans = 0;
    for (int i = 0; i < nums.size(); i++) {
      ans ^= nums[i];     // 4 ^ 2 ^ 2 ^ 3 ^ 3 = 4 ^ 0 = 4
    }
    return ans;
  }
};

a ^ b   // 如果a, b相同, 则0; 如果不同则1

将两两相同的数字合并, 运算后只得到剩下的一个single number

发表于

217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Solution:

// 两遍扫描, Time:O(n), Spcae:O(1)
class Solution {
 public:
  bool containsDuplicate(vector<int> &nums) {
    if (nums.size() == 1 || nums.size() == 0) return 0;
    int n = nums.size();
    for (int i = 0; i < n-1; i++) {
      for (int j = i + 1; j < n; j++) {
        if (nums[i] == nums[j]) return 1;
      }
    }
    return 0;
  }
};
// 先排序, 对排序后的的数组1开始的元素, 检查前一个元素是否相等。
// Time:O(n*logn), Space:O(1)
class Solution {
 public:
  bool containsDuplicate(vector<int> &nums) {
    if (nums.size() == 1 || nums.size() == 0) return 0;

    sort(nums.begin(), nums.end());

    for (int i = 1; i < nums.size(); i++) {
      if (nums[i] == nums[i-1]) return 1;
    }
    return 0;
  }
};

发表于

189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?

Solution:

不断往新数组中添加元素, 该元素的索引通过求余数得到

// Time:O(n), Space:O(n);
class Solution {
 public:
  void rotate(vector<int>& nums, int k) {
    vector<int> v;
    int n = nums.size();
    for (int i = k; i < n + k; i++) {
      v.push_back(nums[i % n]);
    }
    nums = v;
    // return v;
  }
};

扫描k遍, 每一遍都将首个元素移到最后

// ERROR:
// Time:O(n^2), Space:O(1);
class Solution {
 public:
  void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    for (int i = 0; i < k; i++) {
      for (int j = 0; j < n-1; j++) {
        int tmp = nums[j]; nums[j] = nums[j+1]; nums[j+1] = tmp;
      }
    }
  }
};  // 从左往右写反

扫描k遍， 每遍都将最后一个元素移动最前

// Time:O(n^2), Space:O(1);
class Solution {
 public:
  void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    for (int i = 0; i < k; i++) {
      for (int j = n-1; j > 0; j--) {
        int tmp = nums[j]; nums[j] = nums[j-1]; nums[j-1] = tmp;
      }
    }
  }
};  // 改成从右往左
// 但是Time Limit Exceeded

最新的解法,

0 1 2 3 4
3 4 0 1 3

观察数组构造, 将3通过交换到最首位, 4位于其次

// Time:   Space:O(n)
class Solution {
 public:
  void rotate(vector<int>& nums, int k) {
    if (nums.size() == 0 || k == 0 || k % nums.size() ==0)
      return;
    int n = nums.size(), m = k % n;

    for (int i = n-m; i <= n-1; i++) {
      for (int j = i; j > i-(n-m); j--) {
        int tmp = nums[j]; nums[j] = nums[j-1]; nums[j-1] = tmp;
      }
    }
  }
};  // 改成从右往左, 添加数组为空, k为零的情况, 求余也为0的情况

发表于

1029 旧键盘(20)

旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。

输入格式：

输入在 2 行中分别给出应该输入的文字、以及实际被输入的文字。每段文字是不超过 80 个字符的串，由字母 A-Z（包括大、小写）、数字 0-9、以及下划线 _（代表空格）组成。题目保证 2 个字符串均非空。

输出格式：

按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有 1 个坏键。

输入样例：

7_This_is_a_test
_hs_s_a_es

输出样例：

7TI

Solution:

通过实际被输出的文字建立可行的Hash表, f(key) = toupper(key) - ‘0’;

某个下标对应的值为1代表可行.

遍历输入的那段文字, 若不在Hash表中的, 则是坏键。

坑点:
1, 因为英文字母只输出大写, 所以建表时, 把所有的alpha变成大小来建立, 用大写索引, 用大写输出.
2, 不用在意ascii码, 只要随便取个字符, 记录相对距离就可以。
3, 因为要保证每个坏键只输出一次, 找到一个坏键之后, 在hash表中改成1, 下次这个碰到这个键, 就可以用if避开它了。

#include <cstdio>
#include <cstring>
#include <iostream>
int ok[500];
char s[85];
char rst[85];

int main() {
  scanf("%s %s", s, rst);
  for (int i = 0; i < strlen(rst); i++) {
    ok[toupper(rst[i]) - '0'] = 1;
  }

  for (int i = 0; i < strlen(s); i++) {
    if (!ok[  toupper(s[i]) - '0']) {
      printf("%c", toupper(s[i]));
      ok[toupper(s[i]) - '0'] = 1;   // bug01
    }
  }
  return 0;
}

发表于

1021 个位数统计(15)

给定一个 k 位整数 N=d, 请编写程序统计每种不同的个位数字出现的次数。
例如：给定 N=100311，则有 2 个 0，3 个 1，和 1 个 3。

输入格式：

每个输入包含 1 个测试用例，即一个不超过 1000 位的正整数 N。

输出格式：

对 N 中每一种不同的个位数字，以 D:M 的格式在一行中输出该位数字 D 及其在 N 中出现的次数 M。要求按 D 的升序输出。

输入样例：

100311

输出样例：

0:2
1:3
3:1

Solution:

统计和查找用Hash表.
以字符数组的形式读入”整数”, 扫描这个字符数组, 每个数字字符ch对应的Hash表位置是它的ch-‘a’位置. 该位置变量+1

扫描完成后, 扫描Hash表, 如果某个地址上值不为0就打印出个数, 自然升序.

#include <cstdio>
#include <cstring>

int cnt[11];
char s[1050];
int main() {
  scanf("%s", s);
  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < strlen(s); i++) {
    cnt[s[i]-'0']++;
  }
  int flag = 0;
  for (int i = 0; i < 10; i++) {
    if (cnt[i]) {
      if (!flag) {
        flag = 1;
      } else {
        printf("\n");
      }
      printf("%d:%d", i, cnt[i]);
    }
  }
  return 0;
}