这题确实easy,做这题倒真可以脱离IDE在leetcode编辑器里刷题了。
做这题，又犯了一次java与js字符串的小错误，在Java里获取String长度的length()是method，在js里获取字符串长度的length是property，老是搞混淆了。

Javascript

1
2
3
4
5
6
7
8
9
10
11
12
13

/**
 * @param {string} s
 * @return {string}
 */
var reverseString = function(s) {
    var r = "";
    if (s!=null && s.length>0) {
        for(var i=s.length-1;i>=0;i--) {
            r+=s[i];
        }        
    }
    return r;
};

Submission Detail

• 476 / 476 test cases passed.
• Your runtime beats 96.31 % of javascript submissions.

Java

LOOP+SB

1

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public String reverseString(String s) {
        StringBuilder sb = new StringBuilder();
        if (s!=null && !s.isEmpty()) {
            for(int i=s.length()-1;i>=0;i--) {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}

Submission Detail

• 476 / 476 test cases passed.
• Your runtime beats 13.87 % of java submissions.

跟js写法差不多，这java代码的性能倒不行

2

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public String reverseString(String s) {
        StringBuilder sb = new StringBuilder();
        if (s!=null && !s.isEmpty()) {
        	char[] arr = s.toCharArray();
            for(int i=arr.length-1;i>=0;i--) {
                sb.append(arr[i]);
            }
        }
        return sb.toString();
    }
}

Submission Detail

• 476 / 476 test cases passed.
• Your runtime beats 5.40 % of java submissions.

SB

1
2
3
4
5
6
7
8
9
10

class Solution {
    public String reverseString(String s) {
        String r = "";
        if (s!=null && !s.isEmpty()) {
        	StringBuilder sb = new StringBuilder(s);
        	r = sb.reverse().toString();
        }
        return r;        
    }
}

Submission Detail

• 476 / 476 test cases passed.
• Your runtime beats 5.40 % of java submissions.

直接用StringBuilder的reverse()，用StringBuffer好像也类似，性能没什么变化

逆转字符数组

Ref

• What is the most efficient algorithm for reversing a String in Java?
• How to Invert an Array in Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public String reverseString(String s) {
    	String r = "";
        if (s!=null && !s.isEmpty()) {
        	char[] arr = s.toCharArray();
            for (int i=0; i<arr.length/2; i++) {
                char temp = arr[i];
                arr[i] = arr[arr.length-1-i];
                arr[arr.length-1-i] = temp;
            }
            r = new String(arr);
        }
        return r;        
    }
}

Submission Detail

• 476 / 476 test cases passed.
• Your runtime beats 7.62 % of java submissions.

Rust

Rust 95%+

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn reverse_string(s: &mut Vec<char>) {
        let len = s.len();
        if len > 0 {
            let mut midpoint = len / 2;
            if len % 2 != 0 {
                midpoint += 1;
            }
            for i in 0..midpoint {
                let j = len - i - 1;
                let buffer = s[i];
                s[i] = s[j];
                s[j] = buffer;
            }
        }
    }
}

Submission Detail

• 478 / 478 test cases passed.
• Runtime: 20 ms, faster than 95.94% of Rust online submissions for Reverse String.
• Memory Usage: 5.1 MB, less than 100.00% of Rust online submissions for Reverse String.

Longest increasing subsequence 看来也是道比较经典的算法题，LeetCode 与 LintCode 都有此题。

• 300. Longest Increasing Subsequence
• 76. Longest Increasing Subsequence

有名的算法网站 Rosetta Code 上有此题的N种语言之实现 Longest increasing subsequence

Dynamic Programming

琢磨不出来，上网搜罗

google关键字:

• longest increasing subsequence dynamic programming
• longest increasing subsequence optimal substructure

这是相关资料：

• Longest Increasing Subsequence using Dynamic Programming
  http://www.techiedelight.com/longest-increasing-subsequence-using-dynamic-programming/ 最后是按这篇blog的思路写的代码
• Dynamic Programming #1: Longest Increasing Subsequence youtube视频，看了这个明白需要增加一个数组保存对应每个数组slice的递增子序列的长度：length of LIS ends with D[i]
• Longest increasing subsequence
  https://wcipeg.com/wiki/Longest_increasing_subsequence
• Can I get an explanation for how optimal substructure is used to find the longest increasing subsequence in this powerpoint slide?
  https://stackoverflow.com/questions/39074402/can-i-get-an-explanation-for-how-optimal-substructure-is-used-to-find-the-longes
• Dynamic Programming – Longest Increasing Subsequence
  https://algorithms.tutorialhorizon.com/dynamic-programming-longest-increasing-subsequence/

代码虽然在LeetCode上跑通了，但还是没有完全理解其中的步骤，还是处于知其然而不知其所以然的阶段，好像有点数学归纳法的意味，也有点像递归，动态规划好像也能用来解决兔子序列问题。

java

Efficient algorithms followed Wikipedia

binary search + DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public int lengthOfLIS(int[] nums) {
		int N = nums.length;
		int[] M = new int[N + 1];

		int L = 0;
		for (int i = 0; i < N; i++) {
			int lo = 1;
			int hi = L;
			while (lo <= hi) {
				int mid = new Double(Math.ceil((lo + hi) / 2)).intValue();
				if (nums[M[mid]] < nums[i])
					lo = mid + 1;
				else
					hi = mid - 1;
			}

			int newL = lo;

			M[newL] = i;

			if (newL > L)
				L = newL;
		}
		return L;        
    }
}

Submission Detail

• 54 / 54 test cases passed.
• Runtime: 5 ms, faster than 75.39% of Java online submissions for Longest Increasing Subsequence.
• Memory Usage: 39.2 MB, less than 12.91% of Java online submissions for Longest Increasing Subsequence.

o(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int lengthOfLIS(int[] nums) {
    	if (nums.length==0)
    		return 0;
    	int[] L = new int[nums.length];
    	L[0]=1;
    	for(int i=1;i<nums.length;i++) {
    		for(int j=0;j<i;j++) {
    			if(nums[j]<nums[i] && L[j]>L[i])
    				L[i] = L[j];
    		}
    		L[i]++;
    	}
    	return Arrays.stream(L).max().getAsInt();        
    }
}

Submission Detail

• 24 / 24 test cases passed.
• Your runtime beats 5.56 % of java submissions.

javascript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function(nums) {
  if (nums==null || nums.length==0)
      return 0;
  var arr = new Array(nums.length);
  for(i=0;i<arr.length;i++)
    arr[i] = 0;
	arr[0] = 1;
  for(i=1;i<nums.length;i++) {
    for(j=0;j<i;j++) {
	  if (nums[j]<nums[i] && arr[j]>arr[i]) {
	    arr[i] = arr[j];
	  }
	}
	arr[i]++;
  }
  var maxLISLen = arr[0];
  for(var i=1;i<arr.length;i++) {
    if (arr[i]>maxLISLen)
	  maxLISLen = arr[i];
  }
  return maxLISLen;    
};

Submission Detail

• 24 / 24 test cases passed.
• Your runtime beats 13.56 % of javascript submissions.

此题使用动态规划的算法看来性能不好，时间复杂度为O(n²)，维基百科上说最有效的算法为 Patience sorting，能达到 O(n log n)

1. asynchronous
2. algorithm
3. integer
4. legacy system
5. mutable
6. immutable
7. iterate
8. iteration
9. queue
10. stack
11. array
12. browser
13. hyphen
14. loitering
15. linearithmic
16. literal

就这么一道tag为Easy的题，对自己来说也不简单呐，犯了各种错误，死循环，数组越界，逻辑错误…，先是用js在页面上试验，结果死循环浏览器卡死，只好先换成java在eclipse上调试。按理这道题用到的就是冒泡排序、选择排序里的操作吧。

自己只会用各种库与框架，如果要从头写，看来连对数组操作也不熟悉，google关键字java array shift elements left，找到：

• How do I move the elements of an array by one cell towards left?
• Java, Shifting Elements in an Array

最后总算在leetcode上跑通了，不过还是稀里糊涂的。性能不行，不知道人家高手是怎么做的？难道用快速排序的思路？

java

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public void moveZeroes(int[] nums) {
		for(int i=nums.length-1;i>=0;i--) {
			if (nums[i]==0) {
				for(int j=i+1; j<nums.length; j++) {
					nums[j-1]=nums[j];
				}
				nums[nums.length-1]=0;
			}
		}       
    }
}

Submission Detail

• 21 / 21 test cases passed.
• Your runtime beats 11.98 % of java submissions.

javascript

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
	  for(i=nums.length-1;i>=0;i--) {
		  if (nums[i]==0) {
			  for(j=i+1;j<nums.length;j++) {
			    nums[j-1]=nums[j];
			  }
			  nums[nums.length-1]=0;
		  }
	  }    
};

Submission Detail

• 21 / 21 test cases passed.
• Your runtime beats 18.25 % of javascript submissions.

00:00
What keeps us healthy and happy as we go through life? If you were going to invest now in your future best self, where would you put your time and your energy? There was a recent survey of millennials asking them what their most important life goals were, and over 80 percent said that a major life goal for them was to get rich. And another 50 percent of those same young adults said that another major life goal was to become famous.

00:38
(Laughter)

00:40
And we’re constantly told to lean in to work, to push harder and achieve more. We’re given the impression that these are the things that we need to go after in order to have a good life. Pictures of entire lives, of the choices that people make and how those choices work out for them, those pictures are almost impossible to get. Most of what we know about human life we know from asking people to remember the past, and as we know, hindsight is anything but 20/20. We forget vast amounts of what happens to us in life, and sometimes memory is downright creative.

01:24
But what if we could watch entire lives as they unfold through time? What if we could study people from the time that they were teenagers all the way into old age to see what really keeps people happy and healthy?

01:43
We did that. The Harvard Study of Adult Development may be the longest study of adult life that’s ever been done. For 75 years, we’ve tracked the lives of 724 men, year after year, asking about their work, their home lives, their health, and of course asking all along the way without knowing how their life stories were going to turn out.

02:13
Studies like this are exceedingly rare. Almost all projects of this kind fall apart within a decade because too many people drop out of the study, or funding for the research dries up, or the researchers get distracted, or they die, and nobody moves the ball further down the field. But through a combination of luck and the persistence of several generations of researchers, this study has survived. About 60 of our original 724 men are still alive, still participating in the study, most of them in their 90s. And we are now beginning to study the more than 2,000 children of these men. And I’m the fourth director of the study.

03:03
Since 1938, we’ve tracked the lives of two groups of men. The first group started in the study when they were sophomores at Harvard College. They all finished college during World War II, and then most went off to serve in the war. And the second group that we’ve followed was a group of boys from Boston’s poorest neighborhoods, boys who were chosen for the study specifically because they were from some of the most troubled and disadvantaged families in the Boston of the 1930s. Most lived in tenements, many without hot and cold running water.

03:42
When they entered the study, all of these teenagers were interviewed. They were given medical exams. We went to their homes and we interviewed their parents. And then these teenagers grew up into adults who entered all walks of life. They became factory workers and lawyers and bricklayers and doctors, one President of the United States. Some developed alcoholism. A few developed schizophrenia. Some climbed the social ladder from the bottom all the way to the very top, and some made that journey in the opposite direction.

04:23
The founders of this study would never in their wildest dreams have imagined that I would be standing here today, 75 years later, telling you that the study still continues. Every two years, our patient and dedicated research staff calls up our men and asks them if we can send them yet one more set of questions about their lives.

04:48
Many of the inner city Boston men ask us, “Why do you keep wanting to study me? My life just isn’t that interesting.” The Harvard men never ask that question.

04:59
(Laughter)

05:08
To get the clearest picture of these lives, we don’t just send them questionnaires. We interview them in their living rooms. We get their medical records from their doctors. We draw their blood, we scan their brains, we talk to their children. We videotape them talking with their wives about their deepest concerns. And when, about a decade ago, we finally asked the wives if they would join us as members of the study, many of the women said, “You know, it’s about time.”

05:38
(Laughter)

05:39
So what have we learned? What are the lessons that come from the tens of thousands of pages of information that we’ve generated on these lives? Well, the lessons aren’t about wealth or fame or working harder and harder. The clearest message that we get from this 75-year study is this: Good relationships keep us happier and healthier. Period.

06:11
We’ve learned three big lessons about relationships. The first is that social connections are really good for us, and that loneliness kills. It turns out that people who are more socially connected to family, to friends, to community, are happier, they’re physically healthier, and they live longer than people who are less well connected. And the experience of loneliness turns out to be toxic. People who are more isolated than they want to be from others find that they are less happy, their health declines earlier in midlife, their brain functioning declines sooner and they live shorter lives than people who are not lonely. And the sad fact is that at any given time, more than one in five Americans will report that they’re lonely.

07:07
And we know that you can be lonely in a crowd and you can be lonely in a marriage, so the second big lesson that we learned is that it’s not just the number of friends you have, and it’s not whether or not you’re in a committed relationship, but it’s the quality of your close relationships that matters. It turns out that living in the midst of conflict is really bad for our health. High-conflict marriages, for example, without much affection, turn out to be very bad for our health, perhaps worse than getting divorced. And living in the midst of good, warm relationships is protective.

07:45
Once we had followed our men all the way into their 80s, we wanted to look back at them at midlife and to see if we could predict who was going to grow into a happy, healthy octogenarian and who wasn’t. And when we gathered together everything we knew about them at age 50, it wasn’t their middle age cholesterol levels that predicted how they were going to grow old. It was how satisfied they were in their relationships. The people who were the most satisfied in their relationships at age 50 were the healthiest at age 80. And good, close relationships seem to buffer us from some of the slings and arrows of getting old. Our most happily partnered men and women reported, in their 80s, that on the days when they had more physical pain, their mood stayed just as happy. But the people who were in unhappy relationships, on the days when they reported more physical pain, it was magnified by more emotional pain.

08:52
And the third big lesson that we learned about relationships and our health is that good relationships don’t just protect our bodies, they protect our brains. It turns out that being in a securely attached relationship to another person in your 80s is protective, that the people who are in relationships where they really feel they can count on the other person in times of need, those people’s memories stay sharper longer. And the people in relationships where they feel they really can’t count on the other one, those are the people who experience earlier memory decline. And those good relationships, they don’t have to be smooth all the time. Some of our octogenarian couples could bicker with each other day in and day out, but as long as they felt that they could really count on the other when the going got tough, those arguments didn’t take a toll on their memories.

09:49
So this message, that good, close relationships are good for our health and well-being, this is wisdom that’s as old as the hills. Why is this so hard to get and so easy to ignore? Well, we’re human. What we’d really like is a quick fix, something we can get that’ll make our lives good and keep them that way. Relationships are messy and they’re complicated and the hard work of tending to family and friends, it’s not sexy or glamorous. It’s also lifelong. It never ends. The people in our 75-year study who were the happiest in retirement were the people who had actively worked to replace workmates with new playmates. Just like the millennials in that recent survey, many of our men when they were starting out as young adults really believed that fame and wealth and high achievement were what they needed to go after to have a good life. But over and over, over these 75 years, our study has shown that the people who fared the best were the people who leaned in to relationships, with family, with friends, with community.

11:09
So what about you? Let’s say you’re 25, or you’re 40, or you’re 60. What might leaning in to relationships even look like?

11:19
Well, the possibilities are practically endless. It might be something as simple as replacing screen time with people time or livening up a stale relationship by doing something new together, long walks or date nights, or reaching out to that family member who you haven’t spoken to in years, because those all-too-common family feuds take a terrible toll on the people who hold the grudges.

11:52
I’d like to close with a quote from Mark Twain. More than a century ago, he was looking back on his life, and he wrote this: “There isn’t time, so brief is life, for bickerings, apologies, heartburnings, callings to account. There is only time for loving, and but an instant, so to speak, for that.”

12:22
The good life is built with good relationships.

12:27
Thank you.

12:28
(Applause)

如何迅速提高英语阅读能力？

• 对于中初级学习者来说，迅速提高词汇量比分辨近义词的差别更重要。
• 只要你不是从小大量阅读英文，背单词就是必须的。
• 要按照读音来记单词
• 阅读的时候脑子要思考，不断地问：作者在说什么？文章的走向是怎么样的？里面有哪一些核心内容？有什么样的情感？带着目的去阅读，而非无意识阅读。无意识阅读法，只能浪费时间。
• 在读复杂句的时候，或者碰到不明白的句子的时候，脑子要分清楚主语、谓语、宾语之间的修饰关系。比如说这个It指代了谁？这句超级无敌长的复杂句里，主谓宾在哪里？修饰是放在前面还是后面了？读的时候可以不做语法分析，但是一定要弄明白每个单词在句子里所扮演的角色，以及它们之间所产生的关系。长难句是绝对绕不过去的一个坎，不要心存侥幸，现在就赶紧解决它吧。
• 千万不要总是跳过不懂的东西。

中国人说英语为什么听起来没有礼貌？（8.17更新添加中英文化差异的讨论）

• 中国人的英语以 Chinglish 或 Chenglish 闻名于世。中国人最大的英语发音问题就是没有连读，但这都不是最主要的语言问题。老外们时常议论，很多中国人在说英语时，听起来没有礼貌；并不是这些中国人本身没礼貌，而是他们还没有习惯英语的礼貌表达方式。
• 比如，中国人在餐厅或咖啡厅，会说：“我想要一个汉堡包”或者“我想要一杯咖啡”。但是，如果直接把这些话翻译成英语“I want to have a hamburger.”或“I want to have a coffee.”老外们会觉得这样说话很没有礼貌，当然他们也不会直接告诉你。而在西方国家，老外们一般会说：“Could I have a hamburger, please?”或“Can I have a coffee, please?”在这里joy同学又提到一个需要注意的问题，“打工的孩子最容易不注意的是see you. See u应该是客人说的，隐含了他觉得不错他会再来的意思，而店员最好用低调一点的bye，用see u太强势了。另外人家说谢谢，你也不用说you are welcome, 这实在是太正式了，有点真把自己当回事觉得帮了人家的味道。回答 cheers 或 no worries 就好，如果仅仅是对方爱说谢，你甚至可以不回应他的谢，直接说你要说的就好，如果是买了他的东西他谢你，更不能说you r welcome了
• 再比如，中国人在拒绝别人邀请的午宴或晚宴时，会说：“抱歉，我不能去，我还有别的安排。”翻译成英文就是“Sorry，I can’t. I have another appointment.”如果这样说，那别人第二次也许不会再邀请你了。老外们一般会这样说：“**That is a good idea! I would like to join in but I have another appointment today.**”

这题是 Top Interview Questions 及 Top 100 Liked Questions之一，前后又花了一个星期。

先是了解了下 Cache replacement policies，其中提及 General implementations of Least recently used (LRU) require keeping “age bits” for cache-lines and track the “Least Recently Used” cache-line based on age-bits.

题目里提示 Could you do both operations in O(1) time complexity? ，又了解了下Time complexity。又在kindle上翻了下《算法图解》，了解了下散列表、链表等数据结构，也算加强了下对哈希表的认识。

在平均情况下， 散列表执行各种操作的时间都为O(1)。 O(1)被称为常量时间。你以前没有见过 常量时间，它并不意味着马上，而是说不管散列表多大，所需的时间都相同。

实际上，你以前见过常量时间——从数组中获取一个元素所需的时间就是固定的：不管数组多大，从中获取一个元素所需的时间都是相同的。

填装因子(load factor)度量的是散列表中有多少位置是空的。填装因子越低，发生冲突的可能性越小，散列表的性能越高。一个不错的经验规则是：一旦填装因子大于0.7，就调整散列表的长度。

自己琢磨也是徒劳，不如上网找点提示信息，在quora上找到几条信息

• What is the best way to Implement an LRU Cache?
• How are linked lists good for LRU caches?
• Why is doubly linked list used in LRU(Least Recently Used) implementation as in this link (Implement LRU Cache - GeeksforGeeks)?

Typically LRU cache is implemented using a doubly linked list and a hash map.

An LRU Cache should support fast lookup. Apparently, in order to achieve fast lookup, we need to use Hashtable or HashMap.Also, an LRU Cache requires that insert and delete operations should be in O(1) time. The obvious choice for this requirement is Linked List. Linked List support insert/delete operations in O(1) time if we have the reference of element. While building an LRU cache requires that you think in terms of these two data structures. The reality is that these two data structures actually work coherently to achieve the design.So, we are finalizing on these data structures: HashMap and Doubly Linked List. HashMap holds the keys and values as reference of the nodes (entries) of Doubly Linked List.Doubly Linked List is used to store list of nodes (entries) with most recently used node at the head of the list. So, as more nodes are added to the list, least recently used nodes are moved to the end of the list with node at tail being the least recently used in the list.

自己对java集合类库还是不够熟悉，看到Is there any doubly linked list implementation in Java?才明白原来java.util.LinkedList本来就可以当双向链表使用，

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

在leetcode上提交了两次，终于运行通过，如果自己来实现双向链表是不是更能提高性能? 做了这些题，感觉leetcode的算法题不是那种难得要死的题，不会做说明你的数据结构和算法知识还比较欠缺。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

class LRUCache {
	private LinkedList<DualLinkNode> list;
	private Map<Integer,DualLinkNode> map;
	private final int cacheSize;

    public LRUCache(int capacity) {
    	list = new LinkedList<DualLinkNode>();
    	map = new HashMap<Integer,DualLinkNode>();
    	this.cacheSize = capacity;
    }

    public int get(int key) {
    	if (map.containsKey(key)) {
    		DualLinkNode node = map.get(key);
    		list.remove(node);
    		list.addFirst(node);
    		return node.val;
    	}
    	else {
    		return -1;
    	}
    }

    public void put(int key, int value) {
    	if (map.containsKey(key)) {
    		DualLinkNode node = map.get(key);
    		list.remove(node);
    		node.val=value;
    		list.addFirst(node);
    	}
    	else {
			if (list.size()==cacheSize) {
				DualLinkNode node = list.pollLast();
				map.remove(node.key);
			}
			DualLinkNode node = new DualLinkNode(key,value);
			list.addFirst(node);
			map.put(key, node);
    	}
    }

	private class DualLinkNode {
		public int key;
		public int val;

		public DualLinkNode(int key, int val) {
			super();
			this.key = key;
			this.val = val;
		}
	}
}

Submission Detail

• 18 / 18 test cases passed.
• Your runtime beats 7.69 % of java submissions.

How did you prepare for AWS Certified Solutions Architect - Associate Level certification?
https://www.quora.com/How-did-you-prepare-for-AWS-Certified-Solutions-Architect-Associate-Level-certification

Preparing for the AWS Certified Solutions Architect Associate Certification Exam
https://blog.newrelic.com/2018/05/30/aws-certified-solutions-architect-associate-exam-prep/

AWS Certified Solutions Architect - Associate
https://aws.amazon.com/certification/certified-solutions-architect-associate/

AWS Certified Solutions Architect – Associate
https://aws.amazon.com/tw/certification/certified-solutions-architect-associate/

AWS Certified Solutions Architect – Associate
https://aws.amazon.com/cn/certification/certified-solutions-architect-associate/

AWS Well-Architected
采用架构最佳实践进行学习、测量和构建
https://aws.amazon.com/cn/architecture/well-architected/

AWS Well-Architected
Learn, measure, and build using architectural best practices
https://aws.amazon.com/architecture/well-architected/

https://aws.amazon.com/cn/getting-started

Amazon Web Services - Documentation
Documenting Amazon Web Services and SDKs
https://github.com/awsdocs

Java

1

自己做出来的naive solution，直接把整数转换成字符串，然后逆转字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    public int reverse(int x) {
    	int r = 0;
    	if (x>Integer.MAX_VALUE || x<Integer.MIN_VALUE) {
    		return r;
    	}
    	String s = Integer.toString(x);
    	if (s!=null && !s.isEmpty()) {
    		String ss = "";
    		char c = 0;
    		if (x<0)
    			s = s.substring(1);
    		for(int i=s.length()-1;i>=0;i--) {
    			c = s.charAt(i);
    			ss += c;
    		}
    		if (x<0)
    			ss = '-'+ss;
    		System.out.println("ss="+ss);
    		try {
    		    r = Integer.parseInt(ss);
    		} catch (NumberFormatException ex) {
    			r = 0;
    		}
    	}    		
        return r;        
    }
}

Submission Detail

• 1032 / 1032 test cases passed.

2

做 9. Palindrome Number ，提示Coud you solve it without converting the integer to a string? 发现人家的方法更直接利落，温故而知新，重新实现下，结果被卡在 java int out of range 的问题里，1534236469 逆序数超过Integer.MAX_VALUE 返回 1056389759，题目里就提示了 Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows. 最后想到不如把逆序数变量定义为 long类型，再判断是否超过2147483647(0x7fffffff, 2^31-1)，再把long 安全地转换为int返回，java的long安全转换为int的小问题，google关键字 java long to int 参考了下 Safely casting long to int in Java 这样就ok了，在leetcode上运行通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int reverse(int x) {
    	if (x>Integer.MAX_VALUE || x<Integer.MIN_VALUE) {
    		return 0;
    	}
    	if (x==0) return 0;
    	int r = 0;
    	int remainder = 0;
    	long reverseNumber = 0L;
    	for(int t = x>0?x:-x; t>0; t/=10) {
    		remainder = t%10;
    		reverseNumber *= 10;
    		reverseNumber += remainder;
    	}
    	if (reverseNumber>Integer.MAX_VALUE)
    		r = 0;
    	else
    		r = Long.valueOf(reverseNumber).intValue();
    	if (x<0)
    		r *= -1;    	
        return r;        
    }
}

Submission Detail

• 1032 / 1032 test cases passed.
• Runtime: 21 ms
• Your runtime beats 97.62 % of java submissions.

一个多月前就看了下，这题label为Easy，跟 7. Reverse Integer 有关系，自己做7. Reverse Intege时就简单把整数转为字符串来解决，而这题提示Coud you solve it without converting the integer to a string，自己对c语言为例的过程化编程还是欠差，google 关键字 Palindrome Number，出来

• C Program to Check Whether a Number is Palindrome or Not
• Palindrome number in C
• To check a number is palindrome or not without using any extra space
• Palindrome Program in Java

最后参照 C Program to Check Whether a Number is Palindrome or Not 的写了java代码，在Eclipse里跑了下，结果不对，又看人家的代码，看来自己还是不理解这个求逆序数的步骤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public boolean isPalindrome(int x) {
    	boolean b =  false;
    	int originalInteger = x;
    	int reversedInteger = 0, remainder = 0;
    	int t = x;
        while (t>0) {
        	remainder = t%10;
        	reversedInteger = reversedInteger*10+remainder;
        	t /= 10;
        }
        if (originalInteger==reversedInteger)
        	b = true;
        return b;        
    }
}

Submission Detail

• 11508 / 11508 test cases passed.
• Your runtime beats 58.36 % of java submissions.