Joyce' Blog

remove-element

发表于 2020-01-22 更新于 2020-01-23

题目描述

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。

解决方案

一个快指针，一个慢指针

int removeElement(vector<int>& nums, int val) {
	int size = nums.size();
	if (!size)
		return 0;
	auto it1 = nums.begin();
	auto it2 = nums.begin();
	int t2;
	while (it2 != nums.end())
	{
		t2 = *it2;
		while(t2 == val)
		{
			it2++;
			size--;
			if (it2 == nums.end())
				return size;
			t2 = *it2;
		}
		*it1 = t2;
		it1++;
		it2++;
	}
	return size;
}

remove-duplicates-from-sorted-array

发表于 2020-01-22

题目描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

解决方案

没啥意思，主要就是vector的基本操作。注意边界条件。

但是我写出来咋这么慢呢？还占这么多内存？

int removeDuplicates(vector<int>& nums) {
	int res = nums.size();
	if (res == 0)
		return 0;
	int temp = nums[0];
	auto it = nums.begin() + 1;
	while (it != nums.end())
	{
		int d = *it;
		if (d == temp)
		{
			nums.erase(it);
			res--;
			continue;
		}
		temp = d;
		it++;
	}
	return res;
}

看了一下别人的题解，大概是我在erase函数上花的时间太多了，难怪题上说“你不需要考虑数组中超出新长度后面的元素。” 那就直接覆盖嘛。需要使用两个指针。

int removeDuplicates(vector<int>& nums) {
	int res = nums.size();
	if (res == 0)
		return 0;
	auto it1 = nums.begin();
	auto it2 = nums.begin() + 1;
	while (it2 != nums.end())
	{
		int d = *it1;
		int t = *it2;
		while (t == d)
		{
			it2++;
			res--;
			if (it2 != nums.end())
				t = *it2;
			else
				return res;
		}
		it1++;
		it2++;
		*it1 = t;
	}
	return res;
}

reverse-nodes-in-k-group

发表于 2020-01-21 更新于 2020-01-22

题目描述

一个链表，每 k 个节点一组进行翻转，返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，最后剩余的节点保持原有顺序。

示例 : 给定链表：1->2->3->4->5，当 k = 2 时，应当返回: 2->1->4->3->5；当 k = 3 时，应当返回: 3->2->1->4->5

说明 : 只能使用常数的额外空间。不能只是单纯的改变节点内部的值，需要实际的进行节点交换。

解决方案

双向队列会比较适合这次的题目，按序压入，再反序取出连起来。为了编程方便，加了preHeader.

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseKGroup(ListNode* head, int k) {
	if (!head || !head->next || k <= 1)
		return head;
	ListNode* preh;
	preh = new ListNode(-1);
	preh->next = head;
	ListNode* lenp=head;
	int i;
	bool flag = true;
	do {
		deque<ListNode*> d;
		for (i=1; lenp && i < k; i++){
			d.push_front(lenp);
			lenp = lenp->next;			
		}
		if (!lenp && i<=k)
			if (!d.empty())
				preh->next = d.back();
			return head;
		d.push_front(lenp);
		ListNode* n1 = d.back();
		n1->next = lenp->next;
		ListNode* n2 = d.front();
		preh->next = n2;
		if (flag){
			head = n2;
			flag = false;
		}
		for (int j = 1; j < k; j++){
			d.pop_front();
			n2->next = d.front();
			n2 = n2->next;
		}
		lenp = d.front()->next;
		preh= d.front();
		d.pop_front();
	} while (true);
}

倒是挺有意思的一道题。本来以为会是在两两交换的基础上完成这道题目，现在发现使用了合适的数据结构，真是能节省不少精力。或许两两交换那道题目也可以做一些改进。

在上面的代码中或许加一个后驱会方便一些。

用递归的方法也可以解这个题，每次交换待反转结点的第一个和最后一个。

真面向样例编程唉什么时候才能真正有质变啊

swap-nodes-in-pairs

发表于 2020-01-21

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

例：给定 1->2->3->4, 你应该返回 2->1->4->3.

解决方案

主要还是弄清楚指针指来指去的顺序。还有注意把两两交换后的节点对连起来。

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};
ListNode* swapPair(ListNode* n1)
{
	ListNode* p = n1;
	ListNode* q = n1->next->next; 
	n1 = n1->next;
	n1->next = p;
	n1->next->next = q;
	return n1;
}
ListNode* swapPairs(ListNode* head) {
	if (!head || !head->next)
		return head;
	ListNode* h = head;
	ListNode* link = head;
	bool flag = true;
	do
	{
		ListNode* tmp = h;
		tmp=swapPair(tmp);
		if (flag)
		{
			head = tmp;
			flag = false;
		}
		else
		{
			link->next = tmp;
			link = tmp->next;
		}
		h = tmp->next->next;
		if (!h||!h->next)
			break;
	} while (true);
	return head;
}

merge-k-sorted-lists

发表于 2020-01-20

题目描述

合并 k 个排序链表

解决方案

我的解题思路是基于合并两个有序链表。合并k个链表时，若每次创建新的节点，可能需要较大内存，因此对上次的代码进行了改进，每次将现有的节点串起来，不再创建新节点。

struct ListNode {
   int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == NULL)
        return l2;
    else if (l2 == NULL)
        return l1;
    ListNode *t1, *t2, *tmp;
    int n = l1->val, m = l2->val;
    if (n > m)
    {
        tmp = l1;
        l1 = l2;
        l2 = tmp;
    }
    t1 = l1;
    t2 = l2;
    while (t1&&t2)
    {
        ListNode *tmp1, *tmp2;
        n = t1->val, m = t2->val;
        if (n > m)
            while (t2->next&&t2->next->val <= n)
                t2 = t2->next;
        else if(n<m)
            while (t1->next&&t1->next->val <= m)
                t1 = t1->next;
        tmp1 = t1->next;
        t1->next = t2;
        t1 = t2;
        tmp2 = t2->next;
        if (t1 != NULL)
            t2->next = tmp1;
        else
            return l1;
        t2 = tmp2;
    }
    if (t2)
        t1 = t2;
    return l1;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
   int num = lists.size();
   if (num == 0)
       return NULL;
    else if (num == 1)
       return lists[0];
    ListNode* res = lists[0];
    for (size_t i = 1; i < num; i++) {
       res = mergeTwoLists(res, lists[i]);
    }
    return res;
}

generate-parentheses

发表于 2020-01-20

问题描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

解决方案

首先想到了二叉树。使用深度遍历，向左走加(，向右走加)，压入合适的字符串。

vector<string> v;
void dfs(string s,int val,int n,int count)
{
	if (count == n && val == 0)
		v.push_back(s);
	else if (count>n||val < 0)
		return;
	else 
	{	
		dfs(s + "(",val + 1, n, count + 1);
		dfs(s + ")",val - 1, n, count);
	}
}
vector<string> generateParenthesis(int n) {

	dfs("", 0, n, 0);
	return v;
}

merge-two-sorted-lists

发表于 2020-01-19 更新于 2020-01-20

题目表述

合并两个有序链表

解决方案

//将两个有序链表合并为一个新的有序链表并返回
//新链表是通过拼接给定的两个链表的所有节点组成的
/*
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
*/
struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
	if (l1 == NULL)
		return l2;
	else if (l2 == NULL)
		return l1;
	ListNode *head, *tp, *t1, *t2;
	int m = l1->val, n = l2->val;
	t1 = l1;
	t2 = l2;
	if (m<n)
	{
		tp = new ListNode(m);
		t1 = l1->next;
	}
	else
	{
		tp = new ListNode(n);
		t2 = l2->next;
	}
	head = tp;
	while (t1&&t2)
	{
		m = t1->val, n = t2->val;
		if (m< n)
		{
			tp->next = new ListNode(m);
			tp = tp->next;
			t1 = t1->next;
		}
		else
		{
			tp->next = new ListNode(n);
			tp = tp->next;
			t2 = t2->next;
		}
	}
	if (t1)
		tp->next = t1;
	else if (t2)
		tp->next = t2;
	return head;
}

之后进行了改进，不再创建新的节点，把现有的节点串起来，但会破坏传进来的原有链表。

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (l1 == NULL)
        return l2;
    else if (l2 == NULL)
        return l1;
    ListNode *t1, *t2, *tmp;
    int n = l1->val, m = l2->val;
    if (n > m)
    {
        tmp = l1;
        l1 = l2;
        l2 = tmp;
    }
    t1 = l1;
    t2 = l2;
    while (t1&&t2)
    {
        ListNode *tmp1, *tmp2;
        n = t1->val, m = t2->val;
        if (n > m)
            while (t2->next&&t2->next->val <= n)
                t2 = t2->next;
        else if(n<m)
            while (t1->next&&t1->next->val <= m)
                t1 = t1->next;
        tmp1 = t1->next;
        t1->next = t2;
        t1 = t2;
        tmp2 = t2->next;
        if (t1 != NULL)
            t2->next = tmp1;
        else
            return l1;
        t2 = tmp2;
    }
    if (t2)
        t1 = t2;
    return l1;
}

ValidParentheses

发表于 2020-01-19

问题描述

括号匹配

解决方案

主要还是考“栈”这一数据数据结构。

bool isValid(string s) {
	stack<char> par;
	char tmp;
	for (int i = 0; i < s.length(); i++)
	{
		tmp = s[i];
		if(tmp=='('||tmp=='['||tmp=='{')
			par.push(s[i]);
		else
		{
			if (par.empty())
				return false;
			char top = par.top();
			switch (s[i])
			{
			case ')':
				if (top != '(')
					return false;
				break;
			case ']':
				if (top != '[')
					return false;
				break;
			case '}':
				if (top != '{')
					return false;
				break;
			default:
				return false;
			}
			par.pop();
		}
	}
	if (par.empty())
		return true;
	else
		return false;
}

语法分析器tips

发表于 2019-11-19 更新于 2019-12-02

关键字struct

c++ 的struct 声明变量的时候不需要加struct前缀。在C语言中，实例化一个结构体必须要加上关键字struct。为了避免每次用的时候都要加上struct前缀，可以定义的时候加上typedef。

YACC文件格式

... definitions ...（%{}%）
%%
... rules ...
%%
... subroutines ...

第一部分包括标志（token）定义和C代码（用“%{”和“%}”括起来）。
如在定义部分定义标志：
%token INTEGER
当运行yacc后，会产生头文件，里面包含该标志的预定义，如：

#ifndef YYSTYPE 
#define YYSTYPE int 
#endif 
#define INTEGER 258 
extern YYSTYPE yylval;

lex使用该头文件中的标志定义。Yacc调用lex的yylex()来获得标志（token），与标志对应的值由lex放在变量yylval中。

yylyal

Lex 将解析的token保存在yylval中，yylval的类型由YYSTYPE决定，YYSTYPE缺省类型是int。为了保存不同类型的变量，yylval 别定义为union（详情见下面参考部分）。

如果没有指定 \ && 就是指向yylval 本身。

yytext

由于yytext是字符串指针，所以注意要进行深拷贝，否则yytext最后指向}，会赋给所有的symbol

参考：

If the type is int (the default), you might write this in yylex:

…
yylval = value;  /* Put value onto Bison stack. */
return INT;      /* Return the type of the token. */
…

When you are using multiple data types, yylval’s type is a union made from the %union declaration (see The Union Declaration). So when you store a token’s value, you must use the proper member of the union. If the %union declaration looks like this:

%union {
  int intval;
  double val;
  symrec *tptr;
}

then the code in yylex might look like this:

…
yylval.intval = value; /* Put value onto Bison stack. */
return INT;            /* Return the type of the token. */
…

enum枚举类型

1	enum　枚举名　{枚举元素1,枚举元素2,……};

第一个枚举成员的默认值为整型的 0，后续枚举成员的值在前一个成员上加 1,可以在定义枚举类型时改变枚举元素的值。在C 语言中，枚举类型是被当做 int 或者 unsigned int 类型来处理的。

vs报错

0xC0000005: 读取位置 xxx时发生访问冲突

访问了不该访问的地方。越界了。

VS2017”const char “ 类型的实参与 “char “ 类型的形参不兼容

属性 – C/C++ – 语言 – 符合模式改为“否”

分不清=和==是要吃大亏的。循环写错了递增条件是要吃大亏的。

Lab_note_11.10

发表于 2019-11-10