刷LeetCode

刷LeetCode,梳理解题思路。

##1.Two Sum##

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

WhileMe:

  • 1)两个for遍历,N[index1]+N[index2] = target 且 index不同,即找到两个index。
  • 2)配对算法,遍历numbers,A= N[index1], B = target - A,用map记录每个number需要的值和index,map.insert(B, A.index1)。在map中找到,即当前值N[index1]和MAP的KEY值配对成功,index2=map.find(N[index1]).value,即找到两个index。

##2.ZigZag Conversion##

The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N A P L S I I G Y I R And then read line by line: “PAHNAPLSIIGYIR” Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows); convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

WhileMe:
拉链算法,拉链宽度即是字符串数组长度,遍历字符串,按照拉链Z,确定数组下标,撒到字符串数组中,最终连起来,组合成新字符串。数组下标确定:数组下标从0开始,步进1,增加到nRows-1,步进为-1,如此反复直至遍历完字符串。

##3.Reverse Integer##

Reverse digits of an integer.

Example1: x = 123, return 321 Example2: x = -123, return -321

WhileMe:
对10求余得余数即个位数,对10整除即去掉个位数,即可得到各个位数值,再计算组合成新值即可。

##4.String to Integer (atoi) ## Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

WhileMe:
去掉字符串开头的空格,获取符号”-“,”+”,遍历后续字符直到字符不是数字为止,对数字计算组合成数值,如果符号为”-“,在数值前加上”-“。

##5.Palindrome Number 回文##

Determine whether an integer is a palindrome. Do this without extra space.

WhileMe

  • 1)判断反转数字后是否相等
  • 2)取头尾逐个比较是否相等(除长度取头,对10求余取尾。对长度求余去头,除10去尾)。

##5.Longest Common Prefix##

Write a function to find the longest common prefix string amongst an array of strings.

WhileMe 找到最短字符串,和其他字符串逐个字符比较,发现不同即找到最长共同前缀。

##6.single number

Given an array of integers, every element appears twice except for one. Find that single one.

WhileMe 相同的两个数异或为0,0异或剩下的一个即为结果。