華為筆試 #華為筆試 #字元串

輸入m和n，以及步長s，在一個m*n的矩陣中，0表示不可走，1表示可走，每次走過s。問從左上角是否能都走到右下角？

輸入：

3 5 2

1 0 1 0 0

0 0 0 1 0

0 0 1 0 1

輸出;

TRUE

#include<iostream>
#include<vector>

using namespace std;
void dfs(vector<vector<int>>& vec,int m,int n, int i, int j,int s)
{
	if (i >= m && j >= n)
		return;
	if (vec[i][j] == 2) return;
	vec[i][j] = 2;
	if (i + s < m&&vec[i + s][j] == 1)
		dfs(vec, m, n, i + s, j, s);
	if (i - s >= 0 && vec[i - s][j] == 1)
		dfs(vec, m, n, i - s, j, s);
	if (j + s < n&&vec[i][j + s] == 1)
		dfs(vec, m, n, i, j + s, s);
	if (j - s >= 0 && vec[i][j - s] == 1)
		dfs(vec, m, n, i, j - s, s);
}

int main()
{
	int m, n, s;
	while (cin >> m >> n>>s) {
		vector<vector<int>> vec(m, vector<int>(n, 0));
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				cin >> vec[i][j];
			}
		}
		dfs(vec, m, n, 0, 0,s);
		cout << ((vec[m - 1][n - 1] == 2) ? "TRUE" : "FALSE" )<< endl;
	}
}

字元串重排

題目1：
	現有多組整數數組，需要将他們合并成一個新的數組。合并規則，從每個數組按順序，取出固定長度
	的内容合并到新的數組中，取完的内容會删除掉，如果該行不足固定長度或者已經為空，則直接取出
	剩餘部分的内容放到新的數組中，繼續下行。如樣例1，獲得長度3，先周遊第一行，獲得2.5.6 ;再遍
	曆第二行，獲得1,7.4;再循環回到第行.獲得7,9,5 ;再周遊第二行，獲得1,7，4;再循環回到第1行，獲
	得7.按順序拼接成最終結果。

輸入：

3

2,5,6,7,9,5,7

1,7,4,3,4

輸出：

2,5,6,1,7,4,7,9,5,3,4,7

#include<iostream>
#include<vector>
#include<string>

using namespace std;
void str_cut(vector<string>str_in, int cut_len);

string result = "";
int main()
{
	vector<string> v_str;
	string _str;
	int cut_len;
	cin >> cut_len;
	getchar();
	while (getline(cin, _str))
	{
		if (!_str.empty())
		{
			v_str.push_back(_str);
		}
		else
		{
			break;
		}
	}
	str_cut(v_str, cut_len);
	cout << result << endl;
	system("pause");
	return 0;
}

void str_cut(vector<string>str_in, int cut_len)
{
	string copy = "";
	static int size_;
	size_ = str_in.size();
	while (size_ > 0)
	{
		for (int i = 0; i < str_in.size(); i++)
		{
			if (str_in[i].size() > 0)
			{
				int num = 0;
				int pos;
				while (num < cut_len)
				{
					pos = str_in[i].find_first_of(',', 0);
					//處理隻剩最後一個數字
					if (pos == -1)
					{
						copy = str_in[i].substr(0);
						result += copy;
						str_in[i].erase(0);
						size_ -= 1;
						if (size_ > 0)
						{
							result += ",";
						}
						break;
					}
					copy = str_in[i].substr(0, pos + 1);
					num += 1;
					result += copy;					
					str_in[i].erase(0, pos + 1);
				}
			}
		}
	}
}

題目2：
給定一個隻包含大寫英文字母的字元串S，要求你給出對S重新排列的所有不相同的排列數。
如：S為ABA，則不同的排列有ABA、AAB、BAA三種。

輸入：
輸入一個長度不超過10的字元串S，確定都是大寫。

輸出：
輸出S重新排列的所有不相同的排列數（包括自身）。

輸入：

ABA

輸出：

3

輸入：

ABCDEFGHHA

輸出：

907200

#include <unordered_map>
int factorial(int n) 
{
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}
int main()
{ 
    string str;
    getline(cin, str);
    int totalPermutation = factorial(str.size());
    unordered_map<char, int> myMap;
    for (int i = 0; i < str.size(); ++i) {
        myMap[str[i]]++;
    }
    int tag = 1;
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        tag *= factorial(it->second);
    }
    cout << totalPermutation / tag << endl;
  return 0;
}


方法二：
#include<iostream>

using namespace std;
int cnt = 0;
//處理重複
bool isSwap(char* pBegin, char* pEnd)
{
	for (char* p = pBegin;p < pEnd;p++)
	{
		if (*p == *pEnd)
			return false;
	}
	return true;
}
void Permutation(char* str, char* head)
{
	
	if (str == NULL)
		return;

	if (*head == '\0')  //head指針掃到結尾了
	{
		++cnt;
		cout << str << endl;  //輸出排列
	}
	else
	{
		for (char* p = head; *p != '\0'; p++)
		{
			if (isSwap(head, p))
			{
				swap(*p, *head);  //交換頭指針指向的字元
				Permutation(str, head + 1);
				swap(*p, *head);  //交換回來
			}
		}
	}
}

int main()
{
	char str[10];
	cout << "The original string is: ";
	cin >> str;
	cout << endl;
	cout << "After permutation, the string is: " << endl;
	Permutation(str, str);
	cout << cnt << endl; //輸出排列個數

	return 0;
}

矩陣左上角走到右下角，最大值

int Max(int a,int b){
  if(a>=b)
    return a;
  else
    return b;
}
int main(){
  int n,m;
  int Num[100][100];
  int dp[100][100];
  cin>>n>>m;
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cin>>Num[i][j];
      if(i==0&&j==0){
        dp[i][j]=Num[i][j];
      }
      else if(i==0){
         dp[i][j]=Num[i][j]+dp[i][j-1];
      }
      else if(j==0){
        dp[i][j]=Num[i][j]+dp[i-1][j];
      }
      else{
        dp[i][j]=Num[i][j]+Max(dp[i-1][j],dp[i][j-1]);  
      }
    }
  }
  cout<<dp[n-1][m-1];
  return 0;
}

某電視台舉辦了低碳生活大獎賽。題目的計分規則相當奇怪：

每位選手需要回答N個問題（其編号為1到N），越後面越有難度。答對的，目前分數翻倍；答錯了則扣掉與題号相同的分數（選手必須回答問題，不回答按錯誤處理）。

每位選手都有一個起步的分數為10分。

某獲勝選手最終得分剛好是S分，如果不讓你看比賽過程，你能推斷出他（她）哪個題目答對了，哪個題目答錯了嗎？

如果把答對的記為1，答錯的記為0，則若N=10，S=100 的回答情況可以用僅含有1和0的串來表示。例如：0010110011 就是可能的情況。

你的任務是算出所有可能情況的種數。

解答要求

時間限制：1000ms, 記憶體限制：64MB

輸入

輸入隻有一行，即兩個用空格隔開的整數N和S，且(1<N<21,10<=S<3000)。

輸出

輸出選手經過N輪答題，最終得分剛好是S分的情況的種數。

輸入樣例

10 100

輸出樣例

3

int cal(const int all_number, int now_num, int sum, const int des) 
{
    if(all_number == now_num) {
        return (((sum - now_num) == des) || (sum * 2 == des)) ? 1 : 0;
    }
    return cal(all_number, now_num + 1, sum - now_num, des) + cal(all_number, now_num + 1, 2 * sum, des);
}
int main(int argc, char *argv[])
{
    int n;
    int s;
    cin >> n >> s;
    cout << cal(n, 1, 10, s) << endl;
    return 0;
}

題目描述

編寫程式，産生由1，2，3這3個數字元号所構成、長度為n的字元串，并且在字元串中對于任何一個子串而言，都不會有相鄰的、完全相同的子串；

解答要求

時間限制：1000ms, 記憶體限制：64MB

輸入

字元串長度n(1=<n<=10)；

輸出

無相鄰重複子串的所有字元串，每個字元串換行輸出。(由小到大輸出)

樣例

輸入樣例 1

5

輸出樣例 1

12131

12132

12312

12313

12321

13121

13123

13212

13213

13231

21231

21232

21312

21321

21323

23121

23123

23132

23212

23213

31213

31231

31232

31321

31323

32123

32131

32132

32312

32313

#include <stdio.h>
#define maxn 50
char ans[maxn];
void dfs(int idx, int l){
    int i,j,k;
    if(idx == l) {
        printf("%s\n", ans);
        return;
    }
    for(i = 1; i < 4; i++){
        ans[idx] = '0'+i;
        for(j = 1; j <= (idx+1)/2; j++){
            for(k = 0; k < j; k++){
                if(ans[idx-k] != ans[idx-j-k])break;
            }
            if(j == k) break;
        }
        if(j <= (idx+1)/2)continue;
        dfs(idx+1, l);
    }
}
int main(){
    int l;
    scanf("%d", &l);
    dfs(0, l);
    return 0;
}

Word Maze 是一個網絡小遊戲，你需要找到以字母标注的食物，但要求以給定單詞字母的順序吃掉。假設給定單詞if，你必須先吃掉i然後才能吃掉f。

但現在你的任務可沒有這麼簡單，你現在處于一個迷宮Maze（n×m的矩陣）當中，裡面到處都是以字母标注的食物，但你隻能吃掉能連成給定單詞W的食物。

注意區分英文字母大小寫,并且你隻能上下左右行走。

樣例

輸入樣例 1

5 5

SOLO

CPUCY

EKLQH

CRSOL

EKLQO

PGRBC

輸出樣例 1

YES

#include <string>
#include <vector>
#include <iostream>
using namespace std;
bool dfs(vector<string> &board, string word, int start, int i, int j)
{
    if (board[i][j] != word[start]) {
        return false;
    }
    if (start == word.size() - 1) {
        return true;
    }
    char tmp = board[i][j];
    board[i][j] = '0';
    start++;
    if ((i > 0 && dfs(board, word, start, i - 1, j)) ||
        (i < board.size() - 1 && dfs(board, word, start, i + 1, j)) ||
        (j > 0 && dfs(board, word, start, i, j - 1)) ||
        (j < board[0].size() - 1 && dfs(board, word, start, i, j + 1))) {
        return true;
    }
    board[i][j] = tmp;
    return false;
}
int main()
{  
    int m;
    int n;
    string word;
    cin >> m >> n >> word;
    vector<string> board;
    string str;
    while (cin >> str) {
        board.push_back(str);
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (dfs(board, word, 0, i, j)) {
                cout << "YES" << endl;
                return 0;
            }
        }
    }
    cout << "NO" << endl;
    return 0;
}

字元串中第一個重複最少或者最多的字元；

字元串中第一個不重複或者重複的字元；

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

char FindFirstChar(string str) {
	map<char, int> item;
	int len = str.size();
	for (int i = 0; i < len; i++) {
		item[str[i]]++;
	}
	//找出第一個不重複或者重複的字元
	/**
	for (int i = 0; i < len; i++)
	{
		if (item[str[i]] != 1)
			return str[i];
	}
	*/

	//找出重複最多或者重複最少的字元
	/**
	int maxNum = 0;
	for (int i = 0; i < len; i++) {
		if (item[str[i]] > maxNum) {
			maxNum = item[str[i]];
		}
	}
	for (int i = 0; i < len; i++) {
		if (item[str[i]] == maxNum) {
			return str[i];
		}
	}
	*/

	return NULL;
}
int main() {
	string str;
	while (cin >> str)
	{
		char result;
		result = FindFirstChar(str);
		cout << result << endl;
	}
	return 0;
}

給定兩個整數 n 和 k，傳回 1 … n 中所有可能的 k 個數的組合

vector<vector<int> > combine(int n, int k) {
        vector<vector<int>> result;
        if(n<1||k<0||k>n)
            return result;
        vector<int> path;
        findNum(result,path,n,k,1);
        return result;
    }
    void findNum(vector<vector<int>>& result,vector<int>& path,int n,int k,int start){
        if(path.size()==k){
            result.push_back(path);
         //   path.clear();
        }
        for(int i=start;i<=n;i++){
            path.push_back(i);
            findNum(result,path,n,k,i+1);
            path.pop_back();
        }
    }

一張門票50元，有m+n個人排隊，m個人手持50，n個人手持100，問有多少種排隊方式，使得零錢能夠找開。

int f(int m,int n){
    if(n==0){  //所有人手持100
        return 1;
    }else if(m<n){  //手持50比手持100的少，無論怎麼排隊，都無法找開
        return 0;
    }else{
        return f(m-1,n)+digui(m,n-1);
    }

8.26筆試

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

int main()
{
	int n;
	while (cin >> n)
	{
		vector<unsigned int> vec;
		for (int i = 0; i < n; i++) {
			int tmp;
			cin >> tmp;
			vec.push_back(tmp);
		}
		for (int i = 0; i < n; i++) {
			unsigned int x = 0;
			x = ((vec[i] & 0x55555555)<<1) | ((vec[i] & 0xaaaaaaaa)>>1);
			/*for (int j = 0; j < 32; ++j) {
				x += (vec[i] & (1 << j)) << 1;
				x += (vec[i] & (1 << (j + 1))) >> 1;
			}*/
			vec[i] = x;
		}

		unsigned int mask = 3;
		unsigned int temp = 0;
		for (auto num : vec) {
			temp += (num&mask) << 30;
			temp += num >> 2;
			cout << temp << endl;
		}
	}
	return 0;
}

華為筆試

字元串重排

繼續閱讀

LeetCode之整數反轉（7）、字元串轉換整數（8）、回文數（9）1、整數反轉（7）2、字元串轉換整數（8）3、回文數（9）

HDU 5688 Problem D

leetcode3:longest-substring-without-repeating-characters

Mysql入門之簡單的DQL查詢語句【Mysql資料庫基礎】

【leetcode】32.longest-valid-parentheses（最長有效括号）【leetcode】32.longest-valid-parentheses（最長有效括号）

力扣每日一題：65. 有效數字題目：65. 有效數字解題思路

HDU 3608 最長回文

HDU 5685 Problem A

sqli-labs第一關--報錯注入練習

python之判斷字元裡面有沒有|8

淺談MFC CSting類拼接效率

C和java中關于字元串與字元數組的定義和轉化

Java：String類字元串與數組之間的轉換

Java中 byte[] 數組與 String 字元串的轉化

回文樹學習小結

查找檔案中的字元串