158. Read N Characters Given Read4 II - Call multiple times

题目：

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that readsn characters from the file.

Note:
The read function may be called multiple times.

题解：

需要用Queue保存之前多读的character。每次读时，先看Queue里的够不够，如果不够，先读到够为止。

  1. // Forward declaration of the read4 API.
  2. int read4(char *buf);
  3. class Solution {
  4. public:
  5. /**
  6. * @param buf Destination buffer
  7. * @param n   Maximum number of characters to read
  8. * @return    The number of characters read
  9. */
  10. int read(char *buf, int n) {
  11. if(n == 0)
  12. return 0;
  13. int total = 0;
  14. while(this->buffer.size() < n && !this->endOfFile) {
  15. char* temp = new char[4];
  16. int r = read4(temp);
  17. if(r < 4)
  18. this->endOfFile = true;
  19. for(int i = 0; i < r; i++)
  20. this->buffer.push(temp[i]);
  21. }
  22. int l = min((int)this->buffer.size(), n);
  23. for(int i = 0; i < l; i++) {
  24. buf[i] = this->buffer.front();
  25. this->buffer.pop();
  26. total++;
  27. }
  28. return total;
  29. }
  30. private:
  31. queue<char> buffer;
  32. bool endOfFile = false;
  33. };

156. Binary Tree Upside Down

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example:
Given a binary tree {1,2,3,4,5},
1
/ \
2 3
/ \
4 5

return the root of the binary tree [4,5,2,#,#,3,1].
4
/ \
5 2
  / \
 3 1

 1

 2

 3

 4

 5

 6

 7

 8

 9

10

11

12

13

14

15

16

17

18

19

20

21
 
class Solution {

public:

    TreeNode *upsideDownBinaryTree(TreeNode *root) {

        TreeNode *temp, *newRoot = NULL;

        temp = buildUpsideDownBT(root, newRoot);

        return newRoot;

    }

    TreeNode *buildUpsideDownBT(TreeNode *root, TreeNode *&newRoot) {

        if(!root) return root;

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

            newRoot = root;

            return root;

        }

        TreeNode *parent = buildUpsideDownBT(root->left, newRoot);

        parent->left = root->right;

        parent->right = root;

        root->left = root->right = NULL;

        return parent->right;

    }

};

总结：
1. 这个递归的核心是，每次建立好一个新的子树后，要返回新子树的最右节点（ln 19)，以便上层的节点可以接回到这个节点的下面。
2. 但如果只返回最右节点，则我们无法知道最后整个新树的根在哪里。所以再base case里必须给新根赋值(ln 12)
3. 每次需要reset最右节点的left/right node，否则最后一层递归，递归到例子中的1节点时，返回前1节点的left/right node仍然为原来的值，而并不为NULL。

这题有一个重要的限制就是，整个数的任何一个右孩子都不会再生枝节，基本就是一个梳子的形状。对于树类型的题目，首先可以想到一种递归的思路：把左子树继续颠倒，颠倒完后，原来的那个左孩子的左右孩子指针分别指向原来的根节点以及原来的右兄弟节点即可。

  1. public TreeNode UpsideDownBinaryTree(TreeNode root) {
  2. if (root == null)
  3. return null;
  4. TreeNode parent = root, left = root.left, right = root.right;
  5. if (left != null) {
  6. TreeNode ret = UpsideDownBinaryTree(left);
  7. left.left = right;
  8. left.right = parent;
  9. return ret;
  10. }
  11. return root;
  12. }

第二个思路是直接用迭代代替递归，做起来也不麻烦，并且效率会更高，因为省去了递归所用的栈空间。

  1. public TreeNode UpsideDownBinaryTree(TreeNode root) {
  2. TreeNode node = root, parent = null, right = null;
  3. while (node != null) {
  4. TreeNode left = node.left;
  5. node.left = right;
  6. right = node.right;
  7. node.right = parent;
  8. parent = node;
  9. node = left;
  10. }
  11. return parent;
  12. }

第三个思路比较特别，把后续遍历转换成层次遍历。注意由于Java不支持对TreeNode地址传引用，所以这里弄了一个全局变量。另外，类似于对链表的处理，这里我弄了一个dummy node简化对根节点的处理。

    1. private TreeNode out = null;
    2. public TreeNode UpsideDownBinaryTree(TreeNode root) {
    3. TreeNode dummy = new TreeNode(0);
    4. dummy.left = new TreeNode(0);
    5. out = dummy;
    6. postorder(root);
    7. return dummy.right;
    8. }
    9. private void postorder(TreeNode root) {
    10. if (root == null)
    11. return;
    12. postorder(root.left);
    13. postorder(root.right);
    14. if (out.left == null) {
    15. out.left = root;
    16. out.left.left = null;
    17. out.left.right = null;
    18. } else if (out.right == null) {
    19. out.right = root;
    20. out.right.left = null;
    21. out.right.right = null;
    22. }
    23. if (out.left != null && out.right != null)
    24. out = out.right;
    25. }

161.One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.

we can transform S to T by using exactly one edit operation. There are three possible cases:

  1. We insert a character into S to get T.
  2. We delete a character from S to get T.
  3. We substitute a character of S to get T.

The code is as follows. If you find the first half of the return statement (!mismatch && (n - m == 1)) hard to understand, run the code on cases that the mismatch only occurs at the last character of the longer string, like S = "ab" and T = "abc".

class Solution {

public:

    bool isOneEditDistance(string s, string t) {

        int m = s.length(), n = t.length();

        if (m > n) return isOneEditDistance(t, s);

        if (n - m > 1) return false;

        bool mismatch = false;

        for (int i = 0; i < m; i++) {

            if (s[i] != t[i]) {

                if (m == n) s[i] = t[i];

                else s.insert(i, 1, t[i]);

                mismatch = true;

                break;

            }

        }

        return (!mismatch && n - m == 1) || (mismatch && s == t);

    }

};

163. Missing Ranges

Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.

For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].

class Solution {

public:

    string get_range(int start, int end)

    {

        return start==end? to_string(start) : to_string(start)+"->"+to_string(end);

    }

    vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {

        vector<string> result;

        int pre = lower-1;

        for(int i =0; i <= nums.size(); i++)

        {

           int cur = (i==nums.size()? upper+1:nums[i]);

           if(cur-pre>=2)

            result.push_back(get_range(pre+1,cur-1));

            pre = cur;

        }

        return result;

    }

};

170. [LeetCode] Two Sum III - Data structure design 两数之和之三 - 数据结构设计

 

Design and implement a TwoSum class. It should support the following operations:add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

class TwoSum{
public:
void add(int number){
hash[number]++;
}
bool find(int number){
for(int i : hash){
int target = number - i.first;
if(hash.find(target) != hash.end()){
return true;
}
}
return false;
}
private:
unordered_map<int, int>hash;
};

LeetCode 186. Reverse Words in a String II（反转单词）

最新文章

  1. WMPlayer
  2. jQuery校验validate详解（转）
  3. selenium如何操作cookies实现免登录
  4. JavaScript原型模式
  5. Java基础知识强化之集合框架笔记13：Collection集合存储学生对象并遍历
  6. KVC和KVO实现监听容器类(数组等)的变化
  7. 分子量(Molar Mass,ACM/ICPC Seoul 2007,UVa 1586)
  8. WAV音频格式分析
  9. Javascript基本概念（一）
  10. 从零开始学习前端开发 — 17、CSS3背景与渐变
  11. mybatis-spring最新版下载地址
  12. 第1章 PCI总线的基本知识
  13. Java集合类常见的问题
  14. Java学习——类与对象
  15. 移动端目标识别(2)——使用TENSORFLOW LITE将TENSORFLOW模型部署到移动端(SSD)之TF Lite Developer Guide
  16. zabbix基础使用--添加ping监控
  17. 输入系统：epoll &amp; inotify
  18. WPF 我的初学必备技能
  19. 怎样去写线程安全的代码(Java)
  20. CSS3 - chrome，傲游，360极速浏览器不支持小于12px的字号的解决办法

热门文章

  1. r.js实践
  2. iOS基础 - UITableView的数据源(dataSource)和代理(delegate)
  3. Android学习笔记-Intent(一)
  4. [转]Libev源码分析 -- 整体设计
  5. [转]Inside Swift
  6. C++数据结构之二叉查找树（BST）
  7. 用Jekyll在github上写博客
  8. IOS学习之路二十三（EGOImageLoading异步加载图片开源框架使用）
  9. 【July】从头到尾彻底理解KMP
  10. jquery选择器之层级过滤选择器