Zichuan365' Blog HomeArchivesCategoriesGalleryAbout
LeetCode / String、数字、数组操作
|LeetCodeString操作、数字操作、数组操作

String操作

6.Z字形变换保存

  • 输入: s = “LEETCODEISHIRING”, numRows = 3

  • 输出: “LCIRETOESIIGEDHN”

  • 输入: s = “LEETCODEISHIRING”, numRows = 4

  • 输出: “LDREOEIIECIHNTSG”

  • 解题利用N个string来实现元素的存储，0123210123，然后进行顺序的反转实现元素的保存
    img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
string convert(string s, int numRows) {
	if (numRows < 2)
		return s;

	vector<string>res(numRows, "");
	int num = 1;
	int index = 0;
	for (int i = 0; i < s.size(); i++) {
		res[index].push_back(s[i]);

		if (index == numRows - 1) {
			num = -1;
		}
		if (index == 0) {
			num = 1;
		}
		index += num;
	}
	string resString;
	for (auto it : res)
		resString += it;

	return resString;
}

14.String的最长公共前缀

  • 编写一个函数来查找字符串数组中的最长公共前缀。

  • 如果不存在公共前缀，返回空字符串 “”。

  • 输入: [“flower”,”flow”,”flight”]

  • 输出: “fl”

  • 输入: [“dog”,”racecar”,”car”]

  • 输出: “”

  • 解释: 输入不存在公共前缀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
string longestCommonPrefix(vector<string>& strs) {
	if (strs.size() == 0)
		return "";
	//substr(i,len)
	//i元素开始的下标index:从0开始

	string res = strs[0];
	for (int i = 1; i < strs.size(); i++) {
		int j = 0;      //防止出现————这种情况:  "aa"  "a"
		for (; j < strs[i].size() && j < res.size(); j++) {
			if (strs[i][j] != res[j])
				break;
		}
		res = res.substr(0, j);
		if (res == "")
			return "";
	}
	return res;
}

763.String划分最多字母区间

  • 字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

  • 输入：S = “ababcbacadefegdehijhklij”

  • 输出：[9,7,8]
  • 解释：
  • 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。
  • 每个字母最多出现在一个片段中。
  • 像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> partitionLabels(string S) {
	vector<int>arr(26, 0);
	for (int i = 0; i < S.size(); i++)
		arr[S[i] - 'a'] = i;

	//有点类似于合并区间
	vector<int>res;
	int index = 0, local = 0;
	for (int i = 0; i < S.size(); i++) {
		index = max(index, arr[S[i] - 'a']);

		//说明可以划分
		if (index == i) {
			res.push_back(i - local + 1);//区间结果保存
			local = i + 1;     //新的未划分起始下标
		}
	}
	return res;
}

43. 字符串相乘

  • 输入: num1 = “123”, num2 = “456”

  • 输出: “56088”
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
string multiply(string num1, string num2) {
	if (num1 == "0" || num2 == "0")
		return "0";

	int m = num1.size();
	int n = num2.size();
	
	//各位相加    arr[0]:最高位
	vector<int>ansArr(m + n);
	for (int i = m - 1; i >= 0; i--) {
		int x = num1[i] - '0';
		for (int j = n - 1; j >= 0; j--) {
			int y = num2[j] - '0';
			ansArr[i + j + 1] +=  x*y;
		}
	}
	//各位进位
	for (int i = m + n - 1; i > 0; i--) {
		ansArr[i - 1] += ansArr[i] / 10;
		ansArr[i] %= 10;
	}

	//判断最高位是否为0
	int index = ansArr[0] == 0 ? 1 : 0;
	
	//int转char
	string ans;
	while (index < m + n) {
		ans.push_back(  (char)( '0' + ansArr[index]));
		index++;
	}
		
	return ans;
}

数字操作

7./ 剑指67.整数反转

  • 输入: 123

  • 输出: 321

  • 输入: -123

  • 输出: -321

  • 输入: 120

  • 输出: 21
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    int reverse(int x) {
    	int maxx = INT_MAX;
    	int minn = INT_MIN;

    	long temp = 0;
    	while (x) {
    		temp = x % 10 + temp * 10;
    		x /= 10;
    	}

    	return (int)(temp > maxx || temp < minn ? 0 : temp);
    }

8. / 剑指67. 字符串转换整数 (atoi)

  • 输入: “42”

  • 输出: 42

  • 输入: 输入: “ -42”

  • 输出: -42
    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
    int strToInt(string str) {
    	//去重
    	long res = 0;
    	bool negative = true;
    	int i = 0;
    	while (str[i] == ' ')
    		i++;

    	if (!isdigit(str[i]) && str[i] != '+' && str[i] != '-')//非数字，正负号return
    		return 0;

    	if (str[i] == '-') {
    		negative = false;
    		i++;
    	}
    	else if (str[i] == '+') {
    		negative = true;
    		i++;
    	}
    	//累加数字
    	while (isdigit(str[i])) {
    		res = res * 10 + str[i] - '0';

    		if (negative == true && res > INT_MAX)
    			return INT_MAX;
    		if (negative == false && -res < INT_MIN)
    			return INT_MIN;
    		i++;
    	}
    	return negative ? res : -res;
    }

9. 判断回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isPalindrome(int x)
{
	int x1 = x;
	if (x < 0)
		return false;
	else {
		long temp = 0;
		while (x) {
			temp = temp * 10 + x % 10;
			x = x / 10;
		}
		return temp == x1;
	}
	return true;
}

172. 阶乘后的零

  • 算一下乘法因子里5的个数

1
2
3
4
5
6
7
8
9
int trailingZeroes(int n) {
	int cnt = 0;
	while (n) {
		cnt += n / 5;
		n /= 5;
	}
	return cnt;

}

258.各位相加

  • 给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

  • 输入: 38

  • 输出: 2

  • 解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。

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
int addDigits(int num) {
	//找规律
	//s1 = 100 * a + 10 * b + 1 * c
	//s2 = a + b + c
	//(s1 -s2) = 99 * a + 9 * b

	if (num == 0)return 0;
	if (num % 9 == 0)
		return 9;
	else
		return num % 9;

	// int addDigits(int num) {
	// while(num > 9){
	//     int res = 0;
	//     while(num)
	//     {
	//         int pop = num % 10;
	//         res += pop;
	//         num /= 10;
	//     }
	//     num = res;
	// }
	// return num;
}

数组操作

54. / 剑指29.螺旋打印矩阵

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

vector<int> spiralOrder(vector<vector<int>>& matrix) {
	vector<int>res;
	if (matrix.empty())
		return res;

	int up = 0;
	int down = matrix.size() - 1;
	int left = 0;
	int right = matrix[0].size() - 1;
	while (1) {
		//左往右
		for (int i = left; i <= right; i++)
			res.push_back(matrix[up][i]);
		if (up == down)return res;
		up++;
		//上往下
		for (int i = up; i <= down; i++)
			res.push_back(matrix[i][right]);
		if (left == right)return res;
		right--;
		//右往左
		for (int i = right; i >= left; i--)
			res.push_back(matrix[down][i]);
		if (up == down)return res;
		down--;
		//下往上
		for (int i = down; i >= up; i--)
			res.push_back(matrix[i][left]);
		if (left == right)return res;
		left++;
	}
	return res;
}

73.矩阵置零

  • 用第一行第一列作标志位，然后再对第一行第一列进行处理

    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
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    void setZeroes(vector<vector<int>>& matrix) {
    	if (matrix.size() == 0)
    		return;
    	int m = matrix.size();
    	int n = matrix[0].size();
    	bool firstRow = false;
    	bool firstCol = false;

    	//第一行和第一列做标识位
    	for (int i = 0; i < m; i++) {
    		for (int j = 0; j < n; j++) {
    			const int item = matrix[i][j];
    			if (item == 0) {
    				if (i == 0) {
    					firstRow = true;
    				}
    				if (j == 0) {
    					firstCol = true;
    				}
    				matrix[0][j] = 0;
    				matrix[i][0] = 0;
    			}
    		}
    	}

    	for (int i = 1; i < m; i++) {
    		for (int j = 1; j < n; j++) {
    			const int item = matrix[i][j];
    			if (matrix[0][j] == 0 || matrix[i][0] == 0) {
    				matrix[i][j] = 0;
    			}
    		}
    	}
    	// 修改第一行和第一列
    	if (firstRow) {
    		for (int i = 0; i < n; i++) {
    			matrix[0][i] = 0;
    		}
    	}

    	if (firstCol) {
    		for (int i = 0; i < m; i++) {
    			matrix[i][0] = 0;
    		}
    	}
    }

581.最短无序连续子数组

  • 输入: [2, 6, 4, 8, 10, 9, 15]

  • 输出: 5

  • 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

  • 解：从左往右，从右往左遍历，找到不满足条件的位置，两者相减

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    int findUnsortedSubarray(vector<int>& nums) {
    	if (nums.size() <= 1)
    		return 0;

    	int tmp1 = INT_MIN;
    	int tmp2 = INT_MAX;

    	int indexL = 0;
    	int indexR = 0;
    	for (int i = 0; i < nums.size(); i++) {
    		if (nums[i] < tmp1)
    			indexR = i;
    		tmp1 = max(tmp1, nums[i]);
    	}
    	for (int i = nums.size() - 1; i >= 0; i--) {
    		if (nums[i] > tmp2)
    			indexL = i;
    		tmp2 = min(tmp2, nums[i]);
    	}
    	return indexR == indexL ? 0 : indexR - indexL + 1;
    }

945.使数组唯一的最小增量

  • 给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。

  • 返回使 A 中的每个值都是唯一的最少操作次数。

  • 输入：[3,2,1,2,1,7]

  • 输出：6

  • 解释：经过 6 次 move 操作，数组将变为 [3, 4, 1, 2, 5, 7]。

  • 可以看出 5 次或 5 次以下的 move 操作是不能让数组的每个值唯一的。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    int minIncrementForUnique(vector<int>& A) {
    	if (A.size() == 0)
    		return 0;
    	sort(A.begin(), A.end());
    	int res = 0;

    	for (int i = 1; i < A.size(); i++) {
    		if (A[i] <= A[i - 1]) {
    			int temp = A[i];
    			A[i] = A[i - 1] + 1;
    			res = res + A[i] - temp;
    		}
    	}
    	return res;
    }

152. 乘积最大子数组

  • 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

  • 遇负反转

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    double maxProduct(vector<double> arr) {
    	double res = INT_MIN;
    	double maxx = 1;
    	double minn = 1;

    	for (int i = 0; i < arr.size(); i++) {
    		//预到负数反转
    		if (arr[i] < 0) {
    			swap(maxx, minn);
    		}
    		maxx = max(arr[i], arr[i] * maxx);
    		minn = min(arr[i], arr[i] * minn);

    		res = max(res, maxx);
    	}
    	return res;
    }
文章作者: Inter
文章链接: https://zuizichuan.cn/2020/09/04/LeetCode-%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%93%8D%E4%BD%9C/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Zichuan365' Blog！