當前位置:網站首頁>Leetcode 算法面試沖刺 實戰 五(數組與循環)(十二)

Leetcode 算法面試沖刺 實戰 五(數組與循環)(十二)

2022-01-28 03:17:11 愛學習的大叔

298 · 尋找素數

輸出n以內所有的素數。
在這裏插入圖片描述
質數又稱素數。一個大於1的自然數,除了1和它自身外,不能被其他自然數整除的數叫做質數;否則稱為合數(規定1既不是質數也不是合數)。

def prime(self, n):
        # write your code here
        if n <= 1: return []
        li = []
        for i in range(2, n + 1):
            for j in range(2, i):
                if i % j == 0:
                    break
            else: li.append(i)
        return li

在這裏插入圖片描述
注意這裏的for break 和 else的用法:
Python 中可以有for break else 用法,錶示若for循環未中途跳出,則進入else內容, 代碼如下:

for i in range(10):
    if i<0:
        break
else:
    print("ok")
#結果會打印ok
for i in range(10):
    if i>5:
        print("break")
        break
else:
    print("ok")
 
#打印break,不打印ok

下面關於break和continue的知識點:

Python 循環語句(break和continue)

while 語句時還有另外兩個重要的命令 continue,break 來跳過循環,continue 用於跳過該次循環,break 則是用於退出循環,此外"判斷條件"還可以是個常值,錶示循環必定成立。本篇主要對比continue和break的區別。

一、Python break語句

Python break語句,就像在C語言中,打破了最小封閉for或while循環。

break語句用來終止循環語句,即循環條件沒有False條件或者序列還沒被完全遞歸完,也會停止執行循環語句。

break語句用在while和for循環中。

如果您使用嵌套循環,break語句將停止執行最深層的循環,並開始執行下一行代碼。

二、Python continue語句

Python continue 語句跳出本次循環,而break跳出整個循環。

continue 語句用來告訴Python跳過當前循環的剩餘語句,然後繼續進行下一輪循環。

continue語句用在while和for循環中。

看了其他答案,都沒有我寫的簡單,他們的條件設置的也很複雜,明白了一句話,就是代碼越簡單,你想的就越多。不要用戰術的勤奮敷衍戰略上的懶惰!

想想,為什麼雷軍說他的代碼很優雅,因為他寫了太多的代碼。我還是要多看書,多看資料。這都是熟能生巧的過程,大家都是慢慢一點點變强的。

297 · 尋找最大值

尋找 n 個數中的最大值。

在這裏插入圖片描述
我的代碼:

def maxNum(self, nums: List[int]) -> int:
        # write your code here
        temp = float('-inf')
        for num in nums:
            if temp < num:
                temp, num = num, temp
        return temp

這裏用了昨天學的最小值float("-inf")。或者這裏也可以賦值為nums[0]。
在這裏插入圖片描述
答案用了一個叫做尾遞歸的:

class Solution:
    """ @param nums: the list of numbers @return: return the maximum number. """
    def maxNum(self, nums):
        return self.max_num(nums, 0, len(nums) - 1, float('-inf'))

    def max_num(self, nums, start, end, result):
        if start > end:
            return result

        result = max(result, nums[start])
        return self.max_num(nums, start + 1, end, result)

尾遞歸定義:
如果一個函數中所有遞歸形式的調用都出現在函數的末尾,我們稱這個遞歸函數是尾遞歸的。當遞歸調用是整個函數體中最後執行的語句且它的返回值不屬於錶達式的一部分時,這個遞歸調用就是尾遞歸。尾遞歸函數的特點是在回歸過程中不用做任何操作,這個特性很重要,因為大多數現代的編譯器會利用這種特點自動生成優化的代碼。

1334 · 旋轉數組

給定一個數組,將數組向右移動k步,其中k為非負數。

在這裏插入圖片描述

def rotate(self, nums, k):
        # Write your code here
        k %= len(nums)
        return nums[-k:] + nums[:-k]

在這裏插入圖片描述
我個人感覺切片的速度應該算是快的了,但是我不確定是不是O(1)的複雜度,我查了下資料,說切片是O(k)的複雜度。

list常規操作的複雜度如下:
在這裏插入圖片描述
然後找到了雙端隊列,我可以嘗試用下雙端隊列
在這裏插入圖片描述
但是報錯了。
我寫的代碼如下:

def rotate(self, nums, k):
        # Write your code here
        deq = deque(nums)
        for _ in range(k):
            deq.appendleft(deq.pop())
        return deq

在這裏插入圖片描述
不知道怎麼錯了。
下面是官方答案:
Example:nums = [1,2,3,4,5,6,7] k = 3
Step1:劃分成[1,2,3,4], [5,6,7]
Step2:分別reverse,[4,3,2,1], [7,6,5]
Step3:合並reverse,[5,6,7,1,2,3,4]

public class Solution {
    
    /** * @param nums: an array * @param k: an integer * @return: rotate the array to the right by k steps */
    public int[] rotate(int[] nums, int k) {
    
        // Write your code here
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - k - 1);
        reverse(nums, n - k, nums.length - 1);
        reverse(nums, 0, nums.length - 1);
        return nums;
    }
    
    public void reverse(int[] n, int i, int j) {
    
        for (int p = i, q = j; p < q; p++, q--) {
    
            int temp = n[p];
            n[p] = n[q];
            n[q] = temp;
        }
    }
}

看懂了。。。這個真不好想。想把數組按照k分成2組,分別reverse,然後再整體reverse。
根據答案自己寫的代碼。但這應該也不是O(1)。

 def rotate(self, nums, k):
        # Write your code here
        n = len(nums)
        k %= n
        self.reverse(0, n - 1 - k, nums)
        self.reverse(n - k, n - 1, nums)
        self.reverse(0, n - 1, nums)
        return nums
        

    def reverse(self, left, right, nums):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

在這裏插入圖片描述

807 · 回文數 II

判斷一個非負整數 n 的二進制錶示是否為回文數
在這裏插入圖片描述
回文數定義:
“回文”是指正讀反讀都能讀通的句子,它是古今中外都有的一種修辭方式和文字遊戲,如“我為人人,人人為我”等。在數學中也有這樣一類數字有這樣的特征,成為回文數(palindrome number)。 [1]
設n是一任意自然數。若將n的各比特數字反向排列所得自然數n1與n相等,則稱n為一回文數。例如,若n=1234321,則稱n為一回文數;但若n=1234567,則n不是回文數。 [1]
注意:
1.偶數個的數字也有回文數124421
2.小數沒有回文數

將一個整數轉化為二進制數:
print(bin(1)) # 0b1
print(bin(-10)) # -0b1010
print("{0:b}".format(10)) # 1010

我的代碼:

def isPalindrome(self, n):
        # Write your code here
        ss =  "{0:b}".format(n)
        start, end = 0, len(ss) - 1
        while start < end:
            if ss[start] != ss[end]: return False
            start += 1
            end -= 1
        return True

總結:轉化二進制和回文數,我都不是很熟悉。
在這裏插入圖片描述
看到了一個nb的答案:

def isPalindrome(self, n):
        # Write your code here
        digits = []
        while n: 
          digits.append(n % 2)
          n = n // 2
        
        return digits == digits[::-1]

這裏讓我知道了,while 0是不執行的,這我之前不知道。另外我還知道了比較回文,可以讓數組反轉,反轉通過li[::-1]。太秀了。

def isPalindrome(self, n):
        # Write your code here
        ss =  "{0:b}".format(n)
        return ss == ss[::-1]

這是我修改後的代碼,牛逼了麼。

版權聲明
本文為[愛學習的大叔]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201280317105223.html

隨機推薦