isaacpei / algorithm-interview Goto Github PK

View Code? Open in Web Editor NEW

18.0 4.0 0.0 24 KB

Weekly algorithm questions for interview

algorithm-interview's Introduction

Algorithm-interview

Weekly algorithm questions for interview

How to use it

Read the problem
Write your code in any language which you would like to use in interview
Submit your answer by adding issue, there's a template for issue, please reuse it

Others' solution

We'll add label like Q001 to solutions, you can use filters to search them
Solutions for questions not for current week will be marked as closed issue

TODOs

How to write code correctly?
How to communicate with interviewer?
Test cases and judging scripts
FAQ and so on..

And...

We have a QQ group: 676901252

algorithm-interview's People

Contributors

Stargazers

Watchers

algorithm-interview's Issues

Question_ID: Q001

Language: C

Time Cost: ∞

Time Complexity: O(n)

Solution

First...
only parse '<' '>' '/'
Then...
output other and add enter and space
And...
Is ok

My Code

#include <stdio.h>

void parse_xml(char *src_xml)
{
	int count = 0;
	int i = 0;
	int is_end = 0;

	while (src_xml[i]) {
		switch (src_xml[i]) {
			case '<':
				if (i != 0)
					printf("\n");
				for(int j =0; j < count; j++)
					printf("    ");
				printf("<");
				count++;
				break;
			case '>':
				printf(">");
				if (!is_end) {
					printf("\n");
					for(int j=0; j<count; j++)
						printf("    ");
				} else {
					is_end = 0;
					count--;
				}
				break;
			case '/':
				is_end = 1;
				count--;
				printf("/");
				break;
			default:
				printf("%c", src_xml[i]);
				break;
		}
		i++;
	}
	printf("\n");
}

int main(int argc, char *argv[])
{
	parse_xml(argv[1]);
	return 0;
}

Other

菜鸟,希望dalao们多指教.
Thx.

Q001_super2bai_solution

Question_ID: Q001

Language: Java

Time Cost: Oops...I don't remember

Time Complexity: O(n)

Solution

First...find <
Then...find >
And... split > and text

My Code

   public static void main(String[] args) throws Exception {
        //测试用例
        String s = "<a><b>456</b></a>";
//      String s = "<a>123<b><c/></b></a>";
//      String s = "<a>123<b>456<c/></b></a>";
//      String s="<a></a>";
        /**
         * 0:开头;1:<b/>;2:value;3:</b>
         * 工作中写代码需要把type提为Enum
         */
        int type = -1;
        String indentStandard = "    ";
        String indentInUse = "";
        String[] left = s.split("\\<");
        for (int i = 1; i < left.length; i++) {
            //结尾标签
            if (left[i].startsWith("/")) {
                if (type != 0) {
                    indentInUse = indentInUse.equals("") ? "" : indentInUse.substring(indentStandard.length());
                }
                type = 3;
                if(left[i].endsWith(">")){
                    System.out.println(indentInUse + "<" + left[i]);
                }else {
                    System.out.println(indentInUse + "<" + left[i].substring(0, left[i].indexOf(">") + 1));
                    System.out.println(indentInUse + left[i].substring(left[i].indexOf(">") + 1));
                }
            }
            //<b/>
            else if (left[i].endsWith("/>")) {
                if (type != 2) {
                    type = 1;
                    indentInUse += indentStandard;
                }
                System.out.println(indentInUse + "<" + left[i]);
            }
            //<b>
            else if (left[i].endsWith(">")) {
                if (type == 0) {
                    indentInUse += indentStandard;
                }
                System.out.println(indentInUse + "<" + left[i]);
                type = 0;
            }
            //<b>123
            else {
                if (type == 0) {
                    indentInUse += indentStandard;
                }
                System.out.println(indentInUse + "<" + left[i].substring(0, left[i].indexOf(">") + 1));
                indentInUse += indentStandard;
                System.out.println(indentInUse + left[i].substring(left[i].indexOf(">") + 1));
                type = 2;
            }
        }
    }

Question_ID: Q002

Language: C++

Time Cost: 40-mins

Time Complexity: O(1)

Solution

维护一个双端队列保存最大值

My Code

#include <iostream>
#include <cstdlib>
#include <string>
#include <queue>
#include <deque>
using namespace std;

template<class T> class MaxQueue {
public:
    void push(const T &elem);
    T pop();
    T get_max();
private:
    queue<T> q;
    deque<T> d;
};

template<class T> void MaxQueue<T>::push(const T &elem)
{
    q.push(elem);
    while (!d.empty() && d.back() < elem)
        d.pop_back();
    d.push_back(elem);
}

template<class T> T MaxQueue<T>::pop()
{
    if (q.empty())
        return -1;

    T res = q.front();
    q.pop();
    if (res == d.front())
        d.pop_front();
    return res;
}

template<class T> T MaxQueue<T>::get_max()
{
    if (d.empty())
        return -1;

    return d.front();
}

int main(void)
{
    MaxQueue<int> que;
    string input;

    while (getline(cin, input)) {
        int idx_split = input.find_first_of(" ", 0);
        string command = input.substr(0, idx_split);
        int arg = atoi(input.substr(idx_split+1).c_str());
        if (command == "push") {
            que.push(arg);
            cout << "None" << endl;
        } else if (command == "pop") {
            cout << que.pop() << endl;
        } else if (command == "get_max") {
            cout << que.get_max() << endl;
        }
    }

    return 0;
}

Other

Q001_ryanorz_c++_solution: no error check, no tag match, just simple enough.

Question_ID: Q001_ryanorz_solution

Language: c++

Time Cost: 40-mins

Time Complexity: O(n)

Solution

Note: no error check, no tag match, just simple enough.

First, get token with 4 types(Content, Pretag, Posttag, Fulltag), my solution does't have error input check yet.
Then, output token

My Code

响应号召，代码变成30行以内

#include <string>
using namespace std;

void formatXML3(const string& input) {
    int offset = 0;
    int level = 0;
    while (offset < input.size()) {
        int start = offset;
        if (input[offset] == '<') // 找出 tag
            offset = input.find_first_of(">", offset+1) + 1;
        else // 找出 content
            offset = input.find_first_of("<", offset+1);
        if (offset == string::npos) // 没找到结尾符号则，则直接偏移到最后
            offset = input.size();
        // </tag> 结尾标签层级先减一再打印
        if (input[start] == '<' && input[start+1] == '/') level--;
        // 打印 level + tag 或 level + content
        printf("%s%s\n", string(level*4, ' ').c_str(),
            input.substr(start, offset-start).c_str());
        // <tag> 开始标签打印完层级加一
        if (input[start] == '<' && input[start+1] != '/' && input[offset-2] != '/') level++;
    }
}

int main(int argc, char* argv[]) {
    string input = "<a>123<b>456<c/></b></a>";
    formatXML3(input);
}

以下是原始版代码

#include <string>
using namespace std;

enum class TokenType {
    Content,
    Pretag,
    Posttag,
    Fulltag
};

string getNextTokenWithoutErrorCheck(string& xmlWithoutFormat, int& offset, TokenType& type) {
    int size = xmlWithoutFormat.size();
    if (offset >= size) return "";
    int start = offset;
    switch (xmlWithoutFormat[start]) {
    case '<':
        while (xmlWithoutFormat[offset] != '>') {
            offset++;
        }
        if (xmlWithoutFormat[offset-1] == '/') {
            type = TokenType::Fulltag;
        } else if (xmlWithoutFormat[start+1] == '/') {
            type = TokenType::Posttag;
        } else {
            type = TokenType::Pretag;
        }
        offset++;
        break;
    default:
        while (xmlWithoutFormat[offset] != '<' && offset < size) {
            offset++;
        }
        type = TokenType::Content;
    }
    return xmlWithoutFormat.substr(start, offset - start);
}

void formatXML(string& xmlWithoutFormat) {
    int level = 0;
    int offset = 0;
    TokenType type;
    while (true) {
        string token = getNextTokenWithoutErrorCheck(xmlWithoutFormat, offset, type);
        if (token.size() == 0) break;
        switch (type) {
        case TokenType::Content:
        case TokenType::Fulltag: {
            for (int i = 0; i < level; i++) printf("\t");
            printf("%s\n", token.c_str());
            break;
        }
        case TokenType::Pretag: {
            for (int i = 0; i < level; i++) printf("\t");
            printf("%s\n", token.c_str());
            level++;
            break;
        }
        case TokenType::Posttag: {
            level--;
            for (int i = 0; i < level; i++) printf("\t");
            printf("%s\n", token.c_str());
            break;
        }
        }
    }
}

int main(int argc, char* argv[]) {
    string input = "<a>123<b>456<c/></b></a>";
    formatXML(input);
}

Other

Question_ID: Q003

Language: Python3

Time Cost: 卡在去找低于平方的算法，远远超过40分钟了

Time Complexity: O(n^2)

Solution

维护一个存储矩形的字典rect_dict和一个存储相交关系的集合edge_set；
每次先添加一个矩形，然后不断从相交集合中取出一对矩形进行合并，删除原来的两个矩形，添加合并后的矩形，直至集合为空。如果取出的一对矩形中至少有一个之前已经被合并过了，则本次合并操作取消。由于合并次数是O(n)的，每次合并后去遍历查询哪些相交也是O(n)的，整个合并的过程是O(n^2)。剩下一个问题就是从相交集合中取出矩形对的次数，可以考虑取出次数等于添加进去的次数，而每次合并添加的次数也是O(n)的，因此取出矩形对的次数也是O(n^2)的；
综上，总的时间复杂度是O(n^2) 的(这里把字典与集合的增删查改视为O(1))。

My Code

# coding: utf-8
class Solution(object):

    def __init__(self):
        pass

    def maximumRectangles(self, rect_list):

        rect_dict, edge_set, counter = {}, set(), 0

        def is_disjoint(u, v): # 判断矩形相离 O(1)
            return u[0] < v[1] or v[0] < u[1] \
                or u[3] < v[2] or v[3] < u[2]

        def minimum_covering(u, v): # 矩形合并 O(1)
            return [ max(u[0], v[0]), min(u[1], v[1]) \
                   , min(u[2], v[2]), max(u[3], v[3]) ]

        def add_rect(u): # 添加矩形 O(n)
            nonlocal rect_dict, edge_set, counter
            for k, v in rect_dict.items():
                if not is_disjoint(u, v):
                    edge_set.add((k, counter))
            rect_dict[counter] = u; counter += 1

        for u in rect_list:
            add_rect(u)
            while len(edge_set) > 0:
                (ka, kb) = edge_set.pop()
                if (ka not in rect_dict) or (kb not in rect_dict):
                    continue
                add_rect(minimum_covering(                       \
                            rect_dict.pop(ka), rect_dict.pop(kb)))
        return list(rect_dict.values())


if __name__ == '__main__':
    rect_list = [
        [1, 0, 0, 1],
        [1, 0, 4, 5],
        [3, 2, 2, 5],
        [2, 1, 5, 6]
    ]
    sol = Solution()
    ret = sol.maximumRectangles(rect_list)
    print(ret)

Other

Question_ID: Q001

Language: Python

Time Cost: 27-mins

Time Complexity: O(n)

Solution & Thoughts

No spaces in xml string, means no attributes will appear in tags.
Line-breaker should appear once and only once before every '<' and after every '>'.
Tags change indents when they appear.

My Code

#!/usr/bin/python
import sys
import re

def format_one_line_xml(xml: str) -> str:
    """One line xml has no space or line break.
    Return formatted xml with 4-space indents.
    """
    lines = []
    indent_count = 0
    xml = re.sub(r'(<[^>]*>)', r'\n\1\n', xml)

    for line in xml.split('\n'):
        if line:
            if line.startswith('</'):
                indent_count -= 1
            
            lines.append("{}{}".format(' ' * 4 * indent_count, line))
            
            if line.startswith('<') and not line.endswith('/>') and not line.startswith('</') \
                and not line.startswith('<!'):
                indent_count += 1

    return '\n'.join(lines)


def main():
    """Main function"""
    xml = sys.argv[1]
    print(format_one_line_xml(xml))


if __name__ == '__main__':
    main()

Other

Comments are welcome.

Question_ID: Q{002}

Language: Lua

Time Cost: 35-mins

Time Complexity: {}

Solution

判定读取到的输入是否合法
get_max查找最大的数
输出

My Code

print("Please input \n1:push x(number)\n2:pop \n3:get_max")
-- 保存数据的table
local stack = {}
local maxStack = {}
local getMax = function()
	local num =  maxStack[1]
	return num == nil and -1 or num
end

local setNumber = function(num)
	if #maxStack == 0 then 
		maxStack[1] = num 
	else
		for i=1,#maxStack do
			if maxStack[i] < num then
				table.insert(maxStack,i,num)
				return
			elseif i == #maxStack then
				table.insert(maxStack,i+1,num)
			end
		end
	end
end
-- 检查语法是否正确
local check = function(str)
	local s = string.sub(str,1,4)
	if s == "push" then
		local num = tonumber(string.sub(str,6))
		if num then
			print("None")
			stack[#stack+1] = num
			setNumber(num)
			return
		end
	else
		if #str == #"pop" and str == "pop" then
			if #stack > 0 then
				local num = stack[1]
				print(num)
				table.remove(stack,1)
				for i=1,#maxStack do
					if maxStack[i] == num then
						table.remove(maxStack,i)
						break
					end
				end
			else
				print("-1")
			end
			return
		else
			if #str == #"get_max" and str == "get_max" then
				if #stack > 0 then
					print(getMax())
				else
					print("-1")
				end
				return
			end
		end
	end
	print("Error input ,please input \n1:push x(number)\n2:pop \n3:get_max")
end

while(1) do
	local readStr = io.read()
	local p,n = check(readStr)
	if p then
		print(p)
	end
end

Other

Lua table like stack

Question_ID: Q003

Language: JAVA

Time Cost: 120-mins

Time Complexity: 菜鸡算不出来感觉应该是O(n^2)求大佬帮忙分析啊

Solution

按照底边从小到大排序，并用链表包装起来，选取链表第一个矩形作为【当前矩形】
2.从【当前矩形】开始顺着链表依次与【当前矩形】比较，一直比到某个矩形底边比【当前矩形】的顶高
3.若本轮循环有矩形被合并，则从链表中删掉，本次循环结束后，重复2
4.若本轮循环没有矩形被合并，选取下一个矩形作为【当前矩形】，重复2

My Code

public class Main {
    static int[][] input = {
            {1, 0, 0, 1},
            {1, 0, 4, 5},
            {3, 2, 2, 5},
            {2, 1, 5, 6}
    };

    public static void main(String[] a) {
        Rectangle[] r = new Rectangle[input.length];
        for (int i = 0; i < input.length; i++)
            r[i] = new Rectangle(input[i]);
        //按照底边从小到大排序
        Arrays.sort(r, Comparator.comparingInt(rect -> rect.d));
        for (int i = 1; i < r.length; i++)
            r[i - 1].append(r[i]);

        Rectangle that = r[0], next = that.next;
        boolean merged = false;//记录本轮循环有没有矩形被合并
        while (that != null) {
            if (next == null || that.u < next.d) {
                if (merged) merged = false;
                else that = that.next;
                if (that != null) next = that.next;
            } else {
                if (!((next.l < that.l && next.r < that.l) || (next.r > that.r && next.l > that.r))) {
                    that.merge(next);
                    next.remove();
                    merged = true;
                }
                next = next.next;
            }
        }
        that = r[0];
        do {
            System.out.print(that + ",\n");
        } while ((that = that.next) != null);
    }
}

class Rectangle {
    int u, d, l, r;
    Rectangle prev, next;

    public Rectangle(int[] a) {
        u = a[0];
        d = a[1];
        l = a[2];
        r = a[3];
    }

    public void merge(Rectangle rect) {
        u = Math.max(u, rect.u);
        l = Math.min(l, rect.l);
        r = Math.max(r, rect.r);
    }

    public void append(Rectangle r) {
        this.next = r;
        if (r != null)
            r.prev = this;
    }

    public void remove() {
        this.prev.append(this.next);
    }

    @Override
    public String toString() {
        return "[" + u + "," + d + "," + l + "," + r + ']';
    }
}

Other

Question_ID: Q001

Language: csharp

Time Cost: 0 min

Time Complexity: O(n)

Solution

find the index of < > \
judge the order of them
append formated line

My Code

using System;
using System.Text;

namespace XmlFormater
{
    class Program
    {
        static void Main(string[] args)
        {
            string intput = "<a>123<b>456<c/></b></a>";
            Console.WriteLine(Fmt(intput));
            Console.ReadKey();
        }

        static string Fmt(string raw)
        {
            StringBuilder fmt = new StringBuilder();
            int indent = 0;
            int offset = 0;

            while (offset != raw.Length)
            {
                // get special tag index
                var start = raw.IndexOf('<', offset);
                var mid = raw.IndexOf('/', offset);
                var end = raw.IndexOf('>', offset);

                // tag like  </..  means end, decrease indent
                if (start + 1 == mid)
                {
                    indent -= 1;
                }

                // tag like ...< means content before start tag, append the content
                if (offset < start)
                {
                    fmt.Append(' ', indent * 4);
                    fmt.Append($"{raw.Substring(offset, start - offset)}\r\n");
                }

                // append tag with indent
                fmt.Append(' ', indent * 4);
                fmt.Append($"{raw.Substring(start, end - start + 1)}\r\n");

                // tag start, increase indent
                if (mid > end)
                {
                    indent += 1;
                }

                //do offset
                offset = end + 1;
            }

            return fmt.ToString();
        }
    }
}

Other

There is no exception check.

Question_ID: Q001

Language: Python

Time Cost: 50-mins

Time Complexity: O(n)

Solution

write a lexer to split tag and content (tokens).
tokens formatting is easy.
my code is ugly like shit

My Code

from string import ascii_letters, digits

KEYWORDS = {'<', '>'}
TAG_ALLOW_CHAR = set(list(ascii_letters) + ['/'] + list(digits))
TAG_ALLOW_NAME_CHAR = set(list(ascii_letters) + list(digits))

class Tag(object):
    def __init__(self, lex):
        if '/' in lex:
            self.tt = -1
        else :
            self.tt = 1
        self.lex = lex
        self.name = ''.join(list(filter(lambda x: x in TAG_ALLOW_NAME_CHAR,  self.lex)))

    def __eq__(self, tag):
        return self.tt + tag.tt == 0 and self.name == tag.name

    def __repr__(self):
        return "<Tag:'{}'>".format(self.lex)

class Content(object):
    def __init__(self, lex):
        self.lex = lex

    def __eq__(self, obj):
        return False

    def __repr__(self):
        return "<Content:'{}'>".format(self.lex)

def lex_xml(xmlstring):
    tokens = []
    stash = []
    in_tag = False
    for c in xml_line:
        if in_tag:
            if c == '>':
                stash.append(c)
                tokens.append(Tag(''.join(stash)))
                stash = []
                in_tag = False
                continue
            elif c not in TAG_ALLOW_CHAR:
                in_tag = False
                if stash:
                    tokens.append(Content(''.join(stash)))
                    stash = []
                in_tag = False
            else:
                stash.append(c)            

        if not in_tag:
            if c == '<':
                if stash:
                    tokens.append(Content(''.join(stash)))
                    stash = []
                stash.append(c)
                in_tag = True
            else:
                stash.append(c)

    if stash:
        tokens.append(Content(''.join(stash)))

    return tokens


def format_tokens(tokens):
    intend = 0
    lex_stack = []
    content_stash = []
    ret = []
    for l in tokens:
        is_tag  = isinstance(l, Tag)
        if is_tag:
            if lex_stack and lex_stack[-1] == l:
                lex_stack.pop()
                intend -= 1
                ret.append("{}{}".format('\t'*intend, l.lex))
            elif l.tt == 1:
                lex_stack.append(l)
                ret.append("{}{}".format('\t'*intend, l.lex))
                intend += 1
            else:
                ret.append("{}{}".format('\t'*intend, l.lex))

            if content_stash:
                ret.append('{}{}'.format('\t'*intend,''.join([i.lex for i in content_stash])))
                content_stash = []
            
        else:
            content_stash.append(l)
    
    return '\n'.join(ret)

if  __name__ == "__main__":
    xml_line = """<a>123<b>456<c/>"1>2"</d>blabla1>2>3>4<5<6<7<8 and i like math</b></a>"""
    # xml_line = "<a<a>>"
    tokens = lex_xml(xml_line)
    print(tokens)
    print(format_tokens(tokens))

Other

I should learn to make a beautiful lexer...

Question_ID: Q001

Language: Lua 5.3.2

Time Cost: 90-mins

Time Complexity: {}

Solution

设置四个符号检测："<"、">"、"</"、"/>"
把所给的xml语句分离出三种数据：标签数据、标签内容数据、特殊标签("/>")数据并记录每个数据在第几层，根据标签数据记录start_kh来定的当前层级
组装三种输入答案

My Code

print("please input xml:")
local readStr = io.read()
-- local readStr = "<a>123<b>456</b></a>"
-- local readStr = "<a>123<b>456<c/></b></a>"
print("U put:"..readStr)

print("ok,let's go")


local start_kh1 = "<"
local start_kh2 = ">"
local start_kh3 = "</"
local start_kh4 = "/>"

--记录前面ok的格式：<a> 
local start_kh={}
--记录后面ok的格式：</a>
-- local end_kh = {}
--合法的格式：<a/> 直接跳过
--记录对应的层级关系数据
local level_date = {}
--记录start_kh4数据回车换行使用
local spe_data = {}

local spos = 0
local level = 0
local content = ""
local find = false
local kh3ok = false
-- for i=1,#readStr do
local i = 1
while(1) do
	if i > #readStr then break end
	local tmp = string.sub(readStr,i,i)
	-- print(tmp)
	if tmp == start_kh1 then
		if #content > 0 then
			level_date[level] = content
			content = ""
		end
		level = level+1
		kh3ok = false
		spos = i
	elseif tmp == "/" then
		if spos > 0 then
			-- 表示可能属于start_kh4 或者 start_kh3
			if spos + 1 == i then
				-- start_kh3
				kh3ok = true
			else
				local end_str = string.sub(readStr,i+1,i+1)
				if end_str and tmp..end_str == start_kh4 then
					--start_kh4 直接忽略哒 
					content = start_kh1 .. content
					content = content .. tmp ..end_str
					i = i + 1
					spos = 0
					spe_data[level] = content
					-- 否则再次遇到<就不对了
					level = level - 1
					content = ""
				else
					--没有任何匹配
					content = content .. tmp
				end
			end
		else
			-- igone
			content = content .. tmp
		end
	elseif tmp == start_kh2 then
		if #content > 0 then
			-- 是标签
			if spos > 0 and not kh3ok then
				start_kh[level] = content
				-- 这个时候需要查找前面是否有这个标签
				find = false
				for k,v in ipairs(start_kh) do
					if v == content then
						find = true
						break
					end
				end
				print(find)
				if not find then
					print("error >>>>>>>> "..content)
					return
				end
				content = ""
			else
				-- content = content..tmp
				content = ""
			end
			-- content = ""
		else
			content = content..tmp
		end
	elseif tmp then
		content = content..tmp
	end
	i = i + 1
end

local tab = "    "
local print_str1 = ""
local print_str2 = ""
for i=1,#start_kh do
	local bq1 = start_kh1..start_kh[i]..start_kh2
	local bq2 = start_kh3..start_kh[i]..start_kh2
	for j=2,i do
		bq1 = tab..bq1
		bq2 = tab..bq2
	end
	

	print_str1 = print_str1..bq1.."\n"
	bq1 = ""
	for j=1,i do
		bq1 = tab..bq1
	end
	print_str1 = print_str1..bq1..level_date[i].."\n"

	if spe_data[i+1] then
		print_str1 = print_str1 .. bq1 ..spe_data[i+1].."\n"
	end

	if #print_str2 > 0 then
		print_str2 = bq2.."\n"..print_str2
	else
		print_str2 = bq2
	end

end

print("result:")
print(print_str1..print_str2)

Other

lua的字符串数组直接用readStr[i]取出来是nil，刚开始怎么都不对后面查阅了一番。
写的比较烂，大家勿喷哈。

Question_ID: Q003

Language: python

Time Cost: 38-mins

Time Complexity: O(n^2)

Solution

My Code

#!/usr/bin/python


def is_common_point_shared(rectangle1, rectangle2):
    """Return if two rectangles share common points"""
    up1, down1, left1, right1 = rectangle1
    up2, down2, left2, right2 = rectangle2

    return not (up1 < down2 or up2 < down1 or left1 > right2 or left2 > right1)


def replace_rectangle(rectangle1, rectangle2):
    """Return a smallest rectangle, which covers the original two"""
    up1, down1, left1, right1 = rectangle1
    up2, down2, left2, right2 = rectangle2

    return [max([up1, up2]), min([down1, down2]),
            min([left1, left2]), max([right1, right2])]


def maximum_rectangle(rectangles):
    """Return a list of 'maximum rectangles'"""
    independent_rectangles = set()

    for next_rectangle in rectangles:
        independ = False

        while not independ:
            independ = True

            for rec in independent_rectangles:
                if is_common_point_shared(next_rectangle, rec):
                    next_rectangle = replace_rectangle(next_rectangle, rec)
                    independent_rectangles.discard(rec)

                    independ = False

                    break

        independent_rectangles.add(tuple(next_rectangle))

    return list(map(list, independent_rectangles))

Unit Tests

import unittest

from Q003 import maximum_rectangle


class MaximumRectangeTest(unittest.TestCase):
    """Tests for maximum_rectangle"""

    def assertEqual(self, first, second, msg=None):
        """Check if 'equals'"""
        if not set(map(tuple, first)) == set(map(tuple, second)):
            raise self.failureException(msg)

    def test_case1(self):
        """case1"""
        args = [[1, 0, 0, 1],
                [1, 0, 4, 5],
                [3, 2, 2, 5],
                [2, 1, 5, 6]]
        expected = [[1, 0, 0, 1], [3, 0, 2, 6]]
        actual = maximum_rectangle(args)
        msg = "Expected {}, but returned {}".format(expected, actual)
        self.assertEqual(expected, actual, msg)

    def test_case2(self):
        """case2"""
        args = [[5, -5, 3, 8],
                [2, -1, 4, 5]]
        expected = [[5, -5, 3, 8]]
        actual = maximum_rectangle(args)
        msg = "Expected {}, but returned {}".format(expected, actual)
        self.assertEqual(expected, actual, msg)

    def test_case3(self):
        """case3"""
        args = [[7, 6, 2, 7],
                [5, -1, 6, 8],
                [2, -3, -1, 4],
                [10, 4, -3, 1]]
        expected = [[7, 6, 2, 7], [5, -1, 6, 8],
                    [2, -3, -1, 4], [10, 4, -3, 1]]
        actual = maximum_rectangle(args)
        msg = "Expected {}, but returned {}".format(expected, actual)
        self.assertEqual(expected, actual, msg)

    def test_case4(self):
        """case4"""
        args = [[7, 6, 2, 7],
                [20, 1, 5, 6],
                [15, 4, 8, 15],
                [12, 10, 10, 20]]
        expected = [[15, 4, 8, 20], [20, 1, 2, 7]]
        actual = maximum_rectangle(args)
        msg = "Expected {}, but returned {}".format(expected, actual)
        self.assertEqual(expected, actual, msg)

    def test_case5(self):
        """case5"""
        args = [[1, 0, 2, 3],
                [0, -3, -1, 2]]
        expected = [[1, -3, -1, 3]]
        actual = maximum_rectangle(args)
        msg = "Expected {}, but returned {}".format(expected, actual)
        self.assertEqual(expected, actual, msg)

    def test_case6(self):
        """case6"""
        args = [[6, 3, -5, -2],
                [5, -3, 1, 6],
                [2, -1, -4, 2]]
        expected = [[6, -3, -5, 6]]
        actual = maximum_rectangle(args)
        msg = "Expected {}, but returned {}".format(expected, actual)
        self.assertEqual(expected, actual, msg)


if __name__ == '__main__':
    unittest.main()

Other

Question_ID: Q003

Language: C++

Time Cost: 60+mins

Time Complexity: O(n^2)

Solution

两两检查合并有交点的矩形，放至容器尾部，继续检查。这样就可以直接跳过已检查的矩形。

My Code

#include <iostream>
#include <vector>
using namespace std;
class Rectangle {
public:
    Rectangle(int u,int d,int l,int r);
    bool hasOverlap(Rectangle& aRectangle);
    Rectangle combine(Rectangle& aRectangle);
    void printInfo();
private:
    int u, d, l, r;
};

Rectangle::Rectangle(int u,int d,int l,int r) {
    this->u = u;
    this->d = d;
    this->l = l;
    this->r = r;
}

bool Rectangle::hasOverlap(Rectangle& aRectangle) {
    return u >= aRectangle.d && d <= aRectangle.u && l <= aRectangle.r && r >= aRectangle.l;
}

Rectangle Rectangle::combine(Rectangle& aRectangle) {
    return Rectangle(max(u,aRectangle.u),min(d,aRectangle.d),min(l,aRectangle.l),max(r,aRectangle.r));
}

void Rectangle::printInfo() {
    printf("%d,%d,%d,%d\n",u,d,l,r);
}

vector<Rectangle> merge(vector<Rectangle>& rectangles)
{
    vector<Rectangle> result = vector<Rectangle>(rectangles);
    for (int i = 1; i < result.size(); i++) {
        for (int j = 0; j < i; j++) {
            Rectangle r = result[i];
            if (r.hasOverlap(result[j])) {
                Rectangle combined = r.combine(result[j]);
                result.erase(result.begin() + i);
                result.erase(result.begin() + j);
                result.push_back(combined);
                i -= 2;
                break;
            }
        }
    }
    return result;
}

int main(int argc, const char * argv[]) {
    vector<Rectangle> input, output;
    int u, d, l, r;
    while (scanf("%d,%d,%d,%d",&u,&d,&l,&r)) {
        input.push_back(Rectangle(u,d,l,r));
    }
    output = merge(input);
    for (int i = 0; i < output.size(); ++i) {
        output[i].printInfo();
    }
    return 0;
}

Other

自己写的正向循环是O(n^3)，学习D师的方法，把循环反过来就能直接跳过已检查过的数据。

Question_ID: Q004

Language: c++

Time Cost: 30-mins

Time Complexity: O(n)

Solution

三个元素一组，排序成“小大小”
第一组最后一个和之后两个再组成三个数的组，重复步骤１
最后剩一个数，构不成三个数的组，就排成“小大”

My Code

#define CATCH_CONFIG_MAIN
#include <iostream>
#include <vector>
#include <algorithm>
#include "catch.hpp"

using namespace std;

void fluctuation(vector<int>& nums) {
    int size = nums.size();
    int flag = true;
    for (int i = 0; i < size-1; i++) {
        if ((flag && nums[i] > nums[i+1]) ||
            (!flag && nums[i] < nums[i+1])) {
            swap(nums[i], nums[i+1]);
        }
        flag = !flag;
    }
}

bool result_check(vector<int>& nums) {
    int size = nums.size();
    bool flag = true;
    for (int i = 0; i < size-1; i++) {
        if (flag) {
            if (nums[i] <= nums[i+1]) {
                flag = !flag;
            } else {
                return false;
            }
        } else {
            if (nums[i] >= nums[i+1]) {
                flag = !flag;
            } else {
                return false;
            }
        }
    }
    return true;
}

TEST_CASE("fluctuation", "fluctuation") {
    WHEN("empty") {
        vector<int> nums = {};
        fluctuation(nums);
        REQUIRE(result_check(nums));
    }
    WHEN("1 element") {
        vector<int> nums = {1};
        fluctuation(nums);
        REQUIRE(result_check(nums));
    }
    WHEN("2 elements") {
        vector<int> nums = {1, 2};
        fluctuation(nums);
        REQUIRE(result_check(nums));
    }
    WHEN("3 elements") {
        vector<int> nums = {1, 2, 3};
        fluctuation(nums);
        REQUIRE(result_check(nums));
    }
    WHEN("4 elements") {
        vector<int> nums = {1, 2, 3, 4};
        fluctuation(nums);
        REQUIRE(result_check(nums));
    }
    WHEN("5 elements") {
        vector<int> nums = {1, 2, 3, 4, 5};
        fluctuation(nums);
        REQUIRE(result_check(nums));
    }
    WHEN("sample case") {
        vector<int> nums = {5, 2, 4, 5, 6, 7};
        fluctuation(nums);
        REQUIRE(result_check(nums));
    }
}

Other

Question_ID: Q001

Language: Python

Time Cost: 40-mins

Time Complexity: O(n)

Solution

主要思路是查找 <> 标签对内容划分层级，按格式输出

查找 <> 标签，输出标签前的内容，没找到直接输出
如果是 <a/> 直接输出标签
如果是 <a> 则输出标签，之后层级加 1
如果是 </a> 则层级减 1，输出标签
如果没到结尾，剩余字符串再从 1 进行

My Code

s = raw_input()
level = 0
i = 0
while i < len(s):
	l = s.find('<',i)
	r = s.find('>',l+1)
	if l >= 0 and r >= 0:
		if l != i:
			print(' '*4*level+s[i:l])
		t = s[l:r+1]
		if t[-2] == '/':
			print(' '*4*level+t)
		elif t[1] == '/':
			level -= 1
			print(' '*4*level+t)
		else :
			print(' '*4*level+t)
			level += 1
		i = r + 1
	else :
		print(' '*4*level+s[i:])
		break

Other

请多多指教

Question_ID: Q002

Language: python

Time Cost: 40-mins

Time Complexity: O(nlogn)

Solution

build a decrease queue to store max elements.
every time new element enter, change the decrease queue.
the head of the queue is the max element.

My Code

def lower_bound(l, goal):
    s,e = 0, len(l) - 1
    while s <= e:
        mid = (s+e) // 2
        if l[mid] >= goal:
            s = mid + 1
        else:
            e = mid - 1
    return s
    
class StackQueue(object):
    def __init__(self):
        self.queue = []
        self.order_queue = []

    def push(self, value):
        self.queue.append(value)
        if self.order_queue:
            if self.order_queue[-1] > value:
                self.order_queue.append(value)
            else:
                pos = lower_bound(self.order_queue, value)
                self.order_queue = self.order_queue[:pos] + [value]
        else:
            self.order_queue = [value]

    def pop(self):
        if not self.queue:
            return -1
        v = self.queue.pop(0)
        if v == self.order_queue[0]:
            self.order_queue.pop(0)
        return v

    def get_max(self):
        if self.order_queue:
            return self.order_queue[0]
        return -1
    
    def __repr__(self):
        return "{} {}".format(self.queue, self.order_queue)

Other

I think there is a linear solution?

Question_ID: Q005

Language: c++

Time Cost: 40-mins + 40mins

Time Complexity: O(n)

Solution

先对整个序列做中位数划分
分别对左右区域做中位数划分
将右侧区域往左侧区域插入

My Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <random>

using std::cout;
using std::endl;
using std::vector;

class Fluctuation
{
    void mid_element(vector<int>::iterator beginIter, vector<int>::iterator endIter)
    {
        if (endIter < beginIter)
            return;
        auto midIter = beginIter + (endIter-beginIter)/2;
        std::nth_element(beginIter, midIter, endIter);
    }
public:
    void fluctuation(vector<int> &nums)
    {
        auto size = nums.size();
        if (size < 2)
            return;
        auto midIter = nums.begin() + (nums.end()-nums.begin())/2;
        mid_element(nums.begin(), nums.end());
        mid_element(nums.begin(), midIter);
        mid_element(midIter+1, nums.end());

        auto midIndex = (nums.size()-1)/2;
        
        // 方法1： 初始方案，移动次数很多
//        for (auto i = midIndex+1; i < size; ++i) {
//            auto target = (i - midIndex) * 2 - 1;
//            for (auto j = i; j > target; --j) {
//                std::swap(nums[j], nums[j-1]);
//            }
//        }
        // 方法2： 循环交换元素方案只需要交换 n-1 次
        size_t index = 1;
        int num = nums[index];
        while (index < size) {
            size_t target = (index <= midIndex) ? 2*index : (index-midIndex)*2-1;
            int temp = nums[target];
            nums[target] = num;
            index = target;
            num = temp;
            if (index == 1)
                break;
        }
    }

    bool test(const vector<int> &nums)
    {
        auto size = nums.size();
        if (size < 2) return true;
        for (auto i = 0; i < size-1; ++i) {
            if (nums[i] == nums[i+1]) return false;
            if ((bool)(i&1) ^ (nums[i] > nums[i+1])) return false;
        }
        return true;
    }
};

int main() {
    Fluctuation solution;

    vector< vector<int> > testcases = {
            {},
            {1},
            {1, 2},
            {1, 1, 2},
            {1, 1, 2, 2},
            {1, 1, 2, 2, 3},
            {1, 1, 1, 2, 2, 2},
    };
    auto seed = std::chrono::system_clock::now().time_since_epoch().count();
    for (auto& testcase : testcases) {
        if (testcase.size() >= 2) {
            shuffle (testcase.begin(), testcase.end(), std::default_random_engine(seed));
        }
        for_each(testcase.begin(), testcase.end(), [](int x) { cout << x << " ";});
        cout << endl;

        solution.fluctuation(testcase);
        if (!solution.test(testcase))
            cout << "error" << endl;

        for_each(testcase.begin(), testcase.end(), [](int x) { cout << x << " ";});
        cout << endl;
        cout << "-------------" << endl;
    }

    return 0;
}

Other

算法想了40分钟，实现测试40分钟.这个算法用脑子想觉得逻辑上是可以的，测试用例也都没问题，严格数学上证明，我不会，囧

Question_ID: Q004

Language: c++

Time Cost: 40-mins

Time Complexity: O(n)

Solution

My Code

void reorder(vector<int>& a) {
  for (int i = 1; i < a.size(); i++) {
    if ((i & 1) ^ (a[i] >= a[i - 1])) {
      swap(a[i], a[i - 1]);
    }
  }
}

Other

Question_ID: Q001

Language: Shell

Time Cost: 60-mins

Time Complexity: O(n)

Solution

先做个截断把 content 和 tag 分开
判断 tag 类型在行首加上缩进

My Code

echo '<a>123<b>456<c/></b></a>' | \                                                                                                              
awk -F '>' '{for(i=1;i<NF;++i)print $i">"}' | \                                                                                                  
sed 's/\(\w\+\)</\1\n</' | \                                                                                                                     
awk 'BEGIN {level=0}                                                                                                                             
     {                                                                                                                                           
        if(substr($0,1,2)=="</"){level--};                                                                                                       
        for(i=0;i<level;++i) printf "\t";                                                                                                        
        print $0;                                                                                                                                
        if(substr($0,1,1)=="<"&&substr($0,2,1)!="/"&&index($0,"/")!=length($0)-1){level++}                                                       
     }'

Other

环境 Ubuntu 16.04

Question_ID: Q001

Language: Haskell

Time Cost: 40-mins

Time Complexity: O(n)

Solution

从前往后扫描一遍，遇到 < 就匹配tag，start tag 缩进加4，end tag 缩进减4，其余(empty-element tag 和 content)缩进保持。

My Code

main = do
    s    <-  getLine
    putStr $ format s

format s = helper s ""

helper          "" i = ""
helper ('<':'/':t) i = etag t i "/<"
helper     ('<':t) i = ztag t i  "<"
helper          t  i = ctag t i   ""

etag     ('>':t) i c = j ++ reverse c ++  ">\n" ++ helper t j
    where j = drop 4 i
etag       (h:t) i c = etag t i (h:c)

ztag ('/':'>':t) i c = i ++ reverse c ++ "/>\n" ++ helper t i
ztag     ('>':t) i c = i ++ reverse c ++  ">\n" ++ helper t j
    where j = "    " ++ i
ztag       (h:t) i c = ztag t i (h:c)

ctag   t@('<':_) i c = i ++ reverse c ++   "\n" ++ helper t i
ctag       (h:t) i c = ctag t i (h:c)

Other

感觉写这类题用支持模式匹配的语言比较爽。

Question_ID: Q003

Language: c++

Time Cost: 30-mins

Time Complexity: O(n^2)

Solution

和正常人工思路一致，时间复杂度很高，有待优化。想到其他方法再后续补充。

互相之间判断相交
相交，则合并，删除相交的矩形，加入合并的矩形，然后重复1
没有相交的时候返回

My Code

#include <vector>
#include <iostream>

using namespace std;

struct Rect {
    int u; // ymax
    int d; // ymin
    int l; // xmin
    int r; // xmax
};

void printRect(Rect rect) {
    printf("[%d, %d, %d, %d]\n", rect.u, rect.d, rect.l, rect.r);
}

void printRectangles(const vector<Rect>& rects) {
    printf("[\n");
    for (auto rect : rects) {
        printf("\t[%d, %d, %d, %d]\n", rect.u, rect.d, rect.l, rect.r);
    }
    printf("]\n");
}

bool rectIntersection(Rect rec1, Rect rec2) {
    // make rec1 below rec2
    if (rec2.d < rec1.d) swap(rec1, rec2);
    return (rec1.u >= rec2.d) && (rec1.r >= rec2.l) && (rec1.l <= rec2.r);
}

Rect rectMerge(Rect rec1, Rect rec2) {
    return {
        max(rec1.u, rec2.u),
        min(rec1.d, rec2.d),
        min(rec1.l, rec2.l),
        max(rec1.r, rec2.r)
    };
}

void maximumRectangles(vector<Rect>& input) {
    int size = input.size();
    for (int i = 0; i < size; i++) {
        for (int j = i+1; j < size; j++) {
            if (rectIntersection(input[i], input[j])) {
                Rect newRec = rectMerge(input[i], input[j]);
                input.erase(input.begin() + j);
                input.erase(input.begin() + i);
                input.push_back(newRec);
                return maximumRectangles(input);
            }
        }
    }
}

int main() {
    vector<Rect> input = {
        {1, 0, 0, 1},
        {1, 0, 4, 5},
        {3, 2, 2, 5},
        {2, 1, 5, 6}
    };
    printf("Input:\n");
    printRectangles(input);
    
    printf("output:\n");
    maximumRectangles(input);
    printRectangles(input);
}

Other

Question_ID: Q002

Language: Python2.7

Time Cost: 10 + 30-mins

Time Complexity: O(1)

Solution

实现一个维护最大值的栈结构
用两个栈模拟一个队列

My Code

# coding: utf-8


class MyStack(object):
    def __init__(self):
        self.stack = []
        self.max_stack = []

    def push(self, x):
        self.stack.append(x)
        if self.max_stack:
            self.max_stack.append(max(x, self.max_stack[-1]))
        else:
            self.max_stack.append(x)

    def pop(self):
        if not self.stack:
            return -1
        self.max_stack.pop()
        return self.stack.pop()

    def get_max(self):
        return self.max_stack[-1] if self.max_stack else None

    def is_empty(self):
        return self.stack == []


class MyQueue(object):

    def __init__(self):
        self.in_stack = MyStack()
        self.out_stack = MyStack()

    def push(self, x):
        self.in_stack.push(x)

    def pop(self):
        if self.out_stack.is_empty():
            while not self.in_stack.is_empty():
                self.out_stack.push(self.in_stack.pop())
        return self.out_stack.pop()

    def get_max(self):
        return max(self.out_stack.get_max(),
                   self.in_stack.get_max()) or -1

Other

Question_ID: Q003

Language: c++

Time Cost: 40-mins

Time Complexity: O(n^2)

Solution

Merge rectangles until no two rectangles share common points.

My Code

#include <bits/stdc++.h>

using namespace std;

// tuple<u, d, l, r>
vector<tuple<int, int, int, int>> solve(vector<tuple<int, int, int, int>> a) {
  list<tuple<int, int, int, int>> li = {a.begin(), a.end()};
  for (auto it1 = li.begin(); it1 != li.end();) {
    bool ok = false;
    for (auto it2 = li.begin(); it2 != it1; it2++) {
      auto [u1, d1, l1, r1] = *it1;
      auto [u2, d2, l2, r2] = *it2;
      if (min(u1, u2) >= max(d1, d2) && min(r1, r2) >= max(l1, l2)) {  // check whether two rectangles intersect
        li.emplace_back(max(u1, u2), min(d1, d2), min(l1, l2), max(r1, r2)); //merge two rectangles, then append to list
        li.erase(it2);
        it1 = li.erase(it1);
        ok = true;
        break;
      }
    }
    if (!ok) it1++;
  }
  return {li.begin(), li.end()};
}

int main(int argc, char *argv[]) {
  int n;
  cin >> n;
  vector<tuple<int, int, int, int>> a;
  for (int i = 0; i < n; ++i) {
    int u, d, l, r;
    cin >> u >> d >> l >> r;
    a.emplace_back(u, d, l, r);
  }
  auto ans = solve(a);
  sort(ans.begin(), ans.end());
  for (auto x : ans) {
    auto [u, d, l, r] = x;
    cout << u << " " << d << " " << l << " " << r << endl;
  }
  return 0;
}

Other

g++ x.cc -std=c++17

Question_ID: Q002

Language: c++

Time Cost: 60-mins

Time Complexity: O(1)

Solution

My Code

#include <list>
#include <iostream>

using namespace std;

class MyQueue {
private:
    list<int> maxList; // 队头保存最大值，队尾保存除比比前面元素外的最大值
    list<int> nums;    // 使用链表存储队列
public:
    void push(int x);
    int pop();
    int getMax();
};

void MyQueue::push(int x) {
    nums.push_back(x);
    // 丢弃之前的比当前元素小的值
    while (!maxList.empty() && maxList.back() < x) {
        maxList.pop_back();
    }
    maxList.push_back(x);
}

int MyQueue::pop() {
    if (nums.empty()) throw exception();
    int x = nums.front();
    nums.pop_front();
    if (x == maxList.front()) {
        maxList.pop_front();
    }
    return x;
}

int MyQueue::getMax() {
    if (!nums.empty()) {
        return maxList.front();
    } else {
        throw exception();
    }
}

Other

照抄m75n的算法

Question_ID: Q004

Language: C++

Time Cost: 40-mins

Time Complexity: O(n)

Solution

类似于快排的划分思路，先找到中位数(这个我直接调用的STL库函数，理论上寻找中位数是可以达到最坏为O(n)的，STL的实现最坏不一定保证但平均应该为O(n))，接着就是用这个中位数进行划分。
和快排不一样的地方是，快排的划分是小于中位数的划分到数组前半段，大于中位数的划分到数组后半段。而这道题的话，则是小于中位数的划分到数组偶数编号，大于中位数的划分到数组奇数编号。为了达到这个目标最简单的方式就是用宏做了个下标映射。

为什么用了40分钟，主要是下标映射的时候卡了好久(我想把前一半下标映射到偶数上，一直没成功)，一时半会儿没转过弯来。

My Code

#include <algorithm>
#include <iostream>


void fluctuation(std::vector<int>& X) {

    int n = X.size();

    #define Y(i) X[(2*(i) + 1) % (n | 1)]

    nth_element(X.begin(), X.begin()+n/2, X.end());

    int pivot = X[n/2];

    int lo = 0, hi = n - 1;
    while (lo < hi) {
        if (Y(lo) >= pivot) {
            ++lo;
        } else
        if (pivot >= Y(hi)) {
            --hi;
        } else {
            std::swap(Y(lo), Y(hi));
        }
    }
}

int main() {

    std::vector<int> X{5, 2, 4, 5, 6, 7};

    fluctuation(X);

    for (int x : X) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Other

Q003_m75n_solution

Question_ID: Q003

Language: C++

Time Cost: 20-mins

Time Complexity: O(n)

Solution

u, d, l, r 拆分为 [d, u] 和 [l, r] 两个线段合并问题，见 Leetcode 56. Merge Intervals
sort 按照 d 和 l 的值升序

My Code

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

struct Rectangle{
    int u;
    int d;
    int l;
    int r;
    Rectangle() : u(0), d(0), l(0), r(0) {}
    Rectangle(int _u, int _d, int _l, int _r) : u(_u), d(_d), l(_l), r(_r) {}
};

bool cmp(const Rectangle& a, const Rectangle& b)
{
    return a.d < b.d ? : a.d == b.d ? a.l < b.l : false;
}

vector<Rectangle> merge(vector<Rectangle>& rectangles)
{
    if (rectangles.empty()) return vector<Rectangle>{};

    vector<Rectangle> res;
    sort(rectangles.begin(), rectangles.end(), cmp);

    res.push_back(rectangles[0]);
    for (int i = 1; i < rectangles.size(); ++i) {
        if (res.back().u < rectangles[i].d || res.back().r < rectangles[i].l || rectangles[i].r < res.back().l) {
            res.push_back(rectangles[i]);
        } else {
            res.back().u = max(res.back().u, rectangles[i].u);
            res.back().l = min(res.back().l, rectangles[i].l);
            res.back().r = max(res.back().r, rectangles[i].r);
        }
    }

    return res;
}

int main(void)
{
    vector<Rectangle> input, output;
    int u, d, l, r;

    while (cin >> u >> d >> l >> r) {
        Rectangle rec(u, d, l, r);
        input.push_back(rec);
    }

    output = merge(input);

    for (int i = 0; i < output.size(); ++i)
        cout << output[i].u << " "
             << output[i].d << " "
             << output[i].l << " "
             << output[i].r << endl;

    return 0;
}

Other

gcc --std=c++11

Q005_dploop_solution

Question_ID: Q005

Language: C++

Time Cost: 40-mins

Time Complexity: O(n)

Solution

和Q004一样的下标映射思路，刚好把相邻的两个数间隔到数组大小的一半距离。不过由于这里的要求是严格不等，所以单纯的两路划分不行，改成了三路划分。至于三路划分为什么可以，我想到了一种绝妙的证明方法，不过这里的空白太小写不下。

My Code

#include <algorithm>
#include <iostream>
#include <vector>


void fluctuation(std::vector<int>& X) {

    int n = X.size();

    #define Y(i) X[(2*(i) + 1) % (n | 1)]

    nth_element(X.begin(), X.begin()+n/2, X.end());

    int pivot = X[n/2];

    int lo = 0, hi = n - 1,  mid = 0;
    while (mid <= hi) {
        if (Y(mid) > pivot) {
            std::swap(Y(lo++), Y(mid++));
        } else
        if (Y(mid) < pivot) {
            std::swap(Y(mid), Y(hi--));
        } else {
            mid++;
        }
    }
}


int main() {

    std::vector<int> X{1, 1, 1, 1, 2, 2, 2};

    fluctuation(X);

    for (int x : X) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

Other

Q001_让奶牛飞_solution

Question_ID: Q001_让奶牛飞_solution

Language: java

Time Cost: 90-mins

Time Complexity: O(n)

Solution

1.遍历字符串，每次打印一行
2.tabNum记录当前行应该有多少个tab，遇到开始标签tabNum+1，遇到结束标签tabNum-1

My Code

public class Main {
    public static void main(String[] a) {
        String s = "aa<a>123<b><c/>456<c/></b></a>aa";
        for (int i = 0, length = s.length(), tabNum = 0; i < length; ) {
            int end;
            if (s.charAt(i) == '<') {
                end = indexOf(s, ">", i, length);
                if (s.charAt(i + 1) == '/')
                    print(s.substring(i, ++end), --tabNum);
                else if (s.charAt(end - 1) == '/')
                    print(s.substring(i, ++end), tabNum);
                else print(s.substring(i, ++end), tabNum++);
            } else {
                end = indexOf(s, "<", i, length);
                print(s.substring(i, end), tabNum);
            }
            i = end;
        }
    }

    static void print(String s, int tabNum) {
        StringBuilder sb = new StringBuilder("\r\n");
        while (tabNum-- > 0)
            sb.append("    ");
        sb.append(s);
        System.out.print(sb);
    }

    static int indexOf(String s, String sub, int from, int ifNotFound) {
        int i = s.indexOf(sub, from);
        return i < 0 ? ifNotFound : i;
    }
}

Q001_Leonhardt_solution

Question_ID: Q001

Language: Java

Time Cost:

Time Complexity:

Solution

找出所有节点
根据<,</,/>的特征打印结果

My Code

public class Xml {
    public static void main(String[] args) {
        String xmlStr = "<a>123<b>456<c/></b></a>";
        String regEx = "(<\\w>|<\\/\\w>|(?<=>)\\w+(?=<)|<\\w\\/>)";
        Pattern pattern = Pattern.compile(regEx);
        Matcher m = pattern.matcher(xmlStr);
        String tab = "";
        while (m.find()){
            String temp = m.group();
            if (temp.contains("</")) {
                tab = tab.replaceFirst("\t", "");
                System.out.println(tab+temp);
            }else if (temp.contains("<") && !temp.contains("/")){
                System.out.println(tab+temp);
                tab += "\t";
            }else {
                System.out.println(tab+temp);
            }
        }
    }
}

Q002_rokic_solution

Question_ID: Q002

Language: python3

Time Cost: 13-mins

Time Complexity: O(n)???

Solution

Easy one, but need code reviews to improve coding style.

My Code

#!/usr/bin/python
from collections import deque

class MaxQueue(object):
    """MaxQueue"""
    def __init__(self, init=None):
        self._queue = deque()
        self._max_queue = deque()

        if init:
            for element in init:
                self.push(element)

    def push(self, element):
        """Insert an element into the queue"""
        while self._max_queue and self._max_queue[-1] < element:
            self._max_queue.pop()

        self._max_queue.append(element)
        self._queue.append(element)

    def pop(self):
        """Pop out one element from queue"""
        try:
            element = self._queue.popleft()
        except IndexError:
            raise Exception("pop from empty maxqueue")

        if element == self._max_queue[0]:
            self._max_queue.popleft()

        return element

    def get_max(self):
        """Get max element of the queue"""
        if self._max_queue:
            return self._max_queue[0]

        return None

Other

How can i improve my solution? Any suggestions?

Q001_Goat_solution

Question_ID: Q001

Language: Python2.7

Time Cost: 10-mins

Time Complexity: O(n)

Solution

正则匹配标签
对于非结束标签，深度加1，结束标签则深度减1
递归扫描整个字符串

My Code

# coding: utf-8
import re
import sys


def parse(xml_str, depth=0, pattern=None):

    if not pattern:
        pattern = re.compile('(<\/\w>|<\w>|<\w\/>)')
    res = pattern.search(xml_str)

    if not res:
        return
    start = res.start()
    end = res.end()
    tag = res.groups()[0]
    if start != 0:
        sys.stdout.write(' ' * 4 * depth + xml_str[:start] + '\n')

    sys.stdout.write(' ' * 4 * depth + tag + '\n')

    if '/' not in tag:
        depth += 1
    else:
        depth -= 1
    sub_str = xml_str[end:]

    parse(sub_str, depth=depth, pattern=pattern)


if __name__ == '__main__':
    parse('<a>123<b>456<c/></b></a>')

Other

Q002_super2bai_solution

Question_ID: Q002

Language: Java

Time Cost: 30mins

Time Complexity: O(n)

Solution

First...read input string
Then...get command
And...operate

My Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Q002Max {
    static int head = -1;
    static int end = -1;
    static int max=-1;
    static int[] queue = new int[4];
    static final String numRegex = "[0-9]*";

    public static void push(int i) {
        if (head == -1) {
            head++;
        }
        if(max<i){
            max=i;
        }
        if (end == queue.length - 1) {
            int[] newQueue = new int[queue.length * 2];
            System.arraycopy(queue, 0, newQueue, 0, queue.length);
            queue = newQueue;
        }
        end++;
        queue[end] = i;
        System.out.println("None");
    }


    public static void pop() {
        if (end == -1 || queue[end] == 0) {
            System.out.println(-1);
            return;
        }
        int popValue=queue[head];
        System.out.println(popValue);
        queue[head] = 0;
        if(max==popValue){
            max = queue[0];
            for (int i = 1; i < queue.length; i++) {
                if (max < queue[i]) {
                    max = queue[i];
                }
            }
        }

        if (head != end) {
            head++;
        } else {
            head = -1;
            end = -1;
            max=-1;
        }
    }

    public static void getMax() {
        if (end == -1 || queue[end] == 0) {
            System.out.println(-1);
            return;
        }

        System.out.println(max);
    }

    private static void getCommandAndValue(String inputString) {
        String[] s = inputString.split(" ");
        String command = s[0].toLowerCase();
        if (s.length != 1 && s.length != 2) {
            System.out.println("invalid input");
        }
        if ("get_max".equals(command) || "getmax".equals(command)) {
            getMax();
        } else if ("quit".equals(command) || "exit".equals(command)) {
            System.exit(0);
        } else if ("pop".equals(command)) {
            pop();
        } else {
            if (s.length != 2 || !isNumeric(s[1]) || !"push".equals(command)) {
                System.out.println("invalid input");
                return;
            }
            int value = Integer.valueOf(s[1]);
            push(value);
        }
        System.out.println("head:" + head);
        System.out.println("end:" + end);
    }

    public static boolean isNumeric(String str) {
        Pattern pattern = Pattern.compile(numRegex);
        Matcher isNum = pattern.matcher(str);
        if (!isNum.matches()) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) throws IOException {
        while (true) {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            try {
                String read = br.readLine();
                getCommandAndValue(read.trim());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
}

Q002_dploop_solution

Question_ID: Q002

Language: C++

Time Cost: 25-mins

Time Complexity: O(1)

Solution

首先是构造一个MaxStack(维护最大值的栈)，再用两个栈模拟一个队列。

My Code

#include <algorithm>
#include <stack>
#include <string>
#include <iostream>


class MaxStack {
public:
     MaxStack() {}
    ~MaxStack() {}
    bool empty() {
        return m_stk.empty();
    }
    void push(int x) {
        m_stk.push(x); int y = x;
        if (!m_max.empty()) {
            y = m_max.top();
        }
        m_max.push(std::max(x, y));
    }
    int pop() {
        int z = -1;
        if (!m_stk.empty()) {
            z = m_stk.top();
            m_stk.pop();
            m_max.pop();
        }
        return z;
    }
    int get_max() {
        int z = -1;
        if (!m_max.empty()) {
            z = m_max.top();
        }
        return z;
    }
private:
    std::stack<int> m_stk;
    std::stack<int> m_max;
};


class MaxQueue {
public:
     MaxQueue() {}
    ~MaxQueue() {}
    bool empty() {
        return m_in.empty() && m_out.empty();
    }
    void push(int x) {
        m_in.push(x);
    }
    int pop() {
        if (m_out.empty()) {
            while (!m_in.empty()) {
                m_out.push(m_in.pop());
            }
        }
        return m_out.pop();
    }
    int get_max() {
        return std::max(m_in.get_max()
                     , m_out.get_max());
    }

private:
    MaxStack m_in;
    MaxStack m_out;
};


int main() {
    MaxQueue q; std::string cmd; int x;
    while (std::cin >> cmd) {
        if (cmd == "push") {
            std::cin >> x; q.push(x);
            std::cout << "None" << std::endl;
        } else if (cmd == "pop") {
            std::cout << q.pop() << std::endl;
        } else {
            std::cout << q.get_max() << std::endl;
        }
    }
    return 0;
}

Other

代码看起来比较长，**其实很简单，核心代码实际上就几行。

Q004_让奶牛飞_solution

Question_ID: Q004

Language: java

Time Cost: 30-mins

Time Complexity: o(n)

Solution

My Code

    //第一个版本
   static void order(int [] in){
        boolean small=false;
        for(int i=1;i<in.length;i++){
            if(small){
                if(in[i]>in[i-1])
                    exchange(in,i,i-1);
            }else{
                if(in[i]<in[i-1])
                    exchange(in,i,i-1);
            }
            small=!small;
        }
    }
   //第二个版本
    static void order(int[] in) {
        for (int i = 1; i < in.length; i++) {
            if ((i & 1) == 0 ? in[i] > in[i - 1] : in[i] < in[i - 1])
                exchange(in, i, i - 1);
        }
    }
    static void exchange(int[] a,int x,int y){
        int t=a[x];
        a[x]=a[y];
        a[y]=t;
    }