You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

As mentioned of problem, except for one element which appears exactly once, others are twice. It’s meant, if we separate from middle, single element have to at odd-side. Because value of middle have to equal value of middle+1 or middle-1.

題目提到,除了單一元素的那個數字,其他數字都是兩個數,這樣表示,以中間點分開,單一數一定是在奇數個的那邊,因為中間點可能會等於左邊那一個或右邊那一個。

Given an array of strings words representing an English Dictionary, return the longest word in words that can be built one character at a time by other words in words.

If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.

Example 1:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

I knew that the best solution is “Tire”. But, I used Hash first and that is method of brute force. I will used “Tire” later.
Sort first. check the word with hashset one by one. If those words are include in hashset, I will compare length of result and the word, and replace result to longer word.

我知道這題的最佳解是用Tire,先使用Hash的方式解這題,之後會再用Tire解一次,先來說明暴力解的方式。
暴力解:
先做排序,逐一檢查每個字的前面字串是否有存在hash裡面。如果沒有,就表示這個字串並不符合。如果有,則檢查是否為最長的字。

Given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some of the given string characters. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
Output: "apple"

Because return the longest word with the smallest lexicographical order. So, I need sort dictionary first. Each of two arrays have a pointer. Base on dictionary array and check s string one by one to find the same as char of dictionary. Record the string of dictionary, if satisfaction condition. I compare and get the longest word of dictionary, then return it.

因為同樣長度的字典要輸出字典排序最前面的字串,所以先針對字典的樹組做排序,兩個數組分別各自一個指針,以字典的數組為主,逐一檢查在s字串中是否都有字典中單一字串的字元。記錄滿足條件下的字典字串,同時比較滿足條件的字串長度,更新最長字串的字串作為最後輸出。

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = "aba"
Output: true

Right point start from 0 and shift to left. Left point start from length-1 and shift to right. Until find different character of right and left point. Check remain string is it a palindrome string, when right point shift to left 1 step or left point shift to right 1 step. I need check two conditions. If both true, return true. Otherwise, return false.

左指針從0開始往右,右指針從length-1開始往左,兩指針向中間前進,直到找到字元不相同的時候。將剩餘的子字串拿出來比對,看看是否在移除1個字元後剩餘的子字串就為相同,有可能是右指針往左,也有可能是左指針需要往右,所以兩個方式都需要判斷,兩者只要其一為true即為true。

Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

Example 1:

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

I suppose first this question is extension of Two Sum. Then I used HashSet to solve this question. But… The RunTime is too bad. So, I change my thinking to Two Points. small point is start from 0 and shift to right, large point is start from squrt(c) and shift to left. If sum of square of small point and square of large point lesser equal c, return true. If lesser than c, small point shift to right. If larger than c, large point shift to left.

一開始的思考方向是Two Sum的延伸,於是先做了一個HashSet的方式,但RunTime實在太差,練習使用TwoPoints。小指針從0開始往右移動,大指針從c開平方的整數值開始往左移動,如果小指針的平方與大指針的平方和為c,則為true。如果大於c則表示大指針過大,需要往左邊移動。反之,則小指針往右移動。

SP Hou

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store