OJ每日练习（5）

Posted on | In

题目名称

  1. Remove Element(Leetcode #27)
  2. Next Permutation(Leetcode #31）
  3. Permurtation Sequence(Leetcode #60)
  4. Plus One(Leetcode #60)
  5. 矩阵中的路径（剑指offer #12）
  6. 机器人的运动范围（剑指offer #13）
  7. 剪绳子(剑指offer #14)

Remove Element(Leetcode #27)

题目描述

从一个数组中去除指定元素，返回新长度。

解题思路

很容易的题目，借鉴STL rmove的实现策略。

解题方案

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        size_t newsize=0;
        for(size_t index=0;index!=nums.size();++index)
            if(nums[index]!=val) 
                nums[newsize++]=nums[index];
        return newsize;
    }
};

Next Permutation(Leetcode #31）

题目描述

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1
2
3
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解题思路

还是STL中的算法，这里简单地描述一下如何实现：

  1. 从后向前到找一组元素对，记作i,ii,满足*i<*ii;如果找不到这样的元素对，翻转[first,last)；
  2. 从后向前，找到第一个比*i大的元素，记作j，swap(i,j);
  3. 翻转[ii,last)

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.size()<=1)
            return;
        auto i =nums.end()-2;
        auto ii = nums.end()-1;
        while(i!=nums.begin() && !(*i<*ii)) --i,--ii;
        if(i==nums.begin() && ((*ii)<(*i))){
            reverse(nums.begin(),nums.end());
            return;
        }
        auto j =nums.end()-1;
        while(!(*i<*j)) --j;
        swap(*i,*j);
        reverse(ii,nums.end());
    }
};

扩展

剑指offer #38（输出所有字符串序列）也可采用此种方案实现，现有实现方案如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> res;
        if(str.empty())
            return res;
        if(str.size()==1){
            res.push_back(str);
            return res;
        }
        string old =str;
        sort(str.begin(),str.end());
        res.push_back(str);
        while(true){
            next_permutation(str.begin(),str.end());
            if(str==old)
                return res;
            res.push_back(str);
        }
    }
};

Permurtation Sequence(Leetcode #60)

题目描述

The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order, we get the following sequence for n = 3:
“123”、”132”、”213”、”231”、”312”、”321”
Given n and k, return the kth permutation sequence.
Note:
Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.
Example 1:

1
2
Input: n = 3, k = 3
Output: "213"

Example 2:
1
2
Input: n = 4, k = 9
Output: "2314"

解题思路

一个不太好的想法是利用STL next_permutation函数，循环k次自然能得到指定序列，但这种方法不甚可取。我们可以换一种思路，采用康托编码完成求解。该算法的核心思想是：假定第k个(康托编码从0计数）排列为[a1,a2,a3,a4....,an]，那么存在公式：K=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0!,也就是说，必有a1=k/(n-1)!，a2=k%(n-1)!/(n-2)!等等，其中a[n]代表比处在第n位的数字小，并且在第n位前面没有出现过的数字的个数。（个位是第1位）
核心计算流程可见https://blog.csdn.net/neutre/article/details/78065633

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string getPermutation(int n, int k) {
        string rest(n, '0');
        for (size_t index = 0; index != n; index++)
            rest[index] = '1' + index;
        if (--k==0) return rest;
        string result(n,'0');
        auto it = rest.end();
        size_t i = 0;
        while (n--){
            result[i] = rest[k/ factorial(n)]  ;
            it=remove(rest.begin(), it, result[i++]);
            k %= factorial(n);
        }
        return result;
    }
private:
    long factorial(size_t n) {
        if (n == 0 || n == 1) return 1;
        else return n*factorial(n - 1);
    }
};

Plus One(Leetcode #60)

题目描述

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:

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

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

解题思路

没什么好说的，做了一个小小的优化：一开始判定是不是由全9组成，是则直接构造返回值（似乎并不是优化）。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int number9 = count(digits.cbegin(),digits.cend(),9);
        if(number9==digits.size()){
            vector<int> res(number9+1,0);
            res[0]=1;
            return res;
        }
        int carry=1;
        for(auto ri=digits.rbegin();ri!=digits.rend();++ri){
            *ri+=carry;
            carry = *ri>=10?1:0;
            *ri%=10;
        }
        return digits;
    }
};

矩阵中的路径（剑指offer #12）

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

解题思路

回溯。由于不能重复进入某个格子，因此需要定义一个bool数组保存进入情况。

解题方案

（这道题的数组用起来很不顺手，改天用纯C++写一个）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str){
        if(matrix==nullptr || rows==0 || cols==0 ||str==nullptr)
            return false;
        bool* visited = new bool[rows*cols];
        memset(visited,false,rows*cols);
        for(int i=0;i<rows;i++){           
            for(int j=0;j<cols;j++)                
                if(isHsaPath(matrix,rows,cols,str,visited,i,j))                   
                    return true;      
        }      
        return false;
    }
 private:
     bool isHsaPath(char *matrix,int rows,int cols,char *str,bool *visited,int curx,int cury) {
        if(*str=='\0')           
            return true;      
        if(cury==cols)       
            curx++,cury=0;          
        if(cury==-1)
            curx--,cury=cols-1;
        if(curx<0||curx>=rows)           
            return false;      
        if(visited[curx*cols+cury]||*str!=matrix[curx*cols+cury])           
            return false;      
        visited[curx*cols+cury]=true;      
        bool sign=isHsaPath(matrix,rows,cols,str+1,visited,curx-1,cury)
                 ||isHsaPath(matrix,rows,cols,str+1,visited,curx+1,cury)       
                 ||isHsaPath(matrix,rows,cols,str+1,visited,curx,cury-1)
                 ||isHsaPath(matrix,rows,cols,str+1,visited,curx,cury+1); 
        visited[curx*cols+cury]=false;   
        return sign; 
    }
};

机器人的运动范围

题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8=19。请问该机器人能够达到多少个格子？

解题思路

类似于上一题，也可以采用回溯解决。这个问题中的visit数组不需要回溯，因为它仅仅表明该格子不再纳入计算而已。

解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int movingCount(int threshold, int rows, int cols){
        vector<vector<int> > visited(rows);
        for(auto &v:visited)
            v.resize(cols,0);
        return aux(0,0,rows,cols,visited,threshold);
    }
private:
    int aux(int i,int j,int rows,int cols,vector<vector<int> > &visited,int threshold){
        if(i<0 || i>=rows || j<0 || j>=cols || sum(i)+sum(j)>threshold)
            return 0;
        if(visited[i][j])
            return 0;
        visited[i][j]=1;
        return aux(i-1,j,rows,cols,visited,threshold)
               +aux(i+1,j,rows,cols,visited,threshold)
               +aux(i,j-1,rows,cols,visited,threshold)
               +aux(i,j+1,rows,cols,visited,threshold)+1;
    }
    
    int sum(int i){
        int res=0;
        while(i){
            res+=(i%10);
            i/=10;
        }
        return res;
    }
};

剪绳子

题目描述

现有一根长度为n的绳子，可将其剪为m段。试问绳长为n的情况下最大成绩是多少。

解题思路

  1. 动态规划，已知f(n)=max(f(i)*f(n-i));用一个数组来记录绳子长度的最大成绩。
  2. 贪心，n>=5时，尽可能多剪长度为3的绳子，当剩下的长度为4时，直接再剪为两段。

解题方案

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int getMaxResult(int length) {
	vector<int> res(length+1);
	res[0] = 0;res[1] = 1;res[2] = 2;res[3] = 3;
	if (length <= 3)
		return res[length];
	int max = 0;
	for (int i = 4; i <= length; i++) {
		max = 0;
		for (int j = 1; j <= i / 2; j++) {
			int r = res[j] * res[i - j];
			if (max < r)
				max = r, res[i] = max;
		}
	}
	return res[length];
}

贪心

1
2
3
4
5
6
7
8
9
10
11
12
int getMaxResult(int length) {
	if(length<2)
	    return 0;
	if(length==2)
	    return 1;
	if*(length==3)
	    return 2;
	int number3 = length/3 ;
    if(length - number3*3 == 1) number3 -= 1 ;
    int number2 = (length - number3*3)/2 ;
    return pow(3, number3)*Math.pow(2, number2) ;
}