左右闭区间
int search(vector<int>& a, int target) {
int mid, left = 0, right = a.size() - 1;
//1.[left, right] -- 2.[left, right) -> left<right
while(left <= right) {
mid = left + ((right - left) >> 1);
if(a[mid] > target) {
//闭区间
//2.right = mid;
right = mid - 1;
}else if(a[mid] < target) {
//闭区间
left = mid + 1;
}else if(a[mid] == target) {
return mid;
}
}
return -1;
}
//左闭右闭
int search(int* nums, int length, int target) {
int mid = 0, left = 0, right = length - 1;
while(left <= right) {
mid = left + ((right - left) >> 1);
if(nums[mid] < target) {
left = mid + 1;
}else if(nums[mid] > traget) {
right = mid - 1;
}else {
return mid;
}
}
return -1;
}
function search(nums, target) {
let mid = 0, left = 0, right = nums.length;
while(left <= right) {
mid = left + ((right - left) >> 1);
if(nums[mid] > target) {
right = mid - 1;
}else if(nums[mid] < target) {
left = mid + 1;
}else {
return mid;
}
}
return -1;
}
public int search(int[] nums, int target) {
int mid = 0, left = 0, right = nums.length;
while(left <= right) {
mid = left + ((right - left) >> 1);
if(nums[mid] > target) {
right = mid - 1;
}else if(left < target) {
left = mid + 1;
}else {
return mid;
}
}
return -1;
}
int remove(vector<int>& a, int target) {
int length = a.size();
for(int i = 0; i < length; i++) {
if(a[i] == target) {
for(int j = i + 1; j < length; j++) {
a[j - 1] = a[j];
}
i--;
length--;
}
}
return length;
}
int remove(vector<int>& a, int target) {
int length = a.size();
int slow = 0;
for(int fast = 0; fast < length; fast ++) {
if(a[fast] != target) {
a[slow] = a[fast];
slow ++;
}
}
return slow;
}
int remove(int* nums, int length, int target) {
int slow = 0;
for(int fast = 0; fast < length; fast ++) {
if(nums[fast] != target) {
nums[slow ++] = nums[fast];
}
}
//新数组的长度
return slow;
}
尽可能移动最少的元素
int remove(vector<int>& a, int target) {
int length = a.size();
int left = 0;
int right = length - 1;
//将右值移动到不与 target 相等的值
while(right >= 0 && nums[right] == target) right --;
while(left <= right) {
if(a[left] == target) {
a[left] == a[right];
//对应的值已移动到前面
right --;
}
left ++;
while(right >= 0 && a[rigth] == target) {
right --;
}
}
return left;
}
public int remove(int[] nums, int target) {
int left = 0;
int right = nums.length;
while(left <= right) {
//右指针移动到 ！target
while(right >= 0 && nums[right] == target) right --;
//左指针移动到 target
while(left >= 0 && nums[left] != target) left ++;
if(left <= right) {
nums[left ++] = nums[right --];
}
}
return left;
}
将有序数组内元素平方之后进行排序
int* sortedSquares(vector<int>& a) {
int length = a.size();
int left = 0, right = length - 1, k = length - 1;
int newArr[length]{};
for(int i = 0; i < length; i ++) {
if(a[left] * a[left] < a[right] * a[right]) {
newArr[k --] = a[right] * a[right];
right --;
}else {
newArr[k --] = a[left] * a[left];
left ++;
}
}
a = newArr;
return a;
}
int* sortedSquares(int* nums, int length) {
int left = 0;
int right = length - 1;
int k = length - 1;
//结果数组分配空间
int* result = (int *) malloc(sizeof(int) * length);
while(left <= right) {
if(nums[left] * nums[left] > nums[right] * nums[right]) {
result[k --] = nums[left] * nums[left ++];
}else if(nums[left] * nums[left] < nums[right] * nums[right]) {
result[k --] = nums[right] * nums[right --];
}
}
return result;
}
function sortedSquares(nums) {
let left = 0, right = nums.length - 1;
let k = nums.length - 1;
let result = new Array(nums.length).fill(0);
while(left <= right) {
if(nums[left] * nums[left] > nums[right] * nums[right]) {
result[k --] = nums[left] * nums[left ++];
}else if(nums[left] * nums[left] < nums[right] * nums[right]) {
result[k --] = nums[right] * nums[right --];
}
}
return result;
}
public sortedSquares(int[] nums) {
int left = 0, right = nums.length - 1;
int k = nums.length - 1;
int[] result = new int[nums.length];
while(left <= right) {
if(nums[left] * nums[left] > nums[right] * nums[right]) {
result[k --] = nums[left] * nums[left ++];
}else if(nums[left] * nums[left] < nums[right] * nums[right]) {
result[k --] = nums[right] * nums[right --];
}
}
return result;
}
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
int minSubArrayLen(int s, vector<int>& a) {
int len = a.size();
int result = INT32_MAX;
int sum{0}, subLength{0};
for(int i = 0; i < len; i ++) {
sum = 0;
for(int j = i; j < len; j ++) {
sum += a[j];
if(sum >= s) {
subLength = j - i + 1;
result = result < subLength ? result : subLength;
break; //执行完退出
}
}
}
return result == IN32_MAX ? 0 : result;
}
构建一个窗口不断增长缩减
int minSubArrayLen(int s, vector<int>& a) {
int result = IN32_MAX;
int len = a.size();
int i{0}, subLength{0}, sum{0};
for(int j = 0; j < len; j ++) {
sum += a[j];
while(sum >= s) {
subLength = j - i + 1;
result = result < subLength ? result : subLength;
sum -= a[i];
i ++;
}
}
return result == IN32_MAX ? 0 : result;
}
int minSubArrayLen(int* nums, int length, int target) {
//初始化最大值
int result = INT_MAX;
int left = 0, right = 0, sum = 0;
for(; right < length; right ++) {
sum += nums[right];
while(sum >= target) {
int subLen = right - left + 1;
result = subLen < result ? subLen : result;
sum -= nums[left];
left ++;
}
}
return result == INT_MAX ? 0 : result;
}
function minSubArrayLen(nums, target) {
let result = Infinity;
let left = 0, right = 0, sum = 0;
for(right < nums.length; right ++) {
sum += nums[right];
while(sum >= target) {
let subLen = right - left + 1;
result = subLen < result ? subLen : result;
sum -= nums[left ++];
}
}
return result == Infinity ? 0 : result;
}
public int minSubArrayLen(int[] nums, int target) {
int result = Integer.MAX_VALUE;
int left = 0, right = 0, sum = 0;
for(right < nums.length; right ++) {
sum += nums.[right];
while(sum >= target) {
result = Math.min(result, right - left + 1);
sum -= nums[left ++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
void generateMatrix(int n) {
//定义二维数组并填充 0
vector<vector<int>> array(n, vector<int> (n, 0));
int loop {0};
int startx {0};
int starty {0};
int mid {n / 2};
int offset {1};
int count {1};
int i, j;
while(loop ++ < n / 2) {
i = startx;
j = starty;
//从左往右
for(i = startx; i < n - offset; i ++) {
array[startx][i] = count ++;
}
//从上往下
for(j = starty; j < n - offset; j ++) {
array[j][i] = count ++;
}
//从右往左
for(; i > startx; i --) {
array[j][i] = count ++;
}
//从下往上
for(; j > starty; j --) {
array[j][i] = count ++;
}
startx ++;
starty ++;
//收缩1
offset ++;
}
if(n % 2) {
array[mid][mid] = count;
}
}
int** generateMatrix(int n) {
//定义结果数组
int** result = (int *) malloc(sizeof(int) * n);
//二维定义空间
for(int i = 0; i < n; i ++) {
result[i] = (int *) malloc(sizeof(int) * n);
}
int loop = n / 2;
int mid = n / 2;
int startx = 0, starty = 0;
int offset = 0;
int count = 1;
int row, column;
while(loop --) {
row = startx;
column = starty;
//从左到右
for(row = startx; row < n - offset; row ++) {
result[startx][row] = count ++;
}
//从上到下
for(column = starty; column < n - offset; column ++) {
result[column][row] = count ++;
}
//从右到左
for(; row < startx; row --) {
result[column][row] = count ++;
}
//从下到上
for(; column < starty; column --) {
result[column][row] = count ++;
}
//设定前后边界加1
startx ++;
starty ++;
offset ++;
//如果n是奇数，说明需要画中心点
if(n % 2) result[mid][mid] = count;
}
}
function generateMatrix(n) {
//创建结果二维数组
let result = new Array(n).fill(0).map(() => new Array(n).fill(0));
}
public int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
}
struct ListNode {
int val;
ListNode* next;
//构造函数初始化
ListNode(int x) : val(x), next(NULL) {};
};
typedef struct ListNode {
int val;
struct ListNode* next;
}LNode, * PNode;
PNode InitList(int value) {
PNode node = (PNode) malloc(sizeof(LNode));
node->val = value;
node->next = NULL;
return node;
}
class ListNode {
val;
next;
constructor(value) {
this.val = value;
this.next = null;
}
}
public class ListNode {
private int val;
private ListNode next;
public ListNode() {}
public ListNode(int value) {
this.val = value;
}
public ListNode(int value, ListNode next) {
this.val = value;
this.next = next;
}
}
ListNode* delNode(ListNode* head, int val) {
//删除头节点
while(head != NULL && head->val == val) {
ListNode* temp = head;
head = head->next;
delete temp;
}
//删除相同元素
ListNode* cur = head;
while(cur != NULL && cur->next != NULL) {
if(cur->next->val == val) {
ListNode* temp = cur->next;
cur->next = cur->next->next;
delete temp;
}else {
cur = cur->next;
}
}
return head;
}
ListNode* delNode(ListNode* head, int val) {
//设置虚拟头节点
ListNode* vhead = new ListNode(0);
vhead->next = head;
ListNode* cur = vhead;
while(cur != NULL && cur->next != NULL) {
if(cur->next->val == val) {
ListNode* temp = cur->next;
cur->next = cur->next->next;
delet tempo;
}else {
cur = cur->next;
}
}
head = vhead->next;
delete vhead;
return head;
}
struct ListNode* delNode(struct ListNode* head, int val) {
while(head != NULL && head->val == val) {
struct ListNode* temp = head;
head = head->next;
free(temp);
}
struct ListNode* cur = head;
while(cur != NULL && cur->next != NULL) {
if(cur->next->val == val) {
struct ListNode* temp = cur->next;
cur-next = cur->next->next;
free(temp);
}else {
cur = cur->next;
}
}
return head;
}
//虚拟头节点方法
struct ListNode* delNode(struct ListNode* head, int val() {
typedef struct ListNode ListNode;
ListNode *vhead = (ListNode *) malloc(sizeof(ListNode));
vhead->next = head;
ListNode *cur = vhead;
while(cur != NULL && cur->next != NULL) {
if(cur->next->val == val) {
ListNode *temp = cur->next;
cur->next = cur->next->next;
free(temp);
}else {
cur = cur->next;
}
}
head = vhead->next;
free(vhead);
return head;
}
function delNode(head, val) {
let vhead = new ListNode(0, head);
let cur = vhead;
while(cur && cur.next) {
if(cur.next.val === val) {
cur.next = cur.next.next;
}else {
cur = cur.next;
}
}
return vhead.next;
}
public ListNode delNode(ListNode head, int val) {
ListNode vhead = new ListNode(0, head);
ListNode pre = vhead;
ListNode cur = vhead.next;
while(cur) {
if(cur.val == val) {
pre.next = cur.next;
}else {
pre = cur;
}
cur = cur.next;
}
}
- 获取链表第index个节点的数值
- 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第index个节点前面插入一个节点
- 删除链表的第index个节点
class LinkedList {
private:
int _size;
ListNode* _vhead;
public:
struct ListNode {
int val;
ListNode* next;
ListNode(int val): val(val), next(nullptr){}
};
//构造函数
LinkedList() {
_vhead = new ListNode(0);
_size = 0;
}
//获取index数值
int getVal(int index) {
if(index < 0 || index > _size - 1) {
return -1;
}
//后移节点确保最后cur为index
ListNode* cur = _vhead->next;
while(index--) {
cur = cur->next;
}
return cur->val;
}
//头部添加节点
void preNode(int val) {
ListNode* newNode = new ListNode(val);
newNode->next = _vhead->next;
-vhead->next = newNode;
_size ++;
}
//尾部添加节点
void pushNode(int val) {
ListNode* newNode = new ListNode(val);
ListNode* cur = _vhead;
while(cur->next != NULL) {
cur = cur->next;
}
cur->next = newNode;
_size ++;
}
//删除 index 节点
void delIndexNode(int index) {
ListNode* cur = _vhead;
while(index --) {
cur = cur->next;
}
ListNode* temp = cur->next;
cur->next = cur->next->next;
delete temp;
_size --;
}
//添加 index 节点
void addIndexNode(int index) {
ListNode* newNode = new ListNode(val);
ListNode* cur = _vhead;
while(index --) {
cur = cur->next;
}
newNode->next = cur->next;
cur-next = newNode;
_size ++;
}
//遍历链表
void showLinked() {
ListNode* cur = _vhead;
while(cur->next != NULL) {
cout <<"val == " << cur->next->val;
cur = cur->next;
}
cout << endl;
}
}
typedef struct ListNode {
int val;
struct ListNode* next;
}LNode, * PNode;
//定义指针类型
PNode LinkedInit() {
PNode vhead = (PNode) malloc(sizeof(LNode));
vhead->val = -1;
vhead->next = NULL;
return vhead;
}
//后面添加
PNode pushLinked(PNode vhead, int val) {
PNode cur = vhead;
while(cur->next != NULL) {
cur = cur->next;
}
PNode newNode = (PNode) malloc(sizeof(LNode)):
newNode->val = val;
cur->next = newNode;
return newNode;
}
//前面添加
PNode preLinked(PNode vhead, int val) {
PNode newNode = (PNode) malloc(sizeof(LNode));
newNode->val = val;
newNode->next = vhead->next;
vhead->next = newNode;
return newNode;
}
//删除index
PNode delIndex(PNode vhead, int index) {
PNode cur = vhead;
while(index --) {
cur = cur->next;
}
PNode temp = cur->next;
cur->next = cur->next->next
free(temp);
return temp;
}
//获取index
int getIndex(PNode vhead, int index) {
PNode cur = vhead->next;
while(index --) {
cur = cur->next;
}
return cur->val;
}
//添加index
PNode AddIndex(PNode vhead, int index) {
PNode cur = vhead;
while(index --) {
cur = cur->next;
}
PNode newNode = (PNode) malloc(sizeof(LNode));
newNode->next = cur->next->next;
cur->next = newNode;
return newNode;
}
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
ListNode* temp = NULL;
while(cur != NULL) {
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
PNode reverseList(PNode head) {
PNode cur = head;
PNode pre = NULL;
PNode temp = NULL;
while(cur != NULL) {
temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return head;
}
function reverseList(head) {
let pre = null;
let cur = head;
let temp = null;
while(cur) {
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return head;
}
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode pre = null;
ListNode temp = null;
while(cur) {
temp = head.next;
cur.next = pre;
pre = cur;
cur = temp;
}
}
ListNode* reverseList(ListNode* pre, ListNode* head) {
//head 为null 说明上一个节点为最后节点
if(head == NULL) return pre;
ListNode* temp = head->next;
head->next = pre;
//pre = cur; cur = temp;
return reverseList(head, temp);
}
reverseList(NULL, head);
PNode reverseList(PNode pre, PNode head) {
if(head == NULL) return pre
PNode temp = head->next;
head->next = pre;
return reverseList(head, temp);
}
function reverseList(pre, cur) {
if(cur == null) return pre;
let temp = cur.next;
cur.next = pre;
return reverseList(cur, temp);
}
public ListNode reveseList(ListNode pre, ListNode cur) {
if(cur == null) return pre;
ListNode = cur.next;
cur.next = pre;
return reverseList(cur, temp);
}
ListNode* switchPairs(ListNode* head) {
ListNode* vhead = new ListNode(0);
vhead->next = head;
ListNode* cur = vhead;
while(cur->next && cur->next->next) {
ListNode* temp1 = cur->next;
ListNode* temp2 = cur->next->next;
//开始交换
cur->next = temp2;
cur->next->next = temp1;
cur->next->next->next = temp2->next;
//向后移动两位
cur = cur->next->next;
}
return vhead->next;
}
PNode switchPairs(PNode head) {
PNode vhead = (PNode) malloc(sizeof(LNode));
vhead->next = head;
PNode cur = vhead;
while(cur->next != NULL && cur->next->next != NULL) {
PNode temp1 = cur->next;
PNode temp2 = cur->next->next;
cur->next = temp2;
cur->next->next = temp1;
cur->next->next->next = temp2->next;
cur = cur->next->next;
}
return head->next;
}
function switchPairs(head) {
ListNode vhead = new ListNode(0);
vhead.next = head;
ListNode cur = vhead;
while(cur.next && cur.next.next) {
ListNode temp1 = cur.next;
ListNode temp2 = cur.next.next;
cur.next = temp2;
cur.next.next = temp1;
cur.next.next.next = temp2.next;
cur = cur.next.next;
}
return vhead.next;
}
public ListNode switchPairs(ListNode head) {
ListNode vhead = new ListNode(0, head);
ListNode cur = vhead;
while(cur.next && cur.next.next) {
ListNode temp1 = cur.next;
ListNode temp2 = cur.next.next.next;
cur.next = temp1.next;
cur.next.next = temp1;
cur.next.next.next = temp2;
cur = cur.next.next;
}
return vhead.next;
}
ListNode* switchPairs(ListNode* head) {
if(!head || !head->next) return head;
//记录下一个节点
ListNode* newNode = head-next;
//指向第下一个交换节点
head->next = switchPairs(newNode->next);
//交换当前节点
newNode->next = head;
return newNode;
}
PNode switchPairs(PNode head) {
if(!head || !head->next) return head;
PNode newNode = head->next;
head->next = switchPairs(newNode->next);
newNode->next = head;
return newNode;
}
function switchPairs(head) {
if(!head || !head.next) return head;
let newNode = head.next;
head.next = switchPairs(newNode.next);
newNode.next = head;
return newNode;
}
public ListNode switchPairs(ListNode head) {
if(!head || !head.next) return head;
ListNode newNode = head.next;
head.next = switchPairs(newNode.next);
newNode.next = head;
return newNode;
}
ListNode* delReverseN(ListNode* head, int N) {
ListNode* vhead = new ListNode(0);
vhead->next = head;
ListNode* slowp = vhead;
ListNode* fastp = vhead;
while(N-- && fastp->next) {
fastp = fastp->next;
}
//结果范围大一
fastp = fastp->next;
while(fastp) {
fastp = fastp->next;
slowp = slowp->next;
}
//删除节点，释放内存
ListNode* temp = slowp->next;
slowp->next = slow->next->next;
delete temp;
retrun vhead->next;
}
PNode delReverseN(PNode head, int N) {
PNode vhead = (PNode) malloc(sizeof(LNode));
vhead->next = head;
PNode slowp = vhead;
PNode fastp = vhead;
while(N -- && !vhead->next) {
fastp = fastp->next;
}
while(fastp->next) {
fastp = fastp->next;
slowp = slowp->next;
}
//slowp 的下一个节点即为目标节点
PNode temp = slowp->next;
slowp->next = slowp->next->next;
free(temp);
return vhead->next;
}
function delReverseN(head, N) {
let vhead = new ListNode(0, head);
let slowp = vhead;
let fastp = vhead;
while(N -- && fastp.next) {
fastp = fastp.next;
}
while(fast.next) {
slowp = slowp.next;
fastp = fastp.next;
}
slowp.next = slow.next.next;
return vhead.next;
}
计算节点数
public ListNode delReverseN(ListNode head, int N) {
ListNode cur = head;
int count = 0;
while(cur) {
cur = cur.next;
count ++;
}
if(count == N) {
head = head.next;
}else {
//将指针归位
cur = head;
for(int i = 0; i < count - N -1; i ++) {
cur = cur.next;
}
cur.next = cur.next.next;
}
return head;
}
//从后往前计算count
class Solution {
private:
int count;
public:
void reverse(ListNode* head, int N) {
if(!head) return ;
reverse(head->next);
count ++;
if(count == N + 1) {
head->next = head->next->next;
}
}
ListNode* delReverseN(ListNode head, int N) {
ListNode* vhead = new ListNode(0, head);
count = 0;
reverse(vhead, N);
return vhead->next;
}
}
int count;
void reverse(PNode head, int N) {
if(! head) return ;
reverse(head->next, N);
count ++;
if(count == N + 1) {
head->next = head->next->next;
}
}
PNode delReverseN(PNode head, int N) {
PNode vhead = (PNode) malloc(sizeof(LNode));
count = 0;
reverse(vhead, N);
return vhead->next;
}
function delReverseN(head, N) {
let vhead = new ListNode(0, head);
let count = 0;
function reverse(head) {
if(!head) return ;
reverse(head.next);
count ++;
if(count == N + 1) {
head.next = head.next.next;
}
}
reverse(vhead);
return vhead.next;
}
ListNode* getIntersectionNode(ListNode* linA, ListNode* linB) {
ListNode* lA = linA;
ListNode* lB = linB;
int alen{0}, blen{0};
//计算链表长度
while(lA != NULL) {
lA = lA->next;
alen ++;
}
while(lB != NULL) {
lB = lB->next;
blen ++;
}
//使 A， B指向头部
lA = linA;
lB = linB;
//保持A指向较长的链表
if(blen > alen) {
//交换值
swap(blen, alen);
swap(lB, lA);
}
int comp = alen - blen;
while(comp --) {
lA = lA->next;
}
//寻找相交
while(lA != NULL) {
if(lA == lB) {
return lA;
}
lA = lA->next;
lB = lB->next;
}
retrun NULL;
}
PNode getIntersectionNode(PNode LA, PNode LB) {
PNode la = LA;
PNode lb = LB;
int asize = 0, bsize = 0, comp = 0;
//计算长度
while(la) {
la = la->next;
asize ++;
}
while(lb) {
lb = lb->next;
bsize ++;
}
if(bsize > asize) {
la = LB;
lb = LA;
comp = bsize - asize;
}else {
la = LA;
lb = LB;
comp = asize - bsize;
}
//使长度一致
while(comp --) {
la = la->next;
}
while(la) {
if(la = lb) {
return la;
}
la = la->next;
lb = lb->next;
}
return NULL;
}
function getIntersectionNode(LA, LB) {
let la = LA, lb = LB;
let asize = 0, bsize = 0, comp = 0;
while(la) {
la = la.next;
asize ++;
}
while(lb) {
lb = lb.next;
bsize ++;
}
la = LA;
lb = LB;
if(bsize > asize) {
[asize, bsize] = [bsize, asize];
[la, lb] = [lb, la];
}
comp = asize - bsize;
while(comp --) {
la = la.next;
}
while(la) {
if(la == lb) {
return la;
}
la = la.next;
lb = lb.next;
}
return NULL;
}
public ListNode getIntersectionNode(ListNode LA, ListNode LB) {
ListNode la = LA;
ListNode lb = LB;
int asize = 0, bsize = 0, comp = 0;
while(la) {
la = la.next;
asize ++;
}
while(lb) {
lb = lb.next;
bsize ++;
}
la = LA;
lb = LB;
if(bsize > asize) {
ListNode temp = la;
la = lb;
lb = temp;
int temp2 = asize;
asize = bsize;
bsize = temp2;
}
comp = asize -bsize;
while(comp --) {
la = la.next;
}
while(la) {
if(la == lb) {
return la;
}
la = la.next;
lb = lb.next;
}
return NULL;
}
相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。
因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：
(x + y) * 2 = x + y + n (y + z)
x = (n - 1) (y + z) + z
当 n = 1 时， 表示快指针走了一圈就相遇了
x = z， 分别从头节点和相遇节点出发指针，则相遇节点即为入口节点
ListNode* findSycle (ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
//判断是否相遇
while(slow == fast) {
ListNode* index1 = fast;
ListNode* index2 = head;
//寻找环的入口节点， 相遇点开始各移一个，之后相交则为入口节点
while(index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index2;
}
retrun NULL;
}
}
PNode findSycle(PNode head) {
PNode fast = head;
PNode slow = head;
while(fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
while(slow == fast) {
PNode index1 = head;
PNode index2 = fast;
while(index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return NULL;
}
function findSycle(head) {
let fast = head;
let slow = head;
while(fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
while(slow == fast) {
let index1 = head;
let index2 = fast;
while(index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return NULL;
}
public ListNode findSycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
while(slow == fast) {
ListNode index1 = head;
ListNode index2 = fast;
while(index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return NULL;
}
C++ 给提供了如下三种可用的数据结构：
“eat -> “ate”
bool wordDiff(String s, String t) {
int word[26] = {0};
for(int i = 0; i < s.size(); i ++) {
word[s[i] - 'a'] ++;
}
for(int i = 0; i < t.size(); i ++) {
word[t[i] - 'a'] --;
}
for(int i = 0; i < 26; i ++) {
if(word[i] != 0) {
return false;
}
}
return true;
}
int wordDiff(char* s, char* t) {
int word[26] = {0};
int slen = strlen(s);
int tlen = strlen(t);
for(int i = 0; i < slen; i ++) {
word[s[i] - 'a'] ++;
}
for(int i = 0; i < tlen; t ++) {
word[s[i] - 'a'] --;
}
for(int i = 0; i < 26; i ++) {
if(word[i] != 0) {
return -1;
}
}
return 1;
}
function wordDiff(s, t) {
let word = new Array(26).fill(0);
let basea = 'a'.charCodeAt();
for(int o of s) {
word[o.charCodeAt() - basea] ++;
}
for(int o of t) {
if(word[o.charCodeAt - basea] == 0) return false;
word[o.charCodeAt - basea] --;
}
return true;
}
public bool wordDiff(String s, String t) {
int[] word = new int[26];
for(int i = 0; i < s.length; i ++) {
word[s.charAt(i) -- 'a'] ++;
}
for(int i = 0; i < t.length; i ++) {
if(! word[t.charAt(i) -- 'a']) return false;
word[t.chAt(i) -- 'a'] --;
}
return true;
}
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
//在set中放入整个第一数组
unordered_set<int> nums_set(nums1.begin(), nums1.end());
for(int nums : nums2) {
//数组2的元素在set中找到，则放入结果set
if(nums_set.find(nums) != nums_set.end()) {
result_set.insert(nums);
}
}
return vector<int> (result_set.begin(), result_set.end());
}
function intersection(nums1, nums2) {
let nums_set = new Set(nums1);
let result_set = new Set():
for(let i = 0; i < nums2.length; i ++) {
nums_set.has(nums2[i]) && result_set.add(nums2[i]);
}
return Array.from(result_set);
}
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> result_set = new Set<>();
Set<Integer> nums_set = new Set<>();
for(int i : nums1) {
nums_set.add(i);
}
for(int i : nums2) {
if(nums_set.contains(i) {
result_set.add(i);
}
}
//将结果几何转为数组
return result_set.stream().mapToInt(x -> x).toArray();
}
vector<int> intersection(vector<int>& shu1, vector<int>& shu2) {
unorded_set<int> reult_set;
int hash[1005] = {0};
for(int num : shu1) {
hash[num] = 1;
}
for(int num : shu2) {
if(hash[num] == 1) {
result_set.insert(num);
}
}
return vector<int> (result_set.begin(), result_set.end());
}
int main() {
vector<int> shu1 = {};
intersection(shu1);
}
int* intersection(int* nums1, int size1, int* nums2, int size2, int* returnSize) {
int hash[1005] = {0};
int lessSize = size1 > size2 ? size2 : size1;
int* result = (int *) malloc(sizeof(int) * lessSize);
int resIndex = 0;
int i;
for(i = 0; i < size1; i ++) {
hash[nums1[i]] ++;
}
for(i = 0; i < size2; i ++) {
if(hash[nums2[i]] != 0) {
result[resIndex] = nums2[i];
resIndex ++;
//防止结果数组内数据重复
hash[nums2[i]] = 0;
}
}
//返回结果数组长度
*returnSize = resIndex;
return result;
}
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。
int getSum(int n) {
int sum {0};
while(n) {
sum += (n % 10) * (n % 10);
n = n / 10;
}
return sum;
}
bool isHappy(int n) {
int sum = 0;
unordered_set<int> = set;
while(1) {
sum = getSum(n);
if (sum == 1) {
return true;
}
// 查找存储在 set 内的值，若找到怎说明陷入了循环
if (set.find(sum) != set.end()) {
retrun false;
}else {
set.insert(sum);
}
n = sum;
}
}
使用环形链表方式，如果遇到闭环则表示不为快乐数
int getSum(int n) {
int sum = 0;
while(n) {
sum += (n % 10) * (n % 10);
n = n / 10;
}
return sum;
}
int isHappy(int n) {
if(getSum(n) == 1) return 1;
int a = getSum(n);
int b = getSum(getSum(n));
while(a != 1 && a != b && getSum(b)) {
a = getSum(a);
b = getSum(getSum(b));
}
b == 1 ? return 1 : return -1;
}
function isHappy(n) {
let newSet = new Set();
while(n != 1 && !newSet.has(n)) {
newSet.add(n);
n = getSum(n);
}
return n == 1;
}
public isHappy(int n) {
Set<Integer> newSet = new HashSet<>();
while(n != 1 && !newSet.contains(n)) {
newSet.add(n);
n = getSum(n);
}
return n == 1;
}
| 映射 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
|---|---|---|---|---|---|---|
| std::map | 红黑树 | key有序 | key不可重复 | key不可修改 | O(log n) | O(log n) |
| std::multimap | 红黑树 | key有序 | key可重复 | key不可修改 | O(log n) | O(log n) |
| std::unordered_map | 哈希表 | key无序 | key不可重复 | key不可修改 | O(1) | O(1) |
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
vector<int> doubleSum(vector<int>& num, int target) {
unordered_map<int, int> map;
for(int i = 0; i < num.size(), i ++) {
auto shu = map.find(target - num[i]);
if(shu != map.end()) {
//在map内找到直接返回两个数
//shu->second 返回值; ->first 返回键
return {shu->second, i};
}
//未找到则添加
map.insert(pair<int, int> (num[i], i));
}
}
利用库函数定义 map
typedef struct {
int key;
int value;
UT_hash_handle hh; // make this structure hashable
} map;
map* hashMap = NULL;
void hashMapAdd(int key, int value){
map* s;
// key already in the hash?
HASH_FIND_INT(hashMap, &key, s);
if(s == NULL){
s = (map*)malloc(sizeof(map));
s -> key = key;
HASH_ADD_INT(hashMap, key, s);
}
s -> value = value;
}
map* hashMapFind(int key){
map* s;
// *s: output pointer
HASH_FIND_INT(hashMap, &key, s);
return s;
}
void hashMapCleanup(){
map* cur, *tmp;
HASH_ITER(hh, hashMap, cur, tmp){
HASH_DEL(hashMap, cur);
free(cur);
}
}
void hashPrint(){
map* s;
for(s = hashMap; s != NULL; s=(map*)(s -> hh.next)){
printf("key %d, value %d\n", s -> key, s -> value);
}
}
int* doubleSum(int* nums, int numSize, int target, int* reSize) {
int* result;
map* hashMapRes;
result = (int *) malloc(sizeof(int) * 2);
hashMap = NULL;
for(int i = 0; i < numSize; i ++) {
hashMapRes = hashMapFind(target - nums[i]);
if(hashMapRes && hashMapRes->value != i) {
result[0] = i;
result[1] = hashMapRes->value;
*reSize = 2;
return result;
}else {
hashMapAdd(num[i], i);
}
}
hashMapClearup();
return NULL;
}
function doubleSum(nums, target) {
let hash = {};
for(let i = 0; i < nums.length; i ++) {
if(hash[target - nums[i]] !== undefined) {
return [nums[target - nums[i]], i];
}
hash[nums[i]] = i;
}
return {};
}
public int[] doubleSum(int[] nums, int target) {
int[] result = new int[2];
Map<Integer, Integer> resMap = new HashMap<> ();
for(int i = 0; i < nums.length; i ++) {
int findNum = target - nums[i];
if(resMap.containsKey(findNum)) {
result[0] = i;
result[1] = resMap.get(findNum);
break;
}
resMap.put(nums[i], i);
}
return result;
}
输入:
输出:
2
解释:
两个元组如下:
int fourSum(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int, int> umap;
int count;
for(int a : A) {
for(int b : B) {
//键为 a + b 值为 1
//umap.insert(pair<int , int> ((a + b), 1);
umap[a + b] ++;
}
}
for(int c : C) {
for(int d : D) {
int temp = c + d;
if(map.find(0 - temp) != umap.end()) {
count += umap[0 - temp];
}
}
}
return count;
}
function fourSum(A, B, C, D) {
let nmap = new Map();
let count = 0;
for(let a of A) {
for(let b of B) {
let sum = a + b;
//设置默认值，获取值并且增加1，
nmap.set(sum, (nmap.get(sum) || 0) + 1);
}
}
for(let c of C) {
for(let d of D) {
let sum = c + d;
if(nmap.get(0 - sum)) {
count += nmap.get(sum);
}
}
}
return count;
}
public int fourSum(int[] A, int[] B, int[] C, int[] D) {
Map<Integer, Integer> nmap = new HashMap<>();
int count = 0;
for(int a : A) {
for(int b : B) {
int sum = a + b;
if(nmap.containsKey(sum)) {
nmap.put(sum, nmap.get(sum) + 1);
}else {
nmap.put(sum, 1);
}
}
}
for(int c : C) {
for(int d : D) {
int sum = c + d;
if(nmap.containsKey(0 - sum)) {
count += nmap.get(0 - sum);
}
}
}
return count;
}
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。
(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
bool mes(string ransomNote, string magazine) {
int word[26] {0};
if(ransomNote.size() > magazine.size()) {
return false;
}
for(int i = 0; i < ransomNote.length(); i ++) {
word[ransomNote[i] - 'a'] ++;
}
for(int i = 0; i < magazine.length(); i ++) {
word[magazine[i] - 'a']--;
//判断方式一
if(word[magazine[i] - 'a'] < 0) {
return false;
}
}
//判断方式二
for(int i = 0; i < 26; i ++) {
if(word[i] == 1) {
return false;
}
}
return true;
}
function mes(ransomNote, magazine) {
let word[26] = new Array(26).fill(0);
let base = 'a'.charCodeAt();
for(let o of ransomNote) {
word[o.charCodeAt() - base] ++;
}
for(let o of magazine) {
word[o.charCodeAt - base] --;
if(! word[o.charCodeAt - base]) return false;
}
return true;
}
public bool mes(String ransomNote, String magazine) {
int[] word = new int[26];
for(char o : ransomNote.toCharArray()) {
word[o - 'a'] ++;
}
for(char o : magazine.toCharArray()) {
word[o - 'a'] --;
if(!word[o - 'a']) return false;
}
return true;
}
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
vector<vector<int>> threeSum(vector<int> num) {
vector<vector<int>> result;
//排序
sort(num.begin(), num.end());
for(int i = 0; i < num.size(); i ++) {
if(num[i] > 0) {
break;
}
//去重,保证3个数不与之前的重复， 防止在下一循环重新计算在内
if(i > 0 && num[i] == num[i - 1]) {
continue;
}
unordered_set<int> set;
for(int j = 0; j < num.size(); j ++) {
if(j > i + 2 && num[i] == num[j - 1] &&
num[j - 1] == num[j - 2]) {
continue;
}
int c = 0 - (num[i] + num[j]);
if(set.find(c) != set.end()) {
result.push_back({num[i], num[j], c});
set.erase(c);
}else {
set.insert(num[j]);
}
}
}
return result;
}
vector<vector<int>> threeSum(vector<int> num) {
//排序
sort(num.begin(), num.end());
vector<vector<int>> result;
for(int i = 0; i < num.sizes(); i ++) {
if(num[i] > 0) {
break;
}
//去重
if(i > 0 && num[i] < num[i - 1]) {
continue;
}
int left = i + 1;
int right = num.size() - 1;
while(left < right) {
if((num[left] + num[i] + num[right]) > 0) {
right --;
}else if((num[left] + num[i] + num[right]) < 0) {
left ++;
}else {
result.push_back({num[left], num[i], num[right]});
//去重
while(left < right && num[left] == num[left + 1])
left ++;
while(left < right && num[right] == num[right - 1])
right --;
//同时向内缩进
left ++;
right --;
}
}
}
return result;
}
//qsort辅助cmp函数
int cmp(const void* ptr1, const void* ptr2) {
return *((int*)ptr1) > *((int*)ptr2);
}
int** threeSum(int* nums, int numsSize, int returnSize) {
int** result = (int **) malloc(sizeof(int *) * 1800);
int count = 0;
//对nums数组进行排序
qsort(nums, numsSize, sizeof(int), cmp);
for(int i = 0; i < numsSize; i ++) {
if(nums[i] > 0) {
break;
}
//去重
if(i > 0 && nums[i] - nums[i - 1]) {
continue;
}
int left = i + 1;
int right = numsSize - 1;
while(left < right) {
int sum = nums[left] + nums[i] + nums[right];
if(sum > 0) {
right --;
}else if(sum < 0) {
left ++;
}else {
int* res = (int *) malloc(sizeof(int) * 3);
res[0] = nums[i];
res[1] = nums[left];
res[2] = nums[right];
result[count ++] = res;
free(res);
//数组去重
while(left < right && nums[right] == nums[right - 1]) right --;
while(left < right && nums[left] == nums[left + 1]) left ++;
right --;
left ++;
}
}
}
*returnSize = count;
return result;
}
function threeSum(nums) {
let result = new Array(new Array()).fill(0);
//升序排序
nums.sort((a, b) => a - b);
for(let i = 0; i < nums.length; i ++) {
if(nums[i] > 0) {
break;
}
if(i > 0 && nums[i] == nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while(left < right) {
if(nums[left] + nums[right] + nums[i] < 0) {
left ++;
}else if(nums[left] + nums[right] + nums[i] > 0) {
right --;
}else {
result.push([nums[left], nums[right], nums[i]]);
while(left < right && nums[left] == nums[left + 1]) left ++;
while(left < right && nums[right] == nums[right + 1]) right --;
left ++;
right --;
}
}
}
}
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<> ();
Arrays.sort(nums);
for(int i = 0; i < nums.length; i ++) {
if(nums[i] > 0) {
break;
}
if(i > 0 && nums[i] - nums[i - 1]) continue;
int left = i + 1;
int right = nums.length - 1;
while(left < right) {
if(nums[i] + nums[left] + nums[right] > 0) {
right --;
}else if(nums[i] + nums[left] + nums[right] < 0) {
left ++;
}else {
result.add(Arrys.asList(nums[i], nums[left], nums[right]));
while(left < right && nums[left] == nums[left + 1]) left ++;
while(left < right && nums[right] == nums[right - 1]) right --;
left ++;
right --;
}
}
}
}
遍历前两项，双指针后两项
vector<vector<int>> fourSum(vector<int> num, int target) {
//排序
sort(num.begin(), num.end());
vector<vector<int>> result;
for(int i = 0; i < num.size(); i ++) {
//剪枝
if(num[i] > target && num[i] >= 0) {
break;
}
//去重
if(i > 0 && num[i] == num[i - 1]) {
continue;
}
for(int j = 0; j < num.size(); j ++) {
//2次剪枝
if(num[i] + num[j] > target && num[i] + num[j] >= 0) {
break;
}
//去重
if(j > i + 1 && num[j] == num[j - 1]) {
continue;
}
int left = j + 1;
int right = num.size() - 1;
while(left < right) {
//相加会超限，使用转换
if((long) num[i] + num[j] + num[left] + num[right] > target) {
right --;
} else if((long) num[i] + num[j] + num[left] + num[right] < target) {
left ++;
} else {
result.push_back(vector<int> {num[i], num[j], num[left], num[right]});
//去重
while(left < right && num[left] == num[left + 1])
left ++;
while(left < right && num[right] == num[right - 1])
right --;
right --;
left ++;
}
}
}
}
return result;
}
//qsort辅助cmp函数
int cmp(const void* ptr1, const void* ptr2) {
return *((int*)ptr1) > *((int*)ptr2);
}
int** fourSum(int* nums, int numsSize, int* returnSize, int target) {
int** result = (int **) malloc(sizeof(int *) * 1800);
int count = 0;
//对nums数组进行排序
qsort(nums, numsSize, sizeof(int), cmp);
for(int i = 0; i < numsSize; i ++) {
//剪枝
if(nums[i] > target && nums[i] >= 0) break;
//去重
if(i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for(int j = i + 1; j < numsSize; j ++) {
//剪枝
if(nums[i] + nums[j] > target && nums[j] >= 0) {
break;
}
//去重
if(j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1;
int right = numsSize - 1;
while(left < right) {
if(nums[i] + nums[j] + nums[left] +nums[right] > target) {
right --;
}else if(nums[i] + nums[j] + nums[left] +nums[right] < target) {
left ++;
}else {
int* res = (int *) malloc(sizeof(int) * 4);
res[0] = nums[i];
res[1] = nums[j];
res[2] = nums[left];
res[3] = nums[right];
result[count ++] = res;
//去重
while(left < right && nums[left] == nums[left + 1]) left ++;
while(left < right && nums[right] == nums[right - 1]) right --;
left ++;
right --;
}
}
}
}
*returnSize = count;
return result;
}
function fourSum(nums, target) {
let result = new Array(new Array(4)).fill(0);
for(let i = 0; i < nums.lenght; i ++) {
//剪枝
if(nums[i] > target && nums >= 0) break;
//去重
if(i > 0 && nums[i] == nums[i - 1]) continue;
for(let j = i + 1; j < nums.length; j ++) {
//剪枝
if(nums[i] + nums[j] > target && nums[j] >= 0) break;
//去重
if(j > i + 1; nums[j] == nums[j - 1]) continue;
let left = j + 1;
let right = nums.length - 1;
while(left < right) {
if(nums[i] + nums[j] + nums[left] + nums[right] > 0) {
right --;
}else if(nums[i] + nums[j] + nums[left] + nums[right] < 0) {
left ++;
}else {
result.push([nums[i], nums[j], nums[left], nums[right]]);
//去重
while(left < right && nums[left] == nums[left + 1]) left ++;
while(left < right && nums[right] == nums[right - 1]) right --;
left ++:
right --;
}
}
}
return result;
}
}
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer> result = new ArrayList<> ();
for(int i = 0; i < nums.length; i ++) {
//剪枝
if(nums[i] > target && nums[i] >= 0) break;
//去重
if(i > 0 && nums[i] == num[i - 1]) continue;
for(int j = i + 1; j < nums.length; j ++) {
//剪枝
if(nums[i] + nums[j] > target && nums[j] >= 0) break;
//去重
if(j > i; nums[j] == nums[j - 1]) continue;
int left = j + 1;
int right = 0;
while(left < right) {
if(nums[i] + nums[j] + nums[left] + nums[right] > 0) {
right --;
}else if(nums[i] + nums[j] + nums[left] + nums[right] < 0) {
left ++;
}else {
result.add(Array.asList(nums[i], nums[j], nums[left], nums[right]));
while(left < right && nums[left] == nums[left + 1]) left ++;
while(left < right && nums[right] == nums[right - 1]) right --;
left ++;
right --;
}
}
}
return result;
}
}
void reverse(vector<char>& charN) {
for(int i = 0, int j = charN.size() - 1; i < charN.size() / 2; i ++, j --) {
int temp = charN[i];
charN[i] = charN[j];
charN[j] = temp;
/*
位运算,异或
charN[i] ^= charN[j];
charN[j] ^= charN[i];
charN[i] ^= charN[j];
*/
}
}
给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = “abcdefg”, k = 2
输出: “bacdfeg”
void reverse(string& s, int start, int end) {
for(int i = start, j = end; i < s.size() / 2; i ++, j --) {
int temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
string reverseString(string s, int k) {
for(int i = 0; i < s.size; i += (2 * k)) {
//判断尾部的字符串是否大于K, 大于则相加后小于size
if(i + k <= s.size()) {
reverse(s, i, i + k);
continue;
}
//尾部字符串小于K， 相加后大于size
reverse(s, i, size() - 1);
}
}
char* reverse(char* s, int k) {
int len = strlen(s);
for(int i = 0; i < len; i += (2 * k)) {
int left = i;
int right = i + k - 1;
while(left < right) {
int temp = s[left];
s[left] = s[right];
s[right] = temp;
left ++;
right --;
}
}
}
function reverse(s, k) {
for(let i = 0; i < s.length; i += 2 * k) {
let left = i;
let right = i + k - 1;
while(left < right) {
let temp = s[left];
s[left] = s[right];
s[right] = temp;
left ++;
right --;
}
}
}
public void reverse(String s, int k) {
for(int i = 0; i < s.length; i += 2 * k) {
int left = i;
int right = i + k - 1;
while(left < right) {
int temp = s[left];
s[left ++] = s[right];
s[right ++] = temp;
}
}
}
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
示例 1： 输入：s = “We are happy.”
输出：”We%20are%20happy.”
string replaceSpace(string s) {
int oldSize = s.size();
int count{0};
//计算空格数量
for(int i = 0; i < s.size(); i ++) {
if(s[i] == ' ') {
count ++;
}
}
//重新分配内存
s.resize(malloc(oldSize + (count * 2)));
int newSize = s.size();
for(int i = oledSize - 1, j = newSize - 1; i < j; i --, j --) {
if(s[i] == ' ') {
s[j] = '0';
s[j - 1] = '2';
s[j - 2] = '%';
//跳过填充
j -= 2;
}else {
s[j] = s[i];
}
}
return s;
}
char* replaceSpace(char* s) {
int oldSize = strlen(s);
int count = 0;
for(int i = 0; i < oldeSize; i ++) {
if(s[i] == ' ') {
count ++;
}
}
int newSize = oldSize + 2 * count;
char* news = (char *) malloc(sizeof(char) * newSize + 1);
for(int i = oldSize - 1, int j = newSize - 1; i < j; i --, j --) {
if(s[i] == ' ') {
news[j] = '0';
news[j - 1] = '2';
news[j - 2] = '%';
j -= 2;
}else {
news[j] = s[i];
}
}
news[newSize] = '\0';
return news;
}
function replaceSpace(s) {
let array = Array.from(s);
//计算空格
let oldLen = array.length;
for(let i = 0; i < array.length; i ++) {
if(array[i] == ' ') array.push(' ');
}
for(let i = oldLen - 1, j = array.length - 1; i >= 0; i --, j --) {
if(array[i] == ' ') {
array[j] = '0';
array[j - 1] = '2';
array[j - 2] = '%';
j -= 2;
}else {
array[j] = array[i];
}
}
return array.join('');
}
public String replaceSpace(String s) {
if(s == NULL || s.length() == 0) return s;
StringBuilder str = new StringBuilder(s);
//扩容两个空格的位置
for(char o : s) {
if(o == ' ') str.append(" ");
}
int oldSize = s.length();
//扩容
s += str.toString();
char[] charArray = s.toCharArray();
for(int i = oldSize - 1, j = s.length() - 1; i > 0; i --, j --) {
if(charArray[i] == ' ') {
charArray[j] = '0';
charArray[j - 1] = '2';
charArray[j - 2] = '%';
j -= 2;
}else {
charArray[j] = charArray[i];
}
}
return String(charArray);
}
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1：
输入: “the sky is blue”
输出: “blue is sky the”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
思路: 去除多余空格 -> 翻转字符串 -> 翻转单词
//反转字符
void reverse(string& s, int start, int end) {
for(int i = start, j = end; i < j; i ++, j --) {
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];
}
}
//移除多余空格
void removeExtraSpaces(string& s) {
int slow {0};
//快指针移动
for(int i = 0; i < s.size(); i ++) {
if(s[i] != ' ') {
//手动添加一个空格
if(slow != 0) s[slow ++] = ' ';
//将非空格赋值
while(i < s.size() && s[i] != ' ') {
s[slow ++] = s[i ++];
}
}
}
s.resize(slow);
}
string reverseWords(string& s) {
removeExtraSpaces(s);
reverse(s, 0, s.size() - 1);
int start {0};
//筛选出不为空格的字符进行翻转
for(int i = 0; i < s.size(); i ++) {
if(s[i] != ' ') {
while(i < s.size() && s[i] != ' ') {
i ++;
}
reverse(s, start, i - 1);
start = i + 1;
}
}
return s;
}
//去除多余空格
void removeExtraSpaces(char* s) {
int len = strlen(s);
int slow = 0, fast = 0;
for(; fast < len; fast ++) {
if(s[fast] != ' ') {
//添加空格
if(slow != 0) s[slow ++] = ' ';
//其他字符串复制
while(fast < len && s[fast] != ' ') {
s[slow ++] = s[fast ++];
}
}
}
s[slow] = '\0';
}
//翻转字符单词
char* reverseWords(char* s) {
int len = strlen(s);
//去除多余空格
removeExtraSpaces(s);
//全部翻转字符
reverse(0, len - 1, s);
//翻转单词
int start = 0;
for(int i = 0; i < len; i ++) {
if(s[i] != ' ') {
while(i < len && s[i] != ' ') {
i ++;
}
reverse(start, i - 1, s);
//空格的后一个字符
start = i + 1;
}
}
return s;
}
function removeExtraSpaces(s) {
let fast = 0, slow = 0;
for(; fast < charA.length; fast ++) {
if(s[fast] != ' ') {
if(slow != 0) s[slow ++] == ' ';
while(fast < s.length && s[fast] != ' ') {
s[slow ++] = s[fast ++];
}
}
}
}
function reverseWord(s) {
let charA = Array.from(s);
removeExtraSpaces(charA);
//翻转所有字符
reverse(charA, charA.length - 1);
let start = 0;
for(int i = 0; i < charA.length; i ++) {
if(charA[i] != ' ') {
while(i < charA.length && charA[i] != ' ') {
//移动到空格
i ++;
}
reverse(charA, start, i - 1);
start = i + 1;
}
}
//charA.join('');
return charA.toString();
}
private void removeExtraSpaces(char[] s) {
int slow = 0, fast = 0;
for(; fast < s.length(); fast ++) {
if(s[slow] != ' ') {
if(slow != 0) s[slow ++] = ' ';
while(fast < s.length() && s[slow] != ' ') {
s[slow ++] = s[fast ++];
}
}
}
}
public String reverseWords(String s) {
char[] charA = s.toCharArray();
removeExtraSpaces(charA);
reverse(charA, 0, charA.length());
int start = 0;
for(int i = 0; i < charA.length(); i ++) {
if(charA[i] != ' ') {
while(i < charA.length() && charA[i] != ' ') i ++;
reverse(charA, start, i - 1);
start = i + 1;
}
}
return String(charA);
}
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。
示例 1：
输入: s = “abcdefg”, k = 2
输出: “cdefgab”
string leftReverse(string s, int n) {
reverse(s, 0, n);
reverse(s, n + 1, s.size());
reverse(s, 0, s.size());
return s;
}
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1: 输入: haystack = “hello”, needle = “ll” 输出: 2
KMP主要应用在字符串匹配上。
KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。
文章中字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
void getNext(int* next, string s) {
//初始化, 使 j 为 -1, 判断 i 与 j + 1
//方便记录下标， 与回退下标位置
int j = -1;
next[0] = j;
//i 为 1 表示第二个数开始才有最长相同前后缀
for (int i = 1; i < s.size(); i ++) {
//如果前后缀不匹配
while(j >= 0; s[i] != s[j + 1]) {
//回退
j = next[j];
}
if(s[i] == s[j + 1]) {
j ++;
}
//记录下标，同样表示相同前后缀
next[i] = j;
}
}
前缀减一
void getNext(int* next, string needle) {
int j = -1;
next[0] = j;
for(int i = 1; i < needle.size(); i ++) {
while(j >= 0 && s[i] != s[j + 1]) {
j = next[j];
}
if(s[i] == s[j + 1]) {
j ++;
}
next[i] = j;
}
}
int strStr(string haystack, string needle) {
int j = -1;
if(needle.size() == 0) retrun 0;
int next[needle.size()] {0};
getNext(next, needle);
for(int i = 0; i < haystack.size(), i ++) {
while(j >= 0 && haystack[i] != needle[j + 1]) {
j = next[j];
}
if(haystack[i] == needle[j + 1]) {
j ++;
}
//如果j指向了模式串t的末尾，那么就说明模式串t完全匹配文本串s里的某个子串了
if(j == needle.size() - 1) {
return (i - needle.size() + 1);
}
}
return -1;
}
void getNext(int* next, char* s) {
//KMP算法
int j = -1;
next[0] = j;
int len = strlen(s);
for(int i = 1; i < len; i ++) {
while(j >= 0 && s[i] != s[j + 1]) {
//回退
j = next[j];
}
if(s[i] == s[j + 1]) {
j ++;
}
next[i] = j;
}
}
int strStr(char* haystack, char* needle) {
int hlen = strlen(haystack);
int nlen = strlen(needle);
int j = -1;
int next[nlen] = 0;
getNext(next, needle);
for(int i = 0; i < hlen; i ++) {
while(j != -1 && haystack[i] != needle[j + 1]) j = next[j];
if(haystact[i] == needle[j + 1]) j ++;
if(j = nlen - 1) return i - nlen + 1;
}
}
function getNext(next, s) {
let j = -1;
next[0] = j;
for(let i = 1; i < s.length; i ++) {
while(j != -1 && s[i] != s[j + 1]) j = next[-1];
if(s[i] == s[j + 1]) j ++;
next[i] = j;
}
}
function strStr(haystack, needle) {
let j = -1;
let next = new Array(needle.length).fill(0);
getNext(next, needle);
for(int i = 0; i < haystack.length; i ++) {
while(j != -1 && haystack[i] != needle[j + 1]) j = next[j];
if(haystack[i] == needle[j + 1]) j ++;
if(j == needle.length - 1) return i - needle + 1;
}
}
private void getNext(int[] next, String s) {
char[] charA = s.toCharArray();
int j = -1;
next[0] = j;
for(int i = 1; i < charA.length(); i ++) {
while(j != -1 && charA[i] != charA[j + 1]) j = next[j];
if(charA[i] == charA[j + 1]) j ++;
next[i] = j;
}
}
// 前缀表不减一
private getNext(int[] next, String s) {
int j = 0;
next[j] = j;
char[] charA = s.toCharArray();
for(int i = 1; i < charA.length(); i ++) {
while(j > 0 && charA[i] !== charA[j]) {
j = next[j - 1];
}
if(charA[i] == charA[j]) {
j ++;
}
next[j] = j;
}
}
public int strStr(String haystack, String needle) {
char[] hchar = haystack.toCharArray();
char[] nchar = needle.toCharArray();
int j = -1;
int[] next = next int[nchar.length()];
getNext(next, needle);
for(int i = 0; i < hchar.length(); i ++) {
while(j != -1 && hchar[i] != nchar[j + 1]) j = next[j];
if(hchar[i] == nchar[j + 1]) j ++;
if(j == nchar.length() - 1) return i - nchar.length() + 1;
}
}
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: “abab”
输出: True
解释: 可由子字符串 “ab” 重复两次构成
思路： 如果字符串重复，获取最长相等前后缀，是除去一个子串的长度
abcabcabcabc
void getNext(int* next, string s) {
//自减一
int j = -1;
next[0] = j;
for(int i = 0; i < s.size(); i ++) {
while(j != -1 && s[i] != s[j + 1]) {
j = next[j];
}
if(s[i] == s[j + 1]) {
j ++;
}
next[j] = i;
}
}
bool isRepeated(string s) {
if(s.size() == 0) {
return false;
}
int len = s.size();
int next[len];
getNext(next, s);
//---(next[s.size() - 1] + 1) 表示最长相等前后缀
//---len - (next[s.size() - 1] + 1) 表示子串长度
//---len % 字串长度 == 0 时表示为字串重复
if(next[len - 1] != -1 && len % (len - (next[len - 1] + 1))) {
return true;
}
return false;
}
void getNext(int* nums, char* s) {
int j = -1;
nums[0] = j;
int len = strlen(s);
for(let i = 0; i < len; i ++) {
if(j >= 0 && s[i] != s[j + 1]) j = nums[j];
if(s[j + 1] == s[i]) j ++;
nums[i] = j;
}
}
int isRepeated(char* s) {
int len = strlen(s);
int* next[len] = {};
getNext(next, s);
if(next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) return 1;
return 0;
}
function getNext(next, s) {
let j = -1;
next.push(j);
for(let i = 0; i < s.length; i ++) {
if(j != -1 && s[i] != s[j + 1]) j = next[j];
if(s[i] == s[j + 1]) j ++;
next.push(j);
}
}
function isRepeated(s) {
let len = s.length;
let next = new Array(s.length).fill(0);
getNext(next, s);
if(s[len - 1] != -1 && len % (len - (s[len - 1] + 1)) == 0) return true;
return false;
}
public void getNext(int[] next, char[] charA) {
int j = -1;
next[0] = j;
for(int i = 0; i < charA.length(); i ++) {
if(j != -1 && charA[i] != charA[j + 1]) j = next[j];
if(charA[i] == charA[j + 1]) j ++;
next[i] = j;
}
}
public bool isRepeated(String s) {
charA[] charA = s.toCharArray();
int[] next = new Array(s.length());
getNext(next, charA);
int len = s.length;
if(next[len - 1] != -1 && len % (len - (len[len - 1] + 1)) == 0) return true;
return false;
}
使用栈实现队列的下列操作：
push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。
class MyQueue {
private :
stack<int> stackIn;
stack<int> stackOut;
public :
MyQueue() {}
int push(x) {
stackIn.push(x);
}
int pop() {
if(stackOut.empty()) {
while (!stackIn.empty) {
stackOut.push(stackIn.top());
stackIn.pop();
}
int result = stackOut.top();
stackOut.pop();
return result;
}
}
int peek() {
int result = this->pop();
stackOut.push(result);
return result;
}
int empty() {
return stackIn.empty() && stackOut.empty();
}
}
typedef struct {
int stackInTop, stackOutTop;
int stackIn[100], stackOut[100];
}MyQueue;
//初始化
MyQueue* queue() {
MyQueue* queue = (MyQueue *) malloc(sizeof(MyQueue));
queue->stackInTop = 0;
queue->stackOutTop = 0;
return queue;
}
int push(MyQueue* que, int x) {
que->stackIn[que->stackInTop ++] = x;
return x;
}
int pop(MyQueue* que) {
//避免多次操作内存
int inTop = que->stackInTop;
int outTop = que->stackOutTop;
if(outTop == 0) {
while(inTop != 0) {
que->stackOut[outTop ++] = que->stackIn[-- inTop];
}
int result = stackOut[--outTop];
//将输入栈返回到输出栈
while(outTop != 0) {
que->stackIn[inTop ++] = que->stackOut[-- outTop];
}
que->stackInTop = inTop;
que->stackOutTop = outTop;
return result;
}
}
int peek(MyQueue* que) {
return que->stackIn[0];
}
int empty(MyQueue* que) {
return que->stackInTop == 0 && que->stackTop == 0;
}
void freeMyQueue(MyQueue* que) {
que->stackInTop = 0;
que->stackOutTop = 0;
}
class solution {
let stackIn, let stackOut;
constructor() {
//stackIn = new Array();
stackIn = [];
stackOut = [];
}
push(val) {
this.stackIn.push(val);
}
pop() {
if(this.stackOut.length) return stackOut.pop());
while(this.stackIn.length) {
this.stackOut.push(this.stackIn.pop());
}
return this.stackOut.pop();
}
peek() {
return stackIn[0];
}
isEmpty() {
return !this.stackIn.length && !this.stackOut.length;
}
}
class Solution {
Stack<Integer> stackIn;
Stack<Integer> stackOut;
//初始化
public Solution() {
stackIn = new Stack<> ();
stackOut = new Stack<> ();
}
//队列添加元素
public void push(int val) {
stackIn.push(val);
}
//队列删除最前元素
public void pop() {
insideOut();
stackOut.pop();
}
//返回队列第一个元素
public int peek() {
insideOut();
return stack.peek();
}
//返回是否队列为空
public bool isEmpty() {
return stackIn.isEmpty() && stackOut.isEmpty();
}
public void insideOut() {
if(!stackOut.isEmpty()) return ;
while(!stackIn.isEmpty()) stackOut.push(stackIn.pop());
}
}
使用队列实现栈的下列操作：
class MyStack {
public:
queue<int> que1;
queue<int> que2;
int push(int x) {
que1.push(x);
}
int pop() {
int size = que1.size();
//留下最后一个元素
size --;
while(sizs --) {
que2.push(que1.front());
que1.pop();
}
int result = que1.front();
que1.pop();
while(!que2.empty()) {
que1.push(que2.front());
que2.pop();
}
return result;
}
int top() {
return que1.back();
}
int empty() {
return que1.empty();
}
}
class MyStack {
public:
int pop() {
int size = que.size();
size --;
while(size --) {
que.push(que.pop());
}
int result = que.front();
que.push(que.pop());
return result;
}
}
C语言可以通过数组来实现顺序队列，通过实现逻辑环形的数组顺序队列
还可以用一个单链表链表记录队列中的节点并记录后一个节点
用另一个结构体包含头节点和尾节点的双指针
typedef struct QueNode {
int val;
//单向队列
struct QueNode* next;
}QNode;
typedef struct Que {
//指向队列尾部
QNode* tail;
//指向队列头部
QNode* head;
}Que;
//队列初始化
void QueInit(Que* que) {
//assert()宏接受一个整形表达式参数。
//如果表达式的值为假，assert()宏就会调用_assert函数在标准错误流中打印一条错误信息，并调用abort()
//（abort()函数的原型在stdlib.h头文件中）函数终止程序。
assert(que);
que->tail = que->head = NULL;
}
void push(Que* que, int val) {
Qpush(que, val);
}
int pop(Que* que, int size) {
//留下最后一个元素
size --;
while(size --) {
Qpush(que, que->head->val);
Qpop(que);
}`
int result = que->head->val;
Qpop(que);
return result;
}
class MyStack {
let que;
constructor() {
que = [];
}
push(val) {
this.que.shift(val);
}
pop() {
let size = this.que.length;
size --;
while(size --) {
//反向利用数组
this.que.unshift(this.que.pop());
}
return this.que.pop();
}
}
class MyStack {
Queue<Integer> que;
public MyStack() {
que = new LinkedList<> ();
}
public void push(int val) {
que.offer(val);
}
public int pop() {
int size = que.size();
while(size-- > 1) {
que.offer(que.poll());
}
return que.poll();
}
}
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
示例 1:
bool isValid(string s) {
if(s.size() % 2 != 0) return false;
stack<char> stack;
for(int i = 0; i < s.size(), i ++) {
if(s[i] == "[" ) {
stack.push("]");
}else if(s[i] == "{") {
stack.push("}");
}else if(s[i] == "(") {
stack.push(")");
}else if(s[i] == stack.top()) {
stack.pop();
}else (stack.empty() || s[i] != stack.top()) {
return false;
}
}
//为空则匹配成功
retrun stack.empty();
}
typedef struct stack {
int stackTop;
char stack[100];
}Stack;
Stack* stackInit(Stack* stack) {
stack->stackTop = 0;
return stack;
}
int match(char par, Stack* stack) {
switch(par) {
case ']':
return stack->stack[--stack->stackTop] != '[';
case ')':
return stack->stack[--stack->stackTop] ！= '(';
case '}':
return stack->stack[--stack->stackTop] != '{';
}
return 0;
}
int isValid(Stack* stack, char* s) {
int len = strlen(s);
stackInit();
for(int i = 0; i < len; i ++) {
if(s[i] == '[' || s[i] == '{' || s[i] == '(') {
stack->stack[stack->stackTop ++] = s[i];
}else if(stack->stackTop == 0 || match(s[i], stack)) {
return -1;
}else {
//栈弹出
stack->stackTop --;
}
}
return stack->stackTop == 0 ? 1 : -1;
}
function isValid(s) {
let stack = [];
for(let i = 0; i < s.length; i ++) {
switch(s[i]) {
case "{" :
stack.push("}");
break;
case "[" :
stack.push("]");
break;
case "(" :
stack.push(")");
break;
default:
if(s[i] != stack.pop()) return false;
}
}
return !stack.length;
}
function isValid(s) {
let stack = [];
let map = {
"{": "}",
"[": "]",
"(": ")"
}
for(let i of s) {
if(map.hasOwnProperty(i)) {
stack.push(map[i]);
}else {
if(i != stack.pop()) return false;
}
}
return !stack.length;
}
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
c++
string findNeiborDel(string s) {
stack<char> stack;
for(int i = 0; i < s.size(); i ++) {
if(s[i] == stack.top()) {
stack.pop();
}else if(stack.empty() || s[i] != stack.top()) {
stack.push(s[i]);
}
}
string result = "";
while(!stack.empty()) {
result += stack.top();
stack.pop();
}
//反转字符串
revese(result.begin(), result.end());
return result;
}
c++
string findNeiborDel(string s) {
string result;
for(char a : s) {
if(result.empty() || result.back() != a) {
result.push_back(a);
}else if(result.back() == a) {
result.pop_back();
}
}
return result;
}
js
function findNeibor(s) {
let result = [];
for(let i of a) {
if(i == result[result.length]) result.pop();
else if(!result.length || i != result[result.length]) result.push(i);
}
return result.join('');
}
java
public String findNeibor(String s) {
StringBuilder sr = new StringBuilder();
int top = -1;
for(int i = 0; i < s.length(); i ++) {
char c = s.charAt(i);
if(top != -1 || sr.charAt(top) == c) {
sr.deleteCharAt(top);
top --;
}
else if(sr.charAt(top) != c) {
sr.append(c);
top ++;
}
}
return sr;
}
根据 逆波兰表示法，求表达式的值。
有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
示例 2：
int evalRPN(vector<string> s) {
stack<long long> stack;
for(int i = 0; i < s.size(); i ++) {
if(s[i] == "+" || s[i] == "-" || s[i] == "*" || s[i] == "/") {
long long num1 = stack.top();
stack.pop();
long long num2 = stack.top();
stack.pop();
if(s[i] == "+") {
stack.push(num1 + num2);
}else if(s[i] == "-") {
stack.push(num1 - num2);
}else if(s[i] == "*") {
stack.push(num1 * num2);
}else if(s[i] == "/") {
stack.push(num1 / num2);
}
}else {
stack.push(s[i]);
}
}
return stack.top();
}
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
思路：
使用一个单调队列，队列前面的值为最大值
class Solution {
private:
class MyQueue {
//使用双端队列
deque<int> que;
void pop(value) {
if(!que.empty() && value == que.front()) {
que.pop_front();
}
}
void push(value) {
while(!que.empty() && value > que.back()) {
que.pop_back();
}
que.push_back(value);
}
int front() {
return que.eqmpt() && que.front();
}
}
public:
vector<int> maxSiblingWindow(vector<int>& num, int k) {
MyQueue que;
vector<int> result;
//将前K个放入单调队列
for(int i = 0; i < k; i ++) {
que.push(num[i]);
}
result.push_back(que.front());
for(int i = k; i < num.size(); i ++) {
//删除k之后相同的值
que.pop(num[i - k]);
que.push(num[i]);
//保存最前列的值
que.push_back(que.front());
}
return result;
}
}
class Solution() {
public:
class comparition() {
public:
bool operator(const pair<int, int>& lhs, const pair<int, int>& rhs) {
//左大于右，表示从大到小，优先级队列则为相反，用于构建小顶堆
return lhs.second > rhs.second;
}
vector<int> topKFrequent(vector<int> num, int k) {
vector<int> result(k);
//用map来记录出现的频率
unordered_map<int> map;
//遍历获取频率
for(int i = 0; i < num.size(); i ++) {
//key 为 num的值，value 为出现频率
map[num[i]] ++;
}
//构建小顶堆，使用优先级队列，使具备条件的最先出队，底层实现为堆
//参数为<类型，存放数据容器， 比较方式>
priority_queue<const pair<int, int>, vector<const pair<int, int>>, comparition> pri_que;
//将 map 的值 push 进队列
for(auto it : map) {
pri_que.push(it);
//将超出 k 的弹出，即最小的元素
if(pri_que.size() > k) {
pri_que.pop();
}
}
//优先级队列为倒叙，输入结果容器
for(int i = k - 1; i >= 0; i --) {
//frist 为 key，即是数组元素
result[i] = pri_que.top().frist;
pri_que.pop();
}
return result;
}
}