旋轉數(shù)組
題目：給定一個數(shù)組，將數(shù)組中的元素向右移動 k 個位置哀卫，其中 k 是非負數(shù)。
示例 1:
輸入: [1,2,3,4,5,6,7] 和 k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉 1 步: [7,1,2,3,4,5,6]
向右旋轉 2 步: [6,7,1,2,3,4,5]
向右旋轉 3 步: [5,6,7,1,2,3,4]
示例 2:
輸入: [-1,-100,3,99] 和 k = 2
輸出: [3,99,-1,-100]
解釋:
向右旋轉 1 步: [99,-1,-100,3]
向右旋轉 2 步: [3,99,-1,-100]
說明:
盡可能想出更多的解決方案撬槽，至少有三種不同的方法可以解決這個問題此改。
要求使用空間復雜度為 O(1) 的 原地 算法。
思路：這個題乍一看讓我想起了樹的左旋右旋啊侄柔。不過這個題沒有這么復雜其實共啃，仔細看題就能發(fā)現(xiàn)所謂的右旋就是最右（后）位元素換到前面來了。不考慮性能的話暴力法還是很容易做到的暂题。不管是挨個元素改變值移剪，還是直接數(shù)組復制串塑，反正還是那句話嘹履，實現(xiàn)簡單谒养，優(yōu)化難呀舔。而且這個空間復雜度為O（1）也就是不額外建立數(shù)組僻爽，沒要求時間復雜度。有點思路了庭惜，我先去擼代碼
第一版本出爐：就是最暴力的解法这揣，雖然滿足空間復雜度，但是性能一言難盡怀吻。我再慢慢優(yōu)化：
public void rotate(int[] nums, int k) {
for(int i = 0;i<k;i++){
int last = nums[nums.length-1];
for(int j=nums.length-1;j>0;j--){
nums[j] = nums[j-1];
}
nums[0] = last;
}
}
第二種方法就是數(shù)組倒轉瞬浓。用雙指針的方法將數(shù)組倒轉封裝起來。然后這個
其實很容易理解蓬坡，整個數(shù)組倒轉猿棉。然后在k之前（包括k位）的再到轉，k之后的倒轉屑咳。
單純這么說可能很抽象萨赁，畫個圖就好理解了。
反正情況就是這個情況乔宿，盡量腦補位迂，接下來上代碼：
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
private void reverse(int[] nums, int first, int last) {
while (first < last) {
int temp = nums[first];
nums[first++] = nums[last];
nums[last--] = temp;
}
}
}
然后雖然題目要求三種方式，但是我覺得上種方法性能详瑞，時間已經很優(yōu)了掂林，所以就不再執(zhí)著于方式了，這個題就到這里坝橡。如果感興趣或者必須按照題目做出來的建議去看解析吧泻帮。附上大神提供的完整四種方法的思路。
import java.util.Arrays;
class Solution {
/**
* 雙重循環(huán)
* 時間復雜度：O(kn)
* 空間復雜度：O(1)
*/
public void rotate_1(int[] nums, int k) {
int n = nums.length;
k %= n;
for (int i = 0; i < k; i++) {
int temp = nums[n - 1];
for (int j = n - 1; j > 0; j--) {
nums[j] = nums[j - 1];
}
nums[0] = temp;
}
}
/**
* 翻轉
* 時間復雜度：O(n)
* 空間復雜度：O(1)
*/
public void rotate_2(int[] nums, int k) {
int n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start++] = nums[end];
nums[end--] = temp;
}
}
/**
* 循環(huán)交換
* 時間復雜度：O(n)
* 空間復雜度：O(1)
*/
public void rotate_3(int[] nums, int k) {
int n = nums.length;
k %= n;
// 第一次交換完畢后计寇，前 k 位數(shù)字位置正確锣杂，后 n-k 位數(shù)字中最后 k 位數(shù)字順序錯誤，繼續(xù)交換
for (int start = 0; start < nums.length && k != 0; n -= k, start += k, k %= n) {
for (int i = 0; i < k; i++) {
swap(nums, start + i, nums.length - k + i);
}
}
}
/**
* 遞歸交換
* 時間復雜度：O(n)
* 空間復雜度：O(n/k)
*/
public void rotate(int[] nums, int k) {
// 原理同上
recursiveSwap(nums, k, 0, nums.length);
}
private void recursiveSwap(int[] nums, int k, int start, int length) {
k %= length;
if (k != 0) {
for (int i = 0; i < k; i++) {
swap(nums, start + i, nums.length - k + i);
}
recursiveSwap(nums, k, start + k, length - k);
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
顛倒二進制位
題目：顛倒給定的 32 位無符號整數(shù)的二進制位番宁。
示例 1：
輸入: 00000010100101000001111010011100
輸出: 00111001011110000010100101000000
解釋: 輸入的二進制串 00000010100101000001111010011100 表示無符號整數(shù) 43261596元莫，
因此返回 964176192，其二進制表示形式為 00111001011110000010100101000000蝶押。
示例 2：
輸入：11111111111111111111111111111101
輸出：10111111111111111111111111111111
解釋：輸入的二進制串 11111111111111111111111111111101 表示無符號整數(shù) 4294967293踱蠢，
因此返回 3221225471 其二進制表示形式為 10101111110010110010011101101001。
提示：
請注意棋电，在某些語言（如 Java）中茎截，沒有無符號整數(shù)類型。在這種情況下赶盔，輸入和輸出都將被指定為有符號整數(shù)類型企锌，并且不應影響您的實現(xiàn)，因為無論整數(shù)是有符號的還是無符號的于未，其內部的二進制表示形式都是相同的撕攒。
在 Java 中陡鹃，編譯器使用二進制補碼記法來表示有符號整數(shù)。因此打却，在上面的 示例 2 中杉适，輸入表示有符號整數(shù) -3，輸出表示有符號整數(shù) -1073741825柳击。
進階:
如果多次調用這個函數(shù)猿推，你將如何優(yōu)化你的算法？
思路：這個題捌肴。蹬叭。我不知道是不是我沒太理解，不就是將以此二進制串當做字符串然后完全倒轉么状知？我再仔細審審題然后再來分享思路秽五。
回來了，講一下這道題的幾個坑：1饥悴，說是輸入二進制串坦喘，實際上輸入的是int數(shù)。二西设，有個負數(shù)補碼問題瓣铣。我一開始的思路就卡在負數(shù)這一塊了。
雖然我第一個思路是錯的贷揽，但是這里也貼來上棠笑，知道為什么錯才更好了解為什么對：
public int reverseBits(int n) {
StringBuffer sb = new StringBuffer();
int i = 32;
//因為是n是int,所以肯定是n先等于0，所以只要判斷i就可以了
while(i!=0 && n>=0){
sb.append(n%2);
n = n/2;
i--;
}
return Long.valueOf(sb.toString(),2).intValue();
}
這個就坑在如果是正數(shù)都ok禽绪，但是如果初始數(shù)字是負數(shù)則會報錯蓖救。我是手動判斷二進制位數(shù)的，初始是-1,然后還往sb上追加得出的結果根本不能看做是數(shù)字印屁。所以這種生生拆數(shù)的方式就不行循捺。
還能怎么獲取二進制位數(shù)呢？位移雄人。一種知道但是很少用的技術巨柒。
這里科普幾個知識點：
按位與&。兩個數(shù)字二進制按位對比柠衍，上下皆為1才是1，剩下都是0晶乔。
換言之任何數(shù)n&1.因為1前面位數(shù)都是0珍坊，只有最后一位才是1。所以得出的結果只能是1或者0.結果是1說明n的最后一位是1正罢，得出結果是0說明n的最后一位是0阵漏。
左移<<。這個二進制串往左移動，最高位舍去履怯，最低位補0回还。
右移>>和帶符號右移>>>。普通右移是往右移動叹洲，低位舍去柠硕，高位補0。
而這個帶符號右移是如果之前最高位是1运提，則低位舍去高位補1（保證移之前是負數(shù)移動后還是負數(shù)）如果最高位是0則和普通右移一樣蝗柔。
這道題的解法只需要用到這三種基礎運算。
因為用上文用代碼邏輯來獲取一個數(shù)字的二進制只能保證整數(shù)的正確性民泵，所以這里要用位移來實現(xiàn)癣丧。
大概步驟就是一個一個獲取二進制的位數(shù)，然后直接放到應該放的位置（這個是有個反轉的栈妆，比如獲取的最后一位要放到結果的第一位胁编，獲取的倒數(shù)第二位放到結果的第二位）。
說了這么多直接上代碼：
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
//因為我第一版本用的while,所以不改了鳞尔，這里其實while或者for都可以嬉橙。
int i = 0;
int result = 0;
//一共只有32位數(shù)。從0開始铅檩，所以到31就結束憎夷。
while(i<32){
//獲取二進制串的最后一位是0是1.
int temp = n&1;
//依次放置的是前置位的數(shù)字，因為i最大是31昧旨，所以放置的數(shù)位最后是0位拾给。
result = result+(temp<<(31-i));
//這個n每次右移一位，保證每次獲取的temp是不斷往上的位數(shù)兔沃。
n = n>>1;
i++;
}
return result;
}
}
其實這道題感覺考得就是二進制的基礎運算知識蒋得。我覺得我最大的錯誤就是主觀解題，第一思路就不對（比如看了題目應該直接考慮用二進制解決問題乒疏，我還傻了吧唧的去字符串累加）额衙。
其實位移用的真不多，所以這里下意識反應不對我也原諒自己了怕吴，順便看了評論窍侧，說到了jdk中的二進制反轉，人家的代碼也只能嘆為觀止转绷，因為我死活也沒看懂伟件。看了半天加上找了好多資料议经，還問了人斧账，才勉強理解谴返。。
我隨便上個例子來講：
上圖是我把jdk的方法源碼拆開來一步一步運行的咧织。其實乍一看規(guī)律挺不好找嗓袱。但是只要知道原理就能發(fā)現(xiàn)規(guī)律了。
其實第一步就是一個兩兩交換的步驟习绢。
從最后一位開始渠抹，最后一位和倒數(shù)第二位交換位置。倒數(shù)第三和倒數(shù)第四交換位置毯炮，倒數(shù)第五和倒數(shù)第六交換位置逼肯。。以此類推桃煎。如果到了第一個位數(shù)篮幢，前面沒有可交換的了則補0。圖上就是第一個1为迈，再前面沒數(shù)字了三椿，補了個0，01交換為10.然後結束了葫辐。
第二步是一個兩個一組兩兩交換搜锰。也是從最后兩位開始。倒數(shù)第二和倒數(shù)第一整體和倒數(shù)第四耿战，倒數(shù)第三這個整體交換蛋叼。倒數(shù)第八第七和倒數(shù)第六第五交換。剂陡。一直到首位還是沒有則補0狈涮。圖上因為到了第一二位，前面沒有了鸭栖，所以補了兩個0.也就是00 10兩組交換位置歌馍，變成了10 00。
第三步也是這樣晕鹊，但是變成了四個四個一組兩兩交換松却，沒有前面補0
第四步是以八為單位的交換，其實就是字符串翻轉了（因為二進制中的八位數(shù)是十六進制中的一個數(shù)字）溅话。
至此晓锻，整個翻轉完成。
然後這個題就到這了（做題用半小時飞几，研究jdk源碼半小天兒~~）
但是我還是要說一個問題：那就是性能問題带射。上個題做出來不難，但是對于jdk源碼理解起來很難循狰，而且還費時間窟社。但是最終一樣的代碼我在leetCode上運行了一下，jdk源碼方法和我自己寫的簡單位移計算的方法運行起來執(zhí)行速度相同绪钥，而且消耗也相同灿里？
其實這個就挺有意思了，思路上不是一種方法實現(xiàn)的程腹，但是性能是一樣的匣吊。之前因為看不懂源碼所以覺得應該就是厲害，但是現(xiàn)在有點墜下神壇的感覺寸潦。畢竟運行起來并沒有多優(yōu)秀吧色鸳？好吧，這是一個疑問见转，以后可能隨著知道的越多就能理解了命雀？下一題吧
位1的個數(shù)
編寫一個函數(shù)，輸入是一個無符號整數(shù)斩箫，返回其二進制表達式中數(shù)字位數(shù)為 ‘1’ 的個數(shù)（也被稱為漢明重量）吏砂。
示例 1：
輸入：00000000000000000000000000001011
輸出：3
解釋：輸入的二進制串 00000000000000000000000000001011 中，共有三位為 '1'乘客。
示例 2：
輸入：00000000000000000000000010000000
輸出：1
解釋：輸入的二進制串 00000000000000000000000010000000 中狐血，共有一位為 '1'。
示例 3：
輸入：11111111111111111111111111111101
輸出：31
解釋：輸入的二進制串 11111111111111111111111111111101 中易核，共有 31 位為 '1'匈织。
提示：
請注意，在某些語言（如 Java）中牡直，沒有無符號整數(shù)類型缀匕。在這種情況下，輸入和輸出都將被指定為有符號整數(shù)類型井氢，并且不應影響您的實現(xiàn)弦追，因為無論整數(shù)是有符號的還是無符號的，其內部的二進制表示形式都是相同的花竞。
在 Java 中劲件，編譯器使用二進制補碼記法來表示有符號整數(shù)。因此约急，在上面的 示例 3 中零远，輸入表示有符號整數(shù) -3。
進階:
如果多次調用這個函數(shù)厌蔽，你將如何優(yōu)化你的算法牵辣？
思路：這道題就是上道題的變題，甚至比上題還要簡單奴饮，沒啥可說的了纬向。上題的思路上修改一下就行了择浊。
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int result = 0;
for(int i=0;i<32;i++){
int x = n&1;
if(x==1){
result++;
}
n = n>>1;
}
return result;
}
}
一步步位移獲取每一位上的數(shù)，如果是1則總數(shù)遞加逾条，不是就算了琢岩。簡單明了。這道題過师脂。
上升的溫度
又做到一個sql題担孔，但是因為這個題目讓我學會了一個函數(shù)，所以在這列出來了吃警，
日期的相減：dateDiff（date1,date2）結果是日期1減去日期2 的天數(shù)糕篇；
完整答案：
select w.Id from Weather w,Weather w1
where DateDiff(w.RecordDate,w1.RecordDate)=1
and w.Temperature> w1.Temperature
今天就整理到這里，如果稍微幫到你了記得點個喜歡點個關注喲~每天進步一點點酌心，也祝大家工作順順利利拌消！
