【模拟面试】#12 最小差值 I 二进制链表转整数 从英文中重建数字

题目1

给你一个整数数组 A，请你给数组中的每个元素 A[i] 都加上一个任意数字 x （-K <= x <= K），从而得到一个新数组 B 。

返回数组 B 的最大值和最小值之间可能存在的最小差值。

示例 1：

输入：A = [1], K = 0
输出：0
解释：B = [1]

示例 2：

输入：A = [0,10], K = 2
输出：6
解释：B = [2,8]

示例 3：

输入：A = [1,3,6], K = 3
输出：0
解释：B = [3,3,3] 或 B = [4,4,4]

提示：

1. 1 <= A.length <= 10000
2. 0 <= A[i] <= 10000
3. 0 <= K <= 10000

思路及代码

这题一开始竟然给我整蒙了。仔细分析一下发现的。

我们只要知道数组A的最大值和最小值相差多少，然后与2K比较，如果这个差值比2K还要大，那我们无论怎么想加得到的B数组的最大值和最小值都不可能相等，此时最佳的B数组最大值和最小值的差值为max[A]-min[A]-2K；但如果max[A]-min[A]要小于2K的话，我们通过加加减减可以得到一个元素全部一样的B数组，此时max[B]-min[B]当然是等于0喽
原文链接：https://blog.csdn.net/m0_37344350/article/details/93965066

class Solution {
public:int smallestRangeI(vector& A, int K) {sort(A.begin(),A.end());int len = A.size();if(A[len-1] - A[0] <= 2*K){return 0;}else{return A[len-1] - A[0] - 2*K;}}
};

题目2

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

示例 1：

输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)

示例 2：

输入：head = [0]
输出：0

示例 3：

输入：head = [1]
输出：1

示例 4：

输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出：18880

示例 5：

输入：head = [0,0]
输出：0

提示：

• 链表不为空。
• 链表的结点总数不超过 30。
• 每个结点的值不是 0 就是 1。

思路及代码

左移+或

左移一位，新位是0，这时候或上当前链表的值，有1则为1，这样链表读完了，相当于就把每一位的情况都填到这个整数对应位里面去了。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:int getDecimalValue(ListNode* head) {int result = 0;ListNode* p = head;while(p != NULL){result <<= 1;result |= (p->val);p = p->next;}return result;}
};

题目3

给定一个非空字符串，其中包含字母顺序打乱的英文单词表示的数字0-9。按升序输出原始的数字。

注意:

1. 输入只包含小写英文字母。
2. 输入保证合法并可以转换为原始的数字，这意味着像 "abc" 或 "zerone" 的输入是不允许的。
3. 输入字符串的长度小于 50,000。

示例 1:

输入: "owoztneoer"输出: "012" (zeroonetwo)

示例 2:

输入: "fviefuro"输出: "45" (fourfive)

思路及代码

按轮次进行统计，找特殊规律，例如第一次统计，因为只有0的英文zero包含z，因此我们可以确定读到几个z就有几个0，按照这种思想，得出以下规律，接着就是很简单的编码了。

class Solution {
public:string originalDigits(string s) {int zimu[26] = {0};//字母计数int res[10] = {0};//结果计数int len = s.size();for(int i = 0;i < len;i++){zimu[s[i] - 'a']++;}int current;//第一轮特殊 z w u x gcurrent = zimu['z' - 'a'];zimu['z' - 'a'] = 0;zimu['e' - 'a'] -= current;zimu['r' - 'a'] -= current;zimu['o' - 'a'] -= current;res[0] = current;current = zimu['w' - 'a'];zimu['w' - 'a'] = 0;zimu['t' - 'a'] -= current;zimu['o' - 'a'] -= current;res[2] = current;current = zimu['u' - 'a'];zimu['u' - 'a'] = 0;zimu['f' - 'a'] -= current;zimu['r' - 'a'] -= current;zimu['o' - 'a'] -= current;res[4] = current;current = zimu['x' - 'a'];zimu['x' - 'a'] = 0;zimu['s' - 'a'] -= current;zimu['i' - 'a'] -= current;res[6] = current;current = zimu['g' - 'a'];zimu['g' - 'a'] = 0;zimu['e' - 'a'] -= current;zimu['i' - 'a'] -= current;zimu['h' - 'a'] -= current;zimu['t' - 'a'] -= current;res[8] = current;//第二轮特殊 o h f scurrent = zimu['o' - 'a'];zimu['o' - 'a'] = 0;zimu['n' - 'a'] -= current;zimu['e' - 'a'] -= current;res[1] = current;current = zimu['h' - 'a'];zimu['h' - 'a'] = 0;zimu['t' - 'a'] -= current;zimu['r' - 'a'] -= current;zimu['e' - 'a'] -= current * 2;res[3] = current;current = zimu['f' - 'a'];zimu['f' - 'a'] = 0;zimu['i' - 'a'] -= current;zimu['v' - 'a'] -= current;zimu['e' - 'a'] -= current;res[5] = current;current = zimu['s' - 'a'];zimu['s' - 'a'] = 0;zimu['v' - 'a'] -= current;zimu['n' - 'a'] -= current;zimu['e' - 'a'] -= current * 2;res[7] = current;//第三轮还剩下的只有9了，就以统计i为例current = zimu['i' - 'a'];res[9] = current;string ret = "";for(int i = 0;i < 10;i++){for(int j = 0;j < res[i];j++){ret = ret + std::to_string(i);}}return ret;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！