OJ每日练习（6）

Posted on | In

题目名称

  1. Gray Code(Leetcode #89)
  2. Gas Station(Leetcode #134）
  3. Candy(Leetcode #135)
  4. Single Number(Leetcode #136)
  5. 二进制中1的个数（剑指offer #15）
  6. 数值的整数次方（剑指offer #16）
  7. 打印从1到最大的n位数(剑指offer #17)
  8. 删除链表的节点（剑指offer #18）

Gray Code(Leetcode #89)

题目描述

The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
Example 1:

1
2
3
4
5
6
7
Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

For a given n, a gray code sequence may not be uniquely defined.For example, [0,2,3,1] is also a valid gray code sequence.
1
2
3
4
00 - 0
10 - 2
11 - 3
01 - 1

解题思路

解题的核心思想在于，格雷码与自然数的二进制码存在对应关系，其公式为：Nth Gray Code == n^(n>>1)。

解题方案

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> grayCode(int n) {
        if(n==0)
            return vector<int>(1,0);
        vector<int> res(pow(2,n),0);
        for(size_t index=1;index!=pow(2,n);++index)
            res[index]=index^(index>>1);
        return res;
    }
};

Gas Station(Leetcode #134）

题目描述

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.
Note:
If there exists a solution, it is guaranteed to be unique.Both input arrays are non-empty and have the same length.Each element in the input arrays is a non-negative integer.
Example 1:

1
2
3
4
5
6
7
8
9
10
11
Input: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.Therefore, return 3 as the starting index.

Example 2:
1
2
3
4
5
6
7
8
9
10
Input: 
gas  = [2,3,4]
cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.Therefore, you can't travel around the circuit once no matter where you start.

解题思路

第一种解法基于暴力，对每一个节点都判断其能否到达终点。
第二种解法基于推论：若从点A无法到达点B，那么A到B之间的任何一个点都不可能到达点B。因此只需要在失败后将目光投向下一个节点即可（本题的思路让我想起了最大子序列和）。

解题方案

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        for (size_t index = 0; index != gas.size(); ++index) {
		    int res = canTraverse(index, gas, cost);
		    if (res != -1) return res;
		    else continue;
	    }
	    return -1;
    }
private:
    int canTraverse(size_t i, vector<int> & gas, vector<int> &cost) {
	    int n = gas.size();
        int res=0;
	    for (size_t loop = 0; loop != n; ++loop) {
		    res += (gas[(i + loop) % n] - cost[(i + loop) % n]);
		    if (res < 0) return -1;
	    }
	    return i;
    }
};

一次遍历

（tank表征当前存量，total表征需要克服的缺额）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int start=0,total=0,tank=0;
        for(size_t i=0;i!=gas.size();++i){
            tank+=gas[i]-cost[i];
            if(tank<0){
                start=i+1;
                total+=tank;
                tank=0;
            }
        }
        return total+tank<0?-1:start;
    }
};

Candy(Leetcode #135)

题目描述

There are N children standing in a line. Each child is assigned a rating value.You are giving candies to these children subjected to the following requirements:Each child must have at least one candy.Children with a higher rating get more candies than their neighbors.What is the minimum candies you must give?
Example 1:

1
2
3
Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

解题思路

使用两个数组，一个从前向后遍历，确保从前向后的区间必然保证优先级，一个从后向前，做同样的动作。最终每个孩子分到的糖果是这两个数组中对应位置的最大值。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int candy(vector<int>& ratings) {
        if(ratings.size()<=1)
            return ratings.size();
        vector<int> temp1(ratings.size(),1);
        vector<int> temp2(temp1);
        for(size_t i=1;i!=ratings.size();++i)
            if(ratings[i]>ratings[i-1])
                temp1[i]=temp1[i-1]+1;
        for(size_t i=ratings.size()-2;i!=-1;--i)
            if(ratings[i]>ratings[i+1])
                temp2[i]=temp2[i+1]+1;
        int res=0;
        for(size_t i=0;i!=temp1.size();++i)
            res+=max(temp1[i],temp2[i]);
        return res;
    }
};

Single Number(Leetcode #136)

题目描述

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

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

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

解题思路

对于重复元素，需要了解的一个重要性质是：A^A=0；了解这个后这道题自然迎刃而解。

解题方案

1
2
3
4
5
6
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        return accumulate(nums.cbegin(),nums.cend(),0,bit_xor<int>());
    }
};

扩展

倘若当前数组内存在两个只出现了一次的元素，如何找出这两个元素？

解题思路

全部异或后得到这两个数的异或值diff,然后执行diff&=-diff，可以获取这两个数从后向前第一个不相等的位（例如00001,00100）等。对于原有数组中的元素，必然可以被分为两组，一组该位为0，一组该位为1。这两个数就位于这两组之中，再次对两组执行异或运算即可。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int diff = accumulate(data.cbegin(),data.cend(),0,bit_xor<int>());
        diff&=-diff;
        for(auto i:data)
            if(i&diff)
                *num1^=i;
            else
                *num2^=i;
    }
};

更进一步的扩展

如果当前数组内元素都出现了3次，仅有一个只出现了两次，如何找出这个元素？

解题思路

用二进制模拟三进制，思路如下：因为一个元素最多出现3次，那么采用2个bit即可表征所有状态：00—>01->10->00;因此我们设立两个int：ones、twos，用来记录元素出现的次数。因此，建立真值表如下所示：

twos ones number output twos output ones
0 0 1 0 1
0 1 1 1 0
1 0 1 0 0

综上，有运算式：

1
2
ones = (ones ^ nums[i]) & ~twos;
twos = (twos ^ nums[i]) & ones;

解题方案

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ones=0,twos=0;
        for(size_t index=0;index!=nums.size();++index){
            ones=ones^nums[index]&~twos;
            twos=twos^nums[index]&ones;
        }
        return ones;
    }
};

二进制中1的个数

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

解题思路

直接位运算，记住x&=(x-1)表示去掉最右边的1.

解题方案

1
2
3
4
5
6
7
8
9
class Solution {
public:
     int  NumberOf1(int n) {
        int res=0;
        while(n)
             n&=(n-1),++res;
        return res;
     }
};

数值的整数次方

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

解题思路

直接照抄了STL的解法，不过需要注意的是这里可能exponent是负数。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    double Power(double base, int exponent) {
      if(exponent==0)
          return 1;
      if(base==0)
          return 0;
      if(abs(base-1)<= 1e-10)
          return 1;
      bool flag = exponent>0?0:1;
      exponent = abs(exponent);
      while(!(exponent&1))
          base*=base,exponent>>=1;
      double result = base;
      exponent>>=1;
      while(exponent!=0){
          base*=base;
          if(exponent&1)
              result*=base;
          exponent>>=1;
      }
      return flag?1/result:result;
    }
};

打印从1到最大的n位数(剑指offer #17)

解题思路

本题的关键在于如何高精度表示数字，用数组或字符串存储即可。再配合上一节所说的Plus One即可打印所有数字，过程略去不表。

删除链表的节点（剑指offer #18）

题目描述

O（1）时间删除单链表的指定节点。

解题思路

该问题可以分为以下几步：

  1. 如果头结点为空或指定节点为空，直接返回。
  2. 单链表中仅有头结点，删除头结点后返回。
  3. 需要删除的点是尾节点，遍历链表，找到尾节点之前的点，令其next指向nullptr。
  4. 被删除的节点只是寻常节点（不需要获取前向节点），此时令其值为其next的值，其next指向next—>next即可。

解题方案

(仅给出最后一种情况的解答）

1
2
3
4
5
6
7
8
9
class Solution {
public:
    void deleteNode(ListNode* node) {
        if(node==nullptr)
            return;
        node->val=node->next->val;
        node->next=node->next->next;
    }
};