Leetcode--easy系列10

#205 Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,

Given "egg" , "add" ,
return true.

Given "foo" , "bar" ,
return false.

Given "paper" , "title" ,
return true.

Note:

You may assume both s and t have the same length.

推断2个字符串结构是否同样（默认长度相等）。

最開始我是这样想的，将两个同构不同型的字符串按规则变为同构同型的字符串，比較转换后的字符串是否等。

如paper  'p'变为1，‘a’变为2，‘e’变为3 ‘r’变为4.则字符串变为 12134  title 类似变为12134。相等说明同构。

还有一种思路是分别遍历两个字符串，利用hash表中的s[i]位置存储t[i]中的字符。当下一次s字符串中再次出现s[j] ==s[i] 时，对于 t[j] 位置上的字符应该和先前的字符 t[i] 同样。

//0ms

bool isIsomorphic(char* s, char* t) {

    int hash[128] = {0};

    int i;

    for( i = 0; s[i] != '\0'; i++)

    {

        if(!hash[s[i]])

            hash[s[i]] = t[i];

        else if (hash[s[i]] != t[i])

            return false;

    }

    memset(hash,0,sizeof(hash));

    for( i =0; t[i] != '\0'; i++)

    {

        if(!hash[t[i]])

            hash[t[i]] = s[i];

        else if (hash[t[i]] != s[i])

            return false;

    }

    return true;

}

#206 Reverse Linked List

Reverse
a singly linked list.

//0ms

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

struct ListNode* reverseList(struct ListNode* head) {

    struct ListNode *newhead,*p,*new_p,*r;

	newhead->next = head;

	p = head;

	r = NULL;

	while(p)

	{

		new_p = p->next;

		p->next = r;

		r = p;

		p = new_p;

	}

	return r;

}

#223
Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

2个对角顶点能够确定一个长方形，给定4个点的坐标。求它们构成的2个长方形覆盖的面积。

关键在于怎样依据坐标的相对大小来确定2个长方形是否相互覆盖。

//12ms

int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {

    int area = (C-A)*(D-B) + (G-E)*(H-F);

    int top,bottom,left,right,cover;

    if(A>=G || C<=E || B>=H || D<=F)

        return area;

    top = (D<=H)?D:H;

    bottom = (B>=F)?B:F;

    left = (A>=E)?

A:E;

    right = (C<=G)?

C:G;

    cover = (top - bottom)*(right-left);

    return area-cover;

}

#226
Invert Binary Tree

Invert a binary tree.

     4

   /   \

  2     7

 / \   / \

1   3 6   9

to

     4

   /   \

  7     2

 / \   / \

9   6 3   1

//0ms

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     struct TreeNode *left;

 *     struct TreeNode *right;

 * };

 */

struct TreeNode* invertTree(struct TreeNode* root) {

    struct TreeNode* p;

    if(!root)

        return NULL;

    else if(!root->left && !root->right)

        return root;

     p = root->left;

     root->left = root->right;

     root->right = p;

     invertTree(root->left);

     invertTree(root->right);

     return root;

}